Formas efectivas de encontrar un elemento en una matriz de 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 usar la cadena " title " para obtener la identificación correspondiente que podría hacer:

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

Otro método que podría usar es crear una matriz asociativa junto con la matriz de títulos, que es exactamente lo contrario de los títulos. Es decir, utiliza la cadena como índice y devuelve el número.

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

Entonces podría acceder a la ID:

return titles_id[title]+1;

¿Qué sería más efectivo considerando CPU, memoria, etc.?

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

Gracias Willem

Answer 1

El enfoque de búsqueda lineal tiene una complejidad de O (n), y creo que lo peor el caso para el enfoque de matriz asociativa es probablemente O (log n), (el caso mejor puede ser O (1) si el motor JS está usando hashes y no tiene colisiones). Dependerá de cómo un motor JS implementa típicamente matrices / objetos asociativos , pero puede ser seguro que vencerá a O (n).

Entonces, el segundo enfoque será más rápido, pero por supuesto usará más memoria. Este es un intercambio muy típico, ganando más velocidad, pero usando más memoria, y solo puedes decidir si quieres hacer ese intercambio.

Answer 2

También es importante tener en cuenta la cantidad de pares de valores clave que necesitará almacenar. Si es menor de ~ 50 (dependiendo de la implementación), entonces hacer una búsqueda lineal será tan eficiente como hacer una búsqueda de tabla hash, debido al costo de calcular el valor hash y resolver las colisiones. Una excepción es que el motor JavaScript de Google chrome v8 mantiene una especie de versión en caché de todos los objetos que le permite realizar una búsqueda directa de una propiedad en un objeto, por lo tanto, el uso de la clase Object 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 para listas más pequeñas.

Answer 3

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

A continuación se muestra la información del desarrollador de Mozilla: https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference: Objetos: Matriz: indexOf

indexOf es una extensión de JavaScript para el 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 implementaciones de ECMA-262 que no lo admiten de forma nativa. Este algoritmo es exactamente el que se usa 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;
   };
}

Answer 4

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

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

var TitleArray [] = new Array ();

TitleArray [title] = id;

Entonces tiene acceso directo a la identificación por título:

return TitleArray [título];