2012-01-13 26 views
15

A menudo tengo la necesidad de buscar una matriz de JavaScript que contenga objetos. Quiero buscar un objeto en la matriz que tenga una coincidencia de propiedad. Por ejemplo, buscar en una matriz de objetos Persona donde se encuentra la identificación/clave de la persona === "ABC123"¿Existe una mejor manera de buscar una matriz de JavaScript que utilizar jQuery cada uno?

Se puede hacer fácilmente usando jQuery usando el método $ .each, que es lo que establecí. Puedes ver el ejemplo aquí en jsFiddle. http://jsfiddle.net/johnpapa/EJAFG/

Me pregunto si alguien más ha encontrado una manera más rápida y/o mejor para hacer esto?

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); 

hay gran cantidad de preguntas similares a éste, pero todavía tengo que ver uno con una solución que no sea la iteración (como lo hice aquí).

Entonces la pregunta es ... ¿hay una manera mejor?

+0

Hay una pregunta similar [aquí] [1]. [1]: http://stackoverflow.com/questions/1144423/jquery-selectors-for-plain-javascript-objects-instead-of-dom-elements –

+0

Ver http://stackoverflow.com/questions/143847/best-way-to-find-an-item-in-a-javascript-array y http://stackoverflow.com/questions/237104/array-containsobj-in-javascript – j08691

+0

@ j08691 ambos están comprobando si existe una coincidencia de objeto exacta. Para aquellos, $ .inArray funciona bien. Estoy buscando una búsqueda por clave. –

Respuesta

16

$ .each sería sobre O (n) Yo pensaría. Cualquier bucle "para" simple que se rompa cuando encuentre un artículo aplicable sería como máximo O (n) pero en promedio sería menor a menos que los últimos elementos de la matriz se encontraran constantemente como los elementos coincidentes. Array.filter es un método que funciona pero que no es nativo de algunos navegadores. Existen implementaciones puras de JavaScript del método Array.filter si así lo desea. Para los navegadores que lo alojan de forma nativa, probablemente se ejecute más rápido ya que su implementación probablemente se compila y se ejecuta en código nativo. Pero el método de filtro siempre daría O (n) ya que "filtra" los elementos de la matriz en una nueva matriz.

Personalmente me quedaría con el enfoque for (int i = 0; ...). Menos sobrecarga del cambio de alcance llamando a otras funciones y puede "romper" fácilmente un elemento coincidente.

También quería agregar que podría usar el almacenamiento de base de datos local (que usa SqlLite) proporcionado por HTML 5. Esto obviamente no es ampliamente compatible pero sería MUCHO más rápido que cualquier otro enfoque javascript dado un conjunto de datos lo suficientemente grande. Aquí hay un enlace si quieres echarle un vistazo:

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

aquí es un poco fuera del camino de la pared de hacerlo: Se podría teóricamente indexar sus datos y recuperarlo utilizando los índices del de una forma rápida manera. En lugar de almacenar sus datos en una matriz de JavaScript, la almacena en el DOM y "indexa" los elementos usando clases CSS como "data-id-5". Esto le da la ventaja de utilizar la API de selector nativo incorporada en la mayoría de los navegadores principales. Aquí está un ejemplo:

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> 

Ahora podemos utilizar jQuery y consulta por él: Vamos a consultar para la tecla de "ABC123":

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

+1 por un buen consejo. Es probable que un bucle simple sea más limpio (sin dependencia de una biblioteca externa) y más rápido (menos llamadas a funciones, no creación de objetos jQuery), pero los criterios del OP pueden ser diferentes. Si se trata de una operación que se realiza con frecuencia en una matriz grande, un índice simple es una pequeña sobrecarga al agregar un nuevo objeto que puede aumentar enormemente el rendimiento al realizar una búsqueda. – RobG

+0

+1 @odie Gracias por la entrada. Me lleva a pensar ya sea para loop o $ .each está bien. Es una búsqueda, entonces no hay una bala mágica. Es bueno rebotar ideas :) –

+1

He añadido una forma más que, sin duda, sería increíblemente rápida y directa, técnicamente sin bucle. Cambie el índice para usar Id y podría hacer getElementById ("data-id-ABC123"), que es casi un proceso instantáneo en estos días en la mayoría de los navegadores. – doogle

0

tal vez se puede bucle con un for..in. Ver: http://www.w3schools.com/js/js_loop_for_in.asp. Funciona de manera similar como foreach de php.

+1

Supongo que el for/in tiene el mismo rendimiento que $ .each ... pero quizás estoy equivocado. Vale intentarlo. –

+0

for-in is * not * a foreach. No * use * para iterar en matrices. Además, [no enlace] (http://w3fools.org) a w3schools – hugomg

+0

No dijo que eran lo mismo, pero ¿por qué no usarlo para iterar una matriz? Gracias por el aviso sobre www.w3fools.com. Tu y su punto es válido, sin duda después de leer el sitio. – Ruben

6

Esto no responde a su pregunta de "búsqueda" per se, pero puede ser una solución para usted. Puede crear una clase especializada PersonArray que indice a las personas dentro de ella. El rendimiento con este enfoque es O (1), pero usa más memoria.

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 

Puede ampliar este enfoque para indexar otros campos, también.

Ver también: a demo y a benchmark (con 100.000 elementos).

7

En general, no puede obtener elementos de una matriz más rápido que O (n) a menos que sepa algo acerca de lo que quiere indexar.

Por ejemplo, si está indexando algo que es comparable, puede ordenar la matriz y realizar búsquedas binarias.

Si está realizando búsquedas en una columna y los valores son enteros o cadenas, puede utilizar objetos de Javascript plano como tablas hash.

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']; 

Después de algunas consultas puntuales llegar demasiado complejo para hacerlo fácilmente con la mano en Javascript por lo que podría ser una buena idea para enviar el lado del servidor de procesamiento de esta manera puede utilizar una herramienta más adecuada, al igual que como una base de datos relacional .

+0

Genial, pero debería tratar con duplicados. – RobG

+0

Manejar duplicados es el tipo de cosas que comienza a ser molesto hacerlo a mano. Espero que al menos puedas dar una identificación única para todos. – hugomg

+0

idea genial. Hashing es genial si tiene conocimiento de lo que indexará. THO en este caso no puedo usarlo, me gusta esto. –

1

Si tiene la intención de hacer esto mucho, entonces puede querer crear un índice para propiedades específicas para que los elementos se puedan devolver mucho más rápido. p.ej. lo siguiente implementa un objeto de almacenamiento que agrega y obtiene objetos que se agregan a él.

Mantiene un índice de nombres de objetos (si tienen uno) para que obtenerlos sea eficiente.

Sin embargo, solo notará un aumento en el rendimiento para una gran cantidad de objetos (digamos más de 100) y solo para aquellos con índice (aunque puede crear un índice para cualquier cantidad de propiedades y podría tener un método más genérico para hacer eso).

function Storage() { 
    this.store = []; 
    this.nameIndex = {}; 
} 

// Add item to the store, if has name property, add name to name index 
Storage.prototype.addItem = function(item) { 
    var idx = this.nameIndex; 

    // If the item has a name property 
    if (item.hasOwnProperty('name')) { 

    // If already have an item with that name, add index of 
    // this item to indexs of same named items 
    if (idx.hasOwnProperty(item.name)) { 
     idx[item.name].push(this.store.length); 

    // Otherwise, add this item to the index 
    } else { 
     idx[item.name] = [this.store.length]; 


    } 
    } 
    // Add the item to the store 
    this.store.push(item); 
} 

// Returns a possibly empty array of items with matching names 
Storage.prototype.getItemsByName = function(name) { 
    var result = []; 
    var names; 

    if (this.nameIndex.hasOwnProperty(name)) { 
    list = this.nameIndex[name]; 

     for (var i=0, iLen=list.length; i<iLen; i++) { 
     result.push(this.store[list[i]]); 
     } 
    } 
    return result; 
} 

// Generic method for any property and value 
Storage.prototype.getItemsByAttributeValue = function(propName, propValue) { 
    // loop through items, return array of 
    // those with matching property and value 
} 


var store = new Storage(); 

store.addItem({name:'fred',age:'9'}); 

var obj = store.getItemsByName('fred'); 

alert(obj[0].age); // 9 

store.addItem({name:'sally',age:'12'}); 

obj = store.getItemsByName('sally'); 

alert(obj[0].age); //12 
0

Si tengo que buscar una serie repetida, entonces repetir una vez, en la que agrego cada tecla como una propiedad de un objeto, y luego buscar la clave en ese objeto. Esto mantiene el objetivo de todas las búsquedas en O (n) + c. El almacenamiento es eficiente ya que el objeto almacena referencias a los datos de la matriz, o son primitivos. Simple y rápido.

Cuestiones relacionadas