| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > поиск с тройным ключом |
| Автор: null56 26.7.2012, 14:56 | ||
| Всем привет Задача: создать таблицу поиска, где ключом элемента будет структура из трех 2 байтовых полей, то есть каждое поле ключа может принимать значения в диапозоне [0..65535] Вот так ключ выглядит на языке Си
Интересны любые варианты. Мне в голову пока пришел лишь бинарный поиск или же дерево поиска. Еще может подойти trie или lc-trie, но пока разбираюсь заранее благодарен за помощь |
| Автор: boostcoder 26.7.2012, 15:58 |
| префиксное дерево. |
| Автор: baldina 26.7.2012, 16:37 | ||||||
| подойдет любая структура, ключ он и в африке ключ. на 64-разрядных системах этот ключ вообще меньше слова, удобно использовать хеш-таблицу с ключом
какие операции будут над этой таблицей? с какой частотой? каков предполагаемый размер таблицы? Добавлено @ 16:39
есть ли информация по распределению частот значений a, b, c и/или порядке их использования? |
| Автор: null56 26.7.2012, 17:43 | ||||||||
ну да, как раз сейчас изучаю lc-trie (оно же дерево префиксов) http://www.drdobbs.com/windows/fast-ip-routing-with-lc-tries/184410638 Добавлено через 2 минуты и 41 секунду
это таблица роутинга, который будет формироваться на лету, возможно довольно часто, размер более 100 скорее всего записей
пытался на это обратить внимание, но максимум что можно использовать, так это значение a (она же индекс waveform), количество двух других параметров непредсказуемо Добавлено через 4 минуты и 41 секунду алгоритм lc-trie используется в роутнге ядра, по идее должен подойти, но вопрос в скорости вставки Добавлено через 12 минут и 48 секунд
уж не знаю на сколько эффективен будет хеш за подсказку со структурой спасибо, но вряд ли она будет использоваться на 64 битов |
| Автор: volatile 27.7.2012, 01:01 | ||||
Всего-то? Имхо не стоит ради такого случая изобретать велосипед.
И теперь юзать стандартный std::map<key, data> |
| Автор: baldina 27.7.2012, 10:11 | ||||||
вставка O(1), поиск O(1). единственный недостаток - для эффективной работы требуется память, что бы таблица была заполнена процентов на 50. для 1000 записей думаю это не проблема. дерево (независимо от способа хранения) требует logN операций для поиска, для вставки теоретически столько же, но балансировка - операция дорогая. деревья в маршрутизации хороши лишь тем, что поиск (не вставку!) можно улучшить, имея префиксное дерево. поэтому я и спрашивал про порядок использования.
напоминает "число битов в восьмибитном байте может быть любым" 
только потому что его использовали какие-то умные ребята для своих целей? так они использовали для своих целей. Добавлено через 6 минут и 35 секунд если записей совсем немного (порядка 100), любой способ хранения будет упираться прежде всего в накладные расходы, а не теоретическую сложность. в хеш-таблицах это вычисление хеш-функции, в std::map и т.п. - распределение памяти. в этом случае, возможно, хранение в виде двоичного дерева в массиве, вообще без балансировки, будет лучшим решением. точно скажут тесты. Добавлено через 14 минут и 23 секунды еще одно соображение: хеш vs tree для 100 записей хеш будет примерно вдвое эффективней дерева: высота дерева - 7, количество 16-битных сравнений в хеше - 3-4 (32-битных на 1 меньше) для префиксных деревьев чуть иначе, но судя по Вашим словам, оно тут не будет эффективным. |
| Автор: Earnest 27.7.2012, 11:53 |
volatile, в таких случаях проще использовать memcmp: и букв меньше и работает быстрее.  И я согласна, что не стоит особо заморачиваться, а просто взять стандартный контейнер (map или hashmap) |
| Автор: null56 27.7.2012, 13:26 |
| Earnest, в ядре нет этих контейнеров, поэтому и их писать придется ранее я писал таблицу роутинга, но для статических манипуляций, я использовать rb-tree, работает в целом шустро и само балансируется, но это эффективно, когда количество вставок и удалений невысоко, то есть один раз задал пользователь маршруты, а далее лишь поиск по дереву в данном случае ситуация примерно такая приходит пакет, он несет информацию об удаленном роутере и его компонентах, штук 10-20 компонентов. роутер, на который пришел этот пакет, должен добавить адрес компонента (наше ключевое поле 3 * 16 бит) и соотвествующий этому компоненту роутер в таблицу маршрутизации. если компонент (ключ) уже присутствовал ранее втаблице роутинга, обновляем его запись... к тому же некоторый поток ядра будет периодически удалять записи из таблицы, которые устарели (на основании поля или других условий)... в общем это я к тому, что вставок может быть много и перебалансировка rb-tree может занять время значит остаются хеш и trie baldina, как бы вы хеш таблицу организовали? |
| Автор: baldina 27.7.2012, 13:46 | ||||||
кажется, задача не была достаточно подробно освещена, что бы делать какие-либо выводы  Добавлено через 11 минут и 19 секунд
закрытое хеширование с линейным пробированием, либо двойное хеширование. в качестве хеш-функции для начала - просто взятие остатка от деления ключа на размер таблицы. для удаления устаревших использовать счетчик в каждом поле либо отдельную очередь на удаление (куча). |
