Python: как читать огромный текстовый файл в памяти

Question

Я использую Python 2.6 на Mac Mini с 1 ГБ оперативной памяти. Я хочу, чтобы прочитать в огромном текстовом файле

$ 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 

Таким образом, каждая строка в файле состоит из набора из двух разделенных запятыми целочисленных значений. Я хочу прочитать весь файл и отсортировать его по второму столбцу. Я знаю, что я мог бы сортировать, не читая весь файл в памяти. Но я думал, что для файла размером 500 МБ я все равно могу сделать это в памяти, так как у меня есть 1 ГБ.

Однако, когда я пытаюсь прочитать в файле, Python, похоже, выделяет намного больше памяти, чем требуется файлу на диске. Поэтому даже с 1 ГБ оперативной памяти я не могу читать в 500 МБ файл в памяти. Моего код Python для чтения файла и печатей информации о потреблении памяти является:

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

Выхода я получил:

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 

Уже после прочтения только 25% файл 500MB, Python потребляет 500 МБ. Похоже, что сохранение содержимого файла в виде списка кортежей ints не очень эффективно. Есть ли лучший способ сделать это, чтобы я мог читать в своем 500 МБ файле в 1 ГБ памяти?

Answer 1

Существует рецепт сортировки файлов, размер которых превышает ОЗУ on this page, хотя вам придется адаптировать его для вашего случая с использованием данных в формате CSV. Есть также ссылки на дополнительные ресурсы.

Edit: Правда, файл на диске не «больше оперативной памяти», но представление в памяти может легко стать гораздо больше, чем доступной оперативной памяти. Во-первых, ваша собственная программа не получает всего 1 ГБ (накладные расходы ОС и т. Д.). Для другого, даже если вы сохранили это в самой компактной форме для чистого Python (два списка целых чисел, предполагая 32-разрядную машину и т. Д.), Вы бы использовали 934 МБ для этих 30M пар целых чисел.

Используя numpy, вы также можете выполнить эту работу, используя только около 250 МБ. Это не особенно быстро, чтобы загрузить этот путь, как вы должны сосчитать линии и предварительно выделить массив, но это может быть самый быстрый фактический сорт, учитывая, что это в памяти:

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

Выход на моем машина с файлом образца аналогично тому, что вы показали:

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

по умолчанию в NumPy является Quicksort. Процедура ndarray.sort() (которая сортируется на месте) также может принимать аргумент ключевого слова kind="mergesort" или kind="heapsort", но, похоже, ни одна из них не способна сортировать по Record Array, который, кстати, я использовал как единственный способ, который я мог видеть для сортировки столбцы вместе в отличие от по умолчанию, которые будут сортировать их независимо (полностью испортить ваши данные).

Answer 2

Поскольку все это всего лишь цифры, загрузка их в массив Nx2 приведет к удалению некоторых служебных данных. Используйте NumPy для многомерных массивов. В качестве альтернативы вы можете использовать два обычных питона arrays для представления каждого столбца.

Answer 3

Самый дешевый способ хранения входных строк в памяти - это элементы array.array ('i') - если каждый номер будет соответствовать подписанному 32-битовому целому.Стоимость памяти будет 8N байтов, где N - количество строк.

Вот как сделать сортировку и записать выходной файл в отсортированном порядке:

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

К сожалению sorted() возвращает список, а не итератор, и этот список будет довольно большим: 4N байт для указателей и 12N байтов для объектов int, т.е. 16N байтов для вывода sorted(). Примечание: это основано на CPython 2.X на 32-битной машине; он становится хуже для каждой из 3.X и 64-битных машин. Все это 24N байт. У вас есть 31 миллион строк, поэтому вам нужно 31 * 24 = 744 МБ ... похоже, что он должен работать; обратите внимание, что этот расчет не позволяет выделить какую-либо память, выделенную сортировкой, но у вас есть разумный запас прочности.

Помимо этого: Какова стоимость дополнительного ГБ или 3 памяти, выраженная в часах по вашей ставке заработной платы?

Answer 4

Все объекты python имеют накладные расходы памяти поверх данных, которые они фактически хранят. Согласно getizeof на моей 32-битной системе Ubuntu, кортеж имеет накладные расходы в 32 байта, а int занимает 12 байт, поэтому каждая строка в вашем файле занимает 56 байтов + указатель на 4 байта в списке - я полагаю, что это будет много больше для 64-битной системы. Это соответствует цифрам, которые вы дали, и означает, что ваши 30 миллионов строк будут потреблять 1,8 ГБ.

Я предлагаю, чтобы вместо использования python вы использовали утилиту сортировки unix. Я не Mac-голова, но я полагаю, что опции OS X сортировать те же версии Linux, так что это должно работать:

sort -n -t, -k2 links.csv 

-n означает сортировку численно

-t, значит использовать запятую в качестве разделителя полей

-к2 означает то на втором поле

Это сортирует файл и записать результат в стандартный вывод. Вы можете перенаправить его в другой файл или передать его программе python для дальнейшей обработки.

Редактировать: Если вы не хотите сортировать файл перед запуском своего скрипта python, вы можете использовать модуль подпроцесса для создания канала в утилите сортировки оболочки, а затем прочитать отсортированные результаты на выходе канала ,

Answer 5

Вы можете посмотреть на ттар:

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

Это будет препятствовать вам обработать файл, как большой массив/строку и получит операционную систему для обработки перетасовки данных в и из памяти пусть это подойдет.

Итак, вы можете прочитать в файле csv по одной строке за один раз, затем записать результаты в файл mmap'd (в соответствующем двоичном формате), а затем работать с файлом mmap'd. Поскольку файл mmap'd является временным, вы, конечно, можете просто создать файл tmp для этой цели.

Вот код, который демки с использованием ММАП с TempFile для чтения в данных CSV и сохранить его в виде пары целых чисел:

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) 

Это немного грубый, хотя. На самом деле вы, вероятно, захотите обернуть все это с помощью хорошего класса, чтобы доступ к вашему краю мог быть таким, чтобы заставить их вести себя как список (с индексированием, len и т. Д.). Надеюсь, это даст вам отправную точку.

Answer 6

Я создал модуль для этого случая использования с помощью external merge sort: https://bitbucket.org/richardpenman/csvsort

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