代码之家 › 专栏 › 技术社区 › Charlie

一切就绪。has()方法O(1)和数组。O(n)的索引?

lookup big-o set arrays javascript

Charlie · 技术社区 · 7 年前

Set.has() 方法是O(1)和 Array.indexOf() 是O(n)。

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


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

是真的是O(1)?

1 回复 | 直到 7 年前

zmag 7 年前

我不认为有5个元素的数组是检查时间复杂度的好例子。

多个元素,一次调用

一切就绪。真的有O(1)吗?

对 . 集合的时间复杂度。根据下面的测试结果,has()是O(1)。

const MAX = 10000000
let a = []
a.length = MAX

for (let i = 0; i < MAX; i++) {
  a[i] = i
}

let s = new Set(a)

let o = a.reduce((acc, e) => {
  acc[e] = e
  return acc
}, {})

console.time("Test_Array.IndexOf(0)\t")
a.indexOf(0);
console.timeEnd("Test_Array.IndexOf(0)\t")
console.time("Test_Array.IndexOf(n/2)\t")
a.indexOf(MAX / 2);
console.timeEnd("Test_Array.IndexOf(n/2)\t")
console.time("Test_Array.IndexOf(n)\t")
a.indexOf(MAX);
console.timeEnd("Test_Array.IndexOf(n)\t")

console.time("Test_Set.Has(0)\t\t")
s.has(0)
console.timeEnd("Test_Set.Has(0)\t\t")
console.time("Test_Set.Has(n/2)\t")
s.has(MAX / 2)
console.timeEnd("Test_Set.Has(n/2)\t")
console.time("Test_Set.Has(n)\t\t")
s.has(MAX)
console.timeEnd("Test_Set.Has(n)\t\t")

console.time("Test_Object[0]\t\t")
o[0]
console.timeEnd("Test_Object[0]\t\t")
console.time("Test_Object[n/2]\t")
o[MAX / 2]
console.timeEnd("Test_Object[n/2]\t")
console.time("Test_Object[n]\t\t")
o[MAX]
console.timeEnd("Test_Object[n]\t\t")

.as-console {
  background-color: black !important;
  color: lime;
}

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

Shidersz 7 年前

如果有人读了 specification 属于 has() ,有一个算法描述它:

Set.prototype.has(value) :

如果类型不是对象,则引发TypeError异常。

如果S没有[[SetData]]内部插槽,则引发TypeError异常。

让条目成为Ss[[SetData]]内部插槽值的列表。

对作为条目元素的每个e重复上述步骤,

返回false。

显然,基于这个算法和这个词的存在 REPEAT 人们可能会对此感到困惑 O(1) (我们可以认为这是可能的 O(n) ).然而 specification 我们可以看到:

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

幸亏谢谢你指出这一点。

因此,我们可以创建一个测试来进行比较 Array.indexOf() Set.has() 在最坏的情况下,即查找一个根本不在数组中的项(由于 @阿奎那 用于指示此测试):

// 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;}

现在我们可以看到 设置has() 性能优于 大堆indexOf() . 还有一个额外的比较 Object.hasOwnProperty() 作为参考。

结论:

虽然 O(1) 次线性时间 设置has() ,一般来说,会比 大堆indexOf()

另一项测试:

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

// 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()");

.作为控制台{背景色:黑色!重要;颜色:石灰;}
.作为控制台包装{最大高度:100%!重要;顶部:0;}

道歉对于我的答案的第一个版本可能造成的混乱。感谢大家让我更好地理解我的错误。