Big data trier et rechercher

Question

J'ai deux fichiers de données, les lignes 100 char chacun. Fichier A: 10 ⁸ lignes, fichier B: 10 ⁶ lignes. Et je dois trouver toutes les chaînes de fichier B qui ne sont pas dans le dossier A.
Au début, je pensais alimenter les deux fichiers à MySQL, mais il semble que ce ne sera plus jamais terminer la création d'une clé unique sur 10 ⁸ enregistrements.

Je suis en attente de vos suggestions à ce sujet.

Answer 1

Vous pouvez effectuer cette opération sans une base de données. La clé est de réduire la taille de A, puisque A est beaucoup plus grande que B. Voici comment faire ceci:

Calculer hash 64 bits en utilisant une fonction de hachage décent pour les chaînes dans le fichier B. Stocker dans la mémoire (dans une table de hachage), que vous pouvez le faire parce que B est faible. hachage Ensuite, toutes les chaînes dans votre fichier A, ligne par ligne, et voir si chacun correspond à un hachage pour votre fichier B. Toutes les lignes avec des valeurs de hachage correspondant à une (de B) doivent être stockées dans un fichier C

Lorsque ce processus est dossier complet C aura le petit sous-ensemble de A de chaînes potentiellement correspondant (B). Maintenant, vous avez un beaucoup plus petit fichier C que vous avez besoin de comparer les lignes de B avec. Cela réduit le problème à un problème où vous pouvez réellement charger toutes les lignes de C en mémoire (comme une table de hachage) et comparer chaque ligne de B pour voir si elle est en C.

Answer 2

Vous pouvez améliorer un peu sur la réponse @ michael-goldshteyn ( https://stackoverflow.com/a/3926745/179529). Puisque vous avez besoin de trouver toutes les chaînes B qui ne sont pas en A, vous pouvez supprimer tout élément de la table de hachage des éléments de B, lorsque vous comparez et trouver une correspondance pour avec les éléments en A. Les éléments qui restent dans le tableau Hash sont les éléments qui ne sont pas présents dans le fichier A.

Answer 3

Pour les tailles que vous mentionnez, vous devriez être en mesure de garder tous B en mémoire à la fois, pour que vous puissiez faire une version simplifiée de la réponse de Goldshteyn; quelque chose comme ça 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)

Je l'ai testé cela sur deux fichiers de 10 ^ 5 et 10 ^ 7 taille avec ~ 8 caractères par ligne sur un processeur atomique. La sortie de / usr / bin / time:

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