Работа со списками на миллион строк без падения памяти

Прилетел список на 1.2 миллиона строк, надо выкинуть повторы, отсортировать и сравнить со вчерашним. Скрипт на питоне читал всё в set, машина уходила в своп и висла намертво.

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

Миллион строк это не объём. Это sort -u и десять секунд.

Поддержу, только с оговоркой про локаль. Без неё сортировка на кириллице и на смешанных строках еле ползёт, потому что сравнение идёт по правилам языка.

Не знал вообще. У меня как раз кириллица в половине строк.

а если строки надо не просто выкинуть а посчитать сколько раз каждая встретилась

Тогда sort и uniq -c, дальше по вкусу.

$ LC_ALL=C sort spisok.txt | uniq -c | sort -rn | head -20

Первый sort обязателен: uniq считает только соседние повторы, разбросанные по файлу он не увидит.

Раз тема пошла, разложу по памяти, почему питон здесь и падает.

Строка в питоне это объект. Пустая строка занимает под полсотни байт сама по себе, дальше плюс длина. Положили в set, добавьте ещё указатель и накладные расходы таблицы, а таблица держит запас свободных ячеек, иначе она вырождается. На практике миллион коротких строк в set обходится в двести с лишним мегабайт. Полтора миллиона длинных адресов уже под гигабайт.

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

Если питон нужен по другим причинам, есть середина. Считайте короткую свёртку строки, восемь байт вместо полусотни, саму строку в память класть незачем.

import hashlib
vidano = set()
with open("spisok.txt", "rb") as f, open("out.txt", "wb") as o:
    for s in f:
        h = hashlib.blake2b(s.strip(), digest_size=8).digest()
        if h not in vidano:
            vidano.add(h)
            o.write(s)

Память на том же миллионе падает примерно вчетверо. Не бесплатно: теоретически возможны совпадения свёрток, но на таких объёмах это событие настолько редкое, что им спокойно пренебрегают.

Свёртку попробую, хотя по факту питон мне тут и не сдался. Всю подготовку увёл в утилиты, а разбор оставил скрипту, который уже читает готовый отсортированный файл построчно.

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

$ LC_ALL=C sort -u vchera.txt > a.txt
$ LC_ALL=C sort -u segodnya.txt > b.txt
$ comm -13 a.txt b.txt > novye.txt
$ comm -23 a.txt b.txt > propali.txt

о, про comm не знала, всегда питоном сравнивала

Ещё пара мелочей, которые экономят время на больших файлах.

• sort -S 2G даёт сортировке больше памяти под кусок, временных файлов становится меньше;
• -T /put уводит временные файлы туда, где есть место, иначе они лягут в /tmp и переполнят его;
• --parallel=4 включает несколько потоков, на многоядерной машине разница ощутимая;
• wc -l до и после сортировки за пару секунд показывает, сколько повторов было.

Про -T подпишусь двумя руками. У нас так на сервере закончилось место посреди ночи, и причина сидела ровно во временных файлах.

Собрал короткий порядок по теме, мои 1.2 миллиона проходят за минуту с небольшим.

Питон остался только на последнем шаге. Память держится в районе сорока мегабайт и вверх не идёт. Спасибо всем.