Formas efectivas de encontrar un elemento en una matriz Javascript

Question

Estoy usando una matriz con títulos. Cada índice de títulos corresponde a una identificación en una base de datos que contiene html para ese título dado.

Digamos que tengo una cadena que contiene uno de los títulos.

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

Para utilizar el "título" cadena para obtener el ID correspondiente que podía hacer:

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

Otro método que podría utilizar es crear una matriz asociativa en conjunto con la matriz de títulos, que es la exacta opuesto de títulos. Es decir, usa la cadena como índice y devuelve el número.

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

Podría entonces tener acceso a la Identificación por:

return titles_id[title]+1; 

Lo que sería más eficaz teniendo en cuenta la CPU, memoria, etc?

Además, avíseme si mi lógica es incorrecta.

Gracias Willem

Answer 1

El método de búsqueda lineal tiene una complexity de O (n), y creo que el peor de los casos para el enfoque de matriz asociativa es, probablemente, O (log n), (la mejor caso tal vez O (1) si el motor JS está usando hashes y no hay colisiones). Dependerá de cómo un motor JS implemente típicamente associative arrays/objects, pero puede estar seguro de que va a vencer a O (n).

Por lo tanto, el segundo enfoque será más rápido, pero por supuesto utilizará más memoria. Este es un trade off muy típico, ganando más velocidad, pero usando más memoria, y solo usted puede decidir si desea hacer ese cambio.

Answer 2

Las matrices de Javascript pueden usar un valor como el título "why-birds-fly" para el índice.

Exmaple: var title = "why-birds-fly";

var TitleArray [] = new Array();

TitleArray [title] = id;

entonces usted tiene acceso directo a la Identificación por título:

retorno TitleArray [título];

Answer 3

También es importante tener en cuenta la cantidad de pares de valores clave que deberá almacenar. Si es menor que ~ 50 (dependiendo de la implementación), entonces hacer una búsqueda lineal será tan eficiente como hacer una búsqueda de tablas hash, debido al costo de calcular el valor hash y resolver colisiones. Una excepción es el motor de JavaScript Google Chrome 8 que guarda una especie de versión en caché de todos los objetos que le permiten realizar una búsqueda directa de una propiedad en un objeto, por lo tanto, el uso de la clase Objeto como tabla hash puede ser más rápido, aunque No estoy seguro de si el costo de crear esta versión en caché superará el beneficio de las listas más pequeñas.

Answer 4

Puede usar la función indexOf de Array en su primer método.

A continuación se muestra la información de Mozilla Developer: https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference:Objects:Array:indexOf

indexOf es una extensión de JavaScript al estándar ECMA-262; como tal, puede no estar presente en otras implementaciones del estándar. Puede solucionar esto insertando el siguiente código al comienzo de sus scripts, permitiendo el uso de indexOf en las implementaciones de ECMA-262 que no lo admiten de forma nativa. Este algoritmo es exactamente el utilizado en Firefox y SpiderMonkey.

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