LINUX.ORG.RU
Форум — Development  

Ассоциативная память

 


0

3

Если известна функция распределения вероятностей по ключам, где вероятностью является частота использования ключа (вставка, поиск, удаление и т.д.), то какая структура данных/подход лучше для этого подойдет?
К примеру, известно что 10 ключей из миллиона будут использоваться в 90% случаев. Ясно что можно использоваться два дерева, одно для десяти наиболее вероятных ключей, другое - для остальных.

← Лисп. Точечные пары.
QtCreator unit tests running →

Пахнет алгоритмом Хэмминга. Я думаю на основе этой идеи может быть дерево

vertexua ★★★★★
()
Последнее исправление: vertexua (всего исправлений: 1)

Если известна функция распределения вероятностей по ключам, где вероятностью является частота использования ключа (вставка, поиск, удаление и т.д.), то какая структура данных/подход лучше для этого подойдет?

http://ru.wikipedia.org/wiki/Код_Хэмминга если я правильно понял ТЗ.

emulek ★
()

Не специалист и не очень уверен, что эта структура хорошо подойдёт, но всё же см. splay tree

anonymous
()

по идее, зависит от размера множества ключей и ожидаемого процента наполнения

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

Дерево Хаффмана?

точно. Странно, что оно не туда завело... Вот: http://ru.wikipedia.org/wiki/Код_Хаффмана

идея в (рекурсивном)разделении множества ключей на две НЕ равные части. Вероятность выбора ветви определяется весом этой ветви. Веса и ветви объединяются по Хаффману. Скажем если есть две ветви с весами 0.1 и 0.2, создаётся случайное число 0..0.3, и выбирается первая ветвь если число <0.1.

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

А что, википедики про что-то другое написали?

Нет, просто ты следом за остальными долбоебами перепутал Хаффмана с Хэммингом.

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

перепутал Хаффмана с Хэммингом.

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

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

вся наука создана ...

ибо по закону Арнольда

если закон имеет имя_чела то этот закон был сформулирован кем-то до рождения «подразумеваего чела из имя_чела»

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

аберация памяти и эволюционый принцип в деградации информации при мутантабельном копировании.

qulinxao ★★☆
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Лисп. Точечные пары.
Development
QtCreator unit tests running →