Trier un CSV de 5 Go

This entry was posted in Programmation and tagged heapq python sort on by

Marrant, j’ai jamais eu autant de RAM, et j’ai jamais eu autant de problèmes de RAM. On est en train de faire un bon dans inefficacité des programmes, et ça va pas aller en s’arrangeant entre docker, electron et nos chers navigateurs. Une grosse app Python peut devenir assez velue aussi niveau mémoire, même quand on n’est pas un boulet comme moi.

Et justement, en relisant un célèbre post de Guido sur la réponse à la blague “comment trier un million d’entiers avec 2M de Ram”, j’ai réalisé 2 choses:

  • Le contenu de l’article est génial.
  • Le contenu de l’article est incompréhensible.

Or c’est un peu ma raison d’être, si vous voulez, de prendre les trucs cools mais imbitables et les rendre utilisables.

Aujourd’hui, donc, on va trier un CSV de 5Go en Python. Ça parle plus qu’un fichier de nombres, et puis ça évite d’expliquer le module array qui est juste une optimisation.

J’ai pris mes petites mimines, et j’ai pondu un CSV qui contient 63Mo de:

A,01/02/2016,2
A,13/07/2011,1
B,24/01/1996,3
C,30/12/1999,1
D,13/07/2011,3
D,01/02/2016,5
E,24/01/1996,4
F,30/12/1999,1
G,13/07/2011,4
H,01/02/2016,4
I,01/02/2016,5
I,13/07/2011,2
A,01/02/2016,2
A,13/07/2011,1

En copier/coller.

Puis j’ai lancé un script pour dupliquer le bébé et jusqu’à atteindre 5,9 Go de taille:

with open('data.csv') as infile:
    with open('data2.csv', 'w') as outfile:
        for x in range(100):
            outfile.write(infile.read())
            infile.seek(0)
Si jamais vous doutiez que je vous aime...

Si jamais vous doutiez que je vous aime…

395366400 lignes. Jusqu’ici tout va bien.

Maintenant, supposons qu’on veuille trier sur la date. Si vos souvenirs en Python sont exacts (ou si vous avez lu notre super article sur Ordonner en Python), vous savez que la solution naïve est de loader le fichier cash pistache, puis d’appeler dessus sorted() avec le paramètre key.

D’abord, il faut choisir le callback à passer à key, c’est à dire la fonction qui va être exécutée pour chaque ligne pour extraire la date de la ligne et permettre ainsi à sorted() de comparer avec les autres dates.

>>> str_date = "A,01/02/2016,2".split(',')[1] # récupère la date uniquement
>>> str_date
'01/02/2016'
>>> ''.join(str_date.split('/')[::-1]) # on inverse la date avoir une valeur ordonnable
'20160201'

On en fait une fonction:

def extract_date(ligne):
    str_date = ligne.split(',')[1]
    return ''.join(str_date.split('/')[::-1])

Ensuite on a juste à ouvrir le fichier, trier les lignes, et sauvegarder tout ça dans l’autre fichier:

with open('data2.csv') as infile:
    with open('sorted_data.csv', 'w') as outfile:
        # on fait le tri
        sorted_lines = sorted(infile, key=extract_date)
        # on ecrit les lignes triées dans le nouveau fichier
        outfile.writelines(sorted_lines)

Easy money, double poney.

Enfin avec un fichier de quelques Mo. Parce que si vous faites ça dans un fichier de 5,9 Go, votre RAM va vomir comme une pom pom girl anorexique.

sorted() sur un disque complet, illustré

sorted() sur un disque complet, illustré

Comment résoudre ce problème ?

Et bien en faisant tout pareil, mais avec des petits morceaux !

import heapq
 
from tempfile import TemporaryFile
from itertools import islice
 
# On garde notre fonction key
def extract_date(ligne):
    str_date = ligne.split(',')[1]
    return ''.join(str_date.split('/')[::-1])
 
# Liste de tous les fichiers temporaires avec les lignes triées
sorted_temp_files = []
 
with open('data2.csv') as infile:
    progress = 0
    while True:
        # On lit seulement 3000000 lignes sur 395366400 à chaque tour de boucle
        lines = list(islice(infile, 3000000))
 
        if not lines:  # plus de ligne ? On sort
            break
 
        # On affiche où on en est
        print("{:.2f}%".format(progress))
        progress += (3000000 / 395366400 * 100)
 
        # On tri les lignes, comme avec sorted() mais sur place. 
        # Ça évite de dupliquer les données en mémoire.
        lines.sort(key=extract_date)
 
        # On crée un fichier temporaire qui va contenir les 3000000 lignes
        # triées
        f = TemporaryFile(mode="r+")
        f.writelines(lines)
 
        # On rembobine le fichier pour pouvoir relire le contenu plus tard
        f.seek(0)
 
        # On balance le fichier dans la liste des fichiers triés
        # L'objet fichier hein. Pas le chemin du fichier. C'est pour ça qu'on
        # a fait .seek(0) avant. On va en avoir besoin plus bas.
        sorted_temp_files.append(f)
 
    # Toute la magie se fait là.
    # On utilise heapq.merge(), qui prend en paramètre plein de trucs qu'on 
    # vient de trier, et permet de se balader dedans comme si c'était un seul
    # gros truc trié, mais sans tout charger en mémoire.
    # En gros il regarde les premières valeurs de tous les itérables, les compares,
    # puis fait retourne un générateur qui yield tout dans l'ordre 
    with open('sorted_data.csv', 'w') as outfile:
        for ligne in heapq.merge(*sorted_temp_files, key=extract_date):
            outfile.write(ligne)

Au lieu de charger les 5 Go en mémoire, on plafonne à 400 Mo. Une raison de plus d’apprendre à utiliser les générateurs.

Sametmax, c'est de la bombe

Sametmax, c’est de la bombe

Alors évidemment, c’est long. Y a genre 40 minutes de traitement. Moins si on utilise pypy et qu’on accepte de up la conso RAM. On code pas en Rust :)

Si vous avez besoin de perfs et que Python reste votre outil de prédilections, 3 solutions restent à votre disposition:

– Prétraiter le fichier en lui rajoutant une première colonne qui contient un timestamp. Ca c’est super rapide à trier.
– Utiliser un truc de numpy ou pandas comme np.memmap().sort(kind=’merge’). C’est du C, donc ça speed.
– Acheter de la ram et tout trier en mémoire avec la solution 1.

EDIT:

Un lecteur m’a alpagué sur twitter pour me dire qu’on peut faire ça plus vite et plus facilement avec sort. Oui, évidement.

L’exercice est académique, il est simplifié pour vous permettre de comprendre heapq.merge(). En réalité, on aura vraiment besoin de ça que pour un cas complexe. Exemple, vous lisez un flux de log une socket et vous checkez les adresses IP d’abord pour filtrer celles de la liste noire, puis pour les faire matcher une zone géographique et vous triez tout ça et vous le passez à la suite du pipeline. Et le tout doit marcher sous Linux et Windows Server avec juste la lib standard parce que diab est de mauvais poil.

Évidement que si vous voulez juste trier un CSV vous n’allez pas coder un script python de 30 lignes.

15 thoughts on “Trier un CSV de 5 Go”

  • orwell

    Il manque la balise fermante dans l’exemple de code qui fini par :

    ''.join(str_date.split('/')[::-1]) # on inverse la date avoir une valeur ordonnable

  • Sam Post author

    Y a un edit qui dit clairement “L’exercice est académique et bla bla bla”. Y a toujours moyen de faire mieux. Tu peux aussi mettre les données dans SQL, utiliser l’option “chunk” de pandas (ce que blaze, d’ailleurs), utiliser array.array pour simplement prendre moins de mémoire, etc. Y a 700 solutions au problème du tri d’un csv par une colonne. C’est pas la question.

  • Fred

    Bonjour

    Intéressant comme façon de faire. Ca me rappelle les appareillages de fichiers que je faisais quand j’étudiais l’informatique.

    L’appareillage de fichiers consiste à fusionner 2 fichiers triés. La procédure est la suivante:

    On positionne un flag par fichier à vrai (donc f1 et f2 à vrai)

tant que pas eof sur fichier1 et pas eof sur fichier2, faire

si f1 est vrai, alors

lire fichier1 dans info1

mettre f1 à faux

fin si

si f2 est vrai, alors

lire fichier2 dans info2

mettre f2 à faux

fin si

si info1 ≤ info2 ou eof sur fichier2 alors

traiter info1

mettre f1 à vrai

fin si

si info2 ≤ info1 ou eof sur fichier1 alors

traiter info2

mettre f2 à vrai

fin si

fin faire

    C’est un algo pas compliqué à étendre à n fichiers et à rendre universel en remplaçant la comparaison par une fonction dédiée…

  • Jules

    Sinon, il y a la méthode read_csv de pandas qui par défaut lit les fichiers par morceau quand ils sont trop gros (paramètre low_memory=True).

  • Ribodou

    Bonjour,

    J’ai remarqué quelques fautes:

    pour un cas complex -> pour un cas complexe

    outfile.write(i.read()) -> outfile.write(infile.read())

  • Denis

    Perso, j’aurais attaché la table sous MariaDB (moteur CSV), requêté avec un order by et exporté.

  • bob

    Bonjour,

    Comment supprimer son compte du site indexerror.net (le formulaire de contact sur le site n’est pas fonctionnel) ?

    Merci.

  • Sam Post author

    Hello Bob, envoies moi les détails par email (lesametlemax@gmail.com) et je te ferai la suppression.

    Bonne journée.

Comments are closed.

Des questions Python sans rapport avec l'article ? Posez-les sur IndexError.