Найти повторяющиеся строки в большом файле

Файл содержит большое количество (например, 10 миллиардов) строк, и вам нужно найти повторяющиеся строки. У вас есть N доступных систем. Как вы найдете дубликатыНайти повторяющиеся строки в большом файле

источник

2010-10-09 Tushar Gupta

Это домашнее задание? Это звучит как домашнее задание. – SoapBox

Разделите файл на N штук. На каждой машине загрузите как можно больше фрагмента в память и отсортируйте строки. Напишите эти куски для массового хранения на этой машине. На каждой машине объедините куски в один поток, а затем объедините поток с каждой машины в поток, содержащий все строки в отсортированном порядке. Сравните каждую строку с предыдущей. Если они одинаковы, это дубликат.

источник

2010-10-09 18:26:14 erickson

Чтобы объединить куски в один поток, вам придется загружать все записи в память. Для файла с 1 мильной записью все записи на 1 мил должны быть в памяти на последнем шаге слияния в вышеуказанном алгоритме? Если да, то это побеждает цель. –

@AndyDufresne «Чтобы объединить куски в один поток, вам придется загружать все записи в память». Нет, нет. Вам нужно только достаточно памяти для загрузки следующей строки из каждого фрагмента одновременно, чтобы сравнить их. Как только сравнение будет выполнено, следующая строка займет это пространство памяти. – erickson

Я не понял ваш алгоритм слияния. Скажем, у нас есть 1 миллионный файл записи, и в память можно загрузить только 5k записей. Из того, что я понял, мне нужно сначала разделить файл на N штук с 5K записей каждый. Затем отсортируйте все записи в каждом файле 5k записей и напишите обратно. Чтобы объединить два файла записи 5k, мне нужно было бы загрузить 10k записей в памяти? Если это не то, что вы имели в виду, можете ли вы объяснить шаги, чтобы найти дубликаты записей в файле с 1 миллионом с ограничением памяти для загрузки только 5k записей. –

Ответ эриксона, вероятно, тот, кого ожидал тот, кто задал этот вопрос.

Вы можете использовать каждый из машин N как ведро в Hashtable:

для каждой строки (скажем, номер строки я в последовательности) вычислить хэш-функцию на нем, ч.
отправьте значения i и h на номер машины n для хранения, где n = h% N.
с каждой машины, получить список всех значений хэша h, для которых было получено более одного индекса, вместе со списком индексов.
проверять наборы строк с равными значениями хеша, чтобы убедиться, что они на самом деле равны.

Если честно, то для 10 миллиардов строк вы могли бы правдоподобно сделать это на 1 ПК. Хэш-таблица может занимать примерно 80-120 ГБ с 32-битным хешем, в зависимости от точной реализации хэш-таблицы. Если вы ищете эффективное решение, вы должны быть немного более конкретным, что вы подразумеваете под «машиной», потому что это зависит от того, сколько хранения у каждого есть, и относительной стоимости сетевой связи.

источник

2010-10-09 19:27:41

Найти повторяющиеся строки в большом файле

ответ

Смежные вопросы