Só pra ilustrar, um exemplo prático em JavaScript. Suponha que eu tenha um array assim:
[
{ nome: 'Fulano', idade: 20 },
{ nome: 'Ciclano', idade: 31 },
{ nome: 'Beltrano', idade: 20 },
{ nome: 'Trajano', idade: 31 },
{ nome: 'João', idade: 42 },
]
E eu queira criar outro array que tem os nomes agrupados por idade:
[
{ idade: 20, nomes: [ 'Fulano', 'Beltrano' ] },
{ idade: 31, nomes: [ 'Ciclano', 'Trajano' ] },
{ idade: 42, nomes: [ 'João' ] }
]
A ideia mais simples é usar um for, e para cada elemento, verifico se a idade já existe no resultado. Se não existir, cria o array de nomes, e se já existir, adiciona nesse array:
const result = [];
for (const item of dados) {
let elemento = result.find(e => e.idade == item.idade);
if (!elemento) {
elemento = { idade: item.idade, nomes: [] };
result.push(elemento);
}
elemento.nomes.push(item.nome);
}
console.log(result);
Ok, funciona. Mas esse algoritmo tem um porém: para cada item do array dados, eu uso find para verificar se a idade já está no resultado - pois eu tenho que saber se preciso adicionar uma idade que ainda não está lá. Só que a busca em um array é linear, ou seja, find no fundo é outro loop (que está "escondido", pois ele faz isso internamente). Claro que ele interrompe o loop quando encontra o elemento, mas mesmo assim, conforme o array result cresce, fica cada vez mais custoso percorrê-lo para fazer esta busca.
Daria para melhorar isso usando inicialmente um objeto para mapear cada idade para seu respectivo array, assim o custo da busca é diminuído:
let result = {};
for (const item of dados) {
result[item.idade] ||= { idade: item.idade, nomes: [] };
result[item.idade].nomes.push(item.nome);
}
result = Object.values(result);
console.log(result);
O operador ||= é usado para atribuir um valor caso ele ainda não esteja definido. Por exemplo, a ||= b é o mesmo que a = a || b (se a estiver definido, usa o valor dele, senão usa o valor de b). No caso, result[item.idade] estará definido somente se a idade já estiver no resultado. Caso não esteja, adiciona-a no objeto, cujo valor será o objeto que contém a idade e o respectivo array de nomes.
Isso é mais rápido que find porque a busca de uma propriedade em objetos é mais rápida (não é linear como no array, não precisa fazer um loop pelos elementos até encontrar a idade).
No final, pegamos apenas os valores do objeto, e o resultado é o array que queríamos.
Fiz um teste usando o Benchmark.js, segue todo o código abaixo:
var Benchmark = require('benchmark');
var suite = new Benchmark.Suite;
const dados = [];
for (let i = 0; i < 10000; i++) {
dados.push({ nome: 'Fulano ' + i, idade: i % 80 });
}
suite
.add('for/find', function () {
const result = [];
for (const item of dados) {
let elemento = result.find(e => e.idade == item.idade);
if (!elemento) {
elemento = { idade: item.idade, nomes: [] };
result.push(elemento);
}
elemento.nomes.push(item.nome);
}
})
.add('object', function () {
let result = {};
for (const item of dados) {
result[item.idade] ||= { idade: item.idade, nomes: [] };
result[item.idade].nomes.push(item.nome);
}
result = Object.values(result);
})
.on('complete', function () {
console.log('Fastest is ' + this.filter('fastest').map('name'));
})
.on('cycle', function (event) {
console.log(String(event.target));
})
.run({ 'async': true });
Criei um array com 10 mil itens, com idades variando entre 0 e 79. O resultado está abaixo (lembrando que os números são de operações por segundo, ou seja, quanto mais, melhor):
for/find x 1,021 ops/sec ±0.72% (90 runs sampled)
object x 9,144 ops/sec ±1.70% (91 runs sampled)
Fastest is object
Vale lembrar também que os números podem variar de acordo com cada máquina. Mas em geral, o resultado final (qual é mais rápido) não deve variar.
Enfim, usando o objeto deu umas 9 mil operações por segundo, enquanto o for com find deu apenas mil.
Se aumentarmos o intervalo de idades para 0 a 99, a diferença entre eles aumenta:
for/find x 849 ops/sec ±0.73% (88 runs sampled)
object x 8,354 ops/sec ±1.03% (90 runs sampled)
Fastest is object
Se usarmos um intervalo de 0 a 999 (sei que 999 é muito para idade, mas imagine que fosse outro campo, como uma pontuação qualquer, por exemplo), a diferença aumenta ainda mais:
for/find x 95.69 ops/sec ±2.09% (68 runs sampled)
object x 6,275 ops/sec ±1.38% (79 runs sampled)
Fastest is object
Sim, mais de 6 mil operações por segundo, contra menos de 100 (os números estão no formato americano, a vírgula separa os milhares e o ponto é o separador decimal).
Quanto menos idades repetidas, pior fica, porque o array result fica com mais elementos, e find acaba - na média - demorando mais para verificar se uma idade já existe. Já para um objeto o impacto é menor, porque a busca por uma propriedade não é linear (provavelmente usa alguma tabela de hash ou algo similar - cuja busca é geralmente constante - para ser tão rápido).
Mas como eu já disse, para arrays pequenos não faz tanta diferença assim, e em alguns casos o for pode até ser mais rápido. Por exemplo, para um array com 30 itens e idades entre 0 e 29, o for foi mais rápido:
for/find x 879,554 ops/sec ±1.50% (86 runs sampled)
object x 774,850 ops/sec ±2.04% (82 runs sampled)
Fastest is for/find
Isso porque tem o custo extra de criar o objeto e no final criar outro array contendo somente os valores (quando chamamos Object.values). Esse custo só se paga se tivermos mais elementos. E novamente, isso pode variar de acordo com o hardware, mas enfim, na minha máquina o for já ficou mais lento com apenas 50 itens.
E reforço a questão de que isso será imperceptível para poucos arrays pequenos (a questão de 0.1 segundo versus 0.001 segundo, ambos não dá para perceber, apesar de um ter sido 100 vezes mais rápido). Isso só começa a fazer uma diferença notável com muitos arrays grandes, e por isso que muita gente não liga pra isso e acha que é inútil.
Mas é importante saber sim. São várias dessas pequenas ineficiências que quando somadas acabam degradando aos poucos o sistema. Claro que se for um sistema simples e pequeno, de criticidade baixa, e que seguramente trabalha sempre com poucos dados, aí talvez não precise otimizar tanto. Mas é importante saber desses detalhes sim, para não ser pego de surpresa quando os problemas de desempenho começarem.
