Un archivo contiene un gran número (por ejemplo, 10 mil millones) de cadenas y necesita encontrar cadenas duplicadas. Tienes N cantidad de sistemas disponibles. Cómo encontrará los duplicadosBuscar cadenas duplicadas en un archivo grande
Divida el archivo en N piezas. En cada máquina, cargue la mayor parte de la pieza en la memoria que pueda y ordene las cuerdas. Escriba estos fragmentos para el almacenamiento masivo en esa máquina. En cada máquina, combine los fragmentos en una única secuencia y luego fusione la secuencia de cada máquina en una secuencia que contenga todas las cadenas en orden ordenado. Compara cada cuerda con la anterior. Si son iguales, es un duplicado.
Para fusionar los fragmentos en una única secuencia, debería cargar todos los registros en la memoria. Para un archivo de registro de 1 mil, todos los registros de 1 mil deberían estar en la memoria en el último paso de fusión en el algoritmo anterior, ¿verdad? Si es así, entonces eso frustra el propósito. –
@AndyDufresne "Para fusionar los fragmentos en una única secuencia, tendría que cargar todos los registros en la memoria". No, no lo harías Solo necesita suficiente memoria para cargar la siguiente secuencia de cada fragmento a la vez, para poder compararlos. Una vez que se haya realizado la comparación, la siguiente cadena ocupará ese espacio de memoria. – erickson
No entendí tu algoritmo de fusión. Supongamos que tenemos un archivo de registro de 1 mil y solo se pueden cargar 5k registros en la memoria. Por lo que entendí, primero necesito dividir el archivo en N piezas con 5K registros cada una. Luego, clasifique todos los registros en cada archivo de 5k registros y vuelva a escribir. Para unir dos archivos de registro de 5k, tendría que cargar 10k registros en memoria ¿verdad? Si esto no es lo que quiso decir, puede explicar los pasos para buscar registros duplicados en un archivo de registro de 1 mil con el límite de memoria de cargar solo 5k registros. –
La respuesta de erickson es probablemente la esperada por quien haya planteado esta pregunta.
Se puede usar cada una de las N máquinas como un cubo en una tabla hash:
Para ser honesto, sin embargo, para 10 mil millones de cadenas, podría hacerlo en una PC. La tabla hash puede ocupar algo así como 80-120 GB con un hash de 32 bits, dependiendo de la implementación exacta de hashtable. Si está buscando una solución eficiente, tiene que ser un poco más específico a lo que quiere decir con "máquina", ya que depende de cuánto espacio tiene cada uno y el costo relativo de la comunicación de red.
¿Es esta tarea? Esto suena como tarea. – SoapBox