Russian Qt Forum
Ноябрь 22, 2024, 19:57 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Russian Qt Forum > Forum > Программирование > Алгоритмы > Быстрый алгоритм поиска одинаковых строк
Страниц: [1] 2 3   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Быстрый алгоритм поиска одинаковых строк  (Прочитано 39195 раз)
fa
Гость
« : Сентябрь 13, 2009, 10:48 »
Здравствуйте, необходим быстрый алгоритм поиска одинаковых строк фиксированной длины в файле.

Говоря более конкретно:
имеется файл примерно с таким содержанием:
Код:
A0FE3CFD
33E33492
6F71C7BE
3107BBA2
D504D497
BC8093F5
B0799820
C131EADA
338EC808
BC8093F5
040D900F
4B9C482A
7E0E1E10
ABA9DA9A
88D6CF18
ABA9DA9A
73B459C3

На выходе надо получить примерно такой файл:
Код:
Total: 4
ABA9DA9A - 2
BC8093F5 - 2

Спасибо.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #1 : Сентябрь 13, 2009, 11:58 »
Добрый день

- загружаете все строки
- сортируете
- удаляете одинаковые строки из сортированного массива (здесь же подсчитываете число вхождений)
   
Наверное я не понял вопроса  Улыбающийся
Записан
fa
Гость
« Ответ #2 : Сентябрь 13, 2009, 12:03 »
Дело в том, что строк во водном файле будет порядка 25млн.
И надо добиться как можно меньшего времени поиска Подмигивающий
Записан
MoPDoBoPoT
Гость
« Ответ #3 : Сентябрь 13, 2009, 12:11 »
Первое что пришло на ум - использовать хэш строк.
QHash< хэш_строки, QPair<строка, количество_повторов> >
Чтобы QHash шустрее работал, надо зарезервировать необходимое место. Это можно прикинуть исходя из того, что длины строк одинаковой длины.

----
UPD: строк во входном файле будет порядка 25млн  Шокированный
« Последнее редактирование: Сентябрь 13, 2009, 12:13 от MoPDoBoPoT » Записан
fa
Гость
« Ответ #4 : Сентябрь 13, 2009, 12:41 »
Да, я пробовал сейчас через хэш, правда функцию расчета вручную задал =)
Другой вопрос будет ли он работать корректно?
потому что значение способом тотального сравнения строк и через сравнение хэшей получается разный О.о

Да и как-то вычислять значение хэша от значения хэша =)))))
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #5 : Сентябрь 13, 2009, 13:16 »
Цитата: fa от Сентябрь 13, 2009,  12:03
Дело в том, что строк во водном файле будет порядка 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: без счетчика можно спокойно обойтись, получать его на выходе
« Последнее редактирование: Сентябрь 13, 2009, 13:27 от Igors » Записан
BRE
Гость
« Ответ #6 : Сентябрь 13, 2009, 13:36 »
Строка это текстовое представление 32-битного числа. Проще строку переводить в число при загрузке и хранить число, так же его можно использовать в качества ключа для хэша.
Записан
fa
Гость
« Ответ #7 : Сентябрь 13, 2009, 13:45 »
Цитировать
Если же "не лезет в память" - то это другая задача, нужно определиться.
для этого выход есть, можно разбить исходный файл на 16 по первому символу.

Цитировать
Проще строку переводить в число при загрузке и хранить число, так же его можно использовать в качества ключа для хэша.
можно вот здесь подробнее?
Записан
BRE
Гость
« Ответ #8 : Сентябрь 13, 2009, 13:54 »
Цитата: fa от Сентябрь 13, 2009,  13:45
можно вот здесь подробнее?

Код
C++ (Qt)
	bool validNumber;
	QString strVal = file.readLine();
	quint32 val = strVal.toInt( &validNumber, 16 );
 
Записан
MoPDoBoPoT
Гость
« Ответ #9 : Сентябрь 13, 2009, 14:10 »
Цитата: fa от Сентябрь 13, 2009,  12:41
Да и как-то вычислять значение хэша от значения хэша =)))))
Раз хэш(HEX-код), то
Цитата: BRE от Сентябрь 13, 2009,  13:54
Код
C++ (Qt)
	bool validNumber;
	QString strVal = file.readLine();
	quint32 val = strVal.toInt( &validNumber, 16 );
 
+1
Записан
BRE
Гость
« Ответ #10 : Сентябрь 13, 2009, 14:21 »
QHash<quint32, int> hash; // Сам контейнер (ключ-количество повторений)
QList<quint32> repList; // Список ключей с количеством повторений > 1

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

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

Сообщений: 11445


Просмотр профиля
« Ответ #11 : Сентябрь 13, 2009, 14:24 »
Цитата: BRE от Сентябрь 13, 2009,  13:36
Строка это текстовое представление 32-битного числа. Проще строку переводить в число при загрузке и хранить число,
Верно, памяти в 2 раза меньше

Цитата: BRE от Сентябрь 13, 2009,  13:36
так же его можно использовать в качества ключа для хэша.
А зачем здесь вообще какой-то хэш? Пусть есть отсортированный 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;
}
« Последнее редактирование: Сентябрь 13, 2009, 14:30 от Igors » Записан
BRE
Гость
« Ответ #12 : Сентябрь 13, 2009, 14:51 »
Цитата: Igors от Сентябрь 13, 2009,  14:24
Пусть есть отсортированный QList<int>.
Но его нет.
Что бы его получить нужен дополнительный проход по всем элементам + сортировка.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #13 : Сентябрь 13, 2009, 14:59 »
Цитата: BRE от Сентябрь 13, 2009,  14:51
Цитата: Igors от Сентябрь 13, 2009,  14:24
Пусть есть отсортированный QList<int>.
Но его нет.
Что бы его получить нужен дополнительный проход по всем элементам + сортировка.
Не понял насчет дополнительного прохода. Прочитали из файла в QList, затем

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

Если в память лезет, то все просто
Записан
BRE
Гость
« Ответ #14 : Сентябрь 13, 2009, 15:02 »
Цитата: Igors от Сентябрь 13, 2009,  14:59
Не понял насчет дополнительного прохода. Прочитали из файла в QList, затем

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

Если в память лезет, то все просто
1 проход: цикл загрузки 25 млн элементов в QList
2 проход: сортировка 25 млн элементов qSort
3 проход: цикл по 25 млн элементов для получения результата
Записан
Страниц: [1] 2 3   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


Страница сгенерирована за 0.148 секунд. Запросов: 22.