Russian Qt Forum

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

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

На выходе надо получить примерно такой файл:

Спасибо.

Добрый день

- загружаете все строки
- сортируете
- удаляете одинаковые строки из сортированного массива (здесь же подсчитываете число вхождений)
   
Наверное я не понял вопроса  :)

Дело в том, что строк во водном файле будет порядка 25млн.
И надо добиться как можно меньшего времени поиска ;)

Первое что пришло на ум - использовать хэш строк.
QHash< хэш_строки, QPair<строка, количество_повторов> >
Чтобы QHash шустрее работал, надо зарезервировать необходимое место. Это можно прикинуть исходя из того, что длины строк одинаковой длины.

----
UPD: строк во входном файле будет порядка 25млн  :o

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

Да и как-то вычислять значение хэша от значения хэша =)))))

Давайте прикинем. 8 байт строка + 4 байта счетчик. 25 * 12 = 300 Mb
Это по нынешним временам не так уж много. Но это уже "объем", поэтому лучше использовать примитивные структуры

struct CStr {
// не делайте деструктор, сортировка будет его все время звать
  bool operator == ( const CStr & ) const;
  bool operator <   ( const CStr & ) const;

  int    mCount;
  char mData[8];   // не QString, слишком жирно
};

Читаете все в QList, сортируете его. Удаление строк (erase) лучше на таких объемах избегать - сразу пишете в выходной файл.

Если же "не лезет в память" - то это другая задача, нужно определиться.

Edit: без счетчика можно спокойно обойтись, получать его на выходе

Строка это текстовое представление 32-битного числа. Проще строку переводить в число при загрузке и хранить число, так же его можно использовать в качества ключа для хэша.

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

можно вот здесь подробнее?

C++ (Qt)
	bool validNumber;
	QString strVal = file.readLine();
	quint32 val = strVal.toInt( &validNumber, 16 );
 

Раз хэш(HEX-код), то
+1

QHash<quint32, int> hash; // Сам контейнер (ключ-количество повторений)
QList<quint32> repList; // Список ключей с количеством повторений > 1

Цикл по всем строкам
{
   читаемСтроку
   получилиКлюч
   if( ключ есть в хеше )
   {
      увеличили счетчик повторов у элемента из хеша
      занесли ключ в repList
   }
   else
   {
      добавили ключ в hash. Количество повторов = 1
   }
}

Дальше просмотрев список repList сможем получить все ключи которые встретились > 1 раза. Для получения точного числа повторов для указанного ключа лезим в hash.

Верно, памяти в 2 раза меньше

А зачем здесь вообще какой-то хэш? Пусть есть отсортированный QList<int>.

Но его нет.
Что бы его получить нужен дополнительный проход по всем элементам + сортировка.

Не понял насчет дополнительного прохода. Прочитали из файла в QList, затем

qSort(lst.begin(), lst.end());

Если в память лезет, то все просто

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

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

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

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

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

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

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

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


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

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

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

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

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

+мульен.  :)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) Имеем файл с 32-рарядными числами в 16-чной текстовой записи. Каздое число на новой стоке.
  Вопрос! Ты формируешь файл? Если ты, то пиши без данные без прерноса строк, а лучше в бинарном виде, а не в 16-чной текстовой записи.
2) Читаем файл, лучше для скорости!!! не пользоваться QT-ми строками для чтения и преобразования данных, а читать в буфер, разбирать и преобразовывать самостоятельно.
3) Для сортировки будем использовать алгоритм поразрядной сортировки. Изучи это:
  a) http://www.codelab.ru/task/4 (http://www.codelab.ru/task/4)
и это
  b) http://www.codelab.ru/task/5/ (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))

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

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

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

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

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

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

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

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

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

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