有没有比使用jQuery更好的搜索JavaScript数组的方法？

Question

我经常需要搜索包含对象的javascript数组.我想在数组中搜索具有属性匹配的对象.例如,在Person对象的数组中搜索person的id/key ==="ABC123"

使用$ .each方法使用jQuery可以很容易地完成它,这是我所确定的.你可以在jsFiddle中看到这里的例子.http://jsfiddle.net/johnpapa/EJAFG/

我想知道是否有其他人找到了更快和/或更好的方法来做到这一点？

var Person = function(code, name) {
    this.code = code;
    this.name = name;
};
var people = [
    new Person("ABC123", "Tooth Fairy"),
    new Person("DEF456", "Santa Claus"),
    new Person("PIR000", "Jack Sparrow"),
    new Person("XYZ987", "Easter Bunny")
    ];

var utils = {};
// Could create a utility function to do this
utils.inArray = function(searchFor, property) {
    var retVal = -1;
    $.each(this, function(index, item) {
        if (item.hasOwnProperty(property)) {
            if (item[property].toLowerCase() === searchFor.toLowerCase()) {
                retVal = index;
                return false;
            }
        }
    });
    return retVal;
};

// or we could create a function on the Array prototype indirectly
Array.prototype.inArray = utils.inArray;

// let's use the prototype for now
var i = people.inArray("PIR000", "code");
$('#output').text(people[i].name);

有很多问题与此类似,但我还没有看到一个解决方案,而不是迭代(就像我在这里做的那样).

所以问题是......有更好的方法吗？

Answer 1

$ .each将是关于O(n)我会想.任何简单的"for"循环在找到适用的项目时会中断,最多只能是O(n),但平均来说会更少,除非数组的后一项经常被发现是匹配元素.Array.filter是一种有效的方法,但不是某些浏览器的原生方法.如果你希望使用它,那么Array.filter方法有纯粹的javascript实现.对于本机托管它的浏览器,它可能执行得更快,因为它们的实现可能是在本机代码中编译和运行的.但是过滤器方法总是会产生O(n),因为它将数组的元素"过滤"成一个新数组.

我个人坚持使用for(int i = 0; ...)方法.通过调用其他函数可以减少范围更改的开销,并且可以轻松地"中断"匹配的元素.

我还想补充一点,你可以使用HTML 5提供的本地数据库存储(使用SqlLite).这显然不受广泛支持,但是在给定足够大的数据集的情况下,它会比任何其他javascript方法快得多.如果你想查看它,这是一个链接:

http://blog.darkcrimson.com/2010/05/local-databases/

以下是一种有点不太常见的方法:理论上,您可以将数据编入索引并以快速方式使用这些指标进行检索.您不是将数据存储在javascript数组中,而是将其存储在DOM中,并使用CSS类(如"data-id-5")对元素进行"索引".这为您提供了使用大多数主流浏览器内置的本机选择器API的优势.这是一个例子:

DOM:

 <div id="datastuff" style="display:none">
     <span class="data-id-ABC123" data-person='{"code": "ABC123", "name": "Tooth Fairy"}'></span>
     <span class="data-id-DEF456" data-person='{"code": "DEF456", "name": "Santa Claus"}'></span>
     <span class="data-id-PIR000" data-person='{"code": "PIR000", "name": "Jack Sparrow"}'></span>
     <span class="data-id-XYZ987" data-person='{"code": "XYZ987", "name": "Easter Bunny"}'></span>
 </div>

现在我们可以使用jQuery并查询它:我们将查询"ABC123"的键:

var person = $(".data-id-ABC123").data("person");
console.log(person.name);//Tooth Fairy

Answer 2

通常,除非您知道要索引的内容,否则无法比O(n)更快地从数组中获取元素.

例如,如果要索引可比较的somethnig,则可以对数组进行排序并执行二进制搜索.

如果您正在对列进行搜索并且值为int或字符串,则可以使用普通Javascript对象作为哈希表.

var people = [
    new Person("ABC123", "Tooth Fairy"),
    new Person("DEF456", "Santa Claus"),
    new Person("PIR000", "Jack Sparrow"),
    new Person("XYZ987", "Easter Bunny")
];

var people_table = {};
for(var i=0; i<people.length; i++){
    people_table[ people[i].id ] = people[i];
}

//fast search:
var someone = people_table['ABC123'];

在某一点之后,查询变得太复杂,无法在Javascript中轻松完成,因此发送处理服务器端可能是个好主意,因此您可以使用更合适的工具,例如关系数据库.

Answer 3

这本身并不能解答您的"搜索"问题,但它可能是您的解决方案.您可以创建一个专门的PersonArray类来索引其中的人员.这种方法的性能是O(1),但它使用更多的内存.

var PersonArray = function(persons) {
    this.elements = {};
    var i;
    for (i=0; i < persons.length; i++) {
        this.elements[persons[i].code] = persons[i];
    }
};

PersonArray.prototype.fromCode = function(s) {
    return this.elements[s];   
};

var people = new PersonArray([
    new Person("ABC123", "Tooth Fairy"),
    new Person("DEF456", "Santa Claus"),
    new Person("PIR000", "Jack Sparrow"),
    new Person("XYZ987", "Easter Bunny")
    ]);

console.log(people.fromCode("ABC123"));  // Prints a person
console.log(people.fromCode("DEF456"));  // Prints a person
console.log(people.fromCode("NONE"));  // Undefined

您也可以扩展此方法以索引其他字段.

另请参阅:演示和基准(100,000个元素).