代码之家 › 专栏 › 技术社区 › Willem

在Javascript数组中查找元素的有效方法

associative-array big-o complexity-theory search javascript

7

Willem · 技术社区 · 17 年前

title = "why-birds-fly";
titles[] // an array which contains all the titles

for (i = 0; i < titles.length-1; i++) {
  if (titles[i] == title)
    return i+1;
}

我可以使用的另一种方法是创建一个关联数组和标题数组,这与标题完全相反。也就是说,它使用字符串作为索引并返回数字。

titles_id {blah:0,why-birds-fly:1,blah2:2}

然后,我可以通过以下方式访问ID:

return titles_id[title]+1;

另外,如果我的逻辑完全错误,请告诉我。

谢谢威廉

4 回复 | 直到 17 年前

1

11

Paul Dixon 17 年前

complexity 最好如果JS引擎使用哈希并且没有冲突,则情况可能是O(1))。这将取决于JS引擎通常如何实现 associative arrays/objects

因此,第二种方法会更快,但当然会使用更多的内存。这是一个非常典型的 trade off

2

0

eulerfx 17 年前

考虑需要存储的键值对的数量也很重要。如果它小于~50(取决于实现),那么进行线性搜索将与进行哈希表查找一样高效,因为计算哈希值和解决冲突的成本很高。一个例外是,Google chrome v8 JavaScript引擎保留了所有对象的一种缓存版本,允许它直接查找对象上的属性,因此将object类用作哈希表可能会更快,尽管我不确定创建此缓存版本的成本是否会超过小列表的好处。

3

0

Billy 17 年前

您可以在第一个方法中使用Array的indexOf函数。

以下是Mozilla开发者提供的信息: https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference:Objects:Array:indexOf

if (!Array.prototype.indexOf)
{
  Array.prototype.indexOf = function(elt /*, from*/)
  {
    var len = this.length >>> 0;

    var from = Number(arguments[1]) || 0;
    from = (from < 0)
         ? Math.ceil(from)
         : Math.floor(from);
    if (from < 0)
      from += len;

    for (; from < len; from++)
    {
      if (from in this &&
          this[from] === elt)
        return from;
    }
    return -1;
   };
}

4

-2

Rick Hochstetler 17 年前

Javascript数组可以使用诸如标题“为什么鸟会飞”之类的值作为索引。

var TitleArray[]=new Array();

TitleArray[title]=id;