Redis: внедрить взвешенный ориентированный граф - PullRequest
Новая
       6

Redis: внедрить взвешенный ориентированный граф

6 голосов
/ 19 июня 2011

Каков наилучший способ реализации взвешенного графика с использованием Redis?

В основном мы будем искать кратчайшие пути по графику (возможно, с использованием алгоритма Дейкстры)

В настоящее времямы рассмотрели добавление ребер в Redis

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

Что ты думаешь?Поправьте меня, если я ошибаюсь, но единственная неприятность здесь в том, что за каждый запрос для следующего узла в отсортированном наборе мы платим O (logn) вместо O (1) ...

http://redis.io/commands/zrange

Ответы [ 2 ]

3 голосов
/ 19 июня 2011

Получение следующего элемента в отсортированном наборе - только O (log (n)), если вы получаете их по одному, в этом случае задержка соединения с Redis будет больше проблемой, чем сложностьюоперации.

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

1 голос
/ 11 сентября 2011

Извините за опоздание :), но недавно я столкнулся с той же проблемой, и я смоделировал ее с помощью хэшей. Я согласен с Томом Кларксоном в том, что (почти) все должно быть загружено в локальную память, и я добавляю, говоря, что эффективным способом с точки зрения пространства является использование хешей и хранение графической информации следующим образом: 

Graph = { node1 : { nodeX : edge_weight, nodeY : edge_weight, other_info: bla..},
          node2 : { nodeZ : edge_weight, nodeE : edge_weight, other_info: bla..},
          bla bla...
        }

Если вам нужно больше места и эффективности, сожмите каждое значение (которое может быть строкой JSON ...) и распакуйте / импортируйте / десериализуйте в своем клиентском коде.

...