Какой алгоритм использовать для удаления дубликатов?

Question

Представьте, что у нас есть какой-то файл, который называется, например, «A.txt». Мы знаем, что являются некоторыми дублирующимися элементами. «A.txt» имеет размер очень , больше чем в десять раз больше памяти, может быть, около 50 ГБ. Иногда размер B будет примерно равен размеру A, иногда он будет в много раз меньше размера A. Пусть оно имеет такую ​​структуру:

a 1
b 2
c 445
a 1

Нам нужно получить файл «B.txt», в котором не будет таких дубликатов. Как пример, это должно быть так:

a 1
b 2
c 445

Я думал об алгоритме, который копирует A и выполняет B, затем берет первую строку в B и ищет друг друга, если находит то же самое, удаляет дубликаты. Затем занимает вторую строку и т. Д.

Но я думаю, что слишком слишком медленно. Что я могу использовать?

A - это , а не база данных! Нет SQL, пожалуйста.

Извините, но ничего не сказано, сортировка в порядке.

Несмотря на то, что он может быть отсортирован, что делать, если он не может быть отсортирован?

Answer 1

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

Тогда возникает вопрос: как отсортировать слишком большой файлвписаться в память?

Вот как Unix sort это делает .

См. также этот вопрос .

Answer 2

Предположим, что вы можете поместить 1/k '-й файл в память и по-прежнему иметь место для рабочих структур данных.Весь файл может быть обработан за k или меньше проходов, как показано ниже, и это может быть намного быстрее, чем сортировка всего файла в зависимости от длины строки и констант алгоритма сортировки.Средние значения сортировки O(n ln n), а процесс ниже - O(k n) наихудший случай.Например, если строки содержат в среднем 10 символов и n = 5G строк, ln(n) ~ 22.3.Кроме того, если ваш выходной файл B намного меньше входного файла A, процесс, вероятно, займет всего один или два прохода.

Процесс:

1. Распределитьнесколько мегабайт для буфера ввода I, несколько гигабайт для буфера результатов R и около гигабайта для хэш-таблицы H. Откройте входной файл F и выходной файл O.
2. Повтор: Заполните I из F иобработайте его в R с помощью шага 3.
3. Для каждой строки L в I проверьте, находится ли L уже в H и R. Если это так, переходите к следующему L, иначе добавьте L к R и его хеш кH.
4. Когда R заполнен, скажем, с помощью M записей, записать его в O. Затем повторно заполнить I из F, выполнить дедупликацию, как в шаге 3, и записать в O. При EOF (F) перейдите к 5.
5. Повтор (с использованием старого O в качестве входа F и нового O для вывода): прочитайте M строк из F и скопируйте в O. Затем загрузите R и H, как в шагах 2 и 3, и скопируйте в EOF (F) с дедупликацией, как и раньше.Установите для M новое число неперехваченных строк в начале каждого файла O.

Обратите внимание, что после каждого прохода первые M строк O не содержат дубликатов, и ни одна из этих M строкдублируются в остальной части O. Таким образом, по крайней мере 1/k '-й исходный файл обрабатывается за проход, поэтому обработка занимает максимум k проходов.

Обновление 1 Вместо того, чтобы многократно записывать и читать обратно в уже обработанные начальные строки, следует использовать отдельный выходной файл P, к которому добавляется буфер процесса R в конце каждого прохода.Это сокращает количество операций чтения и записи в k/2, когда файл результатов B почти равен A, или несколько меньше, когда B намного меньше A;но ни в коем случае это не увеличивает количество операций ввода-вывода.

Answer 3

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

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

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

Или вы можете просто добавить отметку к исходным данным независимо от того, будет ли запись включена.

(Также рассмотрите возможность использования эффективного формата хранения, такого как NetCDF для двоичных данных, поскольку текстовое представление намного медленнее для доступа и обработки.)