JavaScript - Formas de realizar buscas em listas muito grandes

Já passou pela situação onde precisava realizar um filtro em uma lista muito grande ? Talvez essa ideia possa te ajudar. Aqui esta um exemplo básico de como aplicar índices em JavaScript.

const users = [
    { age: 37, name: "Moore Hampton" },
    { age: 25, name: "Stephanie Clayton" },
    { age: 30, name: "Pratt Cash" },
    { age: 21, name: "Kenya Gould" },
    { age: 38, name: "Dodson Romero" },
    { age: 34, name: "Weiss Bush" },
    { age: 27, name: "Myrtle Hatfield" },
    { age: 36, name: "Bertie Spencer" },
    { age: 35, name: "Fisher Arnold" },
    { age: 24, name: "Susie Hebert" },
    { age: 37, name: "Beth Lloyd" },
    { age: 24, name: "Keisha Gilliam" },
    { age: 38, name: "Rachel Schultz" },
    { age: 25, name: "Jeanine Flores" },
    { age: 27, name: "Jensen Maddox" },
    { age: 24, name: "Callie Crawford" },
    { age: 22, name: "Campbell Chase" },
    { age: 39, name: "Collins Mercado" },
    { age: 38, name: "Cantu Mcclure" },
    { age: 37, name: "Duffy Buckley" },
    { age: 36, name: "Suzette Navarro" },
    { age: 40, name: "Aida Murray" },
    { age: 35, name: "Alyssa Humphrey" }
];

const usersByAge = {};

users.forEach((user) => {
    if (!usersByAge[user.age]) {
        usersByAge[user.age] = [];
    }

    usersByAge[user.age].push(user);
});

// Usuários com 35 anos
console.log(usersByAge[35]);

// Usuários com 37 anos
console.log(usersByAge[37]);

Já passou por um problema assim ? Compartilhe sua solução.

silvanomarqueshá 2 anos

Gosto muito de criar índices para essa solução, tenho uma função bem simples que me ajuda com isso:

function createIndex<T>(list: T[], key: keyof T) {
    const DEFAULT_INDEX = {} as Record<string, T[]>;

    return list.reduce((index, item) => {
        const indexKey = String(item[key] as keyof typeof index); 
        const existKey = Boolean(index[indexKey]);
        
        if (!existKey) {
            index[indexKey] = [];
        }

        index[indexKey].push(item);

        return index;
    }, DEFAULT_INDEX);
}
jvricartehá 2 anos
Nossa ficou muito bom, eu já precisei trabalhar com esse tipo de operação e acabei fazendo nas piores formas possíveis kkkkkk Segue uma outra alternativa utilizando a estrutura Map: ```ts function createIndex(list: T[], key: keyof T) { const index = new Map(); for (const item of list) { const indexKey = String(item[key]); const itemsForKey = index.get(indexKey) || []; itemsForKey.push(item); index.set(indexKey, itemsForKey); } return index; } ```
duanyespindolahá 2 anos

Pra criação de índices experimente usar Map ao invés de um Object. O tipo Map prevê a criação de novos índices, exclusão, verificação se a chave existe ou não, etc... Para esse tipo de tarefa é mais apropriada do que Object e DESCONFIO (não fiz testes pra saber) que vai ter melhor performance e menos consumo de memória.

PauloIVMhá 2 anos
A implementação de um `Map` é de fato diferente da de um `Object`. Tem algumas diferenças simples de se notar degugando, por exemplo: Se você percorrer os atributos de um `Map`, eles são iterados na ordem de insersão; já se você percorrer os atributos de um `Object` com um `Object.entries()`, a ordem de insersão não necessariamente é respeitada. Não investiguei então não sei dizer com precisão em que se diferencia a performance de um `Map` e um `Object`, mas eu também acredito que um `Map` tenha mais vantagens nesse quesito. Embora a complexidade permaneça O(1) igual o colega falou, imagino que possam ocorrer menos colisões nas funções de hash ou coisas do tipo. Pra mim a única vantagem do `Object` é a sintaxe pra diversas manipulações que você não consegue fazer com tão poucas linhas num `Map`.
khthá 2 anos
Tem várias diferenças, que estão listadas na [documentação](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map#objects_vs._maps). As principais: --- Um objeto pode ter propriedades que vêm do protótipo, o que pode acabar dando resultados confusos (principalmente se o protótipo for modificado em outro ponto do código): ```javascript // todo objeto terá a propriedade "x" Object.prototype.x = 1; const obj = {}; if (obj['x']) { // entra nesse if console.log('obj tem x'); } const map = new Map(); if (map.has('x')) { // não entra nesse if console.log('map tem x'); } // somente se adicionar usando set(), aí passa a ter map.set('x', 42); if (map.has('x')) { // entra nesse if console.log('agora sim, map tem x'); } ``` É claro que se acessarmos `map.x` ou `map['x']`, a propriedade estará lá. Mas em um `Map`, você deve usar os métodos `has` e `get` para, respectivamente, verificar se a chave existe e obter o valor correspondente. --- As chaves de um `Map` podem ser de quaisquer tipos. Já em um object, pode ser somente string ou `Symbol` (outros tipos são convertidos para string). Um `Map` mantém as chaves na ordem de inserção, e você pode iterar um `Map` diretamente com `for..of`: ```javascript const map = new Map(); map.set('nome', 'Fulano'); map.set('idade', 42); // iterar com for..of for (const [ chave, valor ] of map) { console.log(`${chave} = ${valor}`); } // em um objeto, precisa usar um método auxiliar const obj = { nome: 'Fulano', idade: 42 }; for (const [ chave, valor ] of Object.entries(obj)) { console.log(`${chave} = ${valor}`); } ``` --- Além disso, a documentação diz que o objeto tem desempenho pior no caso de ter muitas inserções e remoções. Enfim, não deixe de ler a [documentação](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map#objects_vs._maps) para todos os detalhes.
gabsZxhá 2 anos
Concordo com o uso do Map, acho que a legibilidade do código fica mais legal (geralmente prefiro usar nos meus projetos) e também pelas funções "auxiliares", tipo o has(), mas em termos de performance e consumo de memória acaba por não ter diferença significativa já que tanto no objeto quanto no Map a complexidade é O(1) pra busca e inserção.
brenomazieirohá 2 anos

hummm. Se chegar ao ponto que você precisa fazer isso em uma lista grande, não seria melhor pedir isso ja organizado pro backend? Fazer um foreach e depois dar um console log. entao pq nao logar já no momento do foreach? Mesmo que você faça im foreach ou reduce ou qqr coisa. Só esse processamento ja é pesado se a lista for muito grande. A não ser que você receber um xls assim, mas ai vale a pena processar todo ele primeiro e criar as funções de consulta. Enfim. antes de pensar em uma solução para esse problema uma das formas é pensar porque você tem o problema em si e tentar resolver isso e não só o que esta na sua frente.

Acho que não é a resposta que esperava, mas enfim, pra pensar. :)

khthá 2 anos

Vale lembrar que isso só vale a pena se tiver um array muito grande e forem feitas muitas buscas. Afinal, há um custo inicial para criar o índice de usuários por idade (tanto em tempo quanto em memória), e nem sempre compensa.

Se você só precisa buscar uma ou duas idades, por exemplo, aí um for simples no array é mais rápido. Fiz uns testes usando o Benchmark.js e só a partir de 10 buscas (ou seja, buscar por 10 idades diferentes) começou a valer a pena. Com menos que isso, fazer vários for no array (um para cada idade a ser buscada) foi mais rápido. Testando no JSBench.ME, os resultados foram similares: com poucas buscas, o for simples é mais rápido, e a partir de umas 12 buscas, a sua solução se tornou mais rápida.

Claro que os números exatos podem variar caso a caso, e depende muito do ambiente, dos dados e das buscas feitas. E se forem arrays muito pequenos e/ou poucas buscas, a diferença será irrisória e até imperceptível.

De qualquer forma, temos aqui um exemplo do clássico trade-off (em bom português: "cada escolha, uma renúncia") de tempo e espaço: o programa pode rodar mais rápido, o que compensa o uso extra de memória. Mas tem casos em que não haverá esse ganho. É bom saber que você pode usar essa solução caso precise, mas também é importante saber quando não precisa :-)

programadorhtmlhá 2 anos
Muito bem colocado. Como toda funcionalidade, precisamos analisar e verificar a melhor solução para aquele escopo. Em hipotese alguma um script vai ser "bala de prata". Tudo vai ter seu lado positivo e negativo.
khthá 2 anos
E indo um pouco mais além, daria para criar vários índices para propriedades diferentes: ```javascript const users = [ { age: 37, salary: 10000, name: "Moore Hampton" }, { age: 25, salary: 30000, name: "Stephanie Clayton" }, { age: 30, salary: 30000, name: "Pratt Cash" }, { age: 21, salary: 1000, name: "Kenya Gould" }, { age: 38, salary: 10000, name: "Dodson Romero" }, { age: 34, salary: 1000, name: "Weiss Bush" }, { age: 27, salary: 10000, name: "Myrtle Hatfield" }, { age: 36, salary: 10000, name: "Bertie Spencer" }, { age: 35, salary: 5000, name: "Fisher Arnold" }, { age: 24, salary: 10000, name: "Susie Hebert" }, { age: 37, salary: 10000, name: "Beth Lloyd" }, { age: 24, salary: 10000, name: "Keisha Gilliam" }, { age: 38, salary: 3000, name: "Rachel Schultz" }, { age: 25, salary: 1500, name: "Jeanine Flores" }, { age: 27, salary: 10000, name: "Jensen Maddox" }, { age: 24, salary: 1500, name: "Callie Crawford" }, { age: 22, salary: 3000, name: "Campbell Chase" }, { age: 39, salary: 15000, name: "Collins Mercado" }, { age: 38, salary: 10000, name: "Cantu Mcclure" }, { age: 37, salary: 10000, name: "Duffy Buckley" }, { age: 36, salary: 30000, name: "Suzette Navarro" }, { age: 40, salary: 1000, name: "Aida Murray" }, { age: 35, salary: 15000, name: "Alyssa Humphrey" } ]; function criarIndices(dados, ...propriedades) { const indices = {}; // já deixa criado um índice para cada propriedade for (const prop of propriedades) { indices[prop] = {}; } // para cada elemento, adiciona no respectivo índice de cada propriedade for (const item of dados) { for (const prop of propriedades) { if (! indices[prop][item[prop]]) { indices[prop][item[prop]] = [] } indices[prop][item[prop]].push(item); } } return indices; } const indices = criarIndices(users, 'age', 'salary'); console.log(indices.age[35]); console.log(indices.salary[1000]); ``` Assim só precisa processar o array uma vez, e já deixa criado vários índices. --- Eu não verifiquei se as propriedades existem em cada um dos items do array, então fica como exercício para o leitor :-)
viniciusmdmendoncahá 2 anos

Mano, que dica top viu, me ajudou bastante. A criação do "problema", a forma da solução, os nomes simples e em inglês, muito show viu. Parabéns, thanks!