作为数组和字典的对象的 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() 的排序，所以很明显我会选择原生版本。

所以我有以下问题:

1. 在上面的代码中，它具体在哪里转化为 O(n log(n)) 算法？
2. 你能给我链接这个的源代码吗？例如在 V8 中。

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

Answer 1

只有基于比较 的排序绝不会比 O(n log n) 快。在您的代码中，排序发生在 sparse[entry] = entry 行中，您在其中进行基于索引的排序。这在 O(n) 时间内有效，但有局限性:主要是，它仅在您提前知道值的范围时才有效。在这种情况下，隐式定义的有效值范围是有效数组索引的集合，即从 0 到 2^32 - 1 的整数。(尝试添加一个负数，或一个(非整数) double ，或一个字符串, 到你的输入数组。)

更多说明:

• new Array() 不在字典模式下设置任何内容。您可以使用 var sparse = []; 并且您的代码将完全相同。根据引擎启发式算法，后续使用模式可能会或可能不会在后台将数组转换为字典模式，但您不会看到两者之间的行为差​​异。

• for..of 和 for..in 具有相同的迭代顺序(默认情况下)。它们最大的区别之一是 for..in 遍历 keys(指定为字符串类型)，而 for..of 遍历 values(无论你输入什么类型)。 (尝试使用 [3, 4, "5"]:for..in 将返回 "0", "1", "2", for..of 将返回 3, 4, "5"。)

• for..in 循环的最大问题是它们包含来自原型(prototype)链的内容。如果您包含的任何库执行 Array.prototype.myFancyFunction = ...，那么您对数组的所有 for..in 循环将返回比您多返回一个元素的元素d 期待 ;-)