melhorias na complexidade de um algoritmo de filtragem

melhorias_complexidade.md

Otimização em algoritmos de filtragem

Neste artigo, discutiremos uma melhoria significativa em um algoritmo de filtragem de itens de um array. O cenário envolve a comparação de duas metodologias para filtrar itens com base em um conjunto adicional de itens. Vamos analisar as duas abordagens e entender por que a segunda metodologia apresenta uma melhoria considerável em termos de eficiência computacional.

Introdução

Imagine que temos duas listas, o objetivo é filtrar os itens do array 1 removendo aquelas que também estão presentes no conjunto adicional. O desafio reside em escolher a abordagem mais eficiente em termos de complexidade computacional.

Caso de teste: arrays envolvidos

const extraMessages = [
  {
    id: "1",
    content: "content 1",
  },
  {
    id: "2",
    content: "content 2",
  },
];

const historico = [
  {
    id: "1",
    content: "content 1",
  },
  {
    id: "2",
    content: "content 2",
  },
  {
    id: "3",
    content: "content 3",
  },
];

Metodologia 1: Complexidade O(n * m)

Na primeira metodologia, a abordagem utilizada é a combinação das funções filter e some.

const historicoFiltrado = historico.filter(
  (item) => !extraMessages.some((extra) => extra.id === item.id)
);

Nesta abordagem, a lista historico é filtrada com base em uma condição. Para cada item na lista, a função some verifica se há algum item no outro array (extraMessages) com o mesmo ID. Isso resulta em uma complexidade computacional de O(n * m), onde "n" é o tamanho da lista historico e "m" é o tamanho do array extraMessages. Essa abordagem pode se tornar lenta à medida que a quantidade de dados aumenta.

Metodologia 2: Complexidade O(n + m)

A segunda metodologia introduz uma melhoria significativa na eficiência da filtragem. A abordagem envolve a criação de um mapa que armazena os IDs do array extraMessages. Confira o código dessa abordagem:

const extraMessagesMap = {};
extraMessages.forEach((extra) => {
  extraMessagesMap[extra.id] = true;
});

const historicoFiltrado = historico.filter(
  (item) => !extraMessagesMap.hasOwnProperty(item.id)
);

Nesta abordagem, o objeto extraMessagesMap é construído percorrendo o conjunto de do array extraMessages e armazenando os IDs como chaves. Em seguida, a o array historico é filtrado com base na propriedade hasOwnProperty do objeto de chaves. Isso resulta em uma complexidade computacional de O(n + m), que é mais eficiente do que a abordagem anterior.

Vantagens da Metodologia 2

A segunda metodologia oferece várias vantagens em relação à primeira:

1. Complexidade Reduzida: A complexidade O(n + m) da segunda abordagem é mais eficiente do que a complexidade O(n * m) da primeira, especialmente quando as listas de mensagens são extensas.

2. Melhor Performance: A criação do objeto extraMessagesMap permite um acesso mais rápido durante a filtragem, resultando em um desempenho geral melhor.

3. Escalabilidade: A abordagem baseada em objeto/mapa é mais escalável à medida que a quantidade de dados aumenta, garantindo que o tempo de execução permaneça razoável.

Conclusão

Ao comparar as duas metodologias para filtrar arrays com base em um conjunto adicional de mensagens, fica claro que a segunda abordagem, com complexidade O(n + m), é uma escolha superior em termos de eficiência computacional e desempenho.

A utilização de um objeto para rastrear os IDs dos itens adicionais resulta em uma melhoria significativa na velocidade de processamento, especialmente para grandes conjuntos de dados. Ao enfrentar tarefas semelhantes de filtragem, a metodologia 2 se destaca como a opção preferencial.