Python: сортировка большого списка, который не помещается в памяти

Question

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

ID  DocType NormalizedName  DisplayName Year    Description
12648   Book    a fancy title   A FaNcY-Title   2005    This is a short description of the book
1867453 Essay   on the history of humans    On the history of humans    2016    This is another short description, this time of the essay
...

Дефлированная версия этого файла - около 67 ГБ, сжатая - около 22 ГБ.

Я хотел бы отсортировать строки файла на основе идентификатора (около 300 миллионов строк) в порядке возрастания. Идентификатор каждой строки уникален и варьируется от 1 до 2147483647 (положительная часть long), могут быть пробелы.

К сожалению, у меня есть максимум 8 ГБ доступной памяти, поэтому я не смогу загрузить весь файл сразу.

Как наиболее эффективно отсортировать этот список и записать его обратно на диск?

Answer 1

Я сделал доказательство концепции, используя heapq.merge:

Шаг 1: создать тестовый файл

Создать тестовый файл, содержащий 300 миллионов строк:

from random import randint
row = '{} Essay   on the history of humans    On the history of humans    2016    This is another short description, this time of the essay\n'
with open('large_file.tsv', 'w') as f_out:
    for i in range(300_000_000):
        f_out.write(row.format(randint(1, 2147483647)))

Шаг 2: разбить на куски и отсортировать каждый кусок

Каждый кусок имеет 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(f, key=lambda k: int(k.split()[0]))
        f_out.writelines(lines)
        f_out.close()
        lines = []

Шаг 3: объединить каждый кусок

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

Тайминги:

Моя машина - Ubuntu Linux 18.04, AMD 2400G, дешевый WD SSD Green)

Шаг 2 - разделение и сортировка фрагментов - заняло ~ 12 минут

Шаг 3 - объединение фрагментов - заняло ~ 10 минут

Я ожидаю, что эти значения будут намного ниже на машине с лучшим диском (NVME?) И процессором.