Modi efficaci per trovare un elemento in un array Javascript

Question

Sto usando un array con titoli. Ogni indice dei titoli corrisponde a un ID in un database che contiene HTML per quel determinato titolo.

Diciamo che ho una stringa che contiene uno dei titoli.

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

Per utilizzare la stringa " title " per ottenere l'id corrispondente che potrei fare:

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

Un altro metodo che potrei usare è quello di creare un array associativo insieme all'array dei titoli che è l'esatto opposto dei titoli. Cioè, utilizza la stringa come indice e restituisce il numero.

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

Potrei quindi accedere all'ID tramite:

return titles_id[title]+1;

Quale sarebbe più efficace considerando CPU, memoria, ecc.

Inoltre, per favore fatemi sapere se la mia logica è tutta sbagliata.

Grazie Willem

Answer 1

L'approccio della ricerca lineare ha una complessità di O (n), e penso che il peggio il caso dell'approccio di array associativo è probabilmente O (log n), (il caso migliore forse O (1) se il motore JS utilizza gli hash e non ottiene collisioni). Dipenderà da come un motore JS implementa tipicamente array / oggetti associativi , ma puoi essere sicuramente batterà O (n).

Quindi, il secondo approccio sarà più veloce, ma ovviamente utilizzerà più memoria. Questo è un tipico trade off , guadagnando più velocità, ma usando più memoria e solo puoi decidere se vuoi fare quel trade.

Answer 2

È anche importante considerare il numero di coppie chiave-valore che è necessario memorizzare. Se è inferiore a ~ 50 (a seconda dell'implementazione), fare una ricerca lineare sarà efficiente quanto fare una ricerca nella tabella hash, a causa del costo del calcolo del valore hash e della risoluzione delle collisioni. Un'eccezione è che il motore JavaScript di Google Chrome v8 mantiene una sorta di versione cache di tutti gli oggetti che gli consentono di eseguire una ricerca diretta di una proprietà su un oggetto, quindi l'uso della classe Object come tabella hash potrebbe essere più veloce, anche se I non sono sicuro se il costo di creazione di questa versione memorizzata nella cache supererà il vantaggio per gli elenchi più piccoli.

Answer 3

Puoi usare la funzione indexOf di Array nel tuo primo metodo.

Di seguito sono riportate le informazioni dallo sviluppatore Mozilla: https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference: Oggetti: Array: indexOf

indexOf è un'estensione JavaScript allo standard ECMA-262; come tale potrebbe non essere presente in altre implementazioni della norma. È possibile aggirare questo problema inserendo il seguente codice all'inizio degli script, consentendo l'utilizzo di indexOf nelle implementazioni ECMA-262 che non lo supportano in modo nativo. Questo algoritmo è esattamente quello usato in Firefox e 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

Le matrici Javascript possono utilizzare un valore come il titolo "why-birds-fly " per l'indice.

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

var TitleArray [] = new Array ();

TitleArray [title] = id;

Quindi hai accesso diretto all'ID per titolo:

return TitleArray [title];