如何获取稀疏数组中的下一个元素

Question

我知道JavaScript中的数组与传统数组不同，因为它们在内部只是对象。因此，当涉及到内存管理时，JavaScript允许稀疏数组以类似于密集数组的方式进行操作。在使用稀疏数组时，有没有一种有效的方法来快速访问该数组中的下一个元素？

例如，给定以下数组：

var foo = [];
foo[0] = '0';
foo[1] = '1';
foo[2] = '2';
foo[100] = '100';

console.log(foo.length); // => 101

我知道可以使用for ... in的方法获取所有元素，如下：

for (var n in foo){
    console.log(n);
}
// Output: 
// 0
// 1
// 2
// 100

然而，是否有明确的方法可以简单地从其中一个元素转到下一个元素呢？

例如，是否存在一种实现类似于此行为的方法？

var curElement = foo[2]; // => 2 (the contents of foo[2])
var nextElement = curElement.next(); // => 100 (the contents of foo[100])
//                           ^^^^^^
// Not an actual function, but does there exist some way to potentially
// mimic this type of behavior efficiently?

- Nick Zuber

---

链表和双向链表。 - LJᛃ

我在考虑使用双向链表来追踪数组的键，这样当在一个元素上调用next方法时，它将查找列表中的下一个键，并返回具有该键的元素。然而这将增加空间复杂度O(n)，所以我想知道是否有一些本地方式来实现这种行为，避免额外的空间复杂度。 - Nick Zuber

@LJᛃ 大O符号既可以指时间复杂度，也可以指空间复杂度。 - Nick Zuber

好的，我明白了。但我的观点仍然成立，使用链表而不是数组可能是最干净和最快的解决方案。 - LJᛃ

@LJᛃ：你应该发布一个答案。我同意单链表可能更合理，除非有其他需要在代码中将数据作为实际数组共享的情况。如果不是这种情况，那我会推荐你的回答成为被采纳的答案。 - user1106925

Answer 1

你可以创建自己的 SparseArray 类型，该类型具有所有数组方法，但维护一个单独的索引列表以进行迭代，以便您可以高效地跳过空洞。

以下是这种类型的开头。它允许您迭代、推送、在特定索引处添加、获取/检查特定索引。

还有一个我添加用于显示的 .toString()。

尚未完全测试，可能存在错误。您需要根据需要添加功能。

function SparseArray(arr) {
  this.data = arr || [];
  this.indices = [];

  for (var i = 0; i < this.data.length; i++) {
    if (this.data.hasOwnProperty(i)) {
      this.indices.push(i);        
    }
  }
}

SparseArray.prototype.forEach = function(cb, thisArg) {
  for (var i = 0; i < this.indices.length; i++) {
    cb.call(thisArg, this.data[this.indices[i]], i, this);
  }
};

SparseArray.prototype.push = function(item) {
  this.indices.push(this.data.push(item) - 1);
};

SparseArray.prototype.addAt = function(idx, item) {
  if (idx >= this.data.length) {
    this.indices.push(idx);
    
  } else if (!(idx in this.data)) {
    for (var i = 0; i < this.indices.length; i++) {
      if (this.indices[i] >= idx) {
        this.indices.splice(i, 0, idx);
        break;
      }
    }
  }
  this.data[idx] = item;
};

SparseArray.prototype.hasIndex = function(idx) {
  return idx in this.data;
};

SparseArray.prototype.getIndex = function(idx) {
  return this.data[idx];
};

SparseArray.prototype.nextFrom = function(idx) {
  for (var i = 0; i < this.indices.length; i++) {
    if (this.indices[i] >= idx) {
      return this.data[this.indices[i]];
    }
  }
};

SparseArray.prototype.toString = function() {
  var res = [];
  this.forEach(function(item) {
    res.push(item);
  });
  return res.join(", ");
};

var foo = [];
foo[0] = '0';
foo[1] = '1';
foo[2] = '2';
foo[100] = '100';

var pre = document.querySelector("pre");

var sa = new SparseArray(foo);

pre.textContent += "Start\n" + sa + "\n\n";

sa.addAt(1000, "1000");

pre.textContent += "Adding 1000\n" + sa + "\n\n";

sa.push("1001");

pre.textContent += "Pushing 1001\n" + sa + "\n\n";

pre.textContent += "Next from 300 is: " + sa.nextFrom(300) + "\n\n";

<pre></pre>

- user1106925

Answer 2

如上方评论中squint提到的，我会用另一个数组来实现。你可以跟踪那些对你有意义的索引，这样你就可以直接跳转到这些索引。然而，我还有另一个想法。

如果你想消除大量的开销，你可以保留一个你关心的值的数组和一个它们对应的索引数组。（请注意，这更像是Java中的Map数据结构）。这样，你就可以遍历你需要的数字，并在另一个数组中获取你想要的索引。

Array 1: 1, 3, 6, 8
Array 2: 234, 298, 400, 500

因此，值1在数据的索引234处出现，值3在298处出现...

我认为这将大大提高大型数据集和小型数据集的性能。但是，我不完全确定javascript中的查找如何工作。

- patrickhuie19

Answer 3

尝试使用.slice()，.filter()

// slice index of `curElement` + 1 through `foo` `.length`
var curr = foo.slice(foo.indexOf(curElement) + 1, foo.length);
// if `val` defined , return `val`
// alternatively , `return val !== undefined || val !== null`
var next = curr.filter(function(val) { return val })[0];

var foo = [];
foo[0] = '0';
foo[1] = '1';
foo[2] = '2';
foo[100] = '100';
var curElement = foo[2]; // => 2 (the contents of foo[2])
var curr = foo.slice(foo.indexOf(curElement) + 1, foo.length);
var next = curr.filter(function(val) { return val})[0];
console.log(next)

---

另外，也可以使用 while 循环

var foo = [];
foo[0] = '0';
foo[1] = '1';
foo[2] = '2';
foo[100] = '100';
var n = 2, next;
var curElement = foo[n]; // => 2 (the contents of foo[2])
while (n < foo.length) {
  if (foo[++n] !== undefined) {next = foo[n]; break;}
}
console.log(next)

- guest271314

---

由于OP似乎关注性能，这不是一个好主意。 - LJᛃ

slice 构造一个新的数组并重新索引源数组，使用 filter 比手动迭代值要慢得多，并且也会构造一个新的数组。除此之外，建议的解决方案还将跳过值为 0 的元素... - LJᛃ

@NickZuber 最简单的方法是使用 while 循环。不确定问题要求是否排除了使用 .slice() 或 .filter()？请参见问题中的 _“但是，是否有一种明确的方法可以从其中一个元素转到下一个元素？”_？那么要求是什么呢？ - guest271314

我给你点了踩，因为我在评论中已经阐述了原因。请见谅。 - LJᛃ

更正：slice 不会重新索引源数组。尽管其他观点仍然有效。 - LJᛃ