Eliminar duplicados de manera eficiente y con poca carga de memoria

Quiero filtrar eficientemente una lista de enteros para duplicados de una manera que solo el conjunto resultante necesite ser almacenado.

Una forma de ver esto:

• tenemos un rango de enteros con N grande (digamos 2 40 )$S = \{1, \dots{}, N\}$$N$$2^{40}$
• tenemos una función con, supuestamente, muchas colisiones (las imágenes se distribuyen uniformemente en S )$f : S \to S$$S$
• entonces necesitamos almacenar , es decir { f ( x ) | x ∈ S $f[S]$$\{f(x) | x \in S\}$

Tengo una estimación bastante precisa (probabilística) de lo que es, y por lo tanto puede asignar estructuras de datos de antemano (digamos | f [ S ] | ≈ 2 30 ).$|f[S]|$$|f[S]| \approx 2^{30}$

He tenido algunas ideas, pero no estoy seguro de cuál sería el mejor enfoque:

• un conjunto de bits está fuera de discusión porque el conjunto de entrada no cabe en la memoria.
• una tabla hash, pero (1) requiere algo de sobrecarga de memoria, digamos 150% de y (2) la tabla debe explorarse cuando se construye, lo que requiere tiempo adicional debido a la sobrecarga de memoria.$|f[S]|$
• una clasificación "sobre la marcha", preferiblemente con complejidad (clasificación no comparativa). Con respecto a eso, no estoy seguro de cuál es la principal diferencia entre la clasificación de cubetas y la clasificación rápida .$O(N)$
• una matriz simple con un árbol de búsqueda binario, pero esto requiere tiempo .$O(N \log |f[S]|)$
• quizás usar filtros Bloom o una estructura de datos similar podría ser útil para relajar (con falsos positivos) el problema.

Algunas preguntas sobre stackoverflow parecen abordar este tipo de cosas ( /programming/12240997/sorting-array-in-on-run-time , /programming/3951547/java -array-find-duplicates ), pero ninguno parece coincidir con mis requisitos.

¿Por qué no bin y cadena?

La idea es almacenar enteros positivos representables por bits en una matriz A de 2 k entradas que representan rangos de valores: la entrada A [ y ] , y ≥ 0 , representa el rango [ 2 m y , 2 m ( y + 1 ) - 1 ] . Para cualquier 1 ≤ x < 2 n podemos escribir 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$ donde y tiene k bits y z tiene m bits. Intente almacenar z (¡no x !) En la ubicación y :$x = 2^m y + z$$y$$k$$z$$m$$z$$x$$y$

• Cuando ya, no haga nada: x es un duplicado.$A[y]=z$$x$

• Cuando no está inicializado, almacene z en A [ y ] .$A[y]$$z$$A[y]$

• De lo contrario, almacene un índice en una matriz separada utilizada para encadenar las '(que han colisionado en y ) en listas vinculadas. Tendrá que buscar linealmente a través de la lista encabezada por A [ y ] y, según lo que descubra la búsqueda, potencialmente insertar z en la lista.$z$$y$$A[y]$$z$

Al final, $f(S)$ es fácil de recuperar haciendo un bucle a través de las entradas inicializadas de y, simplemente concatenando dos cadenas de bits, reensamblando cada z encontrado en la ubicación y (ya sea directamente o dentro de una cadena referenciada allí) en el original valor x = 2 m y + z .$A$$z$$y$$x = 2^m y + z$

Cuando la distribución es cercana al uniforme y excede N , no habrá mucho encadenamiento (esto puede evaluarse de la manera habitual) y las cadenas tenderán a ser cortas. Cuando la distribución no es uniforme, el algoritmo aún funciona, pero puede alcanzar el tiempo cuadrático. Si es una posibilidad, use algo más eficiente que las cadenas (y pague un poco de gastos generales por el almacenamiento).$2^k$$N$

El almacenamiento necesario es como máximo bits para A y 2 2 $2^n$$A$$2^{2k}$ bits para las cadenas (suponiendo que ). Este es exactamente el espacio necesario para almacenar 2 k valores de n bits cada uno. Si confía en la uniformidad, puede subasignar el almacenamiento de las cadenas. Si la no uniformidad es una posibilidad, es posible que desee aumentar k y defender plenamente el almacenamiento en cadena.$m \le k$$2^k$$n$$k$

Una forma alternativa de pensar acerca de esta solución es que es una tabla hash con una función hash particularmente agradable (tome los bits más significativos) y, por eso, solo necesitamos almacenar los bits menos significativos m = n - k en la mesa.$k$$m=n-k$

Hay formas de superponer el almacenamiento para las cadenas con el almacenamiento para pero no parece que valga la pena, porque no ahorraría mucho espacio (suponiendo que m es mucho más pequeño que k ) y haría que el código sea más difícil de desarrollar, depurar y mantener.$A$$m$$k$