如何快速检查一个数字是否在一个集合中？

Question

什么是在Javascript中检查数字是否在列表中的最快方法？

我知道indexOf >=，但这对我来说似乎相当慢。

我每秒必须执行数百万次检查，列表相当短（最大〜10个条目）

- pixartist

---

在基准开销不同的情况下，通过10个项目进行O(n)搜索实际上可能比常数时间查找更快。 - Matt Ball

每秒数百万次的检查？真的吗？ - Lee Taylor

所有的检查都针对同一个列表吗？ - georg

值的范围有多大？ - Pointy

如果数据不经常更改，您可以对其进行排序，然后使用二分搜索。这适用于实际上有数百万条记录的情况，因为@MattBall的原因。否则，请改用对象（在其他语言中是字典或哈希表）。 - Yaw Boakye

在2021年，应该使用new Set([ 2, 3, 5, 7, 11 ]).has(7)。 - Sebastian Simon

Answer 1

可以在jsperf上尝试一下，但我怀疑使用对象并将数字设置为属性会比数组搜索更快。

var theList = { 1: true, 2000: true, 253: true, -12077: true, ... };

if (theList[ someNumber ]) { // see if some number is in the list

话虽如此，在 Web 浏览器中，除非是在极高端的机器上且没有做其他事情，否则你不可能以每秒数百万次的速度执行任何有用的 JavaScript 操作。

- Pointy

Answer 2

最好使用indexof()

作为一种替代方法，你也可以使用Enumerable#include，但在你的情况下并不被推荐。

你可以使用Enumerable#include，但我怀疑它是否比indexof()更快。例如：

[1, 2, '3', '4', '5'].include(3);

- Rahul Tripathi

---

你建议他为此加载prototypejs库吗？并且这将是最快的解决方案？ - user2437417

@RahulTripathi 不，但是将数组中的短列表（记住，不超过十个项）转换为对象中的列表非常简单。 - Pointy

@CrazyTrain：完全同意。但我仍然认为使用IndexOf()会是一个更好的主意。如果我错了，请纠正我。附言：我的答案也更新了！！！ :) - Rahul Tripathi

如果 OP 真的需要每秒查找数百万次（在我看来有点可疑），那么他需要尽可能地优化。在这种情况下，人们经常需要用优化后的代码来换取短代码。我认为我们中没有人真正了解实际情况，无法提供最佳解决方案。 - user2437417

是的，您没有提供一个合理的解决方案，可以比.indexOf()方法提高性能。 - user2437417

Answer 3

如果你想要更快的理解速度，请使用array.includes：

[-1, 1, 2].includes(0)  // false
[-1, 1, 2].includes(-1) // true
[-1, 1, 2].includes(-2) // false
[-1, 1, 2].includes(2)  // true
[-1, 1, 2].includes(3)  // false

- vhs