Introdução
A estrutura de dados Fila (Queue) é uma das mais fundamentais da computação e embora seja de fato uma estrutura simples, possui uma grande capacidade de organizar o fluxo de dados. No entanto, a escolha de como implementar uma fila pode ser a diferença entre um sistema fluido e um gargalo de performance. No decorrer deste guia, vamos entender seu conceito, por que ela é essencial para a escalabilidade e como implementá-la de forma performática.
O Conceito FIFO
Diferentemente da estrutura de dados Pilha, que segue o princípio LIFO (Last-In, First-Out), a Fila segue o princípio FIFO (First-In, First-Out). Na prática, seu funcionamento remete exatamente à fila que conhecemos no dia a dia: o primeiro que entra deve ser o primeiro a sair.
Para que esse princípio seja respeitado, utilizamos duas operações fundamentais que ocorrem nas extremidades da estrutura:
- Enqueue: Adiciona um novo elemento no final da fila.
- Dequeue: Remove o elemento que está no início da fila.
Array x Objeto
Para utilizar essa estrutura em nossos projetos podemos seguir por dois caminhos: array ou objeto.
Quando utilizamos array temos a vantagem de possuir propriedades e métodos nativos. No JavaScript, por exemplo, temos o push(), shift(), além de funções extremamente úteis como map(), filter() e reduce(). Com isso não temos o custo de criar toda a lógica do zero.
Para contextos com poucos dados, o array nos atende perfeitamente. No entanto, em cenários de processamento massivo, essa abordagem torna-se um gargalo. Isso ocorre porque a maioria dos métodos de array possui uma complexidade de tempo linear O(n). Isso significa que, à medida que a fila cresce o tempo de execução cresce na mesma proporção. Mas por que isso ocorre especificamente na operação de remoção?
O custo do shift e a reindexação
Quando realizamos uma operação de remoção (dequeue), além de apenas remover o elemento, o JavaScript precisa manter a integridade da estrutura, movendo todos os itens restantes para uma posição anterior.
Dessa forma, ao remover o primeiro item de um array de 1.000 itens, aquele que estava no índice 1 precisa ir para o 0, o que estava no 2 para o 1 e assim sucessivamente. Ou seja, serão necessárias 999 operações de reindexação apenas para essa primeira remoção. Esse procedimento é feito de maneira “invisível” pelo método shift() do JavaScript, mas o custo está lá, consumindo processamento.
Memória contígua e Array esparsos
O processo de reindexação é necessário porque, por padrão, o JavaScript tenta alocar arrays em um bloco de memória contíguo. Isso significa que o endereço de memória de um elemento está imediatamente após o endereço do elemento anterior. Essa organização é o que permite que o acesso a qualquer índice seja instantâneo.
Para que o acesso continue ocorrendo de forma eficiente, a reindexação evita a criação de um Sparse Array (Array Esparso). Esse tipo de array possui índices vazios, o que faz com que o motor do JavaScript trate o bloco de memória como um objeto comum, perdendo a capacidade de prever onde o próximo dado está guardado, causando uma perda na performance.
Otimizando com objeto
Agora que entendemos as limitações do array quando aplicado a uma fila, vamos entender como criar uma fila baseada em objeto, com o objetivo de atingir uma melhor performance, garantindo uma complexidade de tempo constante O(1) nas operações de enqueue e dequeue.
Implementação com JavaScript
class Queue {
#count;
#lowestCount;
#items;
constructor() {
this.#count = 0;
this.#lowestCount = 0;
this.#items = {};
}
// Adiciona um novo elemento no final da fila
enqueue(element) {
this.#items[this.#count] = element;
this.#count++;
}
// Remove e retorna o primeiro elemento da fila
dequeue() {
if (this.isEmpty())
return undefined;
const result = this.#items[this.#lowestCount];
delete this.#items[this.#lowestCount];
this.#lowestCount++;
return result;
}
// Retorna o primeiro elemento da fila
peek() {
if (this.isEmpty())
return undefined;
return this.#items[this.#lowestCount];
}
// Retorna se a fila está vazia ou não
isEmpty() {
return this.size() === 0;
}
// Retorna a quantidade de elementos na fila
size() {
return this.#count - this.#lowestCount;
}
// Limpa a fila
clear() {
this.#items = {};
this.#count = 0;
this.#lowestCount = 0;
}
}
Implementação com TypeScript
class Queue<T> {
private count: number;
private lowestCount: number;
private items: Record<number, T>;
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {}
}
// Adiciona um novo elemento no final da fila
enqueue(element: T): void {
this.items[this.count] = element;
this.count++;
}
// Remove e retorna o primeiro elemento da fila
dequeue(): T | undefined {
if (this.isEmpty())
return undefined;
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
// Retorna o primeiro elemento da fila
peek(): T | undefined {
if (this.isEmpty())
return undefined;
return this.items[this.lowestCount];
}
// Retorna se a fila está vazia ou não
isEmpty(): boolean {
return this.size() === 0;
}
// Retorna a quantidade de elementos na fila
size(): number {
return this.count - this.lowestCount;
}
// Limpa a fila
clear(): void {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
}
Observe que ao utilizarmos o
Queue<T>, o TypeScript fará a inferência automática. Ou seja, se criarmos uma new Queue(), o método peek() saberá que o retorno é uma string ou undefined, fornecendo o autocomplete corretamente no editor.
Quando não usar
Mais importante do que dominar uma estrutura é saber quando utilizá-la. Pois na programação dificilmente existirá uma solução absoluta, toda escolha deve ser baseada em trade-offs. Em cenários de filas pequenas, o array torna o código mais conciso, fácil de manter, além de provavelmente entregar um desempenho melhor.
O desempenho melhor nesses cenários ocorre porque motores modernos, como o V8 tratam os arrays de uma maneira especial. Eles são armazenados internamente em uma estrutura chamada Elements Store, separada das demais propriedades de objeto para fins de otimização. Quando esses arrays não possuem buracos, eles são classificados como Fast Elements e organizados em categorias como:
- PACKED_SMI_ELEMENTS: Para inteiros pequenos. É o nível de performance mais alto.
- PACKED_DOUBLE_ELEMENTS: Para valores de ponto flutuantes ou inteiros que não pertencem a SMI.
- PACKED_ELEMENTS: Para valores que não encaixam nas categorias acima, como strings e objetos.
Por conta dessa otimização de baixo nível, o custo de instanciar uma classe e gerenciar a remoção de propriedades com delete pode ser maior do que a reindexação de um array pequeno.
Trade-offs: Quando a complexidade vale a pena
Pequena Escala (Arrays): Quando a quantidade de itens na Fila é relativamente pequena, os testes mostram que o array possui uma maior performance. Deixando claro que o custo da reindexação é compensado pelas otimizações de Fast Elements do V8. Neste cenário, o que devemos priorizar é a simplicidade do código.
Alta Carga (Objetos): Aqui o cenário muda drasticamente. Uma fila grande é impactada significativamente pela reindexação, mesmo com a otimização do motor V8, pois o custo acumulativo nesses cenários não é sustentável em larga escala.
Cenário de testes com numbers:
| Itens | Fila com Array | Fila com Objeto |
|---|---|---|
| 1.000 | 0.079ms | 0.215ms |
| 10.000 | 1.377ms | 0.794ms |
| 100.000 | 3.574.7ms (3.5s) | 8.9ms |
| 200.000 | 28.541.7ms (28.5s) | 9.38ms |
Conforme a Fila aumenta, torna-se cada vez mais nítida a diferença de performance, ficando claro a vantagem do uso do objeto em cenários de alta carga.
Confira o código utilizado para obter os valores dos testes realizados em ambiente Node:
// Testa a performance da fila utilizando array
function testArrayPerformance(size) {
const queue = [];
for (let i = 0; i < size; i++)
queue.push(i);
const start = performance.now();
for (let i = 0; i < size; i++)
queue.shift();
const end = performance.now();
const performanceResult = end - start;
return performanceResult;
}
// Testa a performance da fila utilizando objeto
function testObjectPerformance(size) {
const queue = new Queue();
for (let i = 0; i < size; i++)
queue.enqueue(i);
const start = performance.now();
for (let i = 0; i < size; i++)
queue.dequeue();
const end = performance.now();
const performanceResult = end - start;
return performanceResult;
}
// Exibe a média da performance de 5 execuções por padrão
function runBenchmark(label, fn, iterations = 5) {
const results = [];
for (let i = 0; i < iterations; i++) {
results.push(fn());
}
const average = results.reduce((a, b) => a + b) / iterations;
console.log(`${label} - Média de ${iterations} execuções: ${average.toFixed(4)}ms`);
}
// Define a quantidade de itens da fila
const size = 100000;
runBenchmark("Array Queue (shift)", () => testArrayPerformance(size));
runBenchmark("Object Queue (dequeue)", () => testObjectPerformance(size));
Conclusão
Com as implementações apresentadas, mostramos como podemos resolver o gargalo de performance, mas além disso, evidenciamos quando devemos ou não nos preocupar com isso.
Espero que tenha ficado claro não apenas como criar uma fila, mas o porquê de cada escolha técnica por trás dela. Procurar entender o que realmente acontece “debaixo do capô” é um dos fatores que nos diferenciam como programadores.
Referências
GRONER, Loiane. Estruturas de Dados e Algoritmos com JavaScript. 2ª Edição. Novatec Editora Ltda. Fevereiro/2019.
BYNENS, Mathias. Elements kinds in V8. V8 Dev Blog, 2017. Disponível em: https://v8.dev/blog/elements-kinds
BRUNI, Camillo. Fast properties. V8 Dev Blog, 2017. Disponível em: https://v8.dev/blog/fast-properties
Créditos de imagem
Foto de Meizhi Lang na Unsplash
Top comments (0)