Python: Wie man riesige Textdatei in den Speicher liest

Question

Ich benutze Python 2.6 auf einem Mac Mini mit 1 GB RAM. Ich möchte eine große Textdatei einlesen

$ 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 

Also jede Zeile in der Datei besteht aus einem Tupel von zwei durch Kommas getrennten Integer-Werten. Ich möchte die ganze Datei einlesen und nach der zweiten Spalte sortieren. Ich weiß, dass ich die Sortierung durchführen kann, ohne die ganze Datei in den Speicher zu schreiben. Aber ich dachte für eine Datei von 500MB sollte ich noch in der Lage sein, es im Speicher zu tun, da ich 1GB zur Verfügung habe.

Wenn ich jedoch versuche, die Datei einzulesen, scheint Python viel mehr Speicher zuzuweisen, als von der Datei auf der Festplatte benötigt wird. Also selbst mit 1GB RAM kann ich die 500MB Datei nicht in den Speicher einlesen. Mein Python-Code für die Datei zu lesen und drucken einige Informationen über den Speicherverbrauch ist:

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

Der Ausgang ich erhielt, war:

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 

Bereits nach nur 25% der 500 MB-Datei zu lesen, Python verbraucht 500 MB. Es scheint also, dass das Speichern des Inhalts der Datei als eine Liste von Tupeln von Ints nicht sehr speichereffizient ist. Gibt es einen besseren Weg, es zu tun, so dass ich meine 500 MB-Datei in meinen 1 GB Speicher einlesen kann?

Answer 1

Es gibt ein Rezept zum Sortieren von Dateien größer als RAM on this page, obwohl Sie es für Ihren Fall mit Daten im CSV-Format anpassen müssen. Dort finden Sie auch Links zu weiteren Ressourcen.

Edit: Es stimmt, die Datei auf der Festplatte ist nicht „größer als RAM“, aber die In-Memory-Darstellung kann leicht werden viel größer als verfügbar RAM. Zum einen bekommt Ihr eigenes Programm nicht die gesamten 1 GB (OS Overhead etc.). Zum anderen, selbst wenn Sie dies in der kompaktesten Form für reines Python (zwei Listen von ganzen Zahlen, unter Annahme einer 32-Bit-Maschine usw.) speichern, würden Sie 934 MB für diese 30M-Paare von ganzen Zahlen verwenden.

Mit numpy können Sie auch den Job erledigen, nur mit ca. 250MB. Es ist nicht besonders schnell auf diese Weise zu laden, wie Sie die Linien und pre-zuteilen das Array zählen, aber es kann die schnellste tatsächliche Art gegeben sein, dass es im Speicher:

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

Ausgabe auf meinem Maschine mit einer Beispieldatei ähnlich dem, was Sie zeigte:

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

Der Standard in numpy ist Quicksort. Die Routine ndrarray.sort() (die in-place sortiert) kann auch das Schlüsselwortargument kind="mergesort" oder kind="heapsort" nehmen, aber es scheint, dass keiner von diesen in der Lage ist, auf einer Record Array zu sortieren, die ich übrigens als einzige Möglichkeit nutzte, um zu sortieren die Spalten zusammen im Gegensatz zu den Standard, der sie unabhängig sortieren würde (total durcheinander Ihre Daten).

Answer 2

Da dies alles nur Zahlen sind, würde das Laden in ein Nx2-Array einige Overhead entfernen. Verwenden Sie NumPy für mehrdimensionale Arrays. Alternativ könnten Sie zwei normale Python arrays verwenden, um jede Spalte darzustellen.

Answer 3

Der günstigste Weg, die Eingangszeilen im Speicher zu speichern, ist array.array ('i') - vorausgesetzt, dass jede Zahl in eine 32-Bit-Ganzzahl mit Vorzeichen passt.Die Speicherkosten betragen 8N Bytes, wobei N die Anzahl der Zeilen ist.

Hier ist, wie die Art zu tun, und die Ausgabedatei in sortierter Reihenfolge schreiben:

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

Leider sorted() gibt eine Liste, nicht einen Iterator, und diese Liste wird ziemlich groß: 4N für Zeiger-Bytes und 12N Bytes für int Objekte, dh 16N Bytes für den sorted() Ausgang. Hinweis: Dies basiert auf CPython 2.X auf einem 32-Bit-Rechner. es wird für jede 3.X- und 64-Bit-Maschine schlimmer. Alles zusammen sind 24N Bytes. Du hast 31 Millionen Zeilen, also brauchst du 31 * 24 = 744 MB ... sieht so aus als ob es funktionieren sollte; Beachten Sie, dass diese Berechnung keinen durch die Sortierung zugewiesenen Speicher zulässt, aber Sie eine angemessene Sicherheitsmarge haben.

Beiseite: Was kostet eine zusätzliche GB oder 3 Speicher in Stunden zu Ihrem Gehaltssatz ausgedrückt?

Answer 4

Alle Python-Objekte haben einen Speicher-Overhead über den Daten, die sie tatsächlich speichern. Laut getsizeof auf meinem 32-Bit-Ubuntu-System hat ein Tupel einen Overhead von 32 Bytes und ein int braucht 12 Bytes, also nimmt jede Zeile in Ihrer Datei einen 56 Bytes + einen 4-Byte-Zeiger in der Liste - ich nehme an, es wird viel mehr für ein 64-Bit-System. Dies entspricht den von Ihnen angegebenen Zahlen und bedeutet, dass Ihre 30 Millionen Zeilen 1,8 GB benötigen.

Ich schlage vor, dass Sie anstelle von Python verwenden Sie die Unix-Sortierfunktion. Ich bin kein Mac-Kopf, aber ich nehme an den OS X Sortieroptionen das gleiche der Linux-Version sind, so sollte diese Arbeit:

sort -n -t, -k2 links.csv 

-n bedeutet sort numerisch

-t, bedeutet ein Komma als Feldtrennmittel

-K2 Sortierung auf dem zweiten Feld

Dadurch wird die Datei sortiert werden und das Ergebnis an stdout schreiben. Sie könnten es in eine andere Datei umleiten oder es zu Ihrem Python-Programm leiten, um die weitere Verarbeitung durchzuführen. Wenn Sie die Datei vor dem Ausführen des Python-Skripts nicht sortieren möchten, können Sie das Unterprozessmodul verwenden, um eine Pipe zum Shell-Sortier-Dienstprogramm zu erstellen, und dann die sortierten Ergebnisse aus der Ausgabe der Pipe lesen .

Answer 5

Sie könnten Mmap aussehen wollen:

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

Es wird können Sie die Datei wie ein großes Array/string behandeln und wird die OS-Daten zu verarbeiten bekommen schlurfen in und Speicher heraus lass es passen.

So könnten Sie in der CSV-Datei, Zeile für Zeile lesen Sie dann die Ergebnisse in eine mmap'd-Datei (in einem geeigneten Binärformat), dann arbeiten Sie auf der mmap'd-Datei. Da die mmap'd-Datei nur temporär ist, könnten Sie natürlich einfach eine tmp-Datei für diesen Zweck erstellen.

Hier einige Code, die Demo mmap mit einem temporären Datei mit in csv Daten zu lesen und speichern Sie es als Paar von ganzen Zahlen:

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) 

Es ist zwar ein wenig rau. Wirklich, du würdest wahrscheinlich all das mit einer netten Klasse einpacken wollen, so dass auf deine Edge zugegriffen werden kann, so dass sie sich wie eine Liste verhalten (mit Indizierung, Len usw.). Hoffentlich dachte es dir einen Startpunkt.

Answer 6

habe ich ein Modul für diesen Fall den Einsatz mit external merge sort: https://bitbucket.org/richardpenman/csvsort

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