Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Строка, где нашелся минимум?  [new]
kostichek
Member

Откуда:
Сообщений: 15
Есть таблица городов Town (TownID, TownName, X, Y).
Есть таблица станций Station (StationID, StationName, X, Y).

X, Y - географические координаты и существует функция dbo.GetDistance(X1,Y1,X2,Y2), которая считает расстояние между точками (X1,Y1) и (X2,Y2).

Нужно вывести список городов с ближайшей к нему станцией. Есть какое-нибудь человеческое решение?

select Town.*, Station.*, minDistance.*
from (select T.TownID,(select TOP 1 S.StationID from Station S order by dbo.GetDistance(S.X,S.Y,T.X,T.Y) asc) AS StationID from Town T) minDistance
inner join Town on Town.TownID = minDistance.TownID
inner join Station on Station.StationID = minDistance.StationID


select TT.*, SS.*, minDistance.*
from (select T.TownID, min(dbo.GetDistance(S.X,S.Y,T.X,T.Y)) md from Station S, Town T group by T.TownID) minDistance
inner join Town TT on TT.TownID = minDistance.TownID
inner join Station SS on dbo.GetDistance(SS.X,SS.Y,TT.X,TT.Y) = minDistance.md

Эти варианты тормозят ужасно и выглядят некрасиво.
23 дек 09, 20:11    [8109959]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
iap
Member

Откуда: Москва
Сообщений: 46975
kostichek,

хотя бы версию сервера сказали.
23 дек 09, 21:18    [8110150]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
Ozzy-Osbourne
Member

Откуда: Balashikha
Сообщений: 139
kostichek,

может, так подойдёт ?
declare @t table(tid int identity, tnm varchar(20), x int, y int)
declare @s table(sid int identity, snm varchar(20), x int, y int)

insert @t select 'Moscow',115,262
insert @t select 'London',161,203
insert @t select 'Paris', 107,128
insert @t select 'Berlin', 75,179

insert @s select 'RWS-1',123,207
insert @s select 'RWS-2',116,183
insert @s select 'RWS-3', 94,197
insert @s select 'RWS-4',188,131
insert @s select 'RWS-5',106,167
insert @s select 'RWS-6', 95,180
insert @s select 'RWS-7',119,173


select 
   tid
  ,tnm
  ,dist=cast(left(dInfo,50) as float)
  ,nearest_sid=cast(substring(dInfo,51,10) as int)
  ,nearest_snm=cast(substring(dInfo,61,20) as varchar)
from(
select t.tid,t.tnm
      ,dInfo=min( cast(sqrt(1.*square(t.x-s.x)+1.*square(t.y-s.y)) as char(50))+cast(s.sid as char(10))+s.snm )
from @t t
join @s s on 1=1
group by t.tid,t.tnm
)x
tidtnmdistnearest_sidnearest_snm
4Berlin122,7724RWS-4
2London38,20991RWS-1
1Moscow149,9674RWS-4
3Paris39,01285RWS-5
23 дек 09, 21:23    [8110163]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
iap
Member

Откуда: Москва
Сообщений: 46975
Ozzy-Osbourne,

у Вас Земля плоская, да? Или я ошибаюсь?
23 дек 09, 21:38    [8110206]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
DeColo®es
Member

Откуда: Москва
Сообщений: 5499
Блог
Как-то так:
select *
from Town t
cross apply(select top 1 dbo.GetDistance(S.X,S.Y,T.X,T.Y) min_dist, * from Station s order by min_dist) st
По-любому работать быстро не будет, поскольку для каждого города нужно перебрать все станции, вычислить дистанции и определить наименьшую.

Если вычиосять такое приходится регулярно, я бы денормализовал и хранил в отдельной таблице все расстояния - там уже по индексам можно искать.
23 дек 09, 22:18    [8110298]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
Ozzy-Osbourne
Member

Откуда: Balashikha
Сообщений: 139
iap
Ozzy-Osbourne, у Вас Земля плоская, да? Или я ошибаюсь?
из текста ТС невозможно понять, как вычисляется расстояние. Со сферическими коня... пардон, координатами возиться не сильно хотелось, поэтому принял модель Аристотеля: Земля - плоская, слонов - три, кит - один. Океан - тоже один :-)

PS. Согласен с DeColo®es, работать будет долго, если не принять спец. мер по реорганизации данных.
24 дек 09, 00:20    [8110570]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
kostichek
Member

Откуда:
Сообщений: 15
iap
kostichek,

хотя бы версию сервера сказали.
2008

DeColo®es
Как-то так:
select *
from Town t
cross apply(select top 1 dbo.GetDistance(S.X,S.Y,T.X,T.Y) min_dist, * from Station s order by min_dist) st
По-любому работать быстро не будет, поскольку для каждого города нужно перебрать все станции, вычислить дистанции и определить наименьшую.

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


С конструкцией cross apply не встречался, видимо, это с 2005 пошло, буду изучать, тем более выглядит симпатично) Как часто придется вычислять и как часто будут меняться таблицы Town и Station пока неясно, к сожалению...

Ozzy-Osbourne
PS. Согласен с DeColo®es, работать будет долго, если не принять спец. мер по реорганизации данных.


Изящно, хоть и не строго с точки зрения программирования. Строки сравнивать некошерно, но можно умножить на 1000000 и прибавить StationID...

То есть, если свести все к таблице T (a,b,val) невозможно стандартными средствами в один запрос вывести для каждого "a" соответствующий "b", где "val" минимальный при этом "a"? Иными словами, в запросе select a,min(val) from T group by a order 1 не подключить вывод b?
24 дек 09, 03:57    [8110702]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
aleks2
Guest
Хе-хе... года два назад уже искали. И функция, что забавно была аналогичной.

Самое человеческое (читай быстрое) решение - доп. таблица с расстояниями

ГородID, СтанцияID, Расстояние.

PS. Не надо бояться больших таблиц - это предназначение MS SQL.
24 дек 09, 07:16    [8110774]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
Excel
Member

Откуда: UA, Kiev
Сообщений: 119
Помню у кого-то в блоге читал, люди писали логистику, и искали как бы побыстрее считать расстояния. Результатом было аналогичное решение:
"Дешевле хранить посчитанные расстояния, чем считать их в риалтайме."
24 дек 09, 10:56    [8111656]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
iap
Member

Откуда: Москва
Сообщений: 46975
kostichek
2008
USE tempdb;
SET NOCOUNT ON;
IF OBJECT_ID(N'Town','U') IS NOT NULL DROP TABLE Town;
IF OBJECT_ID(N'Station','U') IS NOT NULL DROP TABLE Station;
GO
CREATE TABLE Town
(
 TownID INT NOT NULL IDENTITY CONSTRAINT pkTown PRIMARY KEY,
 TownName NVARCHAR(100) NOT NULL,
 TownLocation geography NOT NULL
);
CREATE TABLE Station
(
 StationID INT NOT NULL IDENTITY CONSTRAINT pkStation PRIMARY KEY,
 StationName NVARCHAR(100) NOT NULL,
 StationLocation geography NOT NULL
);
INSERT Town(TownName,TownLocation)VALUES
 (N'Москва', geography::STPointFromText(N'POINT(55.73 37.55)',4326))
,(N'Санкт-петербург', geography::STPointFromText(N'POINT(59.87 30.42)',4326))
,(N'Новосибирск', geography::STPointFromText(N'POINT(54.95 83.1)',4326));
INSERT Station(StationName,StationLocation)VALUES
 (N'Можайск', geography::STPointFromText(N'POINT(55.5 36.03)',4326))
,(N'Пушкино', geography::STPointFromText(N'POINT(56.02 37.85)',4326))/*36-38*/
,(N'Химки', geography::STPointFromText(N'POINT(55.93 37.25)',4326));/*29-24*/

SELECT T.TownID, T.TownName, D.StationName, 0.001*D.Distance [Distance, км]
FROM Town T
CROSS APPLY
(
 SELECT TOP 1 S.StationID,S.StationName,S.StationLocation.STDistance(T.TownLocation)
 FROM Station S
 ORDER BY 3
) D(StationID,StationName,Distance);
aleks2
Самое человеческое (читай быстрое) решение - доп. таблица с расстояниями
С этим, конечно, трудно не согласиться.
Разве что городов будет миллион, а станций - миллиард.
24 дек 09, 12:27    [8112408]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
kostichek
Member

Откуда:
Сообщений: 15
iap
С этим, конечно, трудно не согласиться.
Разве что городов будет миллион, а станций - миллиард.


12 000 городов и столько же станций уже дают 144 000 000 записей в таблице расстояний)

Резюмируя, получается необходимость использования конструкции CROSS APPLY(), а в случае 2000 сервера и Таблицы расстояний (ГородID, СтанцияID, Расстояние) не уйти от таких конструкций?

select Город.*, Станция.*, X.dist_nearest
from (select ГородID, min(Расстояние) as dist_nearest from [Таблица расстояний] GROUP BY ГородID) X
inner join [Таблица расстояний] ON [Таблица расстояний].ГородID = X.ГородID AND [Таблица расстояний].Расстояние = X.dist_nearest
inner join Станция ON Станция.СтанцияID = [Таблица расстояний].СтанцияID
24 дек 09, 13:01    [8112682]     Ответить | Цитировать Сообщить модератору
 Re: Строка, где нашелся минимум?  [new]
DeColo®es
Member

Откуда: Москва
Сообщений: 5499
Блог
kostichek
12 000 городов и столько же станций уже дают 144 000 000 записей в таблице расстояний)

Резюмируя, получается необходимость использования конструкции CROSS APPLY(), а в случае 2000 сервера и Таблицы расстояний (ГородID, СтанцияID, Расстояние) не уйти от таких конструкций?
Не вижу ничего страного в таблице такого "размера".
У нас и поболее таблицы есть, примерно такие же по смыслу - хранение неких денормализованных данных.

Если ID точек и расстояние хранить в int, то получится примерно 2Гб.
Стоимость дискового хранилища на такой объем нужно озвучивать? ;)
24 дек 09, 14:50    [8113617]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить