maneiras eficazes de encontrar um elemento em uma matriz Javascript

Question

Eu estou usando uma matriz com títulos. Cada títulos índice corresponde a um ID numa base de dados que contém HTML para aquela dada título.

Vamos dizer que eu tenho uma string que contém um dos títulos.

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

Para usar o "título" string para obter o ID correspondente eu poderia fazer:

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

Outro método que eu poderia usar é criar uma matriz associativa em conjunto com a matriz de títulos que é o oposto exato de títulos. Ou seja, ele usa a corda como um índice e retorna o número.

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

Eu poderia, então, acessar o ID por:

return titles_id[title]+1;

O que seria mais eficaz CPU considerando, memória, etc?

Além disso, por favor deixe-me saber se minha lógica está tudo errado.

Graças Willem

Answer 1

A abordagem busca linear tem um complexidade de O (n), e eu acho que o pior caso para a abordagem matriz associativa é, provavelmente, o (log n), (o melhor caso, talvez o (1) se o motor JS está usando hashes e ficando sem colisões). Vai depender de como um motor de JS tipicamente implementos associativa matrizes / objetos , mas você pode ter certeza de que ele vai bater o (n).

Assim, a segunda abordagem será mais rápido, mas, claro, usar mais memória. Esta é uma off , ganhando mais velocidade, mas usando mais memória, e só você pode decidir se você quiser fazer que o comércio.

Answer 2

Também é importante considerar o número de pares de valores-chave que você vai precisar para armazenar. Se sua a menos de ~ 50 (dependendo da aplicação), em seguida, fazer uma busca linear será tão eficiente como fazer uma tabela de hash, por causa do custo de calcular o valor de hash e resolver colisões. Uma exceção é o Google Chrome V8 JavaScript mantém uma espécie de versão em cache de todos os objetos que lhe permitem executar uma pesquisa direta de uma propriedade em um objeto, portanto, o uso da classe de objeto como uma tabela hash pode ser mais rápido, embora eu 'm não tem certeza se o custo de criar esta versão em cache superam o benefício para as listas menores.

Answer 3

Você pode usar a função indexOf da matriz em seu primeiro método.

Abaixo está a informação da Mozilla Developer: https://developer.mozilla.org/En/Core_JavaScript_1.5_Reference: objetos: array: indexOf

indexOf é uma extensão JavaScript com o padrão ECMA-262; como tal, não pode estar presente em outras implementações do padrão. Você pode contornar isso inserindo o seguinte código no início de seus scripts, permitindo o uso de indexOf em ECMA-262 implementações que não têm suporte nativo para ele. Este algoritmo é exatamente o utilizado no 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

matrizes de JavaScript pode usar um valor como o título de "why-aves-fly" para o índice.

exmaple: título var = "porquê-pássaro-fly";

var TitleArray [] = new Array ();

TitleArray [título] = id;

Em seguida, você tem acesso directo à id por título:

retorno TitleArray [título];