Python: Comment lire un énorme fichier texte en mémoire

Question

J'utilise Python 2.6 sur un Mac Mini avec 1 Go de RAM. Je veux lire dans un grand fichier texte

$ ls -l links.csv; file links.csv; tail links.csv 
-rw-r--r-- 1 user user 469904280 30 Nov 22:42 links.csv 
links.csv: ASCII text, with CRLF line terminators 
4757187,59883 
4757187,99822 
4757187,66546 
4757187,638452 
4757187,4627959 
4757187,312826 
4757187,6143 
4757187,6141 
4757187,3081726 
4757187,58197 

Ainsi, chaque ligne dans le fichier se compose d'un tuple de deux valeurs séparées par des virgules entières. Je veux lire dans le fichier entier et le trier selon la deuxième colonne. Je sais, que je pourrais faire le tri sans lire le dossier entier dans la mémoire. Mais je pensais pour un fichier de 500 Mo que je devrais quand même pouvoir le faire en mémoire puisque j'ai 1 Go disponible.

Toutefois, lorsque j'essaie de lire dans le fichier, Python semble allouer beaucoup plus de mémoire que ce qui est nécessaire pour le fichier sur le disque. Donc, même avec 1 Go de RAM, je ne suis pas en mesure de lire dans le fichier de 500 Mo en mémoire. Mon code Python pour lire le fichier et l'impression des informations sur la consommation de mémoire est:

#!/usr/bin/python 
# -*- coding: utf-8 -*- 

import sys 

infile=open("links.csv", "r") 

edges=[] 
count=0 
#count the total number of lines in the file 
for line in infile: 
count=count+1 

total=count 
print "Total number of lines: ",total 

infile.seek(0) 
count=0 
for line in infile: 
edge=tuple(map(int,line.strip().split(","))) 
edges.append(edge) 
count=count+1 
# for every million lines print memory consumption 
if count%1000000==0: 
    print "Position: ", edge 
    print "Read ",float(count)/float(total)*100,"%." 
    mem=sys.getsizeof(edges) 
    for edge in edges: 
    mem=mem+sys.getsizeof(edge) 
    for node in edge: 
    mem=mem+sys.getsizeof(node) 

    print "Memory (Bytes): ", mem 

La sortie je suis arrivé était:

Total number of lines: 30609720 
Position: (9745, 2994) 
Read 3.26693612356 %. 
Memory (Bytes): 64348736 
Position: (38857, 103574) 
Read 6.53387224712 %. 
Memory (Bytes): 128816320 
Position: (83609, 63498) 
Read 9.80080837067 %. 
Memory (Bytes): 192553000 
Position: (139692, 1078610) 
Read 13.0677444942 %. 
Memory (Bytes): 257873392 
Position: (205067, 153705) 
Read 16.3346806178 %. 
Memory (Bytes): 320107588 
Position: (283371, 253064) 
Read 19.6016167413 %. 
Memory (Bytes): 385448716 
Position: (354601, 377328) 
Read 22.8685528649 %. 
Memory (Bytes): 448629828 
Position: (441109, 3024112) 
Read 26.1354889885 %. 
Memory (Bytes): 512208580 

Déjà après avoir lu seulement 25% du fichier 500MB, Python consomme 500 Mo. Il semble donc que stocker le contenu du fichier sous la forme d'une liste de tuples d'ints n'est pas très efficace en termes de mémoire. Y at-il une meilleure façon de le faire, de sorte que je peux lire dans mon fichier de 500 Mo dans mon 1 Go de mémoire?

Answer 1

Il existe une recette pour trier les fichiers plus grands que la RAM on this page, bien que vous deviez l'adapter pour votre cas impliquant des données au format CSV. Il existe également des liens vers des ressources supplémentaires.

Edit: Il est vrai que le fichier sur le disque n'est pas « plus grand que la RAM », mais la représentation en mémoire peut facilement devenir beaucoup plus grande que RAM disponible. D'une part, votre propre programme n'obtient pas la totalité de 1 Go (frais généraux du système d'exploitation, etc.). Pour un autre, même si vous avez stocké ceci sous la forme la plus compacte pour du Python pur (deux listes d'entiers, en supposant une machine 32 bits etc.), vous utiliseriez 934 Mo pour ces 30M paires d'entiers.

En utilisant numpy vous pouvez également faire le travail, en utilisant seulement environ 250 Mo. Il n'est pas particulièrement rapide à charger de cette façon, que vous devez compter les lignes et pré-allouer le tableau, mais il peut être le plus rapide genre réel étant donné que c'est en mémoire:

import time 
import numpy as np 
import csv 

start = time.time() 
def elapsed(): 
    return time.time() - start 

# count data rows, to preallocate array 
f = open('links.csv', 'rb') 
def count(f): 
    while 1: 
     block = f.read(65536) 
     if not block: 
      break 
     yield block.count(',') 

linecount = sum(count(f)) 
print '\n%.3fs: file has %s rows' % (elapsed(), linecount) 

# pre-allocate array and load data into array 
m = np.zeros(linecount, dtype=[('a', np.uint32), ('b', np.uint32)]) 
f.seek(0) 
f = csv.reader(open('links.csv', 'rb')) 
for i, row in enumerate(f): 
    m[i] = int(row[0]), int(row[1]) 

print '%.3fs: loaded' % elapsed() 
# sort in-place 
m.sort(order='b') 

print '%.3fs: sorted' % elapsed() 

sortie sur mon machine avec un exemple de fichier similaire à ce que vous montriez:

6.139s: file has 33253213 lines 
238.130s: read into memory 
517.669s: sorted 

La valeur par défaut dans numpy est Quicksort. La routine ndarray.sort() (qui trie in-place) peut également prendre l'argument mot-clé kind="mergesort" ou kind="heapsort" mais il semble que ni l'un ni l'autre ne puisse trier sur un Record Array qui, accessoirement, était la seule façon de trier les colonnes ensemble par opposition à la valeur par défaut qui permettrait de les trier indépendamment (totalement gâcher vos données).

Answer 2

Comme ce ne sont que des nombres simples, les charger dans un tableau Nx2 supprimerait une surcharge. Utilisez NumPy pour les tableaux multidimensionnels. Vous pouvez également utiliser deux python normaux arrays pour représenter chaque colonne.

Answer 3

La méthode la plus économique pour stocker les lignes d'entrée en mémoire est celle des éléments array.array ('i') - en supposant que chaque nombre tiendra dans un entier signé de 32 bits.Le coût de la mémoire sera de 8N octets, où N est le nombre de lignes.

Voici comment faire le tri et écrire le fichier de sortie dans l'ordre de tri:

from array import array 
import csv 
a = array('i') 
b = array('i') 
for anum, bnum in csv.reader(open('input.csv', 'rb')): 
    a.append(int(anum)) 
    b.append(int(bnum)) 
wtr = csv.writer(open('output.csv', 'wb')) 
for i in sorted(xrange(len(a)), key=lambda x: b[x]): 
    wtr.writerow([a[i], b[i]]) 

Malheureusement sorted() retourne une liste, pas un iterator, et cette liste est assez grand: 4N octets pour les pointeurs et 12N octets pour les objets int, c'est-à-dire 16N octets pour la sortie sorted(). Note: ceci est basé sur CPython 2.X sur une machine 32 bits; cela devient pire pour chacune des machines 3.X et 64 bits. Tout ça c'est 24N octets. Vous avez 31 millions de lignes, vous avez donc besoin de 31 * 24 = 744 Mo ... on dirait que ça devrait marcher; Notez que ce calcul n'autorise aucune mémoire allouée par le tri, mais vous disposez d'une marge de sécurité raisonnable.

À côté: Quel est le coût d'un Go ou 3 de mémoire supplémentaire exprimé en heures à votre taux de salaire?

Answer 4

Tous les objets python ont un en-tête de mémoire au-dessus des données qu'ils stockent réellement. Selon getizeof sur mon système Ubuntu 32 bits, un tuple a un overhead de 32 octets et un int prend 12 octets, donc chaque ligne dans votre fichier prend un 56 octets + un pointeur de 4 octets dans la liste - je suppose que ce sera beaucoup plus pour un système 64 bits. Ceci est en ligne avec les chiffres que vous avez donnés et signifie que vos 30 millions de lignes prendront 1,8 Go.

Je suggère d'utiliser l'utilitaire de tri unix plutôt que d'utiliser python. Je ne suis pas un Mac-tête, mais je suppose que les options de tri OS X sont les mêmes la version linux, donc cela devrait fonctionner:

sort -n -t, -k2 links.csv 

-n signifie tri numérique

-t, signifie utiliser une virgule comme séparateur de champ

-k2 signifie tri sur le second champ

Cela triera le fichier et écrire le résultat sur la sortie standard. Vous pouvez le rediriger vers un autre fichier ou le rediriger vers votre programme python pour effectuer un traitement ultérieur. Si vous ne voulez pas trier le fichier avant d'exécuter votre script python, vous pouvez utiliser le module de sous-processus pour créer un tuyau vers l'utilitaire de tri de shell, puis lire les résultats triés à partir de la sortie du tuyau .

Answer 5

Vous voudrez peut-être regarder mmap:

http://docs.python.org/library/mmap.html

Il vous laisse traiter le fichier comme un grand tableau/string et obtiendrez le système d'exploitation pour gérer les données dans et brassage de mémoire laissez-le aller.

Ainsi vous pouvez lire dans le fichier csv, une ligne à la fois, puis écrire les résultats dans un fichier mmap (dans un format binaire approprié), puis travailler sur le fichier mmap. Comme le fichier mmap'd n'est que temporaire, vous pouvez bien sûr créer simplement un fichier tmp dans ce but.

Voici quelques démos code en utilisant mmap avec un tempfile à lire dans les données csv et stocker sous forme de paire d'entiers de:

import sys 
import mmap 
import array 
from tempfile import TemporaryFile 

def write_int(buffer, i): 
    # convert i to 4 bytes and write into buffer 
    buffer.write(array.array('i', [i]).tostring()) 

def read_int(buffer, pos): 
    # get the 4 bytes at pos and convert to integer 
    offset = 4*pos 
    return array.array('i', buffer[offset:offset+4])[0] 

def get_edge(edges, lineno): 
    pos = lineno*2 
    i, j = read_int(edges, pos), read_int(edges, pos+1) 
    return i, j 

infile=open("links.csv", "r") 

count=0 
#count the total number of lines in the file 
for line in infile: 
    count=count+1 

total=count 
print "Total number of lines: ",total 

infile.seek(0) 

# make mmap'd file that's long enough to contain all data 
# assuming two integers (4 bytes) per line 
tmp = TemporaryFile() 
file_len = 2*4*count 
# increase tmp file size 
tmp.seek(file_len-1) 
tmp.write(' ') 
tmp.seek(0) 
edges = mmap.mmap(tmp.fileno(), file_len) 

for line in infile: 
    i, j=tuple(map(int,line.strip().split(","))) 
    write_int(edges, i) 
    write_int(edges, j) 

# now confirm we can read the ints back out ok 
for i in xrange(count): 
    print get_edge(edges, i) 

Il est un peu difficile cependant. Vraiment, vous voudrez sans doute terminer tout cela avec une belle classe, afin que vos bords puissent être accédés d'une manière qui les fasse se comporter comme une liste (avec indexation, len etc.). Espérons que cela vous donnera un point de départ.

Answer 6

J'ai créé un module pour ce cas d'utilisation à l'aide external merge sort: https://bitbucket.org/richardpenman/csvsort

>>> from csvsort import csvsort 
>>> csvsort('links.csv', columns=[1], has_header=False)