Python: Come leggere un enorme file di testo nella memoria

Question

Sto usando Python 2.6 su un Mac Mini con 1GB di RAM. Voglio leggere in un file di testo enorme

$ 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 

Così ogni riga del file è costituito da una tupla di due separati da virgole valori interi. Voglio leggere l'intero file e ordinarlo secondo la seconda colonna. So che potrei fare l'ordinamento senza leggere l'intero file in memoria. Ma ho pensato per un file di 500 MB dovrei essere ancora in grado di farlo in memoria dato che ho 1 GB disponibile.

Tuttavia, quando provo a leggere il file, Python sembra allocare molta più memoria di quella richiesta dal file sul disco. Quindi, anche con 1 GB di RAM non riesco a leggere il file da 500 MB in memoria. Il mio codice Python per la lettura del file e la stampa alcune informazioni circa il consumo di memoria è:

#!/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 

L'uscita ho ottenuto è stato:

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 

Già dopo aver letto solo il 25% del file 500MB, Python consuma 500 MB. Quindi sembra che la memorizzazione del contenuto del file come una lista di tuple di ints non sia molto efficiente in termini di memoria. C'è un modo migliore per farlo, in modo che io possa leggere il mio file da 500 MB nel mio 1 GB di memoria?

Answer 1

Esiste una ricetta per l'ordinamento di file più grandi della RAM on this page, sebbene sia necessario adattarlo per il caso che riguarda i dati in formato CSV. Ci sono anche collegamenti a risorse aggiuntive lì.

Edit: È vero, il file su disco non è "più grande di RAM", ma la rappresentazione in memoria può facilmente diventare molto più grande di RAM disponibile. Per prima cosa, il tuo programma non ottiene l'intero 1GB (overhead del sistema operativo ecc.). Per un altro, anche se lo hai memorizzato nella forma più compatta per Python puro (due elenchi di numeri interi, supponendo macchina a 32 bit, ecc.), Useresti 934 MB per quelle coppie di numeri interi da 30M.

Utilizzando numpy è possibile anche eseguire il lavoro, utilizzando solo circa 250 MB. E non è particolare veloce da caricare in questo modo, come si deve contare le linee e le pre-allocare la matrice, ma può essere il più veloce tipo effettivo dato che è in memoria:

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() 

uscita sul mio macchina con un file di esempio simile a quello che ha mostrato:

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

L'impostazione predefinita in NumPy è Quicksort. La routine ndarray.sort() (che ordina sul posto) può anche accettare l'argomento chiave kind="mergesort" o kind="heapsort" ma sembra che nessuno di questi sia in grado di ordinare su un Record Array che, tra l'altro, ho usato come unico modo che potevo vedere per ordinare le colonne insieme in contrasto con il valore predefinito che li ordinerebbe in modo indipendente (incasinando completamente i dati).

Answer 2

Poiché si tratta solo di numeri, il loro caricamento in un array Nx2 eliminerebbe alcuni costi generali. Usa NumPy per gli array multidimensionali. In alternativa, è possibile utilizzare due python normali arrays per rappresentare ciascuna colonna.

Answer 3

Il modo più economico per memorizzare le righe di input in memoria è come elementi array.array ('i') - assumendo che ciascun numero si adatti a un numero intero a 32 bit con segno.Il costo della memoria sarà di 8N byte, dove N è il numero di linee.

Ecco come fare l'ordinamento e scrivere il file di output in modo ordinato:

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]]) 

Purtroppo sorted() restituisce una lista, non un iteratore, e questo elenco sarà piuttosto grande: 4N byte per i puntatori e 12N byte per oggetti int, ovvero 16N byte per l'uscita sorted(). Nota: questo è basato su CPython 2.X su una macchina a 32 bit; peggiora per ciascuna delle macchine 3.X e 64-bit. Il totale è di 24N byte. Hai 31 milioni di linee, quindi hai bisogno di 31 * 24 = 744 MB ... sembra che dovrebbe funzionare; si noti che questo calcolo non consente alcuna memoria allocata dall'ordinamento, ma si dispone di un ragionevole margine di sicurezza.

A parte: qual è il costo di un GB o di 3 di memoria in più espresso in ore al tasso di salario?

Answer 4

Tutti gli oggetti Python hanno un sovraccarico della memoria in cima ai dati che stanno effettivamente memorizzando. Secondo getizeof sul mio sistema Ubuntu a 32 bit una tupla ha un overhead di 32 byte e un int richiede 12 byte, quindi ogni riga nel tuo file prende un 56 byte + un puntatore a 4 byte nella lista - presumo che sarà molto più per un sistema a 64 bit. Questo è in linea con le cifre che hai dato e significa che i tuoi 30 milioni di righe avranno 1,8 GB.

Suggerisco che invece di usare python si usi l'utilità di ordinamento unix. Io non sono un Mac-head, ma presumo le opzioni di ordinamento OS X sono gli stessi della versione di Linux, quindi questo dovrebbe funzionare:

sort -n -t, -k2 links.csv 

-n significa sorta numericamente

-t, significa utilizzare una virgola come separatore di campo

-k2 significa ordinamento secondo campo

Ciò ordinerà il file e scrivere il risultato su stdout. Potresti reindirizzare a un altro file o collegarlo al tuo programma python per eseguire un'ulteriore elaborazione.

edit: Se non si desidera ordinare il file prima di eseguire lo script python, è possibile utilizzare il modulo sottoprocesso per creare un tubo per l'utilità shell sort, quindi leggere i risultati ordinati dall'uscita del tubo .

Answer 5

Si potrebbe desiderare di guardare mmap:

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

E lascerò trattare il file come un grande array di/string e otterrete il sistema operativo per gestire mischiare dati all'interno e all'esterno della memoria a lascia che si adatti

Quindi è possibile leggere il file csv, una riga alla volta, quindi scrivere i risultati in un file mmap'd (in un formato binario adatto), quindi lavorare sul file mmap'd. Poiché il file mmap'd è solo temporaneo, potresti ovviamente creare un file tmp a questo scopo.

Ecco alcuni codice che utilizzano demo mmap con un tempfile per leggere nei dati csv e lo immagazzinano come coppia di numeri interi:

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) 

E 'un po' ruvido però. Veramente probabilmente vorrai concludere tutto con una bella lezione, in modo da poter accedere ai tuoi bordi in un modo che li faccia comportare come una lista (con indicizzazione, len ecc.). Spero che abbia pensato di darti un punto di partenza.

Answer 6

ho creato un modulo per questo caso d'uso utilizzando external merge sort: https://bitbucket.org/richardpenman/csvsort

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