информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
А кажись неправильный селект у тебя 17.10.06 22:39  Число просмотров: 3454
Автор: 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 мс.
> В общем, я думаю, всё нормально. Спасибо.
<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-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach