Otimização em algoritmos de filtragem
Tags: javascript, algorithms
Published: 2023-08-09 18:53:10

Neste artigo, discutiremos uma melhoria significativa em um algoritmo de filtragem de itens em arrays. O cenário envolve a comparação de duas metodologias para filtrar uma lista com base em um conjunto adicional de itens de uma outra lista. 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

```javascript
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`.

```javascript
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:

```javascript
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.