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

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

Russian Qt Forum > Forum > Программирование > Алгоритмы > Ускорить поиск в списке
Страниц: [1] 2   Вниз
« предыдущая тема следующая тема »
  Печать  
Автор Тема: Ускорить поиск в списке  (Прочитано 11213 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Сентябрь 08, 2011, 21:29 »
Добрый вечер

Переделываю/обновляю код написанный очень давно (и не мной) на С (практически). Программист использовал список, для простоты

Код
C++ (Qt)
struct CObject {
 long mID;    // идентификатор
 CObject * mPrev;  // предыдущий в списке
 CObject * mNext;  // следующий в списке
 ..
};
 
Конечно то же самое с std::list - не суть

Профайлер показывает что тормозит на таком участке
Код
C++ (Qt)
..
CObject * theHead = ... // знаем голову списка
 
CObject * data1 = Lookup(theHead, ID_1);  // нашли в списке элемент с ID_1
...  // используем данные data1 
...
CObject * data10 = Lookup(theHead, ID_10);  // нашли в списке элемент с ID_10
...  // используем данные data10 
 
Lookup просматривает элементы начиная с theHead, пока не найдет с нужным ID. Откуда тормоза понятно. Легко сказать "возьми что-то другое вместо списка" - но во-первых это совсем непросто (код велик), а главное - здесь список прекрасно себя оправдывает во многих др. местах (удаления, перелинковки и.т.п)

"Глубина поиска" не превышает 500  (хотя весь список может быть намного больше).
Как бы мне здесь "ускориться" ?

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

Сообщений: 4747



Просмотр профиля WWW
« Ответ #1 : Сентябрь 08, 2011, 22:11 »
можно дополнительно завести словарь, ключами которого будут идентификаторы, а значениями - указатели на элементы списка. но тогда придется немного модифицировать функции по работе со списком для корректного обновления элементов словаря.
Записан
Изучением C++ вымощена дорога в Qt.

UTF-8 has been around since 1993 and Unicode 2.0 since 1996; if you have created any 8-bit character content since 1996 in anything other than UTF-8, then I hate you. © Matt Gallagher
SimpleSunny
Гость
« Ответ #2 : Сентябрь 08, 2011, 23:20 »
А список можно отсортировать?
Тогда можно было бы хранить каждый n-ый элемент списка в дереве\векторе. И от него уже искать вперед\назад по списку.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #3 : Сентябрь 09, 2011, 01:48 »
Цитата: kambala от Сентябрь 08, 2011,  22:11
можно дополнительно завести словарь, ключами которого будут идентификаторы, а значениями - указатели на элементы списка. но тогда придется немного модифицировать функции по работе со списком для корректного обновления элементов словаря.
Прелесть списка в том что элемент часто "самодостаточен", т.е. его можно удалить из списка совсем не зная "голову", также и вставить. А словарь(и) надо где-то поселить и в каждый вызов как-то добавить - а их много сотен.

Цитата: SimpleSunny от Сентябрь 08, 2011,  23:20
А список можно отсортировать?
Тогда можно было бы хранить каждый n-ый элемент списка в дереве\векторе. И от него уже искать вперед\назад по списку.
Нет, сортировать исходный список нельзя, в нем порядок следования элементов определяет иерархию
Записан
LisandreL
Птица говорун
*****
Offline Offline

Сообщений: 984


Надо улыбаться


Просмотр профиля
« Ответ #4 : Сентябрь 09, 2011, 06:58 »
Код:
...  // используем данные data1 
...
Модификация списка тут есть? Иначе можно пробежаться 1 раз по списку и построить хеш. А потом доступ иметь по нему.
Записан
Drafter
Гость
« Ответ #5 : Сентябрь 09, 2011, 08:44 »
Мне кажется, вы хотите чего-то несбыточного. Если список нельзя ни сортировать, ни индексировать (тем или иным способом), то и про ускорение поиска мечтать нечего. Как говорится, нету ручек - нет варенья.
« Последнее редактирование: Сентябрь 09, 2011, 08:53 от Drafter » Записан
LisandreL
Птица говорун
*****
Offline Offline

Сообщений: 984


Надо улыбаться


Просмотр профиля
« Ответ #6 : Сентябрь 09, 2011, 08:54 »
Цитата: Drafter от Сентябрь 09, 2011,  08:44
Если список нельзя индексировать (тем или иным способом), то и про ускорение поиска мечтать нечего.
Ну строго говоря кроме индексирования может помочь ещё распараллеливание поиска (на многоядерной машине), но для списка это тоже нетривиальное действо.
Записан
brankovic
Гость
« Ответ #7 : Сентябрь 09, 2011, 08:58 »
Цитата: LisandreL от Сентябрь 09, 2011,  06:58
Модификация списка тут есть? Иначе можно пробежаться 1 раз по списку и построить хеш. А потом доступ иметь по нему.

А при чём тут модификация? Можно просто хранить рядом hash_map <long, CObject*>, вставлять в него на вставке в список, удалять при удалении из списка.

А распараллеливание это очень сложная переделка, ТС даже в другой контейнер ленится перекладывать..
« Последнее редактирование: Сентябрь 09, 2011, 09:06 от brankovic » Записан
kambala
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4747



Просмотр профиля WWW
« Ответ #8 : Сентябрь 09, 2011, 11:24 »
Цитата: brankovic от Сентябрь 09, 2011,  08:58
Можно просто хранить рядом hash_map <long, CObject*>, вставлять в него на вставке в список, удалять при удалении из списка.
Цитата: Igors от Сентябрь 09, 2011,  01:48
Цитата: kambala от Сентябрь 08, 2011,  22:11
можно дополнительно завести словарь, ключами которого будут идентификаторы, а значениями - указатели на элементы списка. но тогда придется немного модифицировать функции по работе со списком для корректного обновления элементов словаря.
Прелесть списка в том что элемент часто "самодостаточен", т.е. его можно удалить из списка совсем не зная "голову", также и вставить. А словарь(и) надо где-то поселить и в каждый вызов как-то добавить - а их много сотен.

а самих функций по работе со списком (типа Lookup()) много? или они доступны только через библиотеку?
Записан
Изучением C++ вымощена дорога в Qt.

UTF-8 has been around since 1993 and Unicode 2.0 since 1996; if you have created any 8-bit character content since 1996 in anything other than UTF-8, then I hate you. © Matt Gallagher
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #9 : Сентябрь 09, 2011, 12:51 »
Цитата: kambala от Сентябрь 09, 2011,  11:24
а самих функций по работе со списком (типа Lookup()) много? или они доступны только через библиотеку?
"Много" не то слово Улыбающийся Я не могу даже проконтролировать сколько

Цитата: brankovic от Сентябрь 09, 2011,  08:58
А при чём тут модификация? Можно просто хранить рядом hash_map <long, CObject*>, вставлять в него на вставке в список, удалять при удалении из списка.
А где "рядом"? И как (хотя бы "в каком направлении") менять массу ф-ций заточенных на список? Например, ф-ция перебрасывает элементы их одного списка в другой
Код
C++ (Qt)
void RelinkChildren( CObject * theSoursв2Unlink,   // первый элемент для перелинковки
                     CObject * theTarget2Link,   // элемент (из др списка) к которому линковать
                     size_t elementCount );     // число элементов
 
Это работает быстро и написать это легко. Втулить сюда хеш - и будет уже недешево и не быстро. А при интенсивной перелинковке я могу попасть "из огня да в полымя"

Цитата: LisandreL от Сентябрь 09, 2011,  06:58
Модификация списка тут есть? Иначе можно пробежаться 1 раз по списку и построить хеш. А потом доступ иметь по нему.
Нет, модификации (здесь) нет. Но хеш получается медленнее чем прямой поиск. Почему:  во-первых начинается malloc/free (которых прямой поиск не имеет не смотря на всю свою тупость). А во-вторых, число хешируемых элементов получается намного больше чем извлекаемых. Конкретно: 20-25 элементов ищутся по ID, максимальная глубина просмотра списка не превышает 500 (а для многих всего 10-20). Это не такой уж тормоз сам по себе - просто это место попадает на хороший цикл
« Последнее редактирование: Сентябрь 09, 2011, 12:53 от Igors » Записан
brankovic
Гость
« Ответ #10 : Сентябрь 09, 2011, 13:58 »
Цитата: Igors от Сентябрь 09, 2011,  12:51
Цитата: brankovic от Сентябрь 09, 2011,  08:58
...Можно просто хранить рядом hash_map <long, CObject*>, вставлять в него на вставке в список, удалять при удалении из списка.
А где "рядом"? И как (хотя бы "в каком направлении") менять массу ф-ций заточенных на список?

например одной глобальной переменной, т.е. общий хэш на все списки, можно так по задаче?

Цитата: Igors от Сентябрь 09, 2011,  12:51
Например, ф-ция перебрасывает элементы их одного списка в другой..

если можно общий хэш, то в этой функции перекладывать из хэша в хэш не понадобится. Если нет, то будем дальше думать Улыбающийся
Записан
LisandreL
Птица говорун
*****
Offline Offline

Сообщений: 984


Надо улыбаться


Просмотр профиля
« Ответ #11 : Сентябрь 09, 2011, 14:11 »
Цитата: Igors от Сентябрь 09, 2011,  12:51
Это не такой уж тормоз сам по себе - просто это место попадает на хороший цикл
Ну так вне этого цикла хеш построить нельзя?
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #12 : Сентябрь 09, 2011, 14:17 »
Цитата: brankovic от Сентябрь 09, 2011,  13:58
например одной глобальной переменной, т.е. общий хэш на все списки, можно так по задаче?
Нет. Есть 3D объекты, у каждого есть много чего, ну напр. текстуры (картинки). Они связаны в список, 3D объект хранит голову этого списка. ID текстуры будет уникально в пределах 3D объекта - но не во всем проекте. Со многими др данными аналогично. Решение использовать списки вполне оправдано - в большинстве случаев число элементов мало (ну сколько там тех текстур на 1 объекте - ну десятка 2 отсилы). Однако по мере разрастания задачи рос и объем некоторых списков - и вот это начало неприятно беспокоить.

Цитата: LisandreL от Сентябрь 09, 2011,  14:11
Ну так вне этого цикла хеш построить нельзя?
Пользователь создал 4К объектов (простых кубиков). У каждого кубика свой список. Жалуется - рисует медленно. Смотрю профайлером - а там OpenGL отдыхает, 90% съедается на списках.
Записан
brankovic
Гость
« Ответ #13 : Сентябрь 09, 2011, 14:43 »
Цитата: Igors от Сентябрь 09, 2011,  14:17
ID текстуры будет уникально в пределах 3D объекта - но не во всем проекте.

1. когда вы ищите элемент с данным ID, вы точно знаете, что он там есть?
2. id в рамках объекта начинаются с 0 и идут подряд?
Записан
popper
Гость
« Ответ #14 : Сентябрь 09, 2011, 14:49 »
Если список большой, а извлекать из него нужно намного меньшее количество элементов, то, возможно, будет быстрее осуществлять поиск по массиву ID объектов, данные которых требуется обработать. Т.е. модифицировать Lookup примерно следующим образом:
Код
C++ (Qt)
void Lookup(CObject *header, vector<long> &neededID, vector<CObject*> &result)
{
 // neededID - ordered container
 
 CObject *tmp = header;
 vector<long>::const_iterator iter;
 int count = neededID.size();
 
while (tmp && count) {
    long id = tmp->mID;
    iter = std::find(neededID, id);
    if (iter != neededID.end()) {
       result.push_back(tmp);
       --count;
     }
    tmp = tmp->mNext;
  }
}
 


вызов функции делать 1 раз
« Последнее редактирование: Сентябрь 10, 2011, 12:27 от popper » Записан
Страниц: [1] 2   Вверх
  Печать  
« предыдущая тема следующая тема »
 
Перейти в:  


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