Hay dos matrices de enteros, cada una en archivos muy grandes (el tamaño de cada uno es mayor que la RAM). ¿Cómo encontraría los elementos comunes en las matrices en tiempo lineal?Encontrar elementos comunes de dos matrices muy grandes
No puedo encontrar una solución decente a este problema. ¿Algunas ideas?
Un pase en un archivo crea un mapa de bits (o Bloom filter si el rango entero es demasiado grande para un mapa de bits en la memoria).
Una pasada en el otro archivo, encuentre los duplicados (o candidatos si usa un filtro Bloom).
Si utiliza un filtro Bloom, el resultado es probabilístico. Los nuevos pases pueden reducir el falso positivo (los filtros Bloom no tienen falso negativo).
bien. Tendré que leer acerca de los filtros de floración ahora. basura: P –
Para enteros de 4 bytes, no necesita un filtro Bloom, solo 0.5Gbytes de memoria. – AProgrammer
eso es dooable, supongo. suena como una buena solución. Gracias. –
Obviamente, puede utilizar una tabla hash para encontrar elementos comunes con O (n) la complejidad del tiempo.
En primer lugar, debe crear una tabla hash utilizando la primera matriz y luego comparar la segunda matriz con esta tabla hash.
El tamaño de la lista es MAYOR que la RAM ... su hashtable no mantendrá ninguna matriz completamente ..:/ –
por supuesto, tendría que implementar hash basado en archivos. – CashCow
por favor, elabore ... lo que quiere decir –
Suponiendo que está hablando de números enteros del mismo tamaño, y está escrito en los archivos en modo binario, primero clasifique los 2 archivos (use un quicksort, pero lea y escriba en el archivo "offsets"). Luego solo tiene que moverse desde el inicio de los 2 archivos, y buscar coincidencias; si tiene una coincidencia, escriba la salida en otro archivo (suponiendo que no puede almacenar el resultado en la memoria) y continúe moviéndose en los archivos hasta EOF.
La clasificación no es O (n) como se requiere. –
La ordenación de enteros de tamaño fijo es en realidad O (n): ordenación de radix. Pero manejar archivos más grandes que la memoria puede ser un problema. – blaze
Ordenar archivos. Con enteros de longitud fija se puede hacer en tiempo O (n):
En los archivos ordenados, busque un subconjunto común de enteros: compare los números, anótelos si son iguales, luego avance un número en el archivo con un número más pequeño. Esto es O (n).
Todas las operaciones son O (n) y el algoritmo final es O (n) también.
EDITAR: método de mapa de bits es mucho más rápido si tiene suficiente memoria para mapas de bits. Este método funciona para cualquier número entero de tamaño fijo, de 64 bits, por ejemplo. El mapa de bits de tamaño 2^31 Mb no será práctico durante al menos unos años :)
Suponiendo que el tamaño entero es de 4 bytes. Ahora podemos tener un máximo de 2^32 enteros, es decir, puedo tener un bitvector de 2^32 bits (512 MB) para representar todos los enteros donde cada bit repite 1 entero. 1. Inicialice este vector con todos los ceros 2. Ahora vaya a través de un archivo y establezca bits en este vector en 1 si encuentra un número entero. 3. Ahora revise otro archivo y busque cualquier bit establecido en el bit Vector.
Complejidad de tiempo O (n + m) la complejidad espacio de 512 MB
Eso funcionaría solo si se pueden tratar múltiples ocurrencias como una única salida. Genial en mi opinión. –
2^32 bits es 512Mb, ¿no? – blaze
Esto es casi lo mismo que la solución anterior ' –
Digamos que es suficiente memoria RAM disponible para contener 5% de hash del archivo ya sea de matriz dada (FA).
Por lo tanto, puedo dividir las matrices de archivos (FA1 y FA2) en 20 pedazos cada una, digamos hacer un MOD 20 de los contenidos. Obtenemos FA1 (0) ....FA1 (19) y FA2 (0) ...... FA2 (19). Esto se puede hacer en tiempo lineal.
Hash FA1 (0) en la memoria y compara el contenido de FA2 (0) con este hash. Hashing y verificar la existencia son operaciones de tiempo constante.
Destruye este hash y repite para FA1 (1) ... FA1 (19). Esto también es lineal. Entonces, toda la operación es lineal.
¿Están ordenados? –
no .. números aleatorios –
¿Qué tamaño entero? – harold