c++ - para - Dado un conjunto de datos de 1 TB en el disco con alrededor de 1 KB por registro de datos, ¿cómo puedo encontrar duplicados con 512 MB de RAM y espacio en disco infinito?

memoria virtual recomendada para 4gb ram windows 10 (8)

Cargue los datos en la memoria 512M a la vez, luego clasifique ese fragmento y escríbalo en el disco (como su propio archivo). Una vez que todo el 1T se ha realizado de esta manera, combine los archivos individuales en un gran archivo honkin '', luego lea ese archivo grande (ordenado) secuencialmente, y escríbalo en el archivo final mientras elimina los registros duplicados.

1T, 512M a la vez, serán aproximadamente 2,1 millones de archivos (suponiendo las definiciones binarias de unidades SI en lugar de decimal). 512M de registros 1K solo permitirán 524,288 registros en la memoria a la vez, por lo que probablemente tendrá que hacer la fusión en dos etapas. En otras palabras, combine-clasifique los 2,1 millones de archivos en cuatro grupos para crear cuatro archivos más grandes, luego combine-clasifique esos cuatro en el gran archivo ordenado. Entonces ese es el proceso que procesa secuencialmente para eliminar duplicados.

Un merge-sort simplemente combina varios archivos ya ordenados simplemente seleccionando el primer registro restante de cada archivo y eligiendo el "más bajo". Por ejemplo, los dos archivos a y b :

a b 7 6 3 5 1 4 2 /_/ 1 (a) 2 (b) 3 (a) 4 (b) 5 (b) 6 (b) 7 (a)

Hay 1 TB de datos en un disco con alrededor de 1 KB por registro de datos. ¿Cómo puedo encontrar duplicados usando 512 MB de RAM y espacio en disco infinito?

Encuentre una función hash adecuada y haga un hash de cada registro, almacenando la lista de hash con índices en un archivo. Ahora ordena el archivo hash mediante hash. Finalmente, verifique los registros completos de hashes coincidentes para duplicados reales.

Por supuesto, depende de cuántos duplicados esperas encontrar y qué vas a hacer con la información después.

Genera un hash de cada registro; grabe el número de registro y el hash en la memoria, derrame al archivo cuando sea necesario (clasifique los datos en orden de almohadilla antes de escribir en el archivo). A medida que se le ocurra un nuevo hash, verifique si ya existe en la memoria, es una detección temprana. (Eso puede o no ser un beneficio importante).

Cuando haya leído todos los datos, tendrá varios archivos de hashes más números de registro, ya ordenados. Combina estos archivos, detecta los duplicados sobre la marcha. Ni siquiera necesita hacer más que registrar los duplicados para esta aplicación, por lo que puede descartar los hashes una vez que se demuestre que son únicos.

Dados los tamaños: 0,5 GB de memoria, 1000 GB de datos, 1 KB por registro, alrededor de mil millones de registros, suponiendo que un hash de 256 bits (aunque 128 bits bien podría ser adecuado), estaríamos usando 32 bytes para el hash. y 4 bytes para el número de registro, y alrededor de 1 mil millones de registros, necesitamos alrededor de 36 GB para los archivos de ordenamiento, generados en archivos de 500 MB (correspondientes a la memoria disponible), por lo que habría 70-80 archivos para fusionar en el final, que parece bastante manejable. La lista le daría los números de registro, entonces tendría que acceder al archivo de 1 TB para leer los registros. Debe pensar qué va a hacer con los duplicados; ¿necesita la información sobre el registro inicial y los extras, y si importa cuál de los duplicados guarda y cuáles rechaza? Etc.

Las soluciones ofrecidas hasta ahora parecen demasiado complicadas. Un filtro Bloom , aunque es la estructura de datos du jour de los últimos años, no se aplica mejor en una situación como esta: dado que no se pueden asociar datos con el contenido hash, no solo debe mantener el filtro Bloom, sino que todavía debe registrar cada valor hash (¡solo 6 bits!) y grabar en el disco, destruyendo el beneficio del filtro bloom y teniendo una tasa de colisión absurdamente alta.

Por otro lado, fusionar la ordenación de todo el terabyte no solo tomará comparaciones O(n log n) , sino O(n log n) tráfico de disco, ya que la mayoría de los archivos intermedios tendrían que fusionarse desde el disco, en lugar de que de la memoria. Cualquier solución real debería intentar reducir el tráfico de disco tanto como sea posible, ya que ese es nuestro principal cuello de botella.

Mi solución es simple, haciendo una suposición: que el terabyte de datos se registra en lo que es efectivamente un archivo.

Itere a través de los registros del archivo de terabyte y cópielos. Un hash criptográfico es innecesario, costoso y demasiado grande aquí; en su lugar, use algo como la versión de 64 bits de murmurhash . Puede procesar hash más de 2 GiB / seg (mucho más rápido de lo que probablemente necesitemos, dada la velocidad de almacenamiento en estos días) y tiene una excelente (aunque no criptográficamente segura) resistencia a la colisión. Con un hash de 64 bits, esperaríamos nuestra primera colisión a 2 ^ 32 , por lo que es probable que nuestros aproximadamente mil millones de registros no tengan ninguna colisión.

Escriba los hashes y sus compensaciones de registros asociadas en otro archivo. Dado que los registros contienen datos binarios arbitrarios, no podemos confiar en el género (1) de Unix para ordenarlo, porque algunos de los hash y offsets pueden contener lo que el género (1) interpretará como líneas nuevas. Simplemente escribiremos los registros como de ancho fijo (probablemente 16 bytes: 8 bytes para el murmur2 hash de 64 bits y 8 bytes para el offset en el archivo de terabyte). El archivo resultante debe ser de aproximadamente 16 GB, dada nuestra cantidad de registros.

Podemos ordenar este archivo leyendo el número de registros que encajarán de forma segura en la memoria y ordenándolos, volviendo a tirar los trozos clasificados al disco. Podemos incluir más registros en la memoria con un heapsort (usa O(1) espacio) que con un quicksort (que usa la memoria O(log n) para la pila de llamadas), pero en la mayoría de las implementaciones, quicksort gana en virtud de su memoria localidad y menor cantidad de instrucciones. Estos archivos intermedios (debe haber 35-40 de ellos) se escribirán en el disco.

El último paso es fusionar estos archivos (en la memoria, no es necesario almacenar un resultado en el disco para esto) recopilar todas las colisiones hash y buscar los registros asociados en el archivo de terabyte, comparar los registros para la duplicación y emitir los registros (o sus compensaciones) de cualquier forma que el problema especifique.

Por lo que puedo decir, esta tarea golpea el disco significativamente menos que cualquier otra solución ofrecida, y es muy simple desde el punto de vista conceptual: hash los registros, busca duplicados en los hash y verifica en los registros reales.

Para I/O disco, leería el archivo de datos de terabytes, escribiría 16 GB en el disco, leería esos 16 GB del disco y lo escribiría de nuevo, lo leería y devolvería los duplicados. Como optimización, el proceso de hash de los registros podría acumularlos en la memoria antes de eliminarlos en el disco, ordenándolos antes: eso corta el archivo intermedio de 16 GB y permite que el proceso pase del hash directamente a la fusión e informe de duplicados .

Primero, configure la computadora con un archivo de intercambio infinitamente grande en una unidad infinitamente grande ...

Puede usar un hash para reducir el tamaño del problema. Por ejemplo, si tiene 1 TB de datos, entonces define una función hash y los datos se dividen en diez archivos (el tamaño de cada archivo es inferior a 1 TB). Después de eso, si un archivo aún es demasiado grande, repita el procedimiento hasta que el archivo se pueda almacenar en la memoria. Finalmente, puede contar los tiempos de aparición por tipo.

Son muchos récords ;-) del orden de 1,000,000,000. Sería mejor ser inteligente al respecto ...

La naturaleza de los registros no está especificada: ¿los descubrimos, uno a la vez, leyéndolos secuencialmente, o hay algún tipo de índice, o tal vez están almacenados como archivos en varios directorios? También no especificado en la pregunta está la disponibilidad de un dbms que podemos usar para datos tipo índice (en lugar de tener que ordenarlo con nuestro propio código). También una idea [incluso aproximada] del número de duplicados ayudaría a dirigir algunas de las opciones hacia un proceso eficiente.

Si no existe un índice, podemos / debemos crear uno; esto podría hacerse como el primer pase a través de los datos. El mismo pase se usaría para producir un resumen del mensaje (un hash) de géneros para cada registro (o posiblemente, para fines de eficiencia, para los primeros cientos de bytes del registro).

La idea general es producir rápidamente un índice que pueda usarse para identificar posibles duplicados y finalizar la lista de duplicados reales, posiblemente a través de un procesamiento paralelo .

La información útil en el índice sería:

longitud del registro
primeros bytes del texto
código hash (más sobre esto más abajo)
también el desplazamiento en el archivo o el puntero a los datos pero, por supuesto, a diferencia de los 3 elementos anteriores, esto no se puede utilizar para identificar posibles coincidencias.

La elección del hash es crítica: debería favorecer un algoritmo rápido a expensas de uno que esté perfectamente distribuido; el número de octetos de bytes para cada registro también es un compromiso, tal vez 100 a 200 bytes (es decir, alrededor del 10 al 20% del tamaño promedio del registro) es un buen valor, dependiendo de la proporción esperada de duplicados, y dependiendo del ahorro de tiempo esto proporciona (en comparación con hashing todo el registro). (ver edición abajo)

Una vez que dicho índice está disponible, podemos [relativamente rápido / sin esfuerzo] obtener un recuento de posibles duplicados; en base a este resultado, se puede hacer una segunda aprobación para mejorar la calidad del índice, si no se considera lo suficientemente selectivo (omitiendo los registros que se consideran únicos). Este segundo paso puede calcular otro hash, en todo el registro (excluyendo los primeros x bytes del primer hash), o en otro subconjunto más del registro. Tenga en cuenta que gracias al índice, este segundo pase puede ser multihebra si es posible.

El segundo o último pase requiere ordenar los registros dentro de un grupo de posibles coincidencias (misma longitud, mismos códigos hash (s), mismos primeros x bytes). Esto se puede lograr como describe Pax Diablo, la ventaja del índice es que dicha operación puede, de nuevo, tener múltiples subprocesos e involucrar conjuntos mucho más pequeños (muchos de ellos). Agregado : Nuevamente, Nick Johnson señala que el segundo paso podría ser innecesario si usáramos un código hash largo (sugiere 128 bytes de longitud SHA1). Suponiendo que no hay ganancia en el hashing parcial de los registros, esta es una solución muy plausible ya que el índice podría residir en el disco y aún así ser ordenado y almacenado más rápidamente que si estuviéramos clasificando / almacenando los registros completos.

Editar : Nick Johnson señala que la latencia de las búsquedas en el almacenamiento en disco puede ser tal que una lectura secuencial simple sea más rápida y que el cuello de botella sea un límite de E / S de disco, una función de hash rápida simultánea puede ser más rápida que la secuencia secuencial leer, y por lo tanto no agregar al proceso general. Esta es una posible posibilidad (especialmente si se requiere una lectura secuencial para detectar cada inicio / fin de registro, etc.), y es por eso que "superé mi apuesta" escribiendo " dependiendo del ahorro de tiempo que esto proporciona ...". Esto dice que la estructura real de los registros en el disco es uno de los parámetros abiertos de la pregunta (por ejemplo, si solo estamos leyendo archivos individuales en directorios, imponiendo una lectura no secuencial) y también es probable que haya un almacenamiento de tamaño TeraByte respaldado por un elegante RAID donde latencia de búsqueda sin dejar de ser una preocupación suele mejorar mucho.
Estoy de acuerdo con mi sugerencia de que un enfoque de dos pasos puede ser más eficiente que uno en el que cada registro está completamente codificado, pero me gustaría haber subrayado la posibilidad y los beneficios del enfoque de un solo pase. Al igual que con muchas preguntas de entrevistas, varias características de la situación en cuestión no se especificaron; la idea no es tanto ver al solicitante proporcionar la respuesta correcta absoluta (¡aunque algunas respuestas pueden ser bastante incorrectas!) sino más bien obtener una idea de su proceso de pensamiento y la capacidad de identificar opciones y puntos de decisión.

Use un filtro Bloom : una tabla de hashes simultáneos. Según Wikipedia, el número óptimo de hashes es ln(2) * 2^32 / 2^30 ≈ 2.77 ≈ 3 . (Hmm, conectar 4 da menos falsos positivos pero 3 es aún mejor para esta aplicación). Esto significa que tienes una tabla de 512 megabytes, o 4 gigabits, y procesar cada registro establece tres nuevos bits en ese vasto mar. Si los tres bits ya estaban configurados, es una coincidencia potencial. Registre los tres valores de hash en un archivo. De lo contrario, regístrelos en otro archivo. Tenga en cuenta el índice de registro junto con cada coincidencia.

(Si se tolera una tasa de error del 5%, omita el archivo grande y use el archivo pequeño como resultados).

Cuando haya terminado, debe tener un archivo de aproximadamente 49 millones de posibles coincidencias positivas y un archivo de 975 millones de negativos que pueden coincidir con positivos. Lea el primero en un vector<pair<vector<uint32_t>,vector<uint32_t> > > (índices en el último vector , el primero puede ser una array ) y ordénelo. Coloque los índices en otro vector<uint32_t> ; ellos ya están ordenados Lea el archivo grande, pero en lugar de establecer bits en una tabla, busque los valores hash en el vector . (Por ejemplo, use equal_range .) Use la lista de índices de archivos positivos para rastrear el índice del registro actual en el archivo negativo. Si no se encuentra ninguna coincidencia, ignore. De lo contrario, agregue el índice del registro match->second.push_back(current_negative_record_index) .

Finalmente, itere a través del mapa y los vectores de los índices de registro. Cualquier contenedor con más de una entrada es "casi" cierto que contiene un conjunto de duplicados, pero has llegado hasta aquí, así que búscalos y compáralos por completo para estar seguro.

E / S de disco síncrono total: (una pasada = 1 TiB) + (96 bits de hash por registro = 12 GiB) + (32 bits de índice por positivo = ~ 200 MiB).

Edición final (en serio): Pensándolo bien, el aspecto del Filtro Bloom podría no estar ayudando aquí. La cantidad de datos hash es más un factor limitante que la cantidad de falsos positivos. Con solo una función hash, la cantidad total de datos hash sería 4 GiB y los índices de los 124 millones de falsos positivos esperados serían ~ 500 MiB. Eso debería optimizar globalmente esta estrategia.

Aclaración (obtuvo un voto a la baja): hay una distinción entre un falso positivo del filtro Bloom y una colisión hash. Una colisión hash no se puede resolver, excepto volviendo a los registros originales y comparando, lo cual es costoso. Un falso positivo Bloom puede resolverse volviendo a los valores hash originales y comparándolos, que es lo que hace el segundo pase de este algoritmo. Pensándolo bien, el filtro de un solo hash descrito en la edición "final" causaría indebidamente búsquedas en el disco. Un filtro Bloom de dos hash aumentaría el número de falsos positivos que terminan en un solo cubo del mapa de match , y reduciría el número de falsos positivos a decenas de millones.