Эффективный алгоритм для двустороннего поиска?

Question

[laniminel]

Я ищу оптимальные решения по структуре данных для двустороннего поиска. У меня есть данные и их эквивалентные значения, допустим:

Я хочу:
>>> find(’A’)
value1, value2, value3
>>> find(’value1’)
A, B

Данных достаточно много, чтобы обход двойного списка был неэффективен, а скорость в данном случае первоочередный показатель. К тому же мне нужно иметь возможность обновлять структуру данных.

Любые варианты решения?

Answer 1

[maaGames]

Зависит от того, сколько это "достаточно много" и сколько есть оперативной памяти под эту задачу (ПК, смартфон, эмбедед разработка?).
Если память позволяет, то самым быстрым будет два бинарных дерева (либо два сортированных массива-списка, но тогда после добавления элемента придётся пересортировывать или искать место вставки).
Если A и Value сами по себе большие и/или сложные объекты, которые нельзя продублировать, то можно сделать две индексных таблицы, ссылающихся на оригинальные данные.
Самое быстрое - два отсортированных массива, в каждом из которых и А и Value.
Самое удобное, но чуточку менее быстрое - два бинарных дерева.

Comments

[res2001]

Думаю деревья будут такими же быстрыми на операциях поиска как и обычные отсортированные массивы.
Но тут другое более важно: если нужны только операции поиска, то можно обойтись и отсортированными массивами, если данные планируется добавлять/удалять/изменять, то деревья на этих операциях будут гораздо быстрее.

[maaGames]

res2001, Вообще, пока не назван используемый язык, я что-то передумал говорить о производительности :) Мало ли, как там контейнеры в испльзуемом языке реализованы.
По идее, индексированный доступ (вернее, прямой доступ по указателю) будет всегда быстрее косвенного доступа из дерева. Опять же, в зависимости от реализации, хранятся ли данные прям в узле дерева или в узле указатель на данные...
В любом случае, я бы предпочёл два бинарных дерева.

[res2001]

maaGames,

В любом случае, я бы предпочёл два бинарных дерева.

Я то же.

индексированный доступ (вернее, прямой доступ по указателю) будет всегда быстрее косвенного доступа из дерева.

Это если смотреть на операцию выборки из массива по индексу, когда индекс уже известен.
Если нужно искать в отсортированном массиве заданное значение, то это уже бинарный поиск, там есть свои накладные расходы: вычисление следующего индекса и т.п. Если принять это во внимание, то скорость обоих вариантов будет плюс-минус одинакова, даже, возможно, дерево будет быстрее на очень больших объемах.
Если же задачу можно свести к варианту индексного поиска (т.е. ключ поиска будет являтся индексом в массиве), то, конечно, массивы будут быстрее. Но, по моему, в большинстве случаев это не прокатывает.

[laniminel]

maaGames, Вы оказались правы, прототипирование на Python, с выносом операций низкого уровня в С-функции, на 64 битной машине показало отличный результат (ниже диаграмма памяти для 1 дерева).

Я еще смотрел в сторону B+деревьев, не знаю насколько они хороши в данном случае

[maaGames]

laniminel, B-tree только на скорость поиска влияют, не на использование памяти (если не ошибаюсь, конечно). Раз в первую очередь акцент на эффективность, то нужно сбалансированное дерево строить, чтобы время поиска было log(N). В сортированном массиве тоже сложность поиска log(N) и 500 мегабайт это небольшой размер для современных компьютеров. Так что я бы протестировал и вариант с массивами. Там и служебной информации гораздо меньше. Получается, сейчас ~200 байт на узел дерева, а ведь в нём хранятся как минимум два указателя на дочерние узлы, может ещё указатель на родительский узел. Т.е. 3*8=24 байта служебный. Это 10% от занятой памяти. Так что с массивами вместо 450 будет 400. Хотя, между 400 и 450 никакой разницы в 2019 году.

[laniminel]

maaGames, Я все же выбрал красно-черные. С массивами действительно неплохой вариант, но не хочется писать костыль, когда уже есть хорошо оптимизированные варианты под деревья, а 10% памяти не так критично. Да и получается, что с деревьями работать удобнее. Благодарю за помощь.

Answer 2

[skrimafonolog]

если заточены именно на скорость, то хранить дубли, это нормально.
то есть хранить все комбинации значений:

Ключ-Значение

А - value1
value1 -А

Answer 3

[Владимир Олохтонов]

Попробуйте 2 дикта (если уж пишите на питоне) — под прямой и инвертированный индекс.

Answer 4

[xmoonlight]

1. Узлы (графа) - это и объекты, и данные. Это смешанный граф.
2. Направления связей (между узлами в графе): нет связи, односторонние, двухсторонние.
3. Когда делаете поиск - сразу просматриваются на заданных узлах все направления (к узлу и от него) на единичную глубину.
4. Далее, в зависимости от данных, происходит поиск вглубь, обратно или поиск прекращается.

Делайте асинхронно, чтобы экономить время обработки.