Ускорить поиск в списке

[Igors]

Добрый вечер

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

Код

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]

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

[SimpleSunny]

А список можно отсортировать?
Тогда можно было бы хранить каждый n-ый элемент списка в дереве\векторе. И от него уже искать вперед\назад по списку.

[Igors]

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

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

А список можно отсортировать?
Тогда можно было бы хранить каждый n-ый элемент списка в дереве\векторе. И от него уже искать вперед\назад по списку.

Нет, сортировать исходный список нельзя, в нем порядок следования элементов определяет иерархию

[LisandreL]

Код:

...  // используем данные data1 
...

Модификация списка тут есть? Иначе можно пробежаться 1 раз по списку и построить хеш. А потом доступ иметь по нему.

[Drafter]

Мне кажется, вы хотите чего-то несбыточного. Если список нельзя ни сортировать, ни индексировать (тем или иным способом), то и про ускорение поиска мечтать нечего. Как говорится, нету ручек - нет варенья.

[LisandreL]

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

Ну строго говоря кроме индексирования может помочь ещё распараллеливание поиска (на многоядерной машине), но для списка это тоже нетривиальное действо.

[brankovic]

Модификация списка тут есть? Иначе можно пробежаться 1 раз по списку и построить хеш. А потом доступ иметь по нему.

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

А распараллеливание это очень сложная переделка, ТС даже в другой контейнер ленится перекладывать..

[kambala]

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

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

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

а самих функций по работе со списком (типа Lookup()) много? или они доступны только через библиотеку?

[Igors]

а самих функций по работе со списком (типа Lookup()) много? или они доступны только через библиотеку?

"Много" не то слово Я не могу даже проконтролировать сколько

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

А где "рядом"? И как (хотя бы "в каком направлении") менять массу ф-ций заточенных на список? Например, ф-ция перебрасывает элементы их одного списка в другой

Код

C++ (Qt)
void RelinkChildren( CObject * theSoursв2Unlink,   // первый элемент для перелинковки
                     CObject * theTarget2Link,   // элемент (из др списка) к которому линковать
                     size_t elementCount );     // число элементов
 

Это работает быстро и написать это легко. Втулить сюда хеш - и будет уже недешево и не быстро. А при интенсивной перелинковке я могу попасть "из огня да в полымя"

Модификация списка тут есть? Иначе можно пробежаться 1 раз по списку и построить хеш. А потом доступ иметь по нему.

Нет, модификации (здесь) нет. Но хеш получается медленнее чем прямой поиск. Почему:  во-первых начинается malloc/free (которых прямой поиск не имеет не смотря на всю свою тупость). А во-вторых, число хешируемых элементов получается намного больше чем извлекаемых. Конкретно: 20-25 элементов ищутся по ID, максимальная глубина просмотра списка не превышает 500 (а для многих всего 10-20). Это не такой уж тормоз сам по себе - просто это место попадает на хороший цикл

[brankovic]

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

А где "рядом"? И как (хотя бы "в каком направлении") менять массу ф-ций заточенных на список?

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

Например, ф-ция перебрасывает элементы их одного списка в другой..

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

[LisandreL]

Это не такой уж тормоз сам по себе - просто это место попадает на хороший цикл

Ну так вне этого цикла хеш построить нельзя?

[Igors]

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

Нет. Есть 3D объекты, у каждого есть много чего, ну напр. текстуры (картинки). Они связаны в список, 3D объект хранит голову этого списка. ID текстуры будет уникально в пределах 3D объекта - но не во всем проекте. Со многими др данными аналогично. Решение использовать списки вполне оправдано - в большинстве случаев число элементов мало (ну сколько там тех текстур на 1 объекте - ну десятка 2 отсилы). Однако по мере разрастания задачи рос и объем некоторых списков - и вот это начало неприятно беспокоить.

Ну так вне этого цикла хеш построить нельзя?

Пользователь создал 4К объектов (простых кубиков). У каждого кубика свой список. Жалуется - рисует медленно. Смотрю профайлером - а там OpenGL отдыхает, 90% съедается на списках.

[brankovic]

ID текстуры будет уникально в пределах 3D объекта - но не во всем проекте.

1. когда вы ищите элемент с данным ID, вы точно знаете, что он там есть?
2. id в рамках объекта начинаются с 0 и идут подряд?

[popper]

Если список большой, а извлекать из него нужно намного меньшее количество элементов, то, возможно, будет быстрее осуществлять поиск по массиву 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 раз