Обобщая огромные объемы данных

Question

У меня есть проблема, которую я не смог решить. У меня есть 4 .txt файлы каждый между 30-70 ГБ. Каждый файл содержит n-граммовые записи следующим образом:

blabla1/blabla2/blabla3
word1/word2/word3
...

Я пытаюсь подсчитать, сколько раз появляется каждый элемент, и сохранить эти данные в новом файле, например:

blabla1/blabla2/blabla3  : 1
word1/word2/word3        : 3
...

До сих пор я пытался просто сохранить все записи в словаре и сосчитать их, т.е.

entry_count_dict = defaultdict(int)
with open(file) as f:
    for line in f:
        entry_count_dict[line] += 1

Однако, используя этот метод, я сталкиваюсь с ошибками памяти (у меня доступно 8 ГБ ОЗУ). Данные следуют распределению по Зипфиану, например большинство предметов встречаются только один или два раза. Общее количество записей неясно, но (очень) приблизительная оценка состоит в том, что всего около 15 000 000 записей.

В дополнение к этому я пробовал h5py, где все записи сохраняются в виде набора данных h5py, содержащего массив [1], который затем обновляется, например:

import h5py
import numpy as np

entry_count_dict = h5py.File(filename)
with open(file) as f:
    for line in f:
        if line in entry_count_dict:
            entry_count_file[line][0] += 1
        else:
            entry_count_file.create_dataset(line, 
                                            data=np.array([1]),
                                            compression="lzf")

Однако этот метод является медленным. Скорость записи становится все медленнее и медленнее. Таким образом, если скорость записи не может быть увеличена, такой подход неправдоподобен. Кроме того, обработка данных в чанках и открытие / закрытие файла h5py для каждого чанка не показали существенной разницы в скорости обработки.

Я думал о сохранении записей, которые начинаются с определенных букв, в отдельных файлах, то есть все записи, которые начинаются с a, сохраняются в a.txt и т. Д. (Это можно сделать, используя defaultdic(int)) , Однако для этого файл должен повторяться один раз для каждой буквы, что неправдоподобно, учитывая размеры файла (макс. = 69 ГБ). Возможно, перебирая файл, можно открыть соленье и сохранить запись в диктовке, а затем закрыть солку. Но выполнение этого для каждого элемента значительно замедляет процесс из-за времени, которое требуется для открытия, загрузки и закрытия файла pickle.

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

sort file.txt > sorted_file.txt

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

Любые советы о том, как подойти к этому, будут высоко оценены.

Answer 1

Я думал о сохранении записей, которые начинаются с определенных букв, в отдельных файлах, то есть все записи, начинающиеся с a, сохраняются в формате .txt и т. Д. (Это должно быть выполнено с использованием defaultdic (int)). Однако для этого файл должен повторяться один раз для каждой буквы, что неправдоподобно, учитывая размеры файла (макс. = 69 ГБ).

Вы почти там с этим мышлением. То, что вы хотите сделать, это разделить файл на основе префикса - вам не нужно итерировать один раз для каждой буквы. Это тривиально в awk. Предполагая, что ваши входные файлы находятся в каталоге с именем input:

mkdir output
awk '/./ {print $0 > ( "output/"  substr($0,0,1))}` input/*

Это добавит каждую строку в файл с именем, в котором указан первый символ этой строки (обратите внимание, это будет странно, если ваши строки могут начинаться с пробела; так как это ngram, я полагаю, это не имеет значения). Вы также можете сделать это в Python, но управление открытием и закрытием файлов несколько более утомительно.

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

from collections import Counter

ngrams = Counter()
for line in open(filename):
    ngrams[line.strip()] += 1
for key, val in ngrams.items():
    print(key, val, sep='\t')

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

Answer 2

Существует ряд алгоритмов для выполнения этого типа операции. Все они подпадают под общий заголовок Внешняя сортировка .

То, что вы сделали там с «сохранением записей, начинающихся с определенных букв в отдельных файлах», на самом деле называется сортировкой по группам, что, по идее, должно быть быстрее. Попробуйте это с нарезанными наборами данных.

или, попробуйте Dask , библиотеку распределенных вычислений с поддержкой DARPA + Anaconda, с интерфейсами, знакомыми numpy, pandas, и работает как Apache-Spark. (работает на одной машине тоже) кстати это весы

Я предлагаю попробовать dask.array , который разбивает большой массив на множество маленьких, и реализует неповоротливый интерфейс ndarray с заблокированными алгоритмами, чтобы использовать все ваши ядра при вычислении этих данных, превышающих объем памяти.