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

Ответ 1

Существует рецепт для сортировки файлов размером более RAM на этой странице, хотя вам придется адаптировать его для вашего случая с использованием CSV- формат данных. Существуют также ссылки на дополнительные ресурсы.

Изменить: Правда, файл на диске не "больше, чем ОЗУ", но представление в памяти может легко стать намного больше, чем доступная оперативная память. Во-первых, ваша собственная программа не получает всего 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, который, кстати, я использовал как единственный способ, с помощью которого можно было сортировать столбцы вместе, а не по умолчанию, которые будут сортировать их независимо (полностью испортить ваши данные).

Ответ 2

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

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

sort -n -t, -k2 links.csv

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

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

-k2 означает сортировку по второму полю

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

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

Ответ 3

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

Ответ 4

Самый дешевый способ хранения входных строк в памяти - это элементы 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 памяти, выраженная в часах по вашей ставке заработной платы?

Ответ 5

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

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

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

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

Вот некоторый код, который демонстрирует использование mmap с временным файлом для чтения в данных 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 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 и т.д.). Надеюсь, это даст вам отправную точку.

Ответ 6

Я создал модуль для этого прецедента, используя внешнюю сортировку слияния: https://bitbucket.org/richardpenman/csvsort

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