• XSS.stack #1 – первый литературный журнал от юзеров форума

Как сравнивать строки огромных объёмов ?

triblekill

RAID-массив
Забанен
Регистрация
24.05.2023
Сообщения
62
Решения
1
Реакции
17
Пожалуйста, обратите внимание, что пользователь заблокирован
Всем здрасте, понадобилось написать софт который например удалит дубликаты строк в огромном файле 50 гигабайт попробовал TDictionary, THashSet, THashMap для сравнения строк
почему то они очень сильно едят оперативную память может что то неправильно делаю ?

Код:
//TDictionary

procedure ReadFl(const myfile:string);
var
sr: TStreamReader;
Writer:TStreamWriter;
Line:string;
StrDictionary: TDictionary<string, Integer>;
begin
StrDictionary := TDictionary<string, Integer>.Create;
Writer := TStreamWriter.Create(ExtractFilePath(paramStr(0)) + 'DupDel.txt', False, TEncoding.Default, 65535);
try
sr := TStreamReader.Create(myfile,TEncoding.Default, True,2048);
while not sr.EndOfStream do
begin
Line:=Trim(sr.ReadLine);
if not StrDictionary.ContainsKey(Line) then begin
StrDictionary.Add(Line, 0);
Writer.WriteLine(Line);
end;
end;
finally
sr.Close;
FreeAndNil(sr);
StrDictionary.Free;
Writer.Close;
Writer.Free;
end;
end;

//HashSet Example

procedure ReadFl2(const myfile:string);
var
sr: TStreamReader;
Writer:TStreamWriter;
Hash:integer;
Line:string;
HashSet:THashSet<integer>;
begin
HashSet := THashSet<Integer>.Create(1000000,nil); //1000000 Capacity, Comparer = nil
Writer := TStreamWriter.Create(ExtractFilePath(paramStr(0)) + 'DupDel.txt', False, TEncoding.Default, 65535);
try
sr := TStreamReader.Create(myfile,TEncoding.Default, True,2048);
while not sr.EndOfStream do
begin
Line:=Trim(sr.ReadLine);
Hash:=TStringComparer.OrdinalIgnoreCase.GetHashCode(Line);;
if not HashSet.Contains(Hash) then begin
HashSet.Add(Hash);
Writer.WriteLine(Line);
end;
end;
finally
sr.Close;
FreeAndNil(sr);
HashSet.Free;
Writer.Close;
Writer.Free;
end;
end;
 
App.Merge
Софт работает с любыми обьемами

App.Merge.exe o="rez_out.txt" t=4 "rez.txt"
pause
rez.txt - файл, в котором мы хотим удалить дубликаты.

rez_out.txt - файл, который мы получим в итоге.

Софт с батником , для тех кто в танке батник открывается любым блокнотом
Да и не забудьте положить файлы в эту же папку.

Софт может объединять сразу несколько файлов и после удалять дубли, для этого просто вписываем нужные нам файлы:
Код:
App.Merge.exe o="rez_out.txt" t=4 "rez.txt" "rez2.txt" "rez3.txt"
pause
rez.txt - файл, в котором мы хотим удалить дубликаты.
rez2.txt - 2-й файл, в котором мы хотим удалить дубликаты.
rez3.txt - 3-й файл, в котором мы хотим удалить дубликаты.
rez_out.txt - общий файл, который мы получим в итоге.

Также можно прописать различные опции:
o=[out-file] - Выходной файл.
t=[threads] - Потоки, используется для ускорения сортировки вверх только.
c=[mem] - Используется для управления, сколько оперативной памяти для использования в МБ. По умолчанию 1024. блокированного в 3072.
min=[num] - Минимальная длина слова. По умолчанию = 1
max=[num] - Максимальная длина слова. По умолчанию = 4096.
--export-dups - Экспорт дубликатов в отдельный выходной файл.

Формат команды:
App.Merge.exe o="output-file.txt" t=4 [options] ... "word-list1.txt" "word-list2.lst" "directory1" ...

Для анализа отчета словесного списка:
App.Merge.exe r = "словарь-list1.txt"

Двойные кавычки необходимы для имени пути / файлов, которые содержат пробелы. Можно также указать пути к каталогам, если вы хотите объединить / сортировать множество файлов в папках
https://www.virustotal.com/gui/file...59233ed19ecc0a75bf4afa484c1576dba54/detection
https://yadi.sk/d/1Z_41uXdVW8adA
 
Пожалуйста, обратите внимание, что пользователь заблокирован
Пожалуйста, обратите внимание, что пользователь заблокирован
почему то они очень сильно едят оперативную память может что то неправильно делаю ?
Я не понял, ты чего ожидал то? Ты грузишь 50гб строк в память и ожидаешь, что у тебя не будет 50гб строк в памяти? Считай хеш от каждой строки и храни его. Зависит от конкретной задачи, но если хочешь побыстрее, то бери два простых быстрых хеша (например, FNV и DJB2, они на Latin-1 строках сравнительно неплохие), если хочешь медленнее, но с меньшей вероятностью коллизий бери MD5 и SHA1. И да, два хеша, чтобы уменьшить вероятность коллизии в обоих случаях. Но это тоже, в случае FNV и DJB2 - будет минимум 8 байт * количество строк в файле (если все строки уникальны), от этого ты никуда не уйдешь.
 
Пожалуйста, обратите внимание, что пользователь заблокирован
ожидаешь, что у тебя не будет 50гб строк в памяти
Дело в том что судя по описанию TDictinary и HashSet как то умно хранят хеши то есть первый хеш накладывается на второй частично и память должно есть пару байтов буквально с коллизиями и хешами не проблема разобраться будет подоптимизировать когда пойму почему так ест память
 
Пожалуйста, обратите внимание, что пользователь заблокирован
а тебе обязательно нужно использовать текстовый файл? Если работа на один раз, почему бы не закинуть в бд и там вызвать команду уже готовую ?
 
Пожалуйста, обратите внимание, что пользователь заблокирован
Дело в том что судя по описанию TDictinary и HashSet как то умно хранят хеши то есть первый хеш накладывается на второй частично и память должно есть пару байтов буквально с коллизиями и хешами не проблема разобраться будет подоптимизировать когда пойму почему так ест память
Ну я не знаю, как в Дельфи работает reference counting, возможно, у тебя все выделенные ReadLine строки доживают до конца выполнения функции (если ты уверен, что TDictionary не хранит строку, а хранит только хеш, часто хранение хеша это оптимизация, то есть словарь будет хранить и хеш и строку, чтобы избежать коллизий хеша, и если хеши совпали, то проверяются строки посимвольно, или например, если ты хочешь перечислить ключи, то словарь должен их тоже хранить, или по твоему он тебе будет перечисление хешей возвращать).
 
Пожалуйста, обратите внимание, что пользователь заблокирован
Ну я не знаю, как в Дельфи работает reference counting
Вообщем при сравнении двух файлов 800 и 600 мегабайт памяти жрёт под 3 гигабайта чего не должно по сути то быть
 
Пожалуйста, обратите внимание, что пользователь заблокирован
Вообщем при сравнении двух файлов 800 и 600 мегабайт памяти жрёт под 3 гигабайта чего не должно по сути то быть
Ну я не понимаю, ты до сих пор не понял, что у тебя все строки в памяти остаются, вне зависимости от того в словаре они или в хеш-сете. Если бы эти структуры хранили только хеши, а не значения, ты бы не смог их перечислить. У TDictionary есть свойство Keys, которое возвращает перечисление этих твоих строк, которые, как ты думаешь в памяти не хранятся.
 
Пожалуйста, обратите внимание, что пользователь заблокирован
У TDictionary есть свойство Keys, которое возвращает перечисление этих твоих строк, которые, как ты думаешь в памяти не хранятся.
Та нет вроде бы оборачивает TDictionary в какие то хеши
 
Пожалуйста, обратите внимание, что пользователь заблокирован
Та нет вроде бы оборачивает TDictionary в какие то хеши
Ну загрузи все свои строки в словарь, а потом попробуй в цикле пройти по тому, что свойство Keys возвращает, что ты получишь?
 
Пожалуйста, обратите внимание, что пользователь заблокирован
Ну загрузи все свои строки в словарь, а потом попробуй в цикле пройти по тому, что свойство Keys возвращает, что ты получишь?
Ну я получу конечно обратно строку но он её же экстрактит
 
Пожалуйста, обратите внимание, что пользователь заблокирован
Ну я получу конечно обратно строку но он её же экстрактит
Откуда он ее экстрактит, ну ка?
 
Пожалуйста, обратите внимание, что пользователь заблокирован
Пожалуйста, обратите внимание, что пользователь заблокирован
Из хеша
Нет, я понимаю, что не все знакомы с теорией информации и энтропией, но как ты сам по логике вещей считаешь, можно ли строку произвольной длины ужать до 32 или 64 бит без потерь информации, а потом распаковать обратно без потерь?
 
Пожалуйста, обратите внимание, что пользователь заблокирован
но как ты сам по логике вещей считаешь, можно ли строку произвольной длины ужать до 32 или 64 бит без потерь информации, а потом распаковать обратно без потерь?
Даже до 2-4 байт по сути можно если включить все символы utf-8 алфавит и цифры, я твой намёк то понял на что ты намекаешь но много вопросов остаётся какой хеш там прикрутить чтобы памяти меньше жрало как его сопоставить ещё
 
Что бы сравнивать большие файлы, нужно продумать алгоритм, что бы все это дело грузилось на HDD\SSD. Иначе никак.
В случае с App.Merge он хеширует в md5, после чего берет первые N символов от хеша как временное имя файла и туда закидывает все хеши, что начина.тся с этих символов.

Тебе надо либо идти в интерне смотреть различные реализации, либо выдумывать самому.

какой хеш там прикрутить чтобы памяти меньше жрало
Тут все просто. Меньше длинна хеша - большая вероятность коллизий и наоборот.
 
Пожалуйста, обратите внимание, что пользователь заблокирован
Тут все просто. Меньше длинна хеша - большая вероятность коллизий и наоборот.
Я пока хочу опустить коллизии и остальное главное пока оптимизация хранения похоже что стандартный Comparer не оптимизирован совсем TStringComparer.OrdinalIgnoreCase
какую то реализацию hashset скачивал с гитхаба там памяти ело максимум 16-18 мегабайт да только два файла обрабатывались два часа
 
Вообщем при сравнении двух файлов 800 и 600 мегабайт памяти жрёт под 3 гигабайта чего не должно по сути то быть
Еще можно предположить как идет работа с данными, например при передаче файла внутри программы, ты локально когда загружаешь в память файл, при последующей его передаче он идет по ссылке или по значению, потому что по значению оно продублируется в памяти, что например при грубых расчетах (800+600 = 1400 ) *2 = 2,8гб+-
 


Напишите ответ...
  • Вставить:
Прикрепить файлы
Верх