Описание тега radix-tree
Радикс-дерево - это дерево, в котором каждый узел с одним дочерним элементом объединяется со своим дочерним элементом в качестве формы оптимизации пространства.
1
ответ
Почему в ядре Linux radix_tree_preload возвращается с отключенным выгрузкой
Я просматривал статью о реализации ядра ядра Linux, ссылка на статью упомянута ниже: http://lwn.net/Articles/175432/ В этой статье упоминается, что radix_tree_preload выделяет достаточно памяти, чтобы последующая вставка в дерево не завершилась неуд…
16 дек '13 в 13:51
2
ответа
Расширение дерева до большего количества листьев
Я должен сделать словарь, используя попытки, количество букв в алфавите увеличится с 26 до 120, и, следовательно, число листовых узлов увеличится в геометрической прогрессии. Какие оптимизации можно использовать, чтобы время поиска, вставки и удален…
24 мар '16 в 23:52
1
ответ
Как построить Radix Tree в JavaScript?
Вдохновленный предсказанием следующего слова iOS7 iMessage, я решил попытаться написать скрипт, который на основе пользовательского ввода узнает, какие слова / буквы, скорее всего, хотят завершить текущее слово пользователя или какое слово, скорее в…
11 фев '15 в 06:43
1
ответ
Проблема со списком Python для сложных типов
Ниже приведен фрагмент кода в Python, который хранит префиксы IP в основополагающем дереве, а затем связывает IP и ASN в словаре, если IP принадлежит префиксу. Я хотел бы узнать все различные ASN для конкретного префикса. Более подробная информация …
18 сен '15 в 09:37
1
ответ
Разыменование указателя на неполный тип (основное дерево)
У меня большие проблемы с моим определением структуры. Я пробовал несколько разных способов их определения, но не могу избавиться от ошибки. У меня, вероятно, также есть множество других проблем с кодом, но я не могу исправить их, не найдя их, запус…
27 апр '15 в 14:30
1
ответ
Значение термина "Radix" в дереве Radix
Хотя трудно найти единодушное определение "дерева радиксов", большинство принятых определений дерева корней указывают, что это сжатое дерево префиксов. Что я пытаюсь понять, так это значение термина "основание" в данном случае. Почему сжатые префикс…
17 окт '16 в 13:14
4
ответа
В чем разница между структурами данных trie и radix trie?
Структуры данных trie и radix trie - это одно и то же? Если они одинаковы, то в чем смысл radix trie (AKA Patricia trie)?
05 фев '13 в 12:58
1
ответ
Поменять местами (или упростить) декартово произведение?
Чтобы упростить, но и усложнить задачу, я попытался реализовать концепцию " комбинированных / кратких тегов ", которая в дальнейшем расширится до нескольких основных форм тегов. В этом случае теги состоят из (одного или нескольких) "под-тега (ов)", …
31 дек '14 в 18:18
1
ответ
Слияние двух двоичных файлов
Я хочу объединить две структуры дерева, но лучшая сложность, о которой я могу думать, это Получить список значений из другого дерева: O(n), n - количество узлов в дереве. Вставьте все значения из списка вводной цели: n * O(m), m - длина ключа. Учиты…
18 дек '17 в 20:57
2
ответа
Патриция Три для быстрого поиска адреса IPv4 и спутниковых данных
Я пишу программу на C++, которая требует, чтобы IP-адреса (все IPv4) были быстро найдены и сохранены. Каждый IP-адрес имеет данные, связанные с ним. Если он уже существует в дереве, я намерен объединить данные IP-адреса в дереве с данными новых адре…
03 окт '12 в 13:41
0
ответов
Сброс дерева корней на диск
Я реализовал основополагающее дерево в Scala. Используя список слов, я могу успешно создать дерево в памяти. Проблема в том, что я пытаюсь проиндексировать очень большой файл, содержащий около 30 миллионов слов, и дерево не помещается в памяти. Пред…
16 мар '18 в 19:28
1
ответ
Как пройти по дереву кэша страниц (основному дереву) адресного пространства файла в ядре Linux
Мне нужно получить статистику кэша страниц открытого файла. В файловой структуре есть указатель address_space (f_mapping), который, в свою очередь, имеет корень корневого дерева, называемого page_tree. Мне нужно пройти по этому дереву, чтобы получит…
24 апр '15 в 12:59
3
ответа
Какова пространственная сложность радикального дерева?
Я всегда был обеспокоен использованием пространства радикс-дерева, но я не нашел никаких полезных обсуждений по этому вопросу. Теперь давайте предположим, что у нас есть реализация основанного на ядре дерева, аналогичная linux radix-tree.c, которая …
13 дек '13 в 18:14
3
ответа
Слова, содержащие как минимум 2 общие буквы
Строка называется 2-согласованной, если каждое слово имеет как минимум 2 буквы, общие со следующим словом. Например "Атом другой эпохи" [atom имеет a а также t общего с another а также another имеет e а также a общего с era (ответ не уникален). Преж…
16 июл '15 в 04:59
1
ответ
Поиск строк в адаптивном радикальном дереве
Я просматривал исследовательскую работу "Дерево адаптивных корней: индексирование ARTful для баз данных основной памяти", у меня был вопрос о том, как вы можете сопоставить строки с ключами узла. Например: если бы у меня было слово: Iota, которое бы…
19 ноя '17 в 22:18
1
ответ
Самый длинный поиск префикса с диска
В настоящее время у меня есть некоторая реализация, которая выполняет Longest Prefix Lookup (LPM) из структуры данных радикального дерева. Эта структура данных содержит префиксы IP (основополагающее дерево с максимальной глубиной 128 бит), и в насто…
18 фев '18 в 12:22
0
ответов
Сохраняет ли основание три строки всю строку в узле?
Сегодня я программировал основополагающее дерево в классе Java. В классе мы узнали, что каждый узел в основном дереве хранит строку. Например, если родительский узел узла B является узлом A, узел A хранит "корову", а узел B хранит "коров" Тем не мен…
26 ноя '17 в 15:47
4
ответа
Оценка скорости / использования памяти для различных структур данных
Я пытаюсь решить, какую структуру данных использовать для следующего. Допустим, у меня есть около 10 миллионов ключей, которые содержат указатели на уникальные объекты, содержащие некоторые данные. Ключи UUID представляют собой 16-байтовые двоичные …
13 июл '11 в 11:42
1
ответ
Упорядочение дочерних узлов в дереве trie / radix
Когда я просматриваю Трисы и радикальные деревья, такие как http://en.wikipedia.org/wiki/Compact_prefix_tree и http://en.wikipedia.org/wiki/Trie, я не вижу конкретной информации о лексикографическом упорядочении дети узла. так, например, в этом прим…
16 янв '14 в 03:28
1
ответ
Три против Radix Tree против Патрисии Три
Как я понимаю (также отсюда), сложность памяти этих DS можно заказать как Trie > Radix > Patricia. Но как насчет сложности времени? Я предполагаю, что они почти одинаковы. Если упомянуть мою проблему, я хочу сделать много поисковых запросов с префик…
29 мар '16 в 09:57