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

Больше минусов нет.

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

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

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

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

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

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

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

struct hz *hzarr[100000];

struct hz *find(id){

return arr[id];

}

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

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

Минуса два.

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

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

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

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

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

> забыта инициализация указателей в массиве NULL значением

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

Во вторых, есть http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html

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

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

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

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

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

не понимаю.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

http://www.cs.virginia.edu/papers/Hitting_Memory_Wall-wulf94.pdf

написано 14 лет назад. Стена только выросла.

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

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

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

http://www.csl.cornell.edu/~sam/papers/cf04.pdf

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

Тоже верно!