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

[fa]

1 проход: цикл загрузки 25 млн элементов в QList
2 проход: сортировка 25 млн элементов qSort
3 проход: цикл по 25 млн элементов для получения результата

именно,
упор должен быть на скорость, а не простоту реализации

[MoPDoBoPoT]

   if( ключ есть в хеше )
   {
      увеличили счетчик повторов у элемента из хеша
      занесли ключ в repList
   }   

Только не просто if( ключ есть в хеше ), а if( ключ есть и значение "количество повторов" ==1  ), иначе при количестве повторов>2 список epList будет содержать повторы.

[BRE]

Только не просто if( ключ есть в хеше ), а if( ключ есть и значение "количество повторов" ==1  ), иначе при количестве повторов>2 список epList будет содержать повторы.

Уточню:
   if( ключ есть в хеше )
   {
      увеличили счетчик повторов у элемента из хеша
      if( количество повторов == 2 )
         занесли ключ в repList
   }   

[Igors]

1 проход: цикл загрузки 25 млн элементов в QList
2 проход: сортировка 25 млн элементов qSort
3 проход: цикл по 25 млн элементов для получения результата

именно,
упор должен быть на скорость, а не простоту реализации

А это очень часто совпадает

Городить что-то с QHash имеет смысл если Вы уверены/гарантируете что повторов будет достаточно много.

[fa]

Городить что-то с QHash имеет смысл если Вы уверены/гарантируете что повторов будет достаточно много.

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

[Igors]

я не думаю что корректно вообще поиск через хэш делать...

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

Код:

if (hash.contains(key))       // спуск по дереву
  ++hash[key];                 // еще 1 спуск по дереву
else
  hash.insert(key, 0);        // вызов new и балансировка дерева

Откуда же возьмется скорость? 

[Tonal]

2 Igors Учи матчасть. Хеш - это не дерево, это хешь.
Т.е. для поиска трудоёмкость константа, как и в массиве по индексу: О(1).
Но для вставки там может быть О(n).
А вот для дерева и вставка и поиск О(log n)
Так что при большом количестве уникальных значений дерево (QMap) может оказаться выгоднее.

Ну и всяко нужно ключи в int переводить.
Можно даже свою функцию написать, табличную, чтоб не тормозили выбор системы счисления и локали.

[BRE]

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

[Tonal]

Это всяко.
Но таки характеристики алгоритмов знать нужно.
Например брать в качестве контейнера массив и искать там тупым перебором, для таких объёмов смысл имеет только для получения наихудшего случая.

[BRE]

Это всяко.
Но таки характеристики алгоритмов знать нужно.
Например брать в качестве контейнера массив и искать там тупым перебором, для таких объёмов смысл имеет только для получения наихудшего случая.

+мульен. 

[spectre71]

Здравствуйте, необходим быстрый алгоритм поиска одинаковых строк фиксированной длины в файле.

Говоря более конкретно:
имеется файл примерно с таким содержанием:
...
...
Спасибо.

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

Если это так, то могу привести быстрый линейный алгоритм для чтения и сортировки(или определение кол-ва дубликатов).
Если это не так, то уточни параметры задачи

[Igors]

2 Igors Учи матчасть. Хеш - это не дерево, это хешь.
Т.е. для поиска трудоёмкость константа, как и в массиве по индексу: О(1).
Но для вставки там может быть О(n).
А вот для дерева и вставка и поиск О(log n)

Каюсь, изучать внутренности стандартных классов не люблю . Текст всегда довольно развесистый и тяжелый. Но даже в лучшем случае (дерево) это совсем недешево на миллионах данных.

Конкретно для QHash все гораздо хуже (посмотрел). Он бьет данные на bucket'ы, умеет по ключу спрыгнуть на bucket а внутри него - увы, прямой перебор. В какой-то момент он ре-организует bucket'ы. В общем по скорости - полный завал. Хотя будет хорошо работать если данные "одни повторы".

[Igors]

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

Дело. Давайте выложим каждый по своему варианту и сравним?

[spectre71]

Дело. Давайте выложим каждый по своему варианту и сравним?

Не надо страдать фигней.
Пусть fa ответит по поводу ограничений на входные данных для своей задачи!
Если верно, то что я писал выше, учитывая кол-во чисел(строк) >1'000'000 - однозначно алгоритм поразрядной сортировки.

[BRE]

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