Supprimer des lignes en double d'un gros fichier en python

Vous faites fondamentalement une tresse de fusion et vous enlevez des entrées dupliquées.

briser l'entrée dans des morceaux de taille mémoire, triant chacune des pièces, puis fusionner les morceaux lors de la suppression des doublons est une idée sonore en général.

En fait, jusqu'à quelques concerts, je laisserais le système de mémoire virtuelle le gérer et écrire simplement: xxx

Votre méthode actuelle n'est pas garantie correctement. strong>

Premièrement, il y a la faible probabilité que deux lignes réellement différentes puissent produire la même valeur de hachage. hachage (a) == hachage (b) code> ne signifie pas toujours que a == b code> p>

Deuxièmement, vous rendez la probabilité plus haute avec votre Caper "Réduire / Lambda": P>

>>> reduce(lambda x,y: x+y, ['foo', '1', '23'])
'foo123'
>>> reduce(lambda x,y: x+y, ['foo', '12', '3'])
'foo123'
>>>

Votre solution d'origine est légèrement incorrecte: vous pouvez avoir des lignes différentes de la même valeur (une collision de hachage) et votre code laisserait l'un d'eux.

En termes de complexité algorithmique, si vous attendez relativement peu de duplicats, je pense que la solution la plus rapide serait de numériser la ligne de fichier par ligne, en ajoutant le hachage de chaque ligne (comme vous l'avez fait), mais aussi de stocker l'emplacement. de cette ligne. Ensuite, lorsque vous rencontrez un hachage en double, cherchez à l'endroit d'origine pour vous assurer qu'il s'agit d'une copie de hachage et non seulement une collision de hachage, et si oui, recherchez et sautez la ligne.

Au fait, si les valeurs de CSV sont normalisées (c.-à-d. Les enregistrements sont considérés comme étant égaux si les lignes CSV correspondantes sont équivalentes d'octet-octet) équivalentes, vous n'avez pas besoin d'impliquer l'analyse de la CSV ici, faites simplement traiter des lignes de texte braliment. .

Depuis que je suppose que vous devriez le faire de manière un peu régulière (sinon vous auriez piraté un script unique), et vous avez mentionné que vous avez été intéressé par une solution théorique, voici une possibilité.

Lisez les lignes d'entrée dans les arbres B, commandées par la valeur de hachage de chaque ligne d'entrée, écrivez-les sur le disque lorsque la mémoire remplit. Nous prenons soin de stocker, sur les arbres B, les lignes d'origine attachées au hasch (en tant que jeu, car nous ne nous soucions que de lignes uniques). Lorsque nous lisons un élément dupliqué, nous vérifions les lignes définies sur l'élément stocké et l'ajoutons si c'est une nouvelle ligne qui arrive à hacher à la même valeur. P>

Pourquoi les arbres B? Ils nécessitent moins de lectures de disque lorsque vous ne pouvez (ou voulez-vous que) de lire des parties de leur mémoire. Le degré (nombre d'enfants) sur chaque nœud dépend de la mémoire et du nombre de lignes disponibles, mais vous ne voulez pas avoir trop de nœuds. P>

Une fois que nous avons ces arbres B sur disque, nous comparez l'élément le plus bas de chacun d'eux. Nous enlevons le plus bas de tous, de tous les arbres B qui l'avez. Nous fusionnerons leurs lignes de lignes, ce qui signifie que nous n'avons laissé aucun doublé à gauche pour ces lignes (et aussi que nous n'avons plus de lignes que hachage à cette valeur). Nous écrivons ensuite les lignes de cette fusion dans la structure de sortie CSV. P>

Nous pouvons séparer la moitié de la mémoire pour la lecture des arbres B et la moitié pour conserver la sortie CSV en mémoire pendant un certain temps. Nous rinçons le CSV sur le disque lorsque sa moitié est pleine, ajoute à tout ce qui a déjà été écrit. La quantité de chaque arbre B que nous lisons à chaque étape peut être grossièrement calculé par (disponible_memory / 2) / number_of_btrees, arrondi, donc nous lisons des nœuds complets. P>

en pseudo-python: P>

ins = DictReader(...)
i = 0
while ins.still_has_lines_to_be_read():
    tree = BTree(i)
    while fits_into_memory:
        line = ins.readline()
        tree.add(line, key=hash)
    tree.write_to_disc()
    i += 1
n_btrees = i

# At this point, we have several (n_btres) B-Trees on disk
while n_btrees:
    n_bytes = (available_memory / 2) / n_btrees
    btrees = [read_btree_from_disk(i, n_bytes)
              for i in enumerate(range(n_btrees))]
    lowest_candidates = [get_lowest(b) for b in btrees]
    lowest = min(lowest_candidates)
    lines = set()
    for i in range(number_of_btrees):
        tree = btrees[i]
        if lowest == lowest_candidates[i]:
            node = tree.pop_lowest()
            lines.update(node.lines)
        if tree.is_empty():
        n_btrees -= 1

    if output_memory_is_full or n_btrees == 0:
        outs.append_on_disk(lines)

Que diriez-vous d'utiliser le module de trempe pour lire des morceaux de fichier jusqu'à la limite de mémoire et écrivez-les des morceaux de tri (ThePQ garde les choses toujours dans l'ordre tri).

ou vous pouvez attraper le premier mot en ligne et diviser le fichier en morceaux par cela. Ensuite, vous pouvez lire les lignes (peut-être faire ».join (ligne.split ()) pour unifier l'espacement / les onglets en ligne s'il est correct pour modifier l'espacement) dans Définir l'ordre alphabétique Effacement de l'ensemble entre les pièces (Ensemble Supprimage DUPLICATES) Pour obtenir des choses à moitié triées (SET n'est pas dans l'ordre, si vous voulez que vous puissiez lire dans le tas et écrire pour obtenir l'ordre trié, le dernier occurrence dans le réglage de l'ensemble des valeurs anciennes.) Vous pouvez également modifier la pièce.) et supprimez des lignes en double avec la solution de groupeBy de Joe Koberg. Enfin, vous pouvez rejoindre des morceaux ensemble (vous pouvez bien sûr faire l'écriture lorsque vous allez à la pièce par pièce au fichier final lors du tri des pièces)