JavaScript 作为数组和字典的对象的排序运行时

Question

编辑：看起来我在下面写的是 Pigeonhole Sort.

的一种形式

我一直在研究 JavaScript 数组是如何成为真正特殊的对象并且还具有有序迭代器（因为它们是集合）。

因此，此代码是可能的：

let inputArray = []; // inputArray.length === n
// non-duplicate entries for the sake of this question (easy to alter)
let sparse = new Array(); // Sets up as dictionary

// O(n)
inputArray.forEach(function(entry) { // Uses Dictionary mode
    sparse[entry] = entry; // O(1) 
});

// O(n) (actual is n log n)
let sortedArray = [];
for (let entry of sparse) { // Uses Array mode
    sortedArray.push(entry); // O(1)
}

但是由于排序算法的最快运行时间为O(n log(n))，JavaScript的对象字典模式和数组模式之间的转换肯定会减慢它的速度。我测试了它，它确实像预期的那样变慢了（尽管它比本机 .sort() 快），但它只涵盖按 toString() 排序，所以显然我会选择本机版本。

所以我有以下问题：

上面代码具体在什么地方演变成O(n log(n))算法？
你能link给我这个的源代码吗？例如在 V8 中。

我假设它是在 for...of 阶段创建或访问的惰性迭代器，但我很想看看代码及其原因。

Answer 1

看起来 for...of 在遍历可枚举属性时必须检查每个连续的数字（键），直到它命中 length 个元素。如果这是排序的（并且在数组模式下），那么迭代器很容易有下一个元素，但由于它没有排序（因为它是在映射模式下创建的），它必须检查每个潜在的数字order (0,1,...[最后定义的元素])。我没有去检查源代码，但是从更多的时间测试和打印语句来看，这似乎是答案。

Answer 2

只有 comparison-based 排序永远不会比 O(n log n) 快。在您的代码中，排序发生在 sparse[entry] = entry 行，您在其中进行 index-based 排序。这在 O(n) 时间内有效，但有局限性：主要是，它仅在您提前知道值的范围时才有效。在这种情况下，隐式定义的有效值范围是有效数组索引集，即从 0 到 2^32 - 1 的整数。（尝试添加负数，或 (non-integer) 双精度数，或一个字符串，到您的输入数组。）

更多说明：

new Array() 在字典模式下不设置任何内容。您可以使用 var sparse = []; 并且您的代码将完全相同。根据引擎启发式算法，后续使用模式可能会或可能不会将数组转换为引擎盖下的字典模式，但您不会看到两者之间的行为差异。
for..of 和 for..in 具有相同的迭代顺序（默认情况下）。它们最大的区别之一是 for..in 遍历 keys（指定为字符串类型），而 for..of 遍历 values （无论你输入什么类型）。（用 [3, 4, "5"] 试试：for..in 会 return "0", "1", "2"，for..of 会 return 3, 4, "5"。）
for..in 循环的最大问题是它们包含来自原型链的内容。如果您包含的任何库 Array.prototype.myFancyFunction = ...，那么您对数组的所有 for..in 循环将比您预期的多 return 一个元素 ;-)

JavaScript 作为数组和字典的对象的排序运行时

JavaScript Sorting Runtime of Object acting as Array and Dictionary

javascript

sorting

algorithm

v8