快速查找字符串是否在数组中的方法

Question

在Ruby中,查明字符串是否在数组(.include? x)中是非常慢的.如果将该数组更改为集合,则BAM可以快速查找.

在JavaScript中,没有集合,数组lookups(.indexOf(x) >= 0)也很慢,但我需要在脚本中执行10,000次这些查找.

我的Ruby版本(有套装)在0.125几秒钟内运行,我的JavaScript版本(在NodeJS中)需要29!

是否有任何设置库或更好的方法来执行可以在Ruby附近获得Javascript速度的数组查找？

编辑:将"对象"更改为"字符串"以清除任何混淆

Answer 1

首先,这里有一些基本的混淆,即JavaScript中可用的数据结构.

JavaScript没有数组

从根本上说,JavaScript只有哈希表.标准Array函数构造散列表(我将调用这些整数散列表或int-hash-tables),其中除了字符串键之外,键是整数.这些执行与数组类似,但它们在某些方面有所不同.有缺点和优点.例如,从int-hash-table中删除元素是O(1)操作,而从数组中删除元素是O(n)操作(因为您需要将其余元素复制到新数组中).这就是为什么Array.prototype.spliceJavaScript中的函数非常快.缺点是实施的复杂性.

所以,当你Array在JavaScript上下文中说它被理解为int-hash-table,以及与之相关的所有渐近复杂性.这意味着如果你想在int-hash-table中找到一个字符串值,那么它将是一个O(n)操作.这样做有一个标准功能:Array.prototype.indexOf.但是,如果您想查找密钥,则有两个功能:in和Object.prototype.hasOwnProperty.

有点违反直觉:

[1, 2, 3].hasOwnProperty(0); // true
0 in [1, 2, 3]; // true

两者之间的差异需要进一步解释.它与JavaScript中的所有东西都是对象这一事实有关,因此它们具有一些对象特征.其中一个特征是prototype对象与其原型之间的联系.它是散列表的分层结构,每个散列表都包含对象的属性.

• in 查找对象的直接哈希表,然后递归搜索此对象原型的哈希表.

• 而Object.prototype.hasOwnProperty只关注直接哈希表.你可能认为它应该更快,但等待跳到结论.

由于JavaScript的动态特性,所有函数调用都是动态的,并且环境必须非常小心以确保故障安全代码执行.这意味着在JavaScript中函数调用非常昂贵.因此,经历Object.prototype.hasOwnProperty可能比通过更昂贵in,即使理论上它应该是相反的.但是,给定足够高的继承树和足够的继承属性,最终Object.prototype.hasOwnProperty将接管.

一些例子来获得更好的直觉:

>>> var array = [1, 2, 3];
undefined
>>> 3 in array;
false
>>> array.hasOwnProperty(3);
false
>>> 3 in array;
false
>>> array.__proto__ = [1, 2, 3, 4];
[1, 2, 3, 4]
>>> 3 in array;
true
>>> array.hasOwnProperty(3);
false

TL; DR

• 如果您希望对使用短原型继承链的对象进行最快的键查找in.

• 如果你想要相同,但对于具有广泛继承链的对象,请使用 Object.prototype.hasOwnProperty

• 如果你想最快值查找,使用Array.prototype.indexOf了Array.

• 在散列表中没有用于值查找的内置函数.当然,您可以自己动手,但有许多库已经提供了一个.例如,Underscore提供一个(它称之为indexOf).

Answer 2

来自@nnnnnn的评论:

将数组转换为对象,如下所示:

object = {}
array.forEach(function(string) { // Not cross-browser compatible, it's just an example
  object[string] = 1;
}

然后执行这样的查找:

if (string in object) {