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) ?

推荐答案

如果有人阅读 规范，有一个算法描述它:

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) 为 true，则返回 true.

  显然，基于该算法和 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 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屋！