Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Ну... можешь конечно еще одну таблицу завести [upd] [upd] 17.10.06 16:30 Число просмотров: 3505
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 17.10.06 18:48 Количество правок: 3
|
> Решение оказалось довольно простым. Будет где-то
> тысячи-десятки тысяч путей, каждый по 10-20 точек. Т.е.
> около 200000 записей. Вроде не страшно.
> Но придётся додумывать, т.к. на самом деле "заданный" путь
> изначально известен только в виде начальной и конечной
> точек.
Ну... можешь конечно еще одну таблицу завести (номер пути, начальна точка, конечная точка) это даже в той же таблице можно хранить, но с какой-то пометкой... тогда селект будет похитрее. Но тогда будет некоторая неоднозначность - типа с такими начальной и конечной точкой может быть несколько путей...
Ты уверен вообще, что задача стоит именно так, как ты ее сформулировал, а не задача комивояжера, например?
Напиши поподробнее чтоли для каких целей все это мутится?
-- upd --
Вообще 200000 записей - это ощутимо... все таки там в селекте таблица сама с собой связывается, а если еще и конечную, начальную точку пути будешь хранить - то 3 раза связывать надо это 200000х200000х200000 = 8 хрензнаетскольколионов. Тут уже будет зависеть от СУБД - насколько она там у себя внутри сможет оптимизировать запрос - вопрос достаточно тонкий. Потестируй - если никак - то давай будем дальше думать. Сообщи о результатах потом, плз
-- еще upd --
Вообще от хранения именно ребер, а не вершин никуда не уйти =( Ведь у тебя орграф.
Вот можно немного так извратиться:
Хранишь в таблице просто граф (без привязки к путям, только ребра), но каждому ребру еще приписываешь UID, таким образом у тебя в таблице не будет дублирующихся ребер. И заводишь еще табличку (UID_ребра, номер_пути). Во второй таблице столько же записей, сколько и в первом предложенном варианте. На первый взгляд - вроде как и увеличили количество записей в целом, да еще и UID_ребра добавили, да еще в 2-х таблицах... однако на некоторых СУБД это может дать выигрыш, т.к операция будет происходить в 2 захода и от первого захода записи закэшируются:
1. Читаешь из таблицы графа все UID, пренадлежащие указанному пути (они и закэшируются)
2. Выбираешь из второй таблицы только записи, для которых UID_ребра IN (полученный_список)... ну и также потом count и сортировка по count'у
Подчеркиваю опять - изначальный вариант или этот будут работать на разных СУБД по разному.
Можно еще извартиться в UID_ребра как-то зашифровать ВСЕ пути, которые по нему проходят - тогда не нужна будет вторая таблица... или там, например, хранить не орграф, а просто граф (тогда записей в первой таблице будет примерно в 2 раза меньше), а направление в виде еще одного поля перенести во 2-ю таблицу... а фактически все это те же яйца.
Короче фиг от такого количества записей уйдешь, кажись =(
|
|
|
подробно о проекте
Анализ криптографических сетевых...
