Блог

У меня есть около 3500 средств борьбы с наводнениями, которые я хотел бы представить в виде сети для определения путей потока (по сути, направленный график). В настоящее время я использую SQLServer и CTE для рекурсивного анализа всех узлов и их вышестоящих компонентов, и это работает до тех пор, пока вышестоящий путь не разветвляется на много. Однако некоторые запросы занимают экспоненциально больше времени, чем другие, даже если они физически не намного дальше по пути (т. Е. Два или три сегмента «вниз по течению») из-за дополнительной сложности восходящего потока; в некоторых случаях я пропускаю более десяти минут, прежде чем завершить запрос. Я использую простую таблицу из двух столбцов, один столбец которой является самим объектом, а другой-объектом, расположенным выше по течению от объекта, указанного в первом столбце.

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

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

Итак, мой вопрос в том, правильно ли я храню эту информацию? Есть ли лучший способ, кроме CTE, запросить вышестоящие точки?

Лучший способ хранения графиков-это, конечно, использовать собственную базу данных графиков: -)

Взгляните на neo4j. Он реализован на Java и также имеет привязки Python и Ruby.

Я написал две вики-страницы с простыми примерами моделей предметной области, представленных в виде графиков с использованием neo4j: сборка и роли. Дополнительные примеры можно найти на странице галереи моделирования домена.

Я ничего не знаю о средствах борьбы с наводнениями. Но я бы выбрал первое средство. И используйте временную таблицу и цикл while для создания пути.

-- Поддающийся соблазнению псевдокод (последний, текущий, N)



ОБЪЯВИТЕ @intN НАБОР @intN = 1


ВСТАВИТЬ В TempTable(последний, текущий, N) -- Вставить первый элемент в список без элементов восходящего потока...вызовите это начальное условие, ВЫБЕРИТЕ lastNode, currentNode, @intN ИЗ вашей таблицы, В которой у узла нет ничего выше по течению


В ТО ВРЕМЯ КАК @intN


 IF @@ROWCOUNT = 0
     BREAK
 
конец
Если мы предположим, что каждый узел указывает на одного потомка. Тогда это должно занять не более 3500 итераций. Если несколько узлов имеют одного и того же вышестоящего поставщика, то это займет меньше времени. Но что еще более важно, это позволяет вам сделать это...
ВЫБЕРИТЕ ПОСЛЕДНИЙ, текущий, N ИЗ заманчивого ЗАКАЗА ПО N
И это позволит вам увидеть, есть ли какие-либо циклы или какие-либо другие проблемы с вашим провайдером. Кстати, 3500 строк-это не так уж много, поэтому даже в худшем случае, когда каждый поставщик указывает на другого вышестоящего поставщика, это не должно занять так много времени.

Традиционно графики представлены либо матрицей, либо вектором. Матрица занимает больше места, но ее легче обрабатывать(в вашем случае 3500×3500 записей); вектор занимает меньше места(3500 записей, у каждой есть список тех, к кому они подключаются).

Тебе это помогает?

я думаю, что ваша структура данных в порядке (для SQL Server), но CTE может быть не самым эффективным решением для ваших запросов. Вы можете попробовать создать хранимую процедуру, которая пересекает график, используя вместо этого временную таблицу в качестве очереди, это должно быть более эффективным.

временную таблицу также можно использовать для устранения циклов на графике, хотя их не должно быть

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

Что касается формата на диске, DOT довольно портативен/популярен среди других. Также кажется довольно распространенным хранить список ребер в плоском формате файла, например:

 vertex1 vertex2 {edge_label1} 
 

Где первая строка файла содержит количество вершин в графике, а каждая последующая строка описывает ребра. Будут ли края направлены или неориентированы, зависит от исполнителя. Если вам нужны явные направленные ребра, опишите их с помощью направленных ребер, таких как:

 vertex1 vertex2
vertex2 vertex1
 

Мой опыт хранения чего-то подобного описанному вами в базе данных SQL Server:

Я хранил матрицу расстояний, указывающую, сколько времени требуется для перемещения из точки А в точку Б. Я сделал наивное представление и сохранил их непосредственно в таблице под названием расстояния со столбцами A,B,расстояние,время.

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

Я мог бы предоставить некоторый код, но это был бы C#.