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

[Tronix]

Тут вот какое дело: провел чисто эксперимент с ассемблером и прочим дебагом
Первый файл - 28 Mb строк: 2472037
Второй файл - 18 Kb строк: 1989

Соответственно ищем строки второго файла в первом. Даже если не делать никаких сравнений, кроме как по размеру, то для каждой проверяемой строки нужно пробежаться по циклу 2472037 раз; для 1989 строк количество итераций 1989*2472037 = 4916881593 . На моем не самом хилом компе это происходит за ~15 секунд, что в целом - дофига.

        asm
                nop
                push ebp

                mov edi,Dic2
                mov ebp,edi
                add ebp,dic2_size
                dec ebp

                mov esi,Dic1
                mov edx,esi
                add edx,dic1_size
                dec edx
                @next_line:
                mov esi,Dic1
                movzx ebx, byte ptr [edi]    // BL = t
                        @next_word:
                        movzx eax, byte ptr [esi]   // AL = k
                        cmp eax,ebx
                        jne @skip_cmp
                        @skip_cmp:
                        inc eax
                        add esi,eax

                        cmp esi,edx
                        jb @next_word

                inc ebx
                add edi,ebx

                cmp edi,ebp
                jb @next_line
                pop ds
                pop ebp

        end;

Весь замес идет во внутреннем цикле next_word, который состоит из 7 (семи) опкодов проца. Там происходит сравнение размера строк и больше ничего. Так же там всего одно обращение к памяти, все остальные значения хранятся в регистрах. По-идее тут оптимизировать нечего дальше.

Итого, с этой пустой болванкой, я не смог дождаться окончания выполнения работы при размере второго файла в 18Mb (1496076 строк). Это 1496076*2472037 = 3698355226812 итераций.

Таким образом либо сортировка, либо построение индекса, что бы знать какие строки с какой длинной находятся на какой позиции относительно начала массива.

[Tronix]

Как создать динамический массив строк?

Делаю:

type
   PNodeType = ^NodeType;

   NodeType = record
      Val  : string;
      Prev : PNodeType;
      Next : PNodeType;
   end;

Дальше по старинке:

   while not eof(f) do
   begin
      new(TempList^.Next);
      TempList^.Next^.Prev := TempList;
      TempList := TempList^.Next;
      ReadLn(F,TempList^.Val);
      Inc(N);
   end;
   TempList^.next := nil;
   Close(F);

Проблема в том, что на каждую строку выделяется 255 или вообще 65535 байт, соответственно при чтении ~540Mb файла все это радостно валится в эксепшен виолейтед.

UPD: TstringList - абсолютно такая же фигня. Runtime error: Out of Memory.
Гавно какоето.

[Utkin]

Ну Вам же не обязательно сравнивать всю строку сразу. Допустим брать 3 первых символа от строки и сравнить. Сравнение 3-х символов обходится быстрей чем 50 к примеру (а строки длинные?). Уже если прошло совпадение первых 3-х символов, то сравнивать по полной.

Даже если не делать никаких сравнений, кроме как по размеру, то для каждой проверяемой строки нужно пробежаться по циклу 2472037 раз;

Наверно альтернатив нет. Если никогда не измерять, то никогда и не сверите. Но тут действительно можно пытаться сортировать при добавлении строк в файл.

[Tronix]

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

Ну Вам же не обязательно сравнивать всю строку сразу. Допустим брать 3 первых символа от строки и сравнить.

Выше я беру 1 (один) символ (нулевой символ - размер) и сравниваю. И не могу дождаться завершения процесса.

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

Щаз храню просто в массиве байт. Первый символ - размер, затем строка и тд.

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

Ваще короче делаю вывод, что походу задача на языке паскаль/дельфе не решается. Си рулит.

[northener]

Ваще короче делаю вывод, что походу задача на языке паскаль/дельфе не решается. Си рулит.

Ну ка, ну ка. Код на Си который якобы рулит в студию!

[Аватар]

Ваще короче делаю вывод, что походу задача на языке паскаль/дельфе не решается

Чего это? Какие проблемы с динамическим массивом?

var MyArray: array of String;
--

SetLength(MyArray,100); // память под 100

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

[Tronix]

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

Ну ка, ну ка. Код на Си который якобы рулит в студию!

Кода нет, есть только екзешник и известно что афтор использовал стандартный stdl:qsort
На исходник я бы сам с удовольствием взглянул.
Подозреваю что там используются векторы

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

Чего это? Какие проблемы с динамическим массивом?

var MyArray: array of String;
--

SetLength(MyArray,100); // память под 100

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

Беда в том, что он мне для одной строки выделит 255 или если ansistring 65535 байт. А может у меня строка всего из 4-ех символов?

[Аватар]

Беда в том, что он мне для одной строки выделит 255 или если ansistring 65535 байт

С чего так? SetLength только массив разметит, память под каждую строку будет выделена при заполнении массива и столько сколько нужно, не более того

ADD Я вообще-то про дельфи, с Free паскалем не в теме

[Tronix]

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

С чего так? SetLength только массив разметит, память под каждую строку будет выделена при заполнении массива и столько сколько нужно, не более того

Хм, это интересно... Ща проверим...

UPD: Да, хорошее решение. Только нужно заранее знать кол-во строк ((( То есть файл придется читать два раза.
UPD2: Нет, для 28 Mb файла памяти отжирается ~600 метров. Увы (((

[Аватар]

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