6

我怎样才能有效地在 Javascript 中进行集合成员资格检查？我有一个可能很大的字符串数组，我需要验证给定的字符串是否是数组的成员。

最初我认为in运营商可以提供帮助，但在阅读了 Mozilla Developer Network 上的文档后，我发现它的目的是不同的。在 Javascript 中，它检查指定的属性是否在指定的对象中。

出于与性能相关的原因，我更喜欢使用 js 内置函数，但如果不存在这样的函数，我可能会结束执行以下操作之一：

  1. 使用数组创建一个以数组元素为键的对象，然后使用in
  2. 遍历数组元素并逐项进行比较
  3. 实现二分查找

有什么意见吗？或者更好的想法？

谢谢

4

4 回答 4

2

这是否有足够好的性能？

var inArray = function(array, value) {
    var i = array.length;

    while (i--) {
        if (array[i] == value) {
            return true;
        }
    }

    return false;

}

js小提琴。

除非您的应用程序需要它（测量并查看这是否是瓶颈），否则它应该足够快且足够直接以供阅读。

于 2011-03-08T11:43:48.583 回答
2

正如您将在这个问题中发现的那样，几乎每个框架都有一个功能，一些浏览器甚至原生实现了一个indexOf功能（虽然不是全部）。

似乎他们都通过迭代数组来做到这一点，有些使用另一个方向（从末端开始），因为它似乎更快。对于亚线性算法，您可能需要实现某种哈希集，并在键上进行二进制搜索。

可以在此处找到 HashSet 实现的示例。

于 2011-03-08T11:39:27.887 回答
0

我建议您同时使用对象和数组。

这样，您可以非常快速地对对象进行成员资格测试，并在需要您的项目保持排序时使用数组。

这是我发现模拟“排序字典”类型行为的唯一方法。

于 2011-03-08T11:44:50.723 回答
0

你必须使用数组吗？你可以从一开始就使用一个对象吗？如果您需要遍历元素，您可以在对象上使用 for in 循环。

二进制搜索仅在排序后才有效。如果您知道要多次搜索数组，这可能是个好主意。否则选项 2 会更快。

于 2011-03-08T11:40:06.340 回答