Set.has() 方法是 O(1) 还是 Array.indexOf O(n)? [英] Is the Set.has() method O(1) and Array.indexOf O(n)?

问题描述

我在一个答案中看到 Set.has() 方法是 O(1) 而 Array.indexOf() 是 O(n).

I have seen in an answer that the Set.has() method is O(1) and Array.indexOf() is O(n).

var a = [1, 2, 3, 4, 5];
a.indexOf(5);          


s = new Set(a);
s.has(5);              //Is this O(1)?

Set.has() 真的是 O(1) 吗?

Is Set.has() really O(1) ?

推荐答案

如果阅读 规范的has()，有一个算法描述它:

If one read the specification of has(), there is an algorithm describing it:

Set.prototype.has(value) 的算法:

Algorithm for Set.prototype.has(value):

采取以下步骤:

• 设 S 为 this 值.
• 如果 Type(S) 不是 Object，则抛出 TypeError 异常.
• 如果 S 没有 [[SetData]] 内部槽，则抛出 TypeError 异常.
• 让条目成为 S 的 [[SetData]] 内部槽的值的列表.
• 对作为条目元素的每个 e 重复，
  • 如果 e 不为空且 SameValueZero(e, value) 为真，则返回真.

  显然，基于该算法和单词 REPEAT 的存在，人们可能会混淆它是 O(1)(我们可以认为它可以为 O(n)).但是，在规范上，我们可以阅读:

  And apparently, based on that algorithm and the presence of the word REPEAT one can have some confusion about it to be O(1) (we could think it could be O(n)). However, on the specification we can read that:

  Set 对象必须使用哈希表或其他机制来实现，这些机制平均提供与集合中元素数量次线性的访问时间.

  Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.

  感谢 @CertainPerformance 指出这一点.

  所以，我们可以创建一个测试来比较 Array.indexOf() 和 Set.has() 在最坏的情况下，即寻找一个项目不是't 在数组中(感谢 @aquinas 指出这个测试):

  So, we can create a test to compare Array.indexOf() and Set.has() in the worst case, i.e. look for an item that isn't in the array at all (thanks to @aquinas for pointing this test):

  // Initialize array.
  let a = [];
  
  for (let i = 1; i < 500; i++)
  {
      a.push(i);
  }
  
  // Initialize set.
  let s = new Set(a);
  
  // Initialize object.
  let o = {};
  a.forEach(x => o[x] = true);
  
  // Test Array.indexOf().
  console.time("Test_Array.indexOf()");
  for (let i = 0; i <= 10000000; i++)
  {
      a.indexOf(1000);
  }
  console.timeEnd("Test_Array.indexOf()");
  
  // Test Set.has().
  console.time("Test_Set.has()");
  for (let i = 0; i <= 10000000; i++)
  {
      s.has(1000);
  }
  console.timeEnd("Test_Set.has()");
  
  // Test Object.hasOwnProperty().
  console.time("Test_Object.hasOwnProperty()");
  for (let i = 0; i <= 10000000; i++)
  {
      o.hasOwnProperty(1000);
  }
  console.timeEnd("Test_Object.hasOwnProperty()");

  .as-console {background-color:black !important; color:lime;}
  .as-console-wrapper {max-height:100% !important; top:0;}

  现在我们可以看到 Set.has() 比 Array.indexOf() 表现得更好.还有一个与 Object.hasOwnProperty() 的额外比较以作为参考.

  And now we can see that Set.has() performs better than Array.indexOf(). There is also an extra comparison to Object.hasOwnProperty() to take as reference.

  虽然不能保证 O(1) 的复杂性，但规范要求方法在 次线性时间 内运行.而Set.has()，通常会比Array.indexOf()表现更好.

  While O(1) complexity isn't guaranteed, the specification requires the method to run in sublinear time. And Set.has(), generally, will perform better than Array.indexOf().

  在下一个示例中，我们将生成一组随机样本数据，并在稍后使用它来比较不同的方法.

  On next example, we going to generate a random set of sample data and use it later to compare the differents methods.

  // Generate a sample array of random items.
  
  const getRandom = (min, max) =>
  {
      return Math.floor(Math.random() * (max - min) + min);
  }
  
  let sample = Array.from({length: 10000000}, () => getRandom(0, 1000));
  
  // Initialize array, set and object.
  
  let a = [];
  
  for (let i = 1; i <= 500; i++)
  {
      a.push(i);
  }
  
  let s = new Set(a);
  let o = {};
  a.forEach(x => o[x] = true);
  
  // Test Array.indexOf().
  
  console.time("Test_Array.indexOf()");
  for (let i = 0; i < sample.length; i++)
  {
      a.indexOf(sample[i]);
  }
  console.timeEnd("Test_Array.indexOf()");
  
  // Test Set.has().
  console.time("Test_Set.has()");
  for (let i = 0; i < sample.length; i++)
  {
      s.has(sample[i]);
  }
  console.timeEnd("Test_Set.has()");
  
  // Test Object.hasOwnProperty().
  console.time("Test_Object.hasOwnProperty()");
  for (let i = 0; i < sample.length; i++)
  {
      o.hasOwnProperty(sample[i]);
  }
  console.timeEnd("Test_Object.hasOwnProperty()");

  .as-console {background-color:black !important; color:lime;}
  .as-console-wrapper {max-height:100% !important; top:0;}

  最后，我要道歉，因为我的答案的第一个版本可能引起的混乱.感谢所有人让我更好地了解自己的错误.

  Finally I want to apologize for the confusion the first version of my answer could cause. Thanks to all for giving me a better understanding of my mistakes.

  这篇关于Set.has() 方法是 O(1) 还是 Array.indexOf O(n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！