информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
За кого нас держат?Spanning Tree Protocol: недокументированное применениеПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Крупный взлом GoDaddy 
 Просроченный сертификат ломает... 
 Phrack #70/0x46 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Ну, если у меня путь не в таблице, то джоинить незачем и... 17.10.06 23:11  Число просмотров: 2924
Автор: ZloyShaman <ZloyShaman> Статус: Elderman
Отредактировано 17.10.06 23:12  Количество правок: 2
<"чистая" ссылка>
Ну, если у меня путь не в таблице, то джоинить незачем и нечего. Можно так:
select route_id, count(route_id) weight
       from routes
            where 
            (p1 = x1) AND (p2=x2) OR
            (p1 = x2) AND (p2=x3) OR
             .....
       group by route_id;

---
Но тут минус, план будет каждый раз составляться. Надо что-то придумать.
<programming>
Поиск путей, имеющего максимальное число общих пунктов с заданным 16.10.06 16:30   [whiletrue]
Автор: ZloyShaman <ZloyShaman> Статус: Elderman
<"чистая" ссылка>
Представим множество точек, они не имеют координат, просто каждая точка связана (двухсторонне) с одной (двумя или больше) "соседними" точками. "Путь" - это подмножество соседних (каждая, кроме крайней, непосредственно связана с предыдущей и последующей) точек, которые связаны в определённом порядке. Пусть есть множество таких путей.
Теперь возьмём один путь. Нужно ранжировать (или хотя бы найти первые N) все остальные пути по признаку совпадения с заданным путём. Совпадение мыслится как общие точки пути, следующие в том же порядке. Т.е.
Пути 1-2-3-4-5 и 2-3-4-5-6 имеют общие точки 2-3-4-5 и довольно неплохо совпадают.
А пути 1-2-3-4 и 4-3-2-1 хоть и имеют все общие точки, но совершенно не совпадают.
Соответственно нужен алгоритм быстрого поиска наиболее совпадающих путей.
Дальше хуже. Эти пути нужно хранить в реляционной БД. Этот поиск - основная задача, так что способ хранение путей в БД можно выбрать такой, какой удобно для этой задачи.

Скажите, куда копать, чего набирать в гугле и вообще.
Заранее спасибо.
Тебе надо найти максимально совпадающие пути? Или пути,... 11.12.06 03:55  
Автор: MadBinom Статус: Незарегистрированный пользователь
<"чистая" ссылка>
Тебе надо найти максимально совпадающие пути? Или пути, максимально совпадающие с заданным? Или в одной точке? Короче, если решение все еще нужно - запости поточнее условия задачи, наверное, помогу.
Это у тебя связный орграф 16.10.06 16:55  
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>
Способов хранения графа фактически два

Способ первый: массив ребер.
Пусть в графе M ребер. Заведем массив размером Mx2, в котором будем хранить ребра парами вершин, которые они соединяют. Это наиболее понятный, но достаточно неудобный способ хранения графа. Однако у него есть один большой плюс - при таком способе представления легко вводить дополнительные характеристики ребер. Например, чтобы сохранить веса ребер, достаточно сделать массив размером Mx3 и в дополнительную ячейку для каждого ребра записать его вес.

Способ второй: матрица смежности.
Пусть в графе N вершин. Заведем матрицу размером NxN, где в элемент ai,j запишем количество ребер из вершины i в вершину j. Если граф взвешенный, то вместо количества запишем вес соответствующего ребра. В случае отсутствия ребра запишем бесконечность. Таким образом, проявился один из недостатков такого представления: в матрице смежности невозможно хранить взвешенный граф с кратными ребрами. Однако, в некоторых случаях, это можно обойти. Очень часто из всего множества ребер между данной парой вершин нам достаточно хранить только одно - самое легкое.

В твоем случае - второй способ не очень удобен, т.к. у тебя БД

Насчет конкретно твоего алгоритма поиска еще подумаю.. позже напишу

http://www.intuit.ru/department/algorithms/gaa/
Ну, просто хранение графов - это не проблема. Так что с нетерпением жду наводку на алогритм 16.10.06 17:23  
Автор: ZloyShaman <ZloyShaman> Статус: Elderman
<"чистая" ссылка>
По ссылке очень много теории. Не смог найти, какой из алгоритмов может навести на мысль.
Это я для затравки дал, чтобы ты хотя бы терминов не пугался - над твоей конкретно задачей позже подумаю 16.10.06 17:44  
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>
Мдаа... зря я кажись про все эти графы... 17.10.06 13:12  
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 17.10.06 14:23  Количество правок: 5
<"чистая" ссылка>
Сабж. Решение-то тупейшее =)


create table ways ( -- Таблица путей
way_num INT, -- Номер пути
point_from INT, -- Точка от
point_to INT -- Точка до
)

С этой таблицей понятно? Если да, то вот таким нехитрым селектом получишь че хочешь:

SELECT w2.way_num, COUNT(*)
FROM
ways [as] w1
INNER JOIN
ways [as] w2
ON
w1.way_num = <указанный номер пути> AND
w2.way_num != <указанный номер пути> AND
w1.point_from = w2.point_from AND
w1.point_to = w2.point_to
GROUP BY
w2.way_num
ORDER BY 2

Скажи, сколько тысяч записей будет в таблице и какая собственно БД (а то вон в Информиксе, допустим, иннер джойн очень тормозит...) тогда нужно подумать - стоит ли оптимизировать или сама СУБД быстро отработает...
Я не понял структуру таблицы. Чему соответствует одна запись? Может в аську? 17.10.06 14:56  
Автор: ZloyShaman <ZloyShaman> Статус: Elderman
<"чистая" ссылка>
Не могу =( Я в Альфа-банке сижу - тут все прикрыто, кроме 80-го порта =))) 17.10.06 15:08  
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>
ну у тебя есть несколько путей (множество), давай пронумеруем их, т.е. каждый путь получит свой way_num - это первое поле. В таблице будем хранить не просто вершины пути, а ребра, т.е
для каждого пути - множество пар точек (точка от, точка до) - это 2-е и 3- поля. Понятно?
offtop: попробуй login.icq.com, порт 80. приятно удивишься) (если конечно icq.com не заблочен) 18.10.06 09:30  
Автор: !mm <Ivan Ch.> Статус: Elderman
Отредактировано 18.10.06 09:32  Количество правок: 1
<"чистая" ссылка>
Заблочен =( см.ниже. Варант - только через anonymouse.org и go.icq.com Но это геморрой 18.10.06 15:30  
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>
Тогда еще один вариант 18.10.06 15:56  
Автор: !mm <Ivan Ch.> Статус: Elderman
<"чистая" ссылка>
юзай сервис tcompressor.ru - при первом запуске программы придется подождать, если не платный акк, но зато не надо париться с проксями, плюс у аськи коннект стабильный и работает довольно шустро
я его юзаю уже около месяца, никаких проблем
через него же можно юзать mIRC и прочее

один минус - ограничение по портам - сервис доступен только по 21, 110, 443, 5190, 47901
Спасибо. Возьму на заметку. Только я здесь где-то до конца месяца... Потом таких проблем не будет, но все равно спасибо =) 18.10.06 16:01  
Автор: whiletrue <Роман> Статус: Elderman
<"чистая" ссылка>
Так, идею понял, спасибо. 17.10.06 16:11  
Автор: ZloyShaman <ZloyShaman> Статус: Elderman
<"чистая" ссылка>
Решение оказалось довольно простым. Будет где-то тысячи-десятки тысяч путей, каждый по 10-20 точек. Т.е. около 200000 записей. Вроде не страшно.
Но придётся додумывать, т.к. на самом деле "заданный" путь изначально известен только в виде начальной и конечной точек.
Ну... можешь конечно еще одну таблицу завести [upd] [upd] 17.10.06 16:30  
Автор: 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-ю таблицу... а фактически все это те же яйца.

Короче фиг от такого количества записей уйдешь, кажись =(
В общем, сделал так 17.10.06 22:28  
Автор: ZloyShaman <ZloyShaman> Статус: Elderman
<"чистая" ссылка>
Всё будет на мускуле, так что:
CREATE TABLE `routes`
  ( `route_id` int(11) NOT NULL,
    `p1` int(11) NOT NULL,
    `p1` int(11) NOT NULL,
    `ordr` int(11) NOT NULL,
    KEY `p1p2` (`p1`,`p2`) )
  ENGINE=InnoDB;

---
Тестовых данных напихал около 340000 записей (т.е. 18000 путей по 20 точек), но довольно однообразно. Поскольку инетересующий путь берётся не из базы, то запрос выглядит так:
select route_id, count(route_id) weight
  from routes
  where p1 IN (x1, x2, ...)
    AND p2 IN (x2, x3, ...)
  group by route_id
  order by weight DESC;

---
Выполняется в районе 1,5 секунд. Но это на виртуальной машине. И сильно зависит от количества путей, которые имеют хотя бы одну общую точку. Если общая точка только одна, то 15 мс.
В общем, я думаю, всё нормально. Спасибо.
А кажись неправильный селект у тебя 17.10.06 22:39  
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 17.10.06 22:42  Количество правок: 1
<"чистая" ссылка>
>
> CREATE TABLE `routes`
>   ( `route_id` int(11) NOT NULL,
>     `p1` int(11) NOT NULL,
>     `p1` int(11) NOT NULL,
тут p2 ты имел ввиду наверное...

>     `ordr` int(11) NOT NULL,
>     KEY `p1p2` (`p1`,`p2`) )
>   ENGINE=InnoDB;
> 

---

таблицу понял

ordr - это типа порядок следования ребер друг за другом... это вобщем-то лишняя инфа - ну ладно, может удобней че-то делать будет...

> Тестовых данных напихал около 340000 записей (т.е. 18000
> путей по 20 точек), но довольно однообразно. Поскольку
> инетересующий путь берётся не из базы, то запрос выглядит
> так:
>
> select route_id, count(route_id) weight
>   from routes
>   where p1 IN (x1, x2, ...)
>     AND p2 IN (x2, x3, ...)

это не правильное услвие! Либо паре присваивай ИД и тогда IN (список ИД) или связывай таблицу саму с собой... как в моем первом селекте. Твое условие работает быстрее, но не правильно

>   group by route_id
>   order by weight DESC;
> 

---
> Выполняется в районе 1,5 секунд. Но это на виртуальной
> машине. И сильно зависит от количества путей, которые имеют
> хотя бы одну общую точку. Если общая точка только одна, то
> 15 мс.
> В общем, я думаю, всё нормально. Спасибо.
Ну, если у меня путь не в таблице, то джоинить незачем и... 17.10.06 23:11  
Автор: ZloyShaman <ZloyShaman> Статус: Elderman
Отредактировано 17.10.06 23:12  Количество правок: 2
<"чистая" ссылка>
Ну, если у меня путь не в таблице, то джоинить незачем и нечего. Можно так:
select route_id, count(route_id) weight
       from routes
            where 
            (p1 = x1) AND (p2=x2) OR
            (p1 = x2) AND (p2=x3) OR
             .....
       group by route_id;

---
Но тут минус, план будет каждый раз составляться. Надо что-то придумать.
Вот так правильно, а два IN-а не правильно. 17.10.06 23:42  
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 17.10.06 23:45  Количество правок: 1
<"чистая" ссылка>
Только еще скобки надо бы расставить, а то у AND-а и у OR-а одинаковый приоритет - в итоге не правильно твое условие отработает

Что значит "план будет составляться" - не понял
Ну, перед запросом генерируется же план выполнения. А поскольку запрос состоит из разного числа условий, то этот план не сможет закешироваться и будет генериться каждый раз. 17.10.06 23:45  
Автор: ZloyShaman <ZloyShaman> Статус: Elderman
<"чистая" ссылка>
Я конечно не пробовал, но уверен, что эта проблема (с зафайерволенными портами) решаема 17.10.06 15:53  
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>


http://wiki.noreply.org/noreply/TheOnionRouter/TorFAQ#FirewalledClient
1  |  2 >>  »  






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach