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 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(i.read())
            infile.seek(0)

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:
 
<pre lang="python"> 
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é

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

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.