Как максимально быстро удалить дубли в большом (350Гб) файле?

Question

[Twindo]

Каким способом можно максимально быстро удалить дубли в большом (350Гб) файле (~10 миллиардов записей, строк длинной до 255 символов). Какие инструменты для этого лучше использовать (и как их тюнить под эту задачу)? Поделитесь реальным опытом, если у кого таковой имеется?

З.Ы. Intel Core i5-3550, 8Гб RAM

Answer 1

[sim3x]

Быстро никак не получится

Готовое

sort \
--unique \
--parallel <threads count> -T /path/to/temp/dir/ /path/to/huge/file >>/out/file

Поставь на удаленной машине субд с ram 16gb
Сделайтам таблицу с уникальным полем
И долби своей машины вставками

Comments

[Сергей]

О, норм 350 гб сортировать

Answer 2

[Сергей]

Используйте последовательный проход с фильтрацией с помощью фильтра Блума.

Comments

[Сергей]

Помогу вам с задачей. Очень дорого :)

[Twindo]

Бдагодарю, про фильтр Блума я в курсе и про хэши MurmurHash, FNV hashes и Jenkin’s Hashes и др. тоже. Но меня больше интересуют готовые решения.

Answer 3

[Алексей Черемисин]

Хороший вопрос!
На третий взгляд, я бы поступил по следующему алгоритму.

Взял бы базу данных, ну например mysql.... Для хранения кешей и коллизий.
Итак, нам нужно пройтись по записям бигфайла, и сформировать новый бигфайл.
1) берем строчку файла, считаем от нее (или какой-то части), например sha1.
2) ищем по базе данных наш sha1
(таблица в "hashes" c полями "hash" и "offset", "count")
2.1) Если не нашли:

• копируем текущую строку в новый файл
  
• заносим наш sha1 и начало строки в базу (это нужно для коллизий)
  

2.2) Если нашли:

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

3) Обработка коллизии
(таблица в "collisions" c полями "hash" и "offset", "count")

• берем из collisions все записи по нашему хешу
  
• для каждой записи вынимаем строку из старого файла и сравниваем
  
• если строки равны, то переходим на п1) (можно еще и обновить count этой записи)
  
• если строки не равны, добавляем новую запись в таблицу collisions с новым смещением, текущюю строку пишем в новый файл
  
  

В принципе, этот процесс можно параллелить на бесконечное количество процессов. хотя, нужно бы еще над этим подумать.

PS. Можно еще дополнительное поле в каждой из таблиц сделать "count", обновлять его, если произошло сравнение записей, для статистики.