Я снова изобрел велосипед?

Question

[netslow]

Дерево остатков

Недавно в голову пришла следующая идея:

Если взять список простых чисел 2,3,5,7…
Можно построить дерево, где каждый уровень дерева соответствует простому числу, и у всех узлов данного уровня количество дочерних элементов равно этому числу. Позиция в дереве определяется путем взятия остатка от деления на простое число. Можно сказать, что мы кодируем число в системе остаточных классов(СОК).
Допустим число 15 можно закодировать так:
15 % 2 = 1
15 % 3 = 0
15 % 5 = 0
Значит маршрут поиска элемента в дереве будет 1 0 0

Вот пример полного дерева для основания (2,3)
dl.dropbox.com/u/20772796/tree.png

Выскажие ваше экспертное мнение, встречались ли вы с такими структурами данных?

Если кому-то интересно, я набросал первый вариант реализации на Scala github.com/netslow/rtree

Comments

[sainnr]

Интересно, но не совсем понятно про само дерево — не могли бы вы нарисовать схему-пример такого дерева?

[netslow]

Добавил ссылку на рисунок. Извините за качесво. Набросал на коленке.

[Kindman]

И, чем оно (это представление) отличается в сторону выгоды от бинарного дерева, и соответственно двоичного пути?
В «двоичном» пути элемент пути занимает 1 бит, в «остаточном» же — минимум — 1 байт.

[Ogra]

Компьютер то все равно работает с байтами.

[NikoM]

компьютер работает со словами

[netslow]

Отличается в первую очередь тем, что не требуется постоянная балансировка дерева, оно изначально сбалансировано. К тому же растет это дерево более равномерно. А на хранение остатков действительно потребуется несколько больше памяти, тут не поспоришь. Хотя если посидеть подумать, можно немного оптимизировать это дело

Answer 1

[SabMakc]

Необходимо провести оценку сложности добавление / удаления и поиска элемента в таком дереве.
Потом сравнить со стандартными реализациями (Бинарное, Б-Дерево, АВЛ и т.д.) и тогда уже судить о применимости данного дерева к задачам.
Вполне может оказаться, что при реальном использовании сложность будет крайне высока (взятие целой части — не такая простая задача, выполняется гораздо дольше простого сравнения 2х чисел).

Comments

[netslow]

Вы абсолютно правы! Сейчас как раз над этим голову ломаю. К несчастью не часто работаю с O(), поэтому не имею опыта оценки сложности. Если есть что подсказать или есть полезные ссылки, поделитесь. Буду признателен. В принципе сложность добавления/поиска зависит от выбранного основания, ну а основание зависит от числа, которое требуется закодировать.
И конечно с самого начала у меня в голове засела эта операция — взятие остатка. Логика подсказывает, что операция эта достаточно трудоемкая. Но здесь я тоже не эксперт. Быть может все таки есть оптимизированные варианты взятия остатка?

[B@rmaley.e><e]

, Кормена читали? Там есть пара глав по анализу алгоритмов.

[netslow]

Так же отдельный вопрос — как быть с оценкой сложности параллельных алгоритмов? Про это тоже где-нибудь написано?

Answer 2

[yeputons]

Не встречался. А вы уже придумали этому какое-нибудь применение? Идея красивая

Comments

[netslow]

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

Answer 3

[sainnr]

Мне кажется, стоит разобрать конкретный вариант применения (лучше 2 — удачный и не очень). Тогда на примере решения какой-нибудь задачи уже можно будет оценить сложность использования данного решения и сравнить с другими вариантами решения поставленной задачи.

Answer 4

[IlyaPodkopaev]

в ИППМ РАН целый институт этим занят. некоторые вещи очень быстро считаются. а если еще логарифметику добавить… в общем, этому методу лет 50 не меньше

Comments

[netslow]

В таком случае дайте пожалуйста ссылки на работы

Answer 5

[okazymyrov]

Какова цель этого дерева? Приведи ещё пару примеров для других чисел (например, 7, 12, 14).

Comments

[netslow]

Все зависит от выбранных оснований. Для того, чтобы закодировать числе 7, 12, 14 необходимым и достаточным будет основание (2,3,5). Максимальное количество чисел, которое можно закодировать при таком основании — 30 (2*3*5)
7%2 = 1, 7%3 = 1, 7%5 = 2. Маршрут в дереве 1 1 2
12%2 = 0, 12%3 = 0, 12%5 = 2. Маршрут в дереве 0 0 2
14%2 = 0, 14%3 = 2, 14%5 = 4. Маршрут в дереве 0 2 4

Answer 6

[Андрей Буров]

идея интересная, но не практичная для большого кол-ва данных.
Для большого дерева, необходимо иметь большой список простых чисел

Comments

[netslow]

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

[Ogra]

Только что посчитал: чтобы записать 3 * 10¹⁹ элементов потребуется иметь всего лишь 16 простых чисел.

[Андрей Буров]

значит я ошибался…

Answer 7

[NikoM]

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

Comments

[netslow]

Почему вы так считаете? Не обязательно создавать сразу все узлы, можно создавать их по мере необходимости