Remoção de duplicatas de forma eficiente e com pouca sobrecarga de memória

Desejo filtrar com eficiência uma lista de números inteiros para duplicatas, de maneira que apenas o conjunto resultante precise ser armazenado.

Uma maneira de isso ser visto:

• nós temos um intervalo de números inteiros $S = \{1, \dots{}, N\}$ com$N$ grande (por exemplo,$2^{40}$ )
• temos uma função $f : S \to S$ com, supostamente, muitas colisões (as imagens são distribuídas uniformemente em $S$ )
• então precisamos armazenar , que é { f ( x ) | x ∈ S $f[S]$$\{f(x) | x \in S\}$

Eu tenho uma estimativa bastante precisa (probabilística) do que é e, portanto, pode alocar estruturas de dados com antecedência (digamos | f [ S ] | ≈ 2 30 ).$|f[S]|$$|f[S]| \approx 2^{30}$

Eu tive algumas idéias, mas não tenho certeza qual seria a melhor abordagem:

• um bitset está fora de questão porque o conjunto de entradas não cabe na memória.
• uma tabela de hash, mas (1) requer alguma sobrecarga de memória, digamos 150% de e (2) a tabela deve ser explorada quando criada, o que requer tempo adicional devido à sobrecarga da memória.$|f[S]|$
• uma classificação "on the fly", de preferência com complexidade (classificação sem comparação). Com relação a isso, não tenho certeza de qual é a principal diferença entre a classificação de bucket e o flashsort .$O(N)$
• uma matriz simples com uma árvore de pesquisa binária, mas isso requer tempo .$O(N \log |f[S]|)$
• talvez o uso de filtros Bloom ou uma estrutura de dados semelhante possa ser útil no relaxamento (com falsos positivos) do problema.

Algumas perguntas sobre o stackoverflow parecem abordar esse tipo de coisa ( /programming/12240997/sorting-array-in-on-run-time , /programming/3951547/java -array-find-duplicates ), mas nenhum parece corresponder aos meus requisitos.

Por que não bin e chain?

A idéia é armazenar números inteiros positivos representáveis ​​por bits em uma matriz A de 2 k entradas representando intervalos de valores: entrada A [ y ] , y ≥ 0 , representa o intervalo [ 2 m y , 2 m ( y + 1 ) - 1 ] . Para qualquer 1 ≤ x < 2 n, podemos escrever x = 2 m$n = k+m$$A$$2^k$$A[y]$$y \ge 0$$[2^m y, 2^m(y+1)-1]$$1 \le x \lt 2^n$ onde y possui k bits e z possui m bits. Tente armazenar z (não x !) No local y :$x = 2^m y + z$$y$$k$$z$$m$$z$$x$$y$

• Quando já, não faça nada: x é uma duplicata.$A[y]=z$$x$

• Quando não for inicializado, armazene z em A [ y ] .$A[y]$$z$$A[y]$

• Caso contrário, armazene um índice em uma matriz separada usada para encadear os (que colidiram em y ) nas listas vinculadas. Você terá que pesquisar linearmente a lista encabeçada por A [ y ] e, dependendo do que a pesquisa descobrir, potencialmente inserir z na lista.$z$$y$$A[y]$$z$

No final, é fácil recuperar fazendo um loop pelas entradas inicializadas de A e - apenas concatenando duas seqüências de bits - remontando cada z encontrado no local y (diretamente ou dentro de uma cadeia referenciada) no original valor x = 2 m y + z .$f(S)$$A$$z$$y$$x = 2^m y + z$

Quando a distribuição é quase uniforme e excede N , não haverá muito encadeamento (isso pode ser avaliado da maneira usual) e as cadeias tendem a ser curtas. Quando a distribuição não é uniforme, o algoritmo ainda funciona, mas pode atingir o tempo quadrático. Se for possível, use algo mais eficiente do que cadeias (e pague um pouco mais pelo armazenamento).$2^k$$N$

O armazenamento necessário é de no máximo bits para A e 2 2 k bits para as cadeias (assumindo m ≤ k ). Este é exatamente o espaço necessário para armazenar 2 k valores de n bits cada. Se você está confiante na uniformidade, pode subalocar o armazenamento para as cadeias. Se a não uniformidade for uma possibilidade, convém aumentar k e defender totalmente o armazenamento em cadeia.$2^n$$A$$2^{2k}$$m \le k$$2^k$$n$$k$

Uma forma alternativa de pensar acerca desta solução é que ela é uma tabela hash com uma função hash particularmente agradável (tomar a bits mais significativos) e, por causa disso, precisamos apenas de armazenar os menos significativos m = n - k bits a mesa.$k$$m=n-k$

Existem maneiras de sobrepor o armazenamento das cadeias com o armazenamento de mas isso não parece incomodar, porque não economizaria muito (supondo que m seja muito menor que k ) de espaço e dificultaria o desenvolvimento do código, depurar e manter.$A$$m$$k$