Быстрый алгоритм поиска одинаковых строк

[BRE]

однозначно алгоритм поразрядной сортировки.

+1
Думаю что линейный алгоритм с меньшим количеством проходов не оставит шансов двум проверенным алгоритмам.

[Igors]

Погонял тесты, посмотрел. Чтение и перевод из строки в число выполнял одинаковый код.
Предварительные результаты следующие:
При отсутствии совпадений по скорости выигрывает алгоритм с сортировкой, но с увеличением количества совпадающих строк (и увеличением количества попаданий в хеш) алгоритм с хешем  (использовался QHash) догоняет, а затем и перегоняет первый.

Все то же самое должно быть и по памяти. При небольшом числе совпадений сортировка съест в 3-4 раза меньше, но если все строки одинаковы... Зато с сортировкой голова не болит "какие там данные"

[BRE]

Все то же самое должно быть и по памяти. При небольшом числе совпадений сортировка съест в 3-4 раза меньше, но если все строки одинаковы... Зато с сортировкой голова не болит "какие там данные"

Чем больше совпадений, тем меньше элементов будет храниться в хеше (тем меньше памяти понадобиться).
Для сортировки - не важно сколько будет повторов, все элементы будут загружены в память.

[fa]

1) Правильно ли я понял, что строки не только фиксированной длины, но являются 16-чным представлением целых 32-битных чисел?
2) Правильно ли я понял, что  кол-во строк(чисел) гарантированно не превышает 1024*1024*256 = 67'108'864;

1-ое: верно.
2-ое: теоретически может быть и больше...

уточняю условия задачи.
берется файл абсолютно любого размера, для каждых его 128 байт считается значение контрольной суммы и записывается в файл. и теперь осуществляется поиск одинаковых строк в файле.
соответственно количество строк = размер файла / 128

Но я думаю поразрядная сортировка это оптимальный вариант, вряд ли наберется 67млн строк, к тому же есть вариант записывать при подсчете коллизий в 16 файлов, сортируя по первому символу...
заранее зная первый символ можно еще более увеличить скорость поиска =)

[spectre71]

1) Правильно ли я понял, что строки не только фиксированной длины, но являются 16-чным представлением целых 32-битных чисел?
2) Правильно ли я понял, что  кол-во строк(чисел) гарантированно не превышает 1024*1024*256 = 67'108'864;

1-ое: верно.
2-ое: теоретически может быть и больше...

уточняю условия задачи.
берется файл абсолютно любого размера, для каждых его 128 байт считается значение контрольной суммы и записывается в файл. и теперь осуществляется поиск одинаковых строк в файле.
соответственно количество строк = размер файла / 128

Понятно.
Если не сложно, объясни почему именно по 128 байт, а не больше, что за задача?
Далее, сильно расписывать не буду, спать уже хочся , если что непонятно потом спросишь.

1) Имеем файл с 32-рарядными числами в 16-чной текстовой записи. Каздое число на новой стоке.
  Вопрос! Ты формируешь файл? Если ты, то пиши без данные без прерноса строк, а лучше в бинарном виде, а не в 16-чной текстовой записи.
2) Читаем файл, лучше для скорости!!! не пользоваться QT-ми строками для чтения и преобразования данных, а читать в буфер, разбирать и преобразовывать самостоятельно.
3) Для сортировки будем использовать алгоритм поразрядной сортировки. Изучи это:
  a) http://www.codelab.ru/task/4
и это
  b) http://www.codelab.ru/task/5/
4) Нам оптимальнее всего выделить 2 разряда по 2 байта(high и low), соответственно при чтении каждого числа заполняем такой массив
qint16 order[2]; // order[0] - high; order[1] - low;
5) Если файл слишком большой, то читаем и сортируем "кусками", пишем отсортированные данные для каждого куска в свой файл, а затем объединяем за линейное время.
6) Размер выделяемой памяти под "кусок" тебе понадобится 256 KB(под счетчики) + 2*4*N байт, где N кол-во чисел для сортировки
7) 4*N байт - под массив N вышеописанных массовов(qint16 order[2])
8.) Еще 4*N, для копирования данных после сортировки по первому разряду(см. алгоритмы, тебе нужен будет (b))

[fa]

Если не сложно, объясни почему именно по 128 байт, а не больше, что за задача?

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

[spectre71]

Если не сложно, объясни почему именно по 128 байт, а не больше, что за задача?

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

Каких конкретно алгоритмов вычисления контрольных сумм?

[fa]

Каких конкретно алгоритмов вычисления контрольных сумм?

А вот тут уже никакой конкретики, они приходят и уходят...

[Igors]

3) Для сортировки будем использовать алгоритм поразрядной сортировки. Изучи это:
  a) http://www.codelab.ru/task/4
и это
  b) http://www.codelab.ru/task/5/

Красивый алгоритм (и полезный сайт)
Памяти правда сожрет больше, ну так это "диалектика" 

[fa]

Красивый алгоритм (и полезный сайт)
Памяти правда сожрет больше, ну так это "диалектика"

больше, чем ...

[spectre71]

Красивый алгоритм (и полезный сайт)
Памяти правда сожрет больше, ну так это "диалектика"

больше, чем ...

Например алгоритм quicksort не требует дополнительной памяти, т.е. требуется память только под сам массив сортируемых данных.
Алгоритм поразрядной сортировки(вторая ссылка из которых я  приводил), требует дополнительную память в размере исходного массива + еще немного для хранения счетчиков для разряда; - размер памяти под счетчики зависит от sizeof разряда, например если разряд берем 1 байт, то 256*4=1 KB, а если 2 байт, то 256*256*4=256 KB (на мой взгляд лучший вариант брать разряд 2 байт)

[fa]

Например алгоритм quicksort не требует дополнительной памяти, т.е. требуется память только под сам массив сортируемых данных.
Алгоритм поразрядной сортировки(вторая ссылка из которых я  приводил), требует дополнительную память в размере исходного массива + еще немного для хранения счетчиков для разряда; - размер памяти под счетчики зависит от sizeof разряда, например если разряд берем 1 байт, то 256*4=1 KB, а если 2 байт, то 256*256*4=256 KB (на мой взгляд лучший вариант брать разряд 2 байт)

угу, спасибо =))
но это не страшно )..

[garryHotDog]

для поиска подстроки в строке использовал "Алгорит БМХ (Боейра Мура Хорпсула)"...бытсро, просто, есть исходники...кому надо пишите

[kamre]

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

Как это quicksort не требует? В лучшем случае O(log n) памяти нужно, в худшем O(n).

[spectre71]

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

Как это quicksort не требует? В лучшем случае O(log n) памяти нужно, в худшем O(n).

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