LINUX.ORG.RU

Алгоритм поиска


0

0

Нужно организовать поиск объекта по его уникальному номеру(id). Скорость очень критична. Если вместо всяких там бинарных деревьем использовать просто массив. например:

struct hz *hzarr[100000];

struct hz *find(id){

if(arr[id] != NULL){ return arr[id] }else{ return NULL; } }

Какие минусы, кроме того что транжирю память?


если номер не повторяется, то можешь рассмотреть массив бит, должно помочь съэкономить память

dimon555 ★★★★★
()

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

ptomaine
()

>Нужно организовать поиск объекта по его уникальному номеру(id)

Что мешает использовать std::hash_map? Может интрузивные контейнеры? (http://www.boost.org/doc/libs/1_36_0/doc/html/intrusive.html)

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

stpg
()
Ответ на: комментарий от ptomaine

> А на что она здесь транжирится? На мой взгляд, здесь она просто одним куском выделена. В каких условиях её меньше будет тратиться?

ключевое слово: sparse

dilmah ★★★★★
()

struct hz *hzarr[100000];

struct hz *find(id){

return arr[id];

}

Текущая версия напоминает башорговское if (a == 3) a = 3 else a = a;

naryl ★★★★★
()
Ответ на: комментарий от stpg

Только не hash_map, а unordered_map. hash_map'а в стандарте нет.

Reset ★★★★★
()

Минуса два.

Первое - ты автоматом предполагаешь, что id лежит строго в пределах от 0 до 99999.

Второе - но в этом я не очень уверен - когда транжиришь память, обычно начинаешь чаще промахиваться мимо кэшей L1/L2. А это уже сказывается на скорости. Как я понимаю, в x86 кэш заполняется "строками", и есть подозрение, что эта "строка" больше, чем sizeof(void*) (НЕ ПОМНЮ ТОЧНО). Если это именно так, то в кэш попадает много неиспользуемых смежных NULL. Если это не так, то не исключено, что транжирство в памяти проявится на эффективности кэша как-то ещё.

Ну и третий минус - с точки зрения быстродействия if явно ни к чему, но об этом уже написали.

alexsaa
()

забыта инициализация указателей в массиве NULL значением - это раз. два - промахи кешей могут очень неплохо сожрать быстродействие. особенно если это очень критично.

из плюсов - время поиска O(1)+C :)

Dark_SavanT ★★★★★
()

> Какие минусы, кроме того что транжирю память?

Гы! Верно заметили -- больше никаких! Рассуждения alexsaa про кыш -- совсем не по делу (кышы для таких целей и придумали).

К сожалению, на практике такие задачи редко встречаются: обычно кол-во объектов относительно мало, а вот уникальный id может быть очень большим.

Die-Hard ★★★★★
()

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

twosev ★★
()
Ответ на: комментарий от Die-Hard

> Рассуждения alexsaa про кыш -- совсем не по делу (кышы для таких целей и придумали).

не понимаю.

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

dilmah ★★★★★
()
Ответ на: комментарий от dilmah

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

Не хочешь ли ты сказать, что обращение к элементу массива будет происходить медленнее, чем к элементу дерева? )

anonymous
()
Ответ на: комментарий от anonymous

> Не хочешь ли ты сказать, что обращение к элементу массива будет происходить медленнее, чем к элементу дерева? )

доступ к незакэшированной ячейке может занимать больше 100 тактов

Првда, у дерева свои проблемы -- условные бранчи..

dilmah ★★★★★
()
Ответ на: комментарий от dilmah

> доступ к незакэшированной ячейке может занимать больше 100 тактов

А как ты думаешь, сколько тактов займёт поиск нужного элемента в дереве? (разумеется, не надо брать идеальный случай, когда искомый элемент - это корень дерева=))

anonymous
()
Ответ на: комментарий от dilmah

да, кстати... На что уходят эти 100 тактов? =\

anonymous
()
Ответ на: комментарий от anonymous

> А как ты думаешь, сколько тактов займёт поиск нужного элемента в дереве?

выше шла речь про нагрузку на кэш. Не спорю что конкретно на поиск в дереве скорее всего уйдет больше времени чем даже на некэшированный доступ в массив. Но ведь программа наверняка занимается чем-то еще кроме поиска этих id. Вот эти другие данные вытесняются из кэша и остальные дела программы тоже замедлятся. Ты учитываешь это?

dilmah ★★★★★
()
Ответ на: комментарий от dilmah

> Ты учитываешь это?

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

anonymous
()

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

anonymous
()
Ответ на: комментарий от dilmah

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

И что? Если бы оно в одну уместилось -- другой разговор, но это редкий случай.

Я имел в виду, что именно для sparse - массивов кэш -- панацея: наиболее востребованные элементы (как правило) будут оставаться в кэше (кэши-то современные -- сплошь ассоциативные!)

Die-Hard ★★★★★
()
Ответ на: комментарий от anonymous

> как я понимаю 100 упомянутых тактов тратяться на доступ к памяти

Ээ? Поподробнее пожалуйста.

anonymous
()
Ответ на: комментарий от anonymous

> а если массив большой и данных много то все преимущества сводяться на нет промахами кэша и дорогими обращениями к памяти

Если массив плотный, то с точки зрения кэширования нет никакой разницы с деревом.

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

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

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

Die-Hard ★★★★★
()
Ответ на: комментарий от Die-Hard

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

ну это зависит от использования. Может у него частой операцией является проверка на наличие в базе ID, которых там нет.

dilmah ★★★★★
()
Ответ на: комментарий от dilmah

> ...зависит от использования. Может у него частой операцией является проверка на наличие в базе ID, которых там нет.

Тоже верно!

Die-Hard ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.