Uma estrutura de dados que suporta O (1) access random e o pior caso O (1) anexado?

Eu percebo uma coleção indexável redimensionável que usa uma matriz para armazenar seus elementos (como List no .NET ou ArrayList em Java) amortizou O (1) tempo de inserção no final da coleção. Mas há sempre uma inserção incômoda em conjunturas críticas em que a coleção acaba de atingir sua capacidade e a próxima inserção exige uma cópia completa de todos os elementos da matriz interna para uma nova (presumivelmente duas vezes maior).

Um erro comum (na minha opinião) é ir com uma lista ligada para “corrigir” este problema; mas acredito que a sobrecarga de alocação de um nó para cada elemento pode ser um grande desperdício e de fato minimizaria o benefício de uma inserção garantida O (1) nesse caso raro em que a inserção da matriz é cara – quando, de fato, todos os outros A inserção de matrizes é significativamente mais barata (e mais rápida).

O que eu estava pensando pode fazer sentido é uma abordagem híbrida que consiste em uma lista encadeada de arrays, onde toda vez que o array “head” atual atinge sua capacidade, um novo array duas vezes maior é adicionado à lista encadeada. Então, nenhuma cópia seria necessária, pois a linked list ainda teria o array original. Essencialmente, isso parece análogo (para mim) à abordagem List ou ArrayList , exceto que onde quer que você tenha incorrido anteriormente no custo de copiar todos os elementos da matriz interna, aqui você só incorre no custo de alocar uma nova matriz. mais uma inserção de nó único.

Evidentemente, isso complicaria outros resources se eles fossem desejados (por exemplo, inserir / remover em / do meio da coleção); mas como eu expressei no título, estou realmente apenas procurando por uma coleção de add-only (e iterativa).

Existem estruturas de dados idealmente adequadas para esse fim? Ou você pode pensar em um você mesmo?

Existe uma estrutura bonita chamada matriz extensível que tem a inserção O (1) do pior caso e sobrecarga de memory O (n) (ou seja, é assintoticamente comparável a um array dynamic, mas tem a inserção de pior caso O (1)). O truque é usar a abordagem que o vetor usa – duplicar e copiar -, mas tornar a cópia mais preguiçosa. Por exemplo, suponha que você tenha uma matriz de quatro elementos como este:

 [1] [2] [3] [4] 

Se você quiser adicionar um novo número, digamos 5, comece alocando uma matriz duas vezes maior:

 [1] [2] [3] [4] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 

Em seguida, insira 5 no novo array:

 [1] [2] [3] [4] [ ] [ ] [ ] [ ] [5] [ ] [ ] [ ] 

Finalmente, puxe o 4 da matriz antiga para o novo:

 [1] [2] [3] [ ] [ ] [ ] [ ] [4] [5] [ ] [ ] [ ] 

De agora em diante, sempre que você fizer uma inserção, adicione o elemento à nova matriz e puxe para baixo mais um elemento da matriz antiga. Por exemplo, depois de adicionar 6, teríamos

 [1] [2] [ ] [ ] [ ] [ ] [3] [4] [5] [6] [ ] [ ] 

Depois de inserir mais dois valores, acabamos aqui:

 [ ] [ ] [ ] [ ] [1] [2] [3] [4] [5] [6] [7] [8] 

Se agora precisarmos adicionar mais um elemento, descartamos o array antigo agora vazio e alocamos um array duas vezes maior que o array atual (capaz de conter 16 elementos):

 [1] [2] [3] [4] [5] [6] [7] [8] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] 

E repita esse processo. Descontando o custo de uma alocação de memory (que geralmente é sublinear no tamanho da matriz), você faz no máximo O (1) trabalho por inserção.

Pesquisas ainda são O (1), uma vez que você apenas decide qual das duas matrizes procurar, enquanto as inserções no meio são O (n) por causa do embaralhamento.

Se você está curioso, eu tenho uma implementação Java dessa estrutura no meu site pessoal. Eu não sei o quão útil você vai encontrá-lo, mas você é mais do que bem-vindo para experimentá-lo.

Espero que isto ajude!

EDIT : Se você quiser investir um pouco de tempo lendo sobre um trabalho de pesquisa e tentando implementar uma estrutura de dados bastante complexa, você pode obter o mesmo resultado (pior caso O (1) acrescentar) em O (√n) sobrecarga de espaço (que é comprovadamente ótimo, a propósito) usando as idéias deste artigo. Eu nunca cheguei a realmente implementar isso, mas certamente vale a pena ler se a memory é um recurso super-escasso. Curiosamente, ele usa essa construção acima como uma sub-rotina!

Quando eu preciso de um contêiner como esse, eu uso minha implementação da estrutura descrita em “Matrizes Resizeable em Tempo e Espaço Ótimos”

ESTÁ BEM. O que você descreveu é quase exatamente o que o std :: deque está na biblioteca padrão do C ++. A diferença é que uma matriz (geralmente) é usada para manter os pointers para as sub-matrizes em vez de usar uma linked list.

Uma ideia seria criar uma lista de alguns elementos, como:

 struct item { int data[NUM_ITEMS]; item *next; } 

Neste caso, a inserção levaria O(1) e se você atingisse o limite, basta criar um novo bloco e anexá-lo ao final de sua lista.