Uma implementação autotracked de uma fila dupla, implementada como um buffer de anel apoiado por um nativo Matriz JavaScript, com desempenho ideal para todas as operações comuns:
- O(1) empurrar e pop de qualquer extremidade da fila;
- O(1) ler de qualquer elemento na fila;
- O(N) iteração de toda a fila;
- O(N) acesso a qualquer intervalo de tamanho N dentro da fila;
- O(N+X) armazenamento para uma fila de tamanho N, com X uma sobrecarga fixa na ordem de algumas dezenas de bytes:
- armazenamento de apoio de tamanho
N; - um único valor de capacidade;
- dois ponteiros para o armazenamento, com o custo adicional de uma "tag" Glimmer para cada um deles.
- armazenamento de apoio de tamanho
Isso é útil para casos em que você precisa ser capaz de empurrar e retirar itens de qualquer extremidade de uma fila de tamanho fixo, especialmente onde você deseja ter leituras rápidas de qualquer lugar na fila.
Por exemplo, se você tiver um fluxo de eventos vindo de uma conexão websocket, que você deseja exibir para um usuário, mas você deseja manter apenas 1.000 deles na memória a qualquer momento, isso permite que você simplesmente envie para o volta da fila à medida que novos itens chegam, sem a necessidade de gerenciar manualmente a frente da fila para manter o tamanho da fila.
Crie uma fila de uma capacidade especificada e, em seguida, envie itens para ela a partir de matrizes existentes ou valores individuais:
//Crie uma fila com capacidade 5, a partir de uma matriz existente de elementos:
import TrackedQueue from 'tracked-queue';
let queue = new TrackedQueue<string>({ capacity: 5 });
queue.append(['alpha', 'bravo', 'charlie']);
console.log(queue.size); // 3
console.log([...queue]); // ["alpha", "bravo", "charlie"]
queue.pushBack('delta');
console.log(queue.size); // 4
console.log([...queue]); // ["alpha", "bravo", "charlie", "delta"]Se você adicionar mais elementos no final da fila, excedendo sua capacidade, ele será descartado na frente da fila, com o 'tamanho' da fila nunca excedendo sua capacidade especificada, e quaisquer itens removidos para liberar espaço serão retornados. (O mesmo vale para prepend, na frente da fila.)
let pushedOut = queue.append(["echo", "foxtrot");
console.log(queue.size); // 5
console.log([...queue]); // ["bravo", "charlie", "delta", "echo", "foxtrot"]
console.log(pushedOut); // ["alpha"]Você também pode adicionar e remover itens de qualquer extremidade da fila:
let poppedFromBack = queue.popBack();
console.log(poppedFromBack); // "foxtrot"
console.log([...queue]); // ["bravo", "charlie", "delta", "echo"]
let poppedFromFront = queue.popFront();
console.log(poppedFromFront); // "bravo"
console.log([...queue]); // ["charlie", "delta", "echo"]
queue.pushBack('golf');
queue.pushFront('hotel');
console.log([...queue]); // ["hotel", "charlie", "delta", "echo", "golf"]Estes também retornam um valor que teve que ser removido para abrir espaço para eles, se houver:
let poppedByPush = queue.pushBack('india');
console.log([...queue]); // ["charlie", "delta", "echo", "golf", "india"]
console.log(poppedByPush); // "hotel"
// tornar a fila não vazia
queue.popFront();
let nothingPopped = queue.pushFront('juliet');
console.log([...queue]); // ["juliet", "delta", "echo", "golf", "india"]
console.log(poppedByPush); // undefined- Ember.js v3.16 or above
- Ember CLI v2.13 or above
- Node.js v12 or above
Este projeto segue o rascunho atual da especificação Semantic Versioning for TypeScript Types.
- Versões do TypeScript atualmente suportadas: v4.4, v4.5, e v4.6
- Compiler support policy: simple majors
- Public API: all published types not in a
-privatemodule are public
Este projeto usa Proxy nativo (através de uma dependência) e, portanto, não é compatível com o IE11. Ele suporta N-1 para todos os outros navegadores.
-
Com npm:
npm install tracked-queue
-
With yarn:
yarn add tracked-queue
-
With ember-cli:
ember install tracked-queue
- Consulte docs/API.md para obter a documentação completa da API.
- Consulte docs/under-the-hood.md para obter detalhes sobre como a fila funciona.
O "aplicativo fictício" inclui duas demonstrações de desempenho, que você pode ver executando ember serve e navegando até http://localhost:4200:
-
A render performance demo showing that the queue implementation itself is never the bottleneck for performance; the cost of rendering DOM elements is.
-
Uma demonstração de desempenho operacional, que permite ver o comportamento de push e popping para frente e para trás da fila. (Esta é uma medição ingênua usando [a API
Performance] perf-api.) Algumas coisas a serem observadas:-
Quando a capacidade da fila é muito maior do que o número de itens empurrados para dentro ou para fora dela, o desempenho de
pushBackepopBackda parte de trás da fila é comparável às ações push e pop do array nativo, porque é apenas essas operações mais o aumento do índice para o "back" da fila -
Quando o número de itens empurrados excede a capacidade da fila, fazendo com que a fila “quebre”, os tempos de inserção
pushBackepopBackcaem para cerca de 100 × pior que nativos, mas o uso do espaço é limitado:pushepop nativossão rápidos porque permitem que o buffer cresça de forma ilimitada. Esta é a compensação fundamental de um buffer de anel: ele fornece controle sobre o uso do espaço em troca de custos ligeiramente mais altos para push e pop no final da fila -
O desempenho do
pushFronte dopopFronté cerca de 10 vezes pior do que ounshifte oshiftnativos até um limite (que varia por navegador), ponto em que o desempenho dos métodos nativos se torna centenas de vezes pior e degrada rapidamente, a ponto depushFrontepopFronttravar uma guia do navegador ao lidar com muito mais do que cerca de 100.000 operações, à medida que o redimensionamento do array e a movimentação de itens crescem de forma ilimitada. Enquanto isso,pushFrontepopFronttêm características de desempenho consistentes, não importa o tamanho da fila. You can see these dynamics clearly by varying the number of operations to perform and the size of the queue.
-
Consulte o guia Contribuir para obter detalhes.
Este projeto está licenciado sob a Licença BSD 2-Clause.