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

[gliderexpert]

Спойлер: архиватор

Нет, я понимаю, что не все знакомы с теорией информации и энтропией, но как ты сам по логике вещей считаешь, можно ли строку произвольной длины ужать до 32 или 64 бит без потерь информации, а потом распаковать обратно без потерь?

 

[stepany4]

какую то реализацию hashset скачивал с гитхаба там памяти ело максимум 16-18 мегабайт да только два файла обрабатывались два часа

Существует AVX, о котором, обыкновенно не знают, рекомендую изучить эти наборы инструкций. Как известно, EmEditor, официально самый быстрый текстовый редактор в мире, в том числе операции со строками в нём оптимальны и аналогов начиная от чего-то более увесистого и громоздкого - просто нет. Ничто и нигде прикладное не может сравниться в топ-3 даже условно, когда мы говорим о гигабайтах, десятках гигабайт и любых вычислительных операциях в такой весовой категории. За счет чего достигается такая элегантность баланса вычислений? Наборы инструкций, до которых обыкновенно кодеры не доходят, полагая что это некая эльфийская алгебра для машин (math kernel lib. и пр.).

 

[valgreesh]

Существует AVX, о котором, обыкновенно не знают, рекомендую изучить эти наборы инструкций.

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

 

[stepany4]

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

Я понимаю, что задача вполне конкретна. Но она ни упирается в диск. Возьми EmEditor просто для общего понимания разницы. Отруби инструкции, вообще кеширование в память, попробуй сразу в оперативу что бы писалось, или напротив проставь адекватно что бы на ssd кешировалось. Просто сравни, о чем речь, в чем разница. Это такой простой банальный пользовательский эксперимент.
Я тебе скажу что дело не только в диске. Вообще что касается радужных таблиц, хеширования и разных примочек, на этот счет можно долго умничать, под что-то так рационально, под что-то скажут, да это ламер, это не рационально. Всё это полная херня, потому что люди в принципе работают с разными вещами, не понимая всегда как это работает и считывается что и с чего. Поэтому под hashcat тебе одно скажут, под дехеш напоют другое, не объясняя при этом с чем они работают конкретно. На эти темы не стоит спорить, умничать. Есть многое на этом свете, чего и не снилось нашим мудрецам. )) Возьми на простом примере, или более сложном такой эксперимент проведи. ))

 

[valgreesh]

Я понимаю, что задача вполне конкретна. Но она ни упирается в диск.

Еще как упирается. ТС не привел всех условий, но задачка старая и хорошо известная (легко гуглится, если интересно). А условия таковы, что файл состоит не из гиганских строк, а как раз наоборот - строки короткие, от 8 до 32 символов, но файл огромный. Как бы эту задачу ни решать (а вариантов, вообще, несколько), но все сводится к постоянному обмену с диском. Если интересно, на хабре была статья на решение очень похожей задачи: https://habr.com/ru/articles/714524/

 

[gliderexpert]

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

AVX и прочее нужно для ускорения расчета хешей строк для загрузки файла в ОЗУ при первоначальном открытии. Дальнейшая работа (поиск строки и т.д.) выполняется уже со "сжатыми" строками и эти спец.инструкции особо не требуются.
Существуют попытки использовать GPU для этой цели - https://github.com/n00rsy/CUDA-text-search
Если время "открытия" файла (а правильнее сказать - время чтения данный с НЖМД + вычисление хешей от строк + запись результатов в ОЗУ) не принципиально, или нужно выполнить всего одну операцию (например проверить есть ли в файле строка "1234567") то да - можно сказать что все упирается в диск. Тут уже придется использовать NCQ и т.д

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

 

[valgreesh]

AVX в данном случае - яркий пример premature optimization.

 

[tikus]

 

[rand]

Уважаемый, ты пытаешься обработать 50 гигабайтный файл в оперативке? Это, мягко говоря, не очень элегантный подход. TDictionary, THashSet, и THashMap — это структуры данных, которые хранятся в оперативной памяти. Если твой файл больше, чем доступная ОЗУ, то, естественно, всё рухнет.

Твой код — это классический пример переполнения памяти (out of memory). Ты загружаешь ВЕСЬ файл в память прежде чем начать обработку. Это как пытаться засунуть слона в карман.

Вот что нужно сделать:

1. Обработка построчно: Вместо загрузки всего файла, читай его построчно. Обрабатывай каждую строку, а потом отбрасывай её из памяти. Это позволит тебе обрабатывать файлы любого размера, ограниченные только размером жёсткого диска и временем обработки.

2. Более эффективная структура данных (для небольших файлов): Если файл всё-таки помещается в ОЗУ, то THashSet с хорошей хэш-функцией (не просто GetHashCode) будет предпочтительнее, чем TDictionary, так как он хранит только уникальные значения. Но всё равно, для 50ГБ это не вариант.

3. Внешняя сортировка: Для файлов такого размера тебе понадобится алгоритм внешней сортировки. Это означает, что ты будешь разбивать файл на более мелкие части, сортировать их по отдельности, а затем объединять отсортированные части. Этот подход значительно эффективнее для больших файлов.

4. Потоковая обработка: Рассмотри использование потоковой обработки (streaming). Читай куски файла, обрабатывай их, и затем выводи результат. Это позволит тебе эффективно работать с огромными файлами, не загружая их целиком.

Я бы посоветовал тебе посмотреть на библиотеки, которые уже реализуют внешнюю сортировку, или написать свой скрипт на Python — там это сделать проще и эффективнее. В Python есть модуль mmap для работы с файлами в режиме памяти, что может помочь в некоторых случаях (но для 50ГБ всё равно лучше использовать потоковую обработку).

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

program RemoveDuplicateLines;

uses
  System.SysUtils, System.Hashing;

procedure ProcessLargeFile(inputFilename, outputFilename: string);
var
  infile, outfile: TFileStream;
  line: string;
  hasher: TStringHasher;
  hash: Int64;
  seenLines: TSet<Int64>;
  buffer: array[0..1023] of Char; // буфер для чтения строк
  bytesRead: Integer;
begin
  seenLines := TSet<Int64>.Create;
  try
    infile := TFileStream.Create(inputFilename, fmOpenRead);
    outfile := TFileStream.Create(outputFilename, fmCreate);

    hasher := TStringHasher.Create(TEncoding.UTF8); // Создаём хешер для UTF-8 кодировки
    try
        while infile.Position < infile.Size do begin
            bytesRead := infile.Read(buffer, SizeOf(buffer));
            line := string(buffer);
            line := Trim(line); // Удаляем ведущие и завершающие пробелы
            if Length(line) > 0 then begin
              hash := hasher.HashString(line); // Вычисляем хэш строки
              if not seenLines.Contains(hash) then begin
                seenLines.Add(hash);
                outfile.Write(line + #13#10, Length(line) + 2); // Записываем строку в выходной файл с символами перевода строки
              end;
            end;
        end;
    finally
      hasher.Free;
    end;
  finally
    infile.Free;
    outfile.Free;
    seenLines.Free;
  end;
end;

var
  inputFileName, outputFileName: string;
begin
  // Замените на пути к вашим файлам
  inputFileName := 'путь/к/вашему/большому/файлу.txt';
  outputFileName := 'путь/к/выходному/файлу.txt';
  ProcessLargeFile(inputFileName, outputFileName);
  Writeln('Обработка завершена.');
  Readln;
end.

Ещё раз повторю: для настоящих больших файлов этот Паскаль-код будет работать значительно медленнее, чем Python-вариант. Паскаль — не самый подходящий инструмент для таких задач. Но теперь ты, хотя бы, знаешь, как это сделать на Паскале. Не расслабляйся, ламер! Ещё многому тебе нужно научиться.