Удалить дублирующиеся строки из большого файла в Python

Ваше исходное решение немного неверно: у вас могут быть разные строки, хеширующие одно и то же значение (хеш-коллизия), и ваш код оставит одну из них.

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

Между прочим, если значения CSV нормализованы (т. Е. Записи считаются равными, если соответствующие строки CSV эквивалентны побайтно), вам вообще не нужно включать здесь синтаксический анализ CSV, просто работайте со строками простого текста. .

По сути, вы выполняете сортировку слиянием и удаляете дублирующиеся записи.

Разбиение входных данных на части размером с память, сортировка каждой части, затем объединение частей с удалением дубликатов - в целом здравая идея.

На самом деле, до пары гигов я бы позволил системе виртуальной памяти справиться с этим и просто написал:

input = open(infilename, 'rb')
output = open(outfile, 'wb')

for key,  group in itertools.groupby(sorted(input)):
    output.write(key)

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

Считывать строки ввода в B-деревья, упорядоченные по хэш-значению каждой строки ввода, записывая их на диск при заполнении памяти. Мы заботимся о том, чтобы сохранить на B-деревьях исходные строки, прикрепленные к хешу (как набор, поскольку мы заботимся только об уникальных строках). Когда мы читаем повторяющийся элемент, мы проверяем строки, установленные для сохраненного элемента, и добавляем его, если это новая строка, которая имеет хэш с тем же значением.

Почему B-деревья? Они требуют меньше операций чтения с диска, когда вы можете (или хотите) читать их в память только частично. Степень (количество дочерних элементов) на каждом узле зависит от доступной памяти и количества строк, но вы не хотите иметь слишком много узлов.

Когда у нас есть эти B-деревья на диске, мы сравниваем самый нижний элемент каждого из них. Мы удаляем самый низкий из всех B-деревьев, у которых он есть. Мы объединяем их наборы строк, что означает, что у нас не осталось дубликатов для этих строк (а также что у нас больше нет строк, которые хешируют это значение). Затем мы записываем строки из этого слияния в выходную структуру csv.

Мы можем отделить половину памяти для чтения B-деревьев и половину, чтобы сохранить выходной CSV в памяти в течение некоторого времени. Мы сбрасываем csv на диск, когда его половина заполнена, добавляя к тому, что уже было записано. Количество каждого B-дерева, которое мы читаем на каждом шаге, можно приблизительно рассчитать с помощью (available_memory / 2) / number_of_btrees, округленного таким образом, чтобы мы читали полные узлы.

В псевдо-Python:

ins = DictReader(...)
i = 0
while ins.still_has_lines_to_be_read():
    tree = BTree(i)
    while fits_into_memory:
        line = ins.readline()
        tree.add(line, key=hash)
    tree.write_to_disc()
    i += 1
n_btrees = i

# At this point, we have several (n_btres) B-Trees on disk
while n_btrees:
    n_bytes = (available_memory / 2) / n_btrees
    btrees = [read_btree_from_disk(i, n_bytes)
              for i in enumerate(range(n_btrees))]
    lowest_candidates = [get_lowest(b) for b in btrees]
    lowest = min(lowest_candidates)
    lines = set()
    for i in range(number_of_btrees):
        tree = btrees[i]
        if lowest == lowest_candidates[i]:
            node = tree.pop_lowest()
            lines.update(node.lines)
        if tree.is_empty():
        n_btrees -= 1

    if output_memory_is_full or n_btrees == 0:
        outs.append_on_disk(lines)

Как насчет использования модуля heapq для чтения фрагментов файла до предела памяти и записи их отсортированными фрагментами (heapq сохраняет все в отсортированном порядке).

Или вы можете поймать первое слово в строке и разделить им файл на части. Затем вы можете прочитать строки (возможно, сделать '' .join (line.split ()), чтобы унифицировать интервалы / табуляции в строке, если можно изменить интервал) в наборе в алфавитном порядке, очищая набор между частями (набор удаляет дубликаты), чтобы все было наполовину отсортировано (набор не в порядке, если вы хотите, вы можете прочитать в кучу и записать, чтобы получить отсортированный порядок, последнее вхождение в наборе заменяет старые значения по ходу.) В качестве альтернативы вы также можете отсортировать кусок и удалите повторяющиеся строки с помощью группового решения Джо Коберга. Наконец, вы можете соединить части вместе (вы, конечно, можете писать по мере перехода к окончательному файлу по частям во время сортировки частей)

Ваш текущий метод не гарантирует правильной работы.

Во-первых, существует небольшая вероятность того, что две фактически разные строки могут дать одно и то же значение хеш-функции. hash (a) == hash (b) не всегда означает, что a == b

Во-вторых, вы увеличиваете вероятность с помощью каперса "reduce / lambda":

>>> reduce(lambda x,y: x+y, ['foo', '1', '23'])
'foo123'
>>> reduce(lambda x,y: x+y, ['foo', '12', '3'])
'foo123'
>>>

Кстати, разве "" .join (['foo', '1', '23']) не будет более ясным?

Кстати, почему бы не использовать набор вместо ] dict для htable ?

Вот практическое решение: получите пакет "core utils" с сайта GnuWin32 и установите его. Затем:

1. запишите копию вашего файла без заголовков в (скажем) infile.csv
2. c: \ gnuwin32 \ bin \ sort --unique -ooutfile.csv infile.csv
3. прочтите Outfile.csv и напишите копию с добавленными заголовками

Для каждого из шагов 1 и 3 вы можете использовать скрипт Python или некоторые другие утилиты GnuWin32 (голова, хвост, тройник, кошка, ...).