Удалить дубликаты строк

[Tronix]

Дано 2 текстовых файла. Общий размер этих файлов, допустим, влазит в оперативку (не больше 3 Gb). Нужно удалить из второго файла все строки, которые уже есть в первом файле. Язык - free pascal.

Вопрос первый и главный: как хранить данные в памяти? Сначала попробовал "в лоб" в дельфях TStringList и LoadFromFile - 28 Mb текстовый файл грузил примерно минут 5-6. Этот вариант отпал сразу. Далее попробовал описать массив так:

Type
  SType = Array [0..MaxLongInt div 81-1] of String[80];
  pStr = ^SType;

Тут же столкнулся с 2мя проблемами: 1) для того, что бы выделить необходимое кол-во памяти, нужно знать кол-во строк в файле - приходится сначала прочитать файл и посчитать кол-во строк, а затем еще раз прочитать файл уже в массив. Два раза читаем один и тот же файл. 2) Неэкономный расход памяти - для каждой строки используется 81 байт, даже если строка из 3-ех символов. Если первая проблема не такая уж проблема, то вот чрезмерный перерасход памяти - проблема.

Дальше сделал просто массив байт:

Type
  BufferType    = Array[0..MaxLongInt-1] of Byte;
  pBuffer       = ^BufferType;

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

Пока сделал без сортировки, но работает адски медленно в сравнении с аналогами..

[Аватар]

А вариант загрузить в базу какой-либо СУБД и запросом сделать что нужно не катит?

[Tronix]

Сообщение от Аватар

А вариант загрузить в базу какой-либо СУБД и запросом сделать что нужно не катит?

Ну это по по муравью из танка получится. Тут утилитка то по идее на пару килобайт должна быть.

[Аватар]

Ну это по по муравью из танка получится

Ничего подобного. В тот же ACCESS загрузить и пусть запрос сам находит дубликаты, индексы не забыть сделать для скорости

[Vapaamies]

Сообщение от Tronix

Дано 2 текстовых файла. Общий размер этих файлов, допустим, влазит в оперативку (не больше 3 Gb). Нужно удалить из второго файла все строки, которые уже есть в первом файле.

Если это требуется решить алгоритмически в программе, я бы сделал так:

• Проходим по первому файлу, читаем последовательно строки.
• Строки не сохраняем, вместо этого сохраняем их хеш.
• Проходим по второму файлу, читаем последовательно строки, считаем хеш.
• Ищем хеш, если не находим, сохраняем строку.

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

[Tronix]

Сообщение от Vapaamies

Если это требуется решить алгоритмически в программе, я бы сделал так:

• Проходим по первому файлу, читаем последовательно строки.
• Строки не сохраняем, вместо этого сохраняем их хеш.
• Проходим по второму файлу, читаем последовательно строки, считаем хеш.
• Ищем хеш, если не находим, сохраняем строку.

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

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

Не понял насчет сортированного массива - чего сортировать, хеши? Это же бессмыслица имхо?

[Vapaamies]

Сообщение от Tronix

Это же бессмыслица имхо?

То есть, поиск хеша в наборе должен происходить по волшебству простым перебором, а не методом деления надвое?

[Tronix]

Сообщение от Vapaamies

То есть, поиск хеша в наборе должен происходить по волшебству простым перебором, а не методом деления надвое?

Ну это же поиск, а не сортировка. Да, искать хеш наверное лучше методом деления пополам.
Дык какую хеш-функцию заюзать? Наверное будет лучше, если результат работы хеш-функции будет в виде Int32, или если этого недостаточно, то в Int64, чтоб был массив простых чисел. Отсюда следует, что MD5 вряд-ли подходит, ибо на выходе оно выдает строку типа 'a3f5dedf87ad78d789d56d5', что не лезет в регистр процессора никак за раз.
Но вопрос по прежнему с уникальностью - хватит ли Int32 (int64) для того, что бы не было коллизий?

[Tronix]

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

[Serge_Bliznykov]

Сообщение от Tronix

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

не, не байда. Иногда - очень полезная штука!!

И в данном случае лучше брать не крипографический хеш, а какой-нибудь быстрый (CRC). для избавления от возможных коллизий, можно его (хеш) чуть улучшить. Например, добавить в начало хеша длину строки.
А сортировать нужно как раз по хешу. И его использовать для поиска совпадения.

Впрочем, мне почему то кажется, что Вы уже для себя всё решили!