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

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. マージソート_-_Qiita.png

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

Recommended Posts

Trier les gros fichiers texte en Python
Trier les gros fichiers texte
Texte de cluster en Python
Tri à bulles en Python
Traitement de texte avec Python
Tri personnalisé en Python3
Traitement de texte UTF8 avec python
Trier naturellement le chemin en Python
Trier de gros fichiers avec python
Parler avec Python [synthèse vocale]
Trier par date en python
Translocation de fichiers CSV avec Python Partie 1
GOTO en Python avec Sublime Text 3
Manipuler des fichiers et des dossiers en Python
Gestion des fichiers JSON en Python
Téléchargez des fichiers Google Drive en Python
Extraire du texte d'images avec Python
Python #sort
Lire des fichiers en parallèle avec Python
Exporter et exporter des fichiers en Python
La loi des nombres en python
Lire et écrire du texte en Python
Extraire des chaînes de fichiers avec Python
Lors de la spécification de plusieurs clés dans le tri python
Nouveautés de Python 3.9 (2) - Tri des graphes non circulés dirigés en Python
Trouver des fichiers comme Linux Find en Python
Arborescence de sortie des fichiers en Python
Tapez les annotations pour Python2 dans les fichiers stub!
Automatisez les tâches en manipulant des fichiers en Python
Lire et écrire des fichiers JSON avec Python
Exemple de gestion des fichiers eml en Python
Mise en œuvre du tri Stuge dans Python 3 (tri à bulles et tri rapide)
Essayez de fouiller votre journal avec Python
Téléchargez des fichiers dans n'importe quel format en utilisant Python
Lire des caractères dans des images avec Python OCR
Quadtree en Python --2
Python en optimisation
CURL en Python
Géocodage en python
SendKeys en Python
Méta-analyse en Python
Unittest en Python
Époque en Python
Discord en Python
Allemand en Python
DCI en Python
tri rapide en python
nCr en python
N-Gram en Python
Programmation avec Python
Plink en Python
Constante en Python
FizzBuzz en Python
Sqlite en Python
Étape AIC en Python
LINE-Bot [0] en Python
CSV en Python
Assemblage inversé avec Python
Réflexion en Python