Опубликовано

Как отсортировать огромный файл

У меня есть файл .tsv приличного размера, содержащий документы в следующем формате

ID  DocType NormalizedName  DisplayName Yea
12648   Book    a fancy title   A FaNcY-Title   2005
1867453 Essay   on the history of humans    On the history of humans    2016
...

Этот файл имеет размер около 67 ГБ, в сжатом виде около 22 ГБ. Я хотел бы отсортировать строки файла по идентификатору (около 300 миллионов строк) в порядке возрастания. Идентификатор каждой строки уникален и варьируется от 1 до 2147483647, могут быть пробелы. Взять и загрузить файл целиком в оперативную память не представляется возможным из-за его огромного размера. Возник вопрос как наиболее эффективно отсортировать все строки таблицы.

  1. Читаем файл частями по миллиону строк
import glob

path = "chunk_*.tsv"

chunksize = 1_000_000
fid = 1
lines = []

with open('large_file.tsv', 'r') as f_in:
    f_out = open('chunk_{}.tsv'.format(fid), 'w')
    for line_num, line in enumerate(f_in, 1):
        lines.append(line)
        if not line_num % chunksize:
            lines = sorted(lines, key=lambda k: int(k.split()[0]))
            f_out.writelines(lines)

            print('splitting', fid)
            f_out.close()
            lines = []
            fid += 1
            f_out = open('chunk_{}.tsv'.format(fid), 'w')

    # last chunk
    if lines:
        print('splitting', fid)
        lines = sorted(lines, key=lambda k: int(k.split()[0]))
        f_out.writelines(lines)
        f_out.close()
        lines = []

2. Объединяем отсортированные чанки

from heapq import merge

chunks = []
for filename in glob.glob(path):
    chunks += [open(filename, 'r')]

with open('sorted.tsv', 'w') as f_out:
    f_out.writelines(merge(*chunks, key=lambda k: int(k.split()[0])))

heapq.merge() возвращает генератор, который работает поверх исходных коллекций — поэтому не расходует лишнюю память. И он учитывает, что исходные списки уже отсортированы — поэтому не выполняет лишних действий.