Dmitry_Milk Не дольше чем в дерево. Добавлять в хеш-таблицу можно без выделения памяти из кучи. А куча она умеет потормозить.
r90 У Вас проблемы с теорией алгоритмов. Вставка в табличку будет занимать время ~n, вставка в дерево ~ln(n). Так что ничуть не меньше. Atlantic Покажите алгоритм. Всё это похоже на какой-то гон: вот, если взять хороший аллокатор, если предположить, что преимущественно будет происходить не вставка, а поиск и т.п. Дайте, наконец, кусок кода мапы size_t -> size_t. r90, Вы ведь били себя в грудь: Ну дык его писать -- двадцать минут вместе с отладкой и тестами. Прошла уже почти неделя, код так и не представлен. А Вы заявляли о 20 минутах.
Добавлять в дерево тоже можно без выделения памяти: Код (Text): template < class Key, class Type, class Traits = less<Key>, class Allocator=allocator<pair <const Key, Type> > > class map Создайте свой аллокатор в котором преалоцируйте память.
Да легко. Это стандартная техника для выделения памяти фиксированными кусками. 8 байт на два size_t, которые нужно хранить, еще 4 байта на указатель next для хэш-таблицы. Нужная память выделяется одним блоком размером 12*N байт, указатели next выставляются так, что образуют список свободных блоков. Когда надо выделить 12 байт - берется блок из начала списка, когда надо вернуть 12 байт - добавляется блок в начало списка. Список использует те же (физически) указатели, что и хэш-таблица, перерасхода памяти нет. Выделение и освобождение памяти гарантированно выполняются за константное время, что гораздо лучше стандартной кучи, которая может фрагментироваться. Собственно сам блок: Код (Text): struct SBlock { size_t first; size_t second; SBlock *next; }; Инициализация (для примера - N блоков): Код (Text): SBlock *blocks = new SBlock[N]; SBlock *list_begin = blocks; for (int i = 0; i < N - 1; ++i) blocks[i].next = &blocks[i + 1]; blocks[N - 1].next = 0; Выделение памяти: Код (Text): SBlock* get_block() { SBlock *result = list_begin; if (!result) { // по хорошему тут должно быть выделение нового массива блоков return 0; } list_begin = list_begin->next; return result; } Освобождение памяти: Код (Text): void free_block(SBlock *block) { block->next = list_begin; list_begin = block; } P.S. Аллокатор написал не в stl-совместимом виде, чтобы было понятней.
Atlantic это обычный односвязный список. Вставка/поиск в таком списке будет производиться за время ~n. Дерево даёт возможность вставлять за время ~ln(n). Где же тут бОльшая эффективность?
srm Ну хоть прочитать надо, что я написал. Это список для быстрого и эффективного выделения памяти. Или может еще и хэш-таблицу написать?
Конечно же нужен алгоритм вставки/удаления/поиска в мапе. Меня интересует именно мапа, зачем мне работа с памятью? Вам нужно было прочитать название темы.
srm Мне перепечатать код из учебника по алгоритмам, чтобы доказать, что я знаю как пишется хэш-таблица что-ли? Как то не хочется тратить время. Тем более что в реальном проекте я напишу stdext::hash_map<size_t, size_t> и не буду заморачиваться.
У меня есть сомнения, что мапу size_t -> size_t можно реализовать через хеш таблицу (в смысле, эффективно реализовать - эффективней, чем красно-чёрное дерево). Там же 20 минут вместе с отладкой и примерами! Вы больше времени тратите на дискуссию.
У меня нет сомнений. Хэш-таблицы как бы по умолчанию умеют справляться с коллизиями. Либо списки элементов с одинаковым хэшем, либо двойное хэширование.
Кто-то меня только что убеждал, что stl - ацтой, лучше писать свой велосипед. Зачем же Вы его собираетесь юзать?
Молодец, возьми конфетку с полки. Значит Вы плохо знаете теорию алгоритмов. Да, справляются. Но как это влияет на время работы с мапой? Отсюда и мои сомнения. Подбирать хеш функцию для случайного size_t - гиблое дело. Заранее могу сказать лишь то, что диапазон изменения параметра - от 0x00000000 до 0x7FFFFFFF.
Знаю хорошо. Хэш-таблицы асимптотически быстрее красно-черных деревьев, плюс у красно-черных деревьев медленная вставка и удаление (с большими константами перед logN). Зависит от процента заполненности хэш-таблицы и ее типа. Если хэш-таблица разрешает коллизии списками и заполнена примерно на 100%, то средняя длина списка равна 1 и про коллизии можно не вспоминать вообще. Ах, вот оно что. Не так уж и сложно подобрать. F(X) = (X * 0x8088405 + 1) % N, где N (простое число) - размер таблицы
Плохо знаете. Это только в случае идеальной хеш-функции. А почему Вы так уверены, что будет именно так? Давайте посчитаем скорость поиска при разумном N и оверхед по памяти.
Память я уже написал - 12*N байт + K*4 байт для собственно хэш-таблицы (указатели на начало списков), если K - размер таблицы, N - число хранимых элементов. Скорость поиска - сферический конь в вакууме. Зависит от компилятора, его настроек, реализации хэш-таблицы и дерева. Про асимптотику я уже сказал. Хэш-таблицы быстрее любых деревьев. Про вырожденные случаи типа корявой хэш-функции или специально подобранных данных под хэш-функцию я вообще не посчитал нужным упоминать раньше, это должно быть и так очевидным.
Подставьте конкретные числа и убедитесь, что никакого выигрыша ни в производительности, ни по памяти нет. Да и при чём здесь компилятор, посчитайте сложность алгоритма! Какое количество операций необходимо? Вот именно - это очевидно. Если я говорю про мапу size_t -> size_t, то очевиден диапазон изменения ключа. Вы же навязываете хеш таблицу, прекрасно понимая, что практической пользы от хеш таблицы при изменении аргумента в пределах от 0 до 0x7FFFFFFF нет никакой. Тут подбери какую угодно хеш функцию - будет дофига коллизий, а значит и сложность алгоритма будет приближаться к ~n.
