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

Fast way to find if a string is in an array

本文关键字：数组 是否 字符串 查找      更新时间：2023-09-26

在Ruby中，找出一个字符串是否在数组（.include? x）中是非常慢的。如果将该数组更改为集合，则 BAM，闪电般的快速查找。

在没有集合的 JavaScript 中，数组查找（.indexOf(x) >= 0）也非常慢，但是我需要在脚本中执行 10，000 次这样的查找。

我的Ruby版本（带有集合）在0.125秒内运行，我的JavaScript版本（在NodeJS中）需要29！

是否有任何集合库或更好的方法来执行数组查找，可以使Javascript速度接近Ruby？

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

首先，对于JavaScript中可用的数据结构存在一些根本性的混淆。

博士

  • 如果要对具有短原型继承链的对象进行最快的键查找，请使用 in 。

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

  • 如果需要最快的值查找，请使用 Array.prototype.indexOf 进行Array。

  • 哈希表中没有用于值查找的内置函数。当然，您可以自己动手，但是已经有许多库提供了。例如，下划线提供了一个（它称之为indexOf）。

JavaScript 没有数组

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

所以，当你在JavaScript上下文中说Array时，它被理解为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中的所有事物都是对象这一事实有关，因此它们具有一些object-y特性。其中之一是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

从评论中的@nnnnnn：

将数组转换为对象，如下所示：

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

然后执行如下所示的查找：

if (string in object) {
相关文章：