一个有效的Javascript集结构

Question

在阅读了许多类似问题后:

我还有一个问题:假设我有一个很大的字符串数组(几千个),我必须进行多次查找(即多次检查一个给定的字符串是否包含在这个数组中).在Node.js中执行此操作的最有效方法是什么？

A.排序字符串数组,然后使用二进制搜索？要么:

B.将字符串转换为对象的键,然后使用"in"运算符

？

我知道A的复杂度是O(log N),其中N是字符串的数量.

但我不知道B的复杂性.

如果Javascript对象被实现为哈希表,则B的复杂度平均为O(1),这比A好.但是,我不知道Javascript对象是否真的实现为哈希表!

Answer 1

2016年更新

由于您询问的是node.js并且它是2016年,您现在可以使用ES6中的Set或者Map对象,因为这些内置在ES6中.两者都允许您使用任何字符串作为键.Set当您只想查看密钥是否存在时,该对象是合适的:

if (mySet.has(someString)) {
    //code here
}

并且,Map当您想要存储该键的值时,如下所示:

if (myMap.has(someString)) {
    let val = myMap[someString];
    // do something with val here
}

现在,两个ES6功能都内置于node.js中,从节点V4开始(此编辑的当前版本node.js为v6).

查看此性能比较,了解Set操作比其他许多选项快多少.

较旧的答案

所有重要的性能问题都应该通过jsperf.com等工具中的实际性能测试进行测试.在您的情况下,javascript对象使用类似哈希表的实现,因为没有执行得很好的东西,整个实现会很慢,因为很多javascript使用对象.

对象上的字符串键将是我测试的第一件事,并且是我对最佳表演者的猜测.由于对象的内部是用本机代码实现的,我希望这比你自己的哈希表或在javascript中实现的二进制搜索更快.

但是,当我开始回答时,您应该使用jsperf等工具中最关注的字符串的数量和长度来测试您的具体情况.

@ErelSegalHalevi - 然后在node.js中设计自己的性能测试,或者在node.js中使用jsperf.com的基准测试引擎.node.js与Chrome中的javascript引擎相同,因此您可以通过在Chrome浏览器中尝试使用jsperf.com获得第一笔订单结果.如果您想在node.js中验证,则必须将自己的基准测试移至node.js. 这里的答案不会在银盘上交给你.如果你真的想知道哪个更快,你必须测试你的具体情况.我建议你使用已经构建的性能基准测试工具. (3认同)

Answer 2

我非常确定使用 JS 对象作为字符串存储将导致该对象的“哈希模式”。根据实现的不同，这可能是 O(log n) 到 O(1) 时间。查看一些jsperf基准测试，以比较排序数组上的属性查找与二分搜索。

在实践中，特别是如果我不打算在浏览器中使用代码，我会将此功能卸载到 redis 或 memcached 之类的东西。