如何解决 javascript 引擎数组实现的大型稀疏数组的低效率问题？

Question

这是对我先前问题的跟进

我刚刚发现我拥有的所有 javascript 引擎（Chromium、Node.js、Firefox）在处理稀疏数组时效率极低！示例：

[,1,2,3,,,,,9,,,].find((x,i,a) => console.log(x,i))

原来所有的坑也被这个搜索打中了。但在大型稀疏数组的现实世界用例中，这是非常低效的！

有人可能会争辩说，正式地应该要求 find 对缺失值 return undefined 而不是跳过它们，因此永远无法 return 它们。但这似乎是这些迭代函数中很少有用的属性，规范应该说要跳过稀疏数组中的空洞。

这似乎归结为 in 与 of 运算符的迭代。

那么是否有一种方法可以重新定义或修改这些迭代函数的迭代，使其仅基于实际存在的索引？特别想找到数组中的第一个索引和最后一个索引，以及给定索引的下一个索引（可能是也可能不是洞的索引）。

Answer 1

数组的长度属性取最后一个元素的索引并加一。因此，如果您的数组在索引 0 到 100 之间有空洞，并且在索引 101 处有一个元素，则长度将为 return 101，因为它是最后一个索引 + 1.

无论数组中有多少元素，上述情况都会发生。

这是一个记录在案的功能。如果您想忽略空格，只需检查任何索引处的项目是否为假，然后不要执行逻辑。非常欢迎您修改原型来执行此操作，当然后果自负。

Answer 2

答案是：是，find、findIndex、findLast、findLastIndex在大型稀疏数组上确实效率不高，但不是，并非所有迭代数组函数都是如此。

事实上，forEach、filter、map、reduce，甚至some和every，都没有在稀疏数组的空洞上调用回调函数，我在Chromium、Firefox和Node.JS中测试过.因此，如果使用 findLastIndex 的目的是取代不可靠的数组长度属性的天真使用（因此通常无用，如果在忽略许多稀疏数组场景时经常实际有用）则可以完成以下操作：

(function(arr) {
  try {
    return arr.reduceRight(
      function(r,x,i,a) {
         console.log(r,x,i,a);
         throw i;
      }, -1);
  } catch(r) {
    if(typeof r == 'number')
      return r;
    else
      throw r;
  }
})([,,,3,,,6,,,9,,,])

我不知道除了抛出结果值之外是否有更温和的方法来打破这样的迭代器函数循环，但它有效并且它缩短了在找到结果后继续进行的事情.

如果 find(Index) 从头开始（而不是结束），稀疏数组甚至在找到第一个元素之前也可能导致数百万次迭代，同样可以用 forEach 实现：

let testArray = [];
testArray[20000000] = "first";
testArray[40000000] = "last";
(function(arr) {
  try {
    arr.forEach(
      function(x,i,a) {
         console.log(x,i,a);
         throw i;
      });
    return -1;
  } catch(r) {
    if(typeof r == "number")
      return r;
    else
      throw r;
  }
})(testArray)

当您运行使用不同的索引值（创建不同大小的初始稀疏性）时，您会注意到（再次在所有三个，Chromium、Firefox 和 Node.JS 上）实现效率低下，因为它似乎在内部迭代而不是维护指向第一个实际索引、最后一个实际索引的直接指针，甚至可能 next-pointers 跳过大洞。但这没关系，这些是可以添加的优化，至少规范不要求 call-back 在稀疏数组的空洞上调用，因为它似乎是 find 的情况（我认为这是个坏主意）。

以下内容从现在开始进入我自己的通用工具箱：

Array.prototype.findActualLastIndex = function(f) {
    try {
    return this.reduceRight(
        function(r, x, i, a) {
        if(f(x, i, a))
            throw i;
        else
            return r;
        }, -1);
    } catch(r) {
    if(typeof r == 'number')
        return r;
    else
        throw r;
    }
}

Array.prototype.findActualIndex = function(f) {
    try {
    return this.reduce(
        function(r, x, i, a) {
        if(f(x, i, a))
            throw i;
        else
            return r;
        }, -1);
    } catch(r) {
    if(typeof r == 'number')
        return r;
    else
        throw r;
    }
}

希望这可以帮助到其他人。它不是运行在末端有大量备用区域的最佳选择，但这是我们可以从当前版本的 javascript 引擎中得到的最好结果。

如何解决 javascript 引擎数组实现的大型稀疏数组的低效率问题？

How to work around inefficiencies for large sparse arrays of javascript engines' Array implementations?

javascript

arrays

sparse-matrix