Grandes volúmenes de datos y ordenar la búsqueda

Question

Tengo dos archivos de datos, líneas 100 Char cada uno. Un archivo: 10 ⁸ líneas, archivo B: 10 ⁶ líneas. Y tengo que encontrar todas las cuerdas de archivo B que no están en el archivo A.
Al principio yo estaba pensando en la alimentación de los dos archivos a MySQL, pero parece que no va nunca terminar de crear una clave única en 10 ⁸ registros.

Estoy esperando sus sugerencias en este sentido.

Answer 1

Se puede realizar esta operación sin una base de datos. La clave es reducir el tamaño de A, ya que A es mucho mayor que B. Aquí es cómo hacer esto:

Calcular hash de 64 bits utilizando una función hash decente para las cadenas en el archivo B. Almacenarlos en la memoria (en una tabla hash), que se puede hacer porque B es pequeño. Entonces hash de todas las cadenas en el archivo A, línea por línea, y ver si cada uno coincide con un hash para el archivo B. Cualquier línea con hashes coincidentes (a uno de B), se deben almacenar en un archivo de C.

Cuando este proceso es archivo completo C tendrá la pequeño subconjunto de A de cadenas potencialmente emparejan (a B). Ahora usted tiene un archivo de C mucho más pequeño que es necesario comparar las líneas de B con. Esto reduce el problema a un problema en el que puede cargar todas las líneas de C en la memoria (como una tabla hash) y comparar cada línea de B para ver si está en C.

Answer 2

Se puede mejorar un poco en la respuesta de @ michael-Goldshteyn ( https://stackoverflow.com/a/3926745/179529). Ya que se necesita para encontrar todas las cadenas en B que no están en A, puede eliminar cualquier elemento de la tabla hash de los elementos de B, cuando se comparan y encontrar una coincidencia para ello con los elementos de A. Los elementos que permanecerá en la tabla hash son los elementos que no se encuentran en el archivo A.

Answer 3

Para los tamaños que usted menciona que debe ser capaz de mantener todos B en la memoria a la vez, por lo que podría hacer una versión simplificada de la respuesta de Goldshteyn; algo como esto en Python:

#!/usr/bin/python3

import sys

if __name__=='__main__':
  b = open(sys.argv[2],'r')
  bs = set()
  for l in b:
    bs.add(l.strip())
  b.close()
  a = open(sys.argv[1],'r')
  for l in a:
    l = l.strip()
    if l in bs:
      bs.remove(l)
  for x in bs:
    print(x)

He probado esto en dos archivos de 10 ^ 5 y 10 ^ 7 en tamaño con ~ 8 caracteres por línea en un procesador átomo. La salida de / usr / bin / hora:

25.15user 0.27system 0:25.80elapsed 98%CPU (0avgtext+0avgdata 56032maxresident)k
0inputs+0outputs (0major+3862minor)pagefaults 0swaps
  60298   60298  509244