Algorithme Python pour trier de gros blocs de données

Question

J'ai cherché en ligne une méthode pour trier le type de données que j'ai (fichiers LDIF), mais je n'ai pas trouvé tout à fait ce que je cherche. Il existe déjà des programmes pour effectuer ce tri, mais ils échouent avec des ensembles de données extrêmement volumineux. Eh bien, pour moi, la taille de ces blocs est extrêmement importante, de l'ordre de 2 Go, ce qui épuise la mémoire lors de l'utilisation du script ldifsort.pl, même si j'ai 6 Go de RAM disponible et plusieurs Go de swap. J'espère donc écrire un programme qui va stocker les blocs de données sur le disque dur, trier les clés en mémoire, puis réassembler les blocs dans l'ordre. Et j'aimerais utiliser python3 alors que j'essaie d'apprendre cette langue. Donc, si quelqu'un a des suggestions sur la stratégie de base ou sur des façons spécifiques de le faire avec python3, j'apprécierais vraiment l'aide.

J'ai de gros fichiers de texte contenant des données LDAP, essentiellement sous la forme (très simplifiée) de:

dn: Subscriber=UniqueName1@domain.com;RestOfTree=node1 
groups: 1 
permissions: 1 
IsActive: FALSE 
Barring: TRUE 

dn: ProfileID=UniqueName1@domain.com;Subscriber=UniqueName1;RestOfTree=node1 
groups: 1 
permissions: 1 
ServiceProfile: Lemur 

dn: Subscriber=UniqueName2@domain.com;RestOfTree=node1 
groups: 1 
permissions: 1 
IsActive: FALSE 
Barring: TRUE 

dn: ProfileID=UniqueName2@domain.com;Subscriber=UniqueName2;RestOfTree=node1 
groups: 1 
permissions: 1 
ServiceProfile: Lemur 

Chaque abonné a trois autres blocs qui y sont associés (mon code exemple montre qu'un autre bloc associé à l'abonné), et je voudrais garder tous les quatre blocs ensemble après le tri est terminé.

dn: Subscriber=UniqueName2@domain.com;RestOfTree=node 
dn: ProfileID=UniqueName2@domain.com;Subscriber=UniqueName2;RestOfTree=node 
dn: Subscriber=UniqueName4@domain.com;RestOfTree=node 
dn: ProfileID=UniqueName4@domain.com;Subscriber=UniqueName4;RestOfTree=node 
dn: Subscriber=UniqueName1@domain.com;RestOfTree=node 
dn: Subscriber=UniqueName3@domain.com;RestOfTree=node 
dn: ProfileID=UniqueName3@domain.com;Subscriber=UniqueName3;RestOfTree=node 
dn: ProfileID=UniqueName1@domain.com;Subscriber=UniqueName1;RestOfTree=node 

Je veux que la sortie soit::

Donc, si je lis les dn est dans cet ordre (les données associées est cachée par souci de concision de l'dn)

dn: Subscriber=UniqueName1@domain.com;RestOfTree=node 
dn: ProfileID=UniqueName1@domain.com;Subscriber=UniqueName1;RestOfTree=node 
dn: Subscriber=UniqueName2@domain.com;RestOfTree=node 
dn: ProfileID=UniqueName2@domain.com;Subscriber=UniqueName2;RestOfTree=node 
dn: Subscriber=UniqueName3@domain.com;RestOfTree=node 
dn: ProfileID=UniqueName3@domain.com;Subscriber=UniqueName3;RestOfTree=node 
dn: Subscriber=UniqueName4@domain.com;RestOfTree=node 
dn: ProfileID=UniqueName4@domain.com;Subscriber=UniqueName4;RestOfTree=node 

Une pensée Je devais utiliser sqlite3 pour stocker les données lorsque python les lisait, puis trier les clés dans python, puis utiliser les requêtes pour extraire les données de sqlite et écrire les données dans un fichier. Mais j'ai peur que le temps passé à chercher les clés dans sqlite soit excessif. Alors j'ai pensé que je pourrais trier les données dans sqlite pendant que j'insère les données, mais il semble que sqlite ne supporte pas ceci, et je ne sais pas s'il y a un autre système de base de données qui le fait.

Toute aide ou direction est appréciée.

Merci à Zach pour sa suggestion d'utiliser simplement le tri GNU au lieu d'un système de base de données. Voici la solution que j'ai développée avec son aide.

awk -f ldifformatter.awk Fichiers de données LDAP * .ldif | trier -t \ | -k1 | sed '1d; s/|/\ n/g'> trié.txt

où ldifformatter.awk échange toutes les nouvelles lignes avec "|" sauf pour les dn de haut niveau, qui sont utilisés pour le tri.

Merci, Rusty

Answer 1

L'utilitaire de ligne de commande sort pouvez trier les fichiers texte très volumineux sans les lire entièrement en mémoire (au moins, la version GNU peut). Cependant, pour l'utiliser, vous devrez reformater les données de sorte que chaque enregistrement (tout ce qui doit être conservé ensemble) apparaisse sur une ligne. Si les enregistrements avaient l'air quelque chose comme ceci:

dn: Subscriber=UniqueName1@domain.com;RestOfTree=node1|groups: 1|permissions: 1|IsActive: FALSE|Barring: TRUE||dn: ProfileID=UniqueName1@domain.com;Subscriber=UniqueName1;RestOfTree=node1|groups: 1|permissions: 1|ServiceProfile: Lemur 

alors sort -t \| -k1 fera le travail.

Vous pouvez écrire un programme en Python qui transmet les données dans un fichier temporaire au format approprié, appelle sort en utilisant subprocess.check_call, puis restaure le format d'origine. Utilisez tmpfile.NamedTemporaryFile pour créer le fichier temporaire.

Answer 2

Je me demande si SQLite est vraiment pas à la tâche. Mais de toute façon, vous pouvez utiliser un algorithme de tri externe, par ex. Mergesort, pour garder l'utilisation de la mémoire faible.

http://en.wikipedia.org/wiki/External_sorting

Answer 3

Vous ne devriez pas trier vos données en mémoire. Vous pouvez utiliser merge sort.

Guido van Rossum a écrit un article sur le même problème - Sorting a million 32-bit integers in 2MB of RAM using Python. Il y a des exemples de code dans cet article.