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

[fa]

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

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

Код:

A0FE3CFD
33E33492
6F71C7BE
3107BBA2
D504D497
BC8093F5
B0799820
C131EADA
338EC808
BC8093F5
040D900F
4B9C482A
7E0E1E10
ABA9DA9A
88D6CF18
ABA9DA9A
73B459C3

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

Код:

Total: 4
ABA9DA9A - 2
BC8093F5 - 2

Спасибо.

[Igors]

Добрый день

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

[fa]

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

[MoPDoBoPoT]

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

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

[fa]

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

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

[Igors]

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

Давайте прикинем. 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: без счетчика можно спокойно обойтись, получать его на выходе

[BRE]

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

[fa]

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

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

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

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

[BRE]

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

Код

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

[MoPDoBoPoT]

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

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

Код

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

+1

[BRE]

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

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

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

[Igors]

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

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

так же его можно использовать в качества ключа для хэша.

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

Код:

void PrintDups( QList<int> & lst )
{
  int i, beg = 0, limit = lst.size();
  for (i = 1; i < limit; ++i) {
    if (lst[i] != lst[beg]) {
     if (i - beg > 1)
       cout << lst[beg] << " - " << (i - beg) << endl;
     beg = i;
   }
  }
  if (limit - beg > 1)
    cout << lst[beg] << " - " << (limit - beg) << endl;
}

[BRE]

Пусть есть отсортированный QList<int>.

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

[Igors]

Пусть есть отсортированный QList<int>.

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

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

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

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

[BRE]

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

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

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

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