Trier les gros fichiers texte en Python

[Tri de fusion]: https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3% 83% 88 [io.IOBase.readlines]:http://docs.python.jp/3/library/io.html#io.IOBase.readlines

Contexte

Les fichiers texte doivent être triés dans des scripts Python exécutés dans un environnement Windows.

Les exigences sont les suivantes.

--Exécuter dans l'environnement Windows

• Le fichier cible est un fichier CSV de plusieurs Go
• La clé de tri comporte plusieurs colonnes et il existe également une colonne numérique.

L'invite de commande Windows a une [commande de tri] windows-sort qui prend en charge le tri des fichiers volumineux. Cependant, contrairement à la [commande de tri Linux] et [tri-linux], vous ne pouvez pas spécifier de délimiteur (-t) ou trier sous forme de nombre (-n).

Si la taille est petite, vous pouvez charger toutes les données en mémoire avec un script Python et appeler la fonction sorted, mais si la taille est grande, vous risquez de manquer de mémoire.

Je n'ai pas pu m'en empêcher, j'ai donc décidé d'implémenter un traitement de tri pour les gros fichiers en Python.

Procédure de traitement

Pour trier une énorme quantité de données, utilisez le concept de [Tri par fusion] comme suit.

1. Fractionner
2. Lisez suffisamment de lignes du fichier d'entrée pour tenir en mémoire
3. Triez la partie lue et écrivez-la dans un fichier temporaire
4. Répétez jusqu'à ce que tous les fichiers d'entrée soient lus
5. Fusionner
6. Lisez une ligne de chaque fichier temporaire
7. Ecrivez la plus petite valeur dans le fichier de sortie
8. Répétez jusqu'à ce que tous les fichiers temporaires aient été lus

J'ai créé une [diapositive de procédure de traitement] pour que vous puissiez voir comment cela fonctionne.

Méthode de mise en œuvre

Divisé

Utilisez [io.IOBase.readlines] pour fractionner et lire le fichier.

L'utilisation de readlines sans argument charge toutes les lignes en mémoire, donc l'utilisation de readlines pour les fichiers de grande taille est connue comme un anti-pattern.

Cependant, readlines peut limiter le nombre d'octets / caractères à lire avec un argument, ce qui permet même de lire séparément un gros fichier texte.

>>> from io import StringIO
>>> f = StringIO("11\n22\n3\n4\n5\n666666\n")
>>> f.readlines(5)
['11\n', '22\n']
>>> f.readlines(5)
['3\n', '4\n', '5\n']
>>> f.readlines(5)
['666666\n']
>>> f.readlines(5)
[]

Cela semble être le nombre d'octets pour les fichiers ouverts en mode binaire et le nombre de caractères pour le mode texte.

fusionner

Utilisez heapq.merge pour la fusion. heapq.merge renvoie le résultat de la fusion de plusieurs itérables triés.

>>> import heapq
>>> list(heapq.merge([1, 3, 4, 7], [2, 5], [6]))
[1, 2, 3, 4, 5, 6, 7]

La source

Il est répertorié dans gist. La version Python est la 3.6.

Ce qui suit est un extrait de la partie de tri.

import heapq
import os
from contextlib import contextmanager
from operator import itemgetter
from tempfile import TemporaryDirectory, mktemp
from typing import IO, Callable, List


def large_sort(input_file: IO, output_file: IO, key: Callable=None, reverse: bool=False, limit_chars: int=1024*1024*64):

    with TemporaryDirectory() as tmp_dir:

        for lines in _read_parts(input_file, limit_chars):
            lines = sorted(lines, key=key, reverse=reverse)
            _write_part(lines, tmp_dir)

        with _open_tmp_files(tmp_dir) as tmp_files:
            for row in heapq.merge(*tmp_files, key=key, reverse=reverse):
                output_file.write(row)


def _read_parts(input_file, limit_chars):
    lines = input_file.readlines(limit_chars)
    while lines:
        yield lines
        lines = input_file.readlines(limit_chars)


def _write_part(lines, tmp_dir):
    tmp_filename = mktemp(dir=tmp_dir)
    with open(tmp_filename, "w") as tmp_file:
        tmp_file.writelines(lines)
    return tmp_filename


@contextmanager
def _open_tmp_files(tmp_dir):
    filenames = os.listdir(tmp_dir)
    files = [open(os.path.join(tmp_dir, filename), "r") for filename in filenames]
    try:
        yield files
    finally:
        for file in files:
            file.close()

Dans cette exigence, je voulais une fonction à appeler à partir d'un autre script Python, donc je n'en ai pas besoin, mais dans la source principale, je l'ai rendue disponible à partir de la ligne de commande en faisant référence à la commande sort de linux.

D'autres idées

Je l'ai fait moi-même cette fois, mais je vais l'écrire car il existe d'autres solutions.

--Utilisez un environnement système qui peut utiliser des commandes Linux telles que Cygwin

• Cette fois, l'environnement d'exécution était un PC non-ingénieur, il est donc difficile de dire "Installer Cygwin", donc je l'ai rejeté. --Il semble possible d'extraire et de regrouper uniquement sort.exe et les DLL nécessaires. --Utilisez un outil de tri gratuit ―― J'ai cherché légèrement, mais je ne pouvais pas le trouver que je pourrais utiliser à partir de la ligne de commande et répondre aux exigences. ――Vous pouvez peut-être le trouver si vous recherchez correctement
• Commande de tri PowerShell --Il semble être plus sophistiqué que la commande sort à l'invite de commande, mais cela n'a pas été confirmé.