Big le tri et la recherche de données

Question

J'ai deux fichiers de données, 100 lignes de caractères chacune. Fichier A: 10 lignes, fichier B: 10 lignes. Et j'ai besoin de trouver toutes les chaînes du fichier B qui ne sont pas dans le fichier A.
Au début, je pensais nourrir les deux fichiers à mysql, mais on dirait qu'il ne finira jamais de créer une clé unique sur 10 enregistrements.

J'attends vos suggestions à ce sujet.

Answer 1

Vous pouvez effectuer cette opération sans base de données. La clé consiste à réduire la taille de A, car A est beaucoup plus grand que B. Voici comment procéder:

Calculer des hachages 64 bits en utilisant une fonction de hachage décent pour les chaînes du fichier B. Stockez-les en mémoire (dans une table de hachage), ce que vous pouvez faire parce que B est petit. Ensuite, hachez toutes les chaînes de votre fichier A, ligne par ligne, et voyez si chacune correspond à un hachage pour votre fichier B. Toutes les lignes avec des hachages correspondants (à un de B), doivent être stockées dans un fichier C.

Lorsque ce processus est terminé, le fichier C aura le petit sous-ensemble de A de chaînes potentiellement assorties (à B). Maintenant, vous avez un fichier C beaucoup plus petit 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 table de hachage) et comparer chaque ligne de B pour voir si elle est en C.

Answer 2

Pour les tailles que vous mentionnez devrait être en mesure de garder tout de B en mémoire à la fois, de sorte que vous pourriez 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 en 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 

Answer 3

Vous pouvez améliorer légèrement la réponse de @ michael-goldshteyn (https://stackoverflow.com/a/3926745/179529). Puisque vous avez besoin de trouver toutes les chaînes dans B qui ne sont pas dans A, vous pouvez supprimer n'importe quel élément de la table de hachage des éléments de B, lorsque vous comparez et trouvez une correspondance avec les éléments dans A. Les éléments qui seront rester dans la table de hachage sont les éléments qui n'ont pas été trouvés dans le fichier A.