@laniminel

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

Я ищу оптимальные решения по структуре данных для двустороннего поиска. У меня есть данные и их эквивалентные значения, допустим:
5d86fcfeb0b8d050469498.jpeg
Я хочу:
>>> find(’A’)
value1, value2, value3
>>> find(’value1’)
A, B

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

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

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

А - value1
value1 -А
Ответ написан
Комментировать
sgjurano
@sgjurano
Разработчик
Попробуйте 2 дикта (если уж пишите на питоне) — под прямой и инвертированный индекс.
Ответ написан
Комментировать
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
1. Узлы (графа) - это и объекты, и данные. Это смешанный граф.
2. Направления связей (между узлами в графе): нет связи, односторонние, двухсторонние.
3. Когда делаете поиск - сразу просматриваются на заданных узлах все направления (к узлу и от него) на единичную глубину.
4. Далее, в зависимости от данных, происходит поиск вглубь, обратно или поиск прекращается.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы