Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Поиск кратчайшего пути, рекурсивный cte  [new]
AnaceH
Member

Откуда:
Сообщений: 109
Здравствуйте.
Стоит задача - расчет произвольного курса валют. Имеем таблицу курсов, где хранится коэффициент между парой валют, например EUR-USD = 1.27157 (На самом деле курс хранится на каждый момент времени, но не будем усложнять и без того...)
Так вот, Когда нам надо узнать курс пары, которая хранится в базе - все просто. Но вот когда нам надо узнать курс пары валют, пару которых мы не храним, приходится рассчитывать через другие валюты. Например нужен NOK-SEK. Находим NOK-EUR, потом EUR-SEK и перемножаем. К чему я это все. Написал я значит запрос:
+
declare @Pair varchar(6) = 'NOKSEK'
DECLARE @Currency1 varchar(3) = LEFT(@Pair,3)
DECLARE @Currency2 varchar(3) = RIGHT(@Pair,3) 
declare @TickTime datetime = '20121111'

;with pairs as (
select Currency1, Currency2, PairID, a.AskOpen
from dbo.vw_eConPairs p    
		CROSS APPLY 
		(
			SELECT TOP(1) a.AskOpen
			FROM dbo.eConCandles1M AS a
			WHERE a.PairID = p.PairID AND a.CandleDateTime <= @TickTime
			ORDER BY CandleDateTime DESC 
		) AS a
 union 
 select Currency2, Currency1, PairID, 1/a.AskOpen from dbo.vw_eConPairs p 
		CROSS APPLY 
		(
			SELECT TOP(1) a.AskOpen
			FROM dbo.eConCandles1M AS a
			WHERE a.PairID = p.PairID AND a.CandleDateTime <= @TickTime
			ORDER BY CandleDateTime DESC 
		) AS a
 where not exists (select * from dbo.vw_eConPairs p1 where p1.Currency2 = p.Currency1 and p1.Currency1 = p.Currency2) 
 )  
, cte as 
 (
  select Currency1, Currency2, PairID, cast(AskOpen as decimal (18,15)) AskOpen, 1 n, CAST(Currency1 + '/' + Currency2 as varchar(8000)) path, Currency2 last
    from pairs p 
   where p.Currency1 = @Currency1
  union all 
  select p.Currency1, p.Currency2, p.PairID, cast(c.AskOpen*p.AskOpen as decimal (18,15)), n+1, CAST(path + '/' + p.Currency2  as varchar(8000)), p.Currency2
    from pairs p 
	join cte c 
	  on c.Currency2 = p.Currency1
	 and path not like '%/' + p.Currency2  + '%' and  path not like '%/' +  @Currency2 + '%'
 )
 select top 1 * from cte c
 where last = @Currency2

И даже работает! Но!
Не дает покоя мне top 1 без order by. Ночью прямо спать не могу. Главная проблема - длинна цепочки. То есть чем короче наша цепочка вычислений, тем точнее мы посчитаем курс. Хоть order by и отсутствует, но запрос возвращает самую короткую цепочку, это логично, она была образована на самой "ранней" рекурсии по сравнению с другими. Например, в этом случае возвращает цепочку, образованную на второй рекурсии. А там есть и 5, и 10. Вдруг когда-нибудь SQL Server решит вернуть мне самую раннюю рекурсию, а какую-нибудь другую, ведь имеет право, order by-то нет. И получится неточный результат. А если добавить order by, то он будет выполнять ВСЕ шаги, и займет это 3 секунды, что недопустимо для такой "простой" операции.
В чем вопрос - стоит ли опасаться top 1 без order by и переделывать, и если стоит, то как?
4 дек 12, 20:36    [13577738]     Ответить | Цитировать Сообщить модератору
 Re: Поиск кратчайшего пути, рекурсивный cte  [new]
AnaceH
Member

Откуда:
Сообщений: 109
Речь была конечно же об
AnaceH
 select top 1 * from cte c
 where last = @Currency2
4 дек 12, 21:22    [13577854]     Ответить | Цитировать Сообщить модератору
 Re: Поиск кратчайшего пути, рекурсивный cte  [new]
iap
Member

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

может быть, из всех возможных надо выбирать максимальный или минимальный курс (то есть, произведение курсов)?
Да, медленно. Зато хоть какая-то логика.
4 дек 12, 22:03    [13577947]     Ответить | Цитировать Сообщить модератору
 Re: Поиск кратчайшего пути, рекурсивный cte  [new]
AnaceH
Member

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

Не уверен что надо выбирать минимальный или максимальный. Опытным путем заметил, что чем короче цепочка, тем меньше погрешность. То есть, например, курс из первого поста, рассчитанный через 2 пары равен 1.1735, а курсы, рассчитанные через 9 (наибольшая длина цепи) пар лежат в диапазоне между 1.171 и 1.176. И так далее, чем длиннее цепь, тем больше разброс, а середина как раз самая короткая цепь.

Вернемся к исходному вопросу. Допустим все же мне нужна цепь наименьшей длины. Ее я могу задать как явным образом через
 select top 1 * from cte c
 where last = @Currency2
order by n

Здесь n - это счетчик глубины рекурсии. Беда в том, что сервер в этом случае вычисляет цте до самого конца. Время, затрачиваемое на это меня печалит. С другой стороны, если делать без ордер бай, сервер возвращает опять-таки запись с наименьшей глубиной рекурсии, но уже не потому что я указал это в запросе, а в силу реализации механизма рекурсивного цте. Это-то меня и беспокоит. Все мы знаем, что полагаться на алгоритм, по которому сервер выполняет наш запрос нельзя. Он может поменяться в любой момент. А может и не поменяться. Вот это меня и беспокоит. Хочу понять, можно в данном случае положиться на то, на что в общем случае полагаться нельзя или нет? Ведь в целом поведение сервера абсолютно логично и я не представляю ситуации, в которой он вел бы себя иначе.
4 дек 12, 22:35    [13578029]     Ответить | Цитировать Сообщить модератору
 Re: Поиск кратчайшего пути, рекурсивный cte  [new]
dalex1973
Member

Откуда: Польша
Сообщений: 287
AnaceH
Хочу понять, можно в данном случае положиться на то, на что в общем случае полагаться нельзя или нет? Ведь в целом поведение сервера абсолютно логично и я не представляю ситуации, в которой он вел бы себя иначе.

Рекурсия непредсказуема и может вести к ухудшению производительности (хотя конечно это не правило).
Отсюда мысли:
  • протестируйте не-CTE вариант
  • если хотите остаться при рекурсии, измените рекурсивную часть запроса(после UNION ALL) чтобы после первого совпадения дальше не считало
  • 4 дек 12, 23:45    [13578227]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    AnaceH
    Member

    Откуда:
    Сообщений: 109
    dalex1973
    измените рекурсивную часть запроса(после UNION ALL) чтобы после первого совпадения дальше не считало

    Отличная мысль, но я не догадался как это сделать. Вся эта дилемма с ордер баем из-за того, что я не знаю как прервать рекурсию в нужный момент. В лоб через exists нельзя - ограничение на количество обращений к рекурсивному цте внутри себя.
    Если есть решение, которое я не заметил - подскажите пожалуйста.
    5 дек 12, 00:18    [13578332]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    aleks2
    Guest
    AnaceH
    dalex1973
    измените рекурсивную часть запроса(после UNION ALL) чтобы после первого совпадения дальше не считало

    Отличная мысль, но я не догадался как это сделать. Вся эта дилемма с ордер баем из-за того, что я не знаю как прервать рекурсию в нужный момент. В лоб через exists нельзя - ограничение на количество обращений к рекурсивному цте внутри себя.
    Если есть решение, которое я не заметил - подскажите пожалуйста.


    Переделать на while и не будет проблем с остановкой. А ишо будет быстрее.

    declare @Pair varchar(6) = 'NOKSEK'
    DECLARE @Currency1 varchar(3) = LEFT(@Pair,3)
    DECLARE @Currency2 varchar(3) = RIGHT(@Pair,3) 
    
    declare @curs table(Currency1 varchar(3), Currency2 varchar(3), Coeff float, primary key clustered(Currency1, Currency2));
    insert @curs(Currency1, Currency2, Coeff)
    values ('NOK', 'SIK', 1.1)
         , ('NOK', 'SUK', 1.2)
         , ('NOK', 'SAK', 1.3)
         , ('SAK', 'SEK', 1.4)
         , ('SUK', 'SOK', 1.5)
         , ('SOK', 'SEK', 1.6)
    
    
    declare @t table(PathID varchar(6), Currency1 varchar(3), Currency2 varchar(3), Level int, primary key clustered(Level, Currency2, Currency1), unique(PathID, Currency2, Currency1));
    declare @rc int, @l int = 0;
    
    insert @t(PathID, Currency1, Currency2, Level)
    select Currency1+Currency2, Currency1, Currency2, 0 from @curs where Currency1 = @Currency1;
    
    set @rc = @@rowcount;
    
    while @rc>0 begin
    
      insert @t(PathID, Currency1, Currency2, Level)
        select t.PathID, c.Currency1, c.Currency2, @l+1 
          from ( select * from @t where Level = @l) t inner join @curs C on c.Currency1 = t.Currency2;
    
      set @rc = @@rowcount;
      set @l = @l+1;
      
      if exists(select * from  @t where Level = @l and Currency2 = @Currency2)
        set @rc =0;
      
    end;
    
    select * from @t where PathID = (select top(1) PathID from  @t where Currency2 = @Currency2);
    
    5 дек 12, 07:01    [13578653]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    aleks2
    Guest
    так лучче
    declare @t table(PathID varchar(6), Currency1 varchar(3), Currency2 varchar(3), Level int, primary key clustered(Level, Currency2, Currency1), unique(Currency2, PathID, Currency1));
    
    5 дек 12, 07:04    [13578658]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    AnaceH
    Member

    Откуда:
    Сообщений: 109
    aleks2,

    Допустим, а решения моей задачи с помощью цте нет? Нельзя никак прервать выполнение кроме как использовать top 1 без order by? И, опять-таки, насколько допустимо/недопустимо использовать top 1 без order by в данном случае?
    5 дек 12, 10:27    [13579294]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    aleks2
    Guest
    AnaceH
    aleks2,

    Допустим, а решения моей задачи с помощью цте нет? Нельзя никак прервать выполнение кроме как использовать top 1 без order by? И, опять-таки, насколько допустимо/недопустимо использовать top 1 без order by в данном случае?


    Ну, order by присобачить лехко. Достаточно ввести поле счетчика итераций.

     select 0 asn, ...    from pairs p 
       where p.Currency1 = @Currency1
      union all 
      select c.n+1 as n, ...
        from pairs p join cte c 
    


    А вот остановиться - фигвамм.
    5 дек 12, 10:36    [13579351]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    AnaceH
    Member

    Откуда:
    Сообщений: 109
    Нашел способ как прервать рекурсию
    declare @Pair varchar(6) = 'NOKSEK'
    DECLARE @Currency1 varchar(3) = LEFT(@Pair,3)
    DECLARE @Currency2 varchar(3) = RIGHT(@Pair,3) 
    declare @TickTime datetime = '20121111'
    
    ;with pairs as (
    select Currency1, Currency2, PairID, a.AskOpen
    from dbo.vw_eConPairs p    
    		CROSS APPLY 
    		(
    			SELECT TOP(1) a.AskOpen
    			FROM dbo.eConCandles1M AS a
    			WHERE a.PairID = p.PairID AND a.CandleDateTime <= @TickTime
    			ORDER BY CandleDateTime DESC 
    		) AS a
     union 
     select Currency2, Currency1, PairID, 1/a.AskOpen from dbo.vw_eConPairs p 
    		CROSS APPLY 
    		(
    			SELECT TOP(1) a.AskOpen
    			FROM dbo.eConCandles1M AS a
    			WHERE a.PairID = p.PairID AND a.CandleDateTime <= @TickTime
    			ORDER BY CandleDateTime DESC 
    		) AS a
     where not exists (select * from dbo.vw_eConPairs p1 where p1.Currency2 = p.Currency1 and p1.Currency1 = p.Currency2) 
     )  
    , cte as 
     (
      select Currency1, Currency2, PairID, cast(AskOpen as decimal (18,15)) AskOpen, 1 n, CAST(Currency1 + '/' + Currency2 as varchar(8000)) path, Currency2 last, 1 a
        from pairs p 
       where p.Currency1 = @Currency1
      union all 
      select p.Currency1, p.Currency2, p.PairID, cast(c.AskOpen*p.AskOpen as decimal (18,15)), n+1, CAST(path + '/' + p.Currency2  as varchar(8000)), p.Currency2, max(case p.Currency2 when @Currency2 then 2 else a end) over(partition by 1) 
             
        from pairs p 
    	join cte c 
    	  on c.Currency2 = p.Currency1
    	 and path not like '%/' + p.Currency2  + '%' and  path not like '%/' +  @Currency2 + '%'
    	 and a = 1
     )
     select * from cte c
     where last = @Currency2
    

    Все как я хотел. После первого нахождения хвоста во всю итерацию попадает маркер a=2, и следующая итерация уже не выполняется.
    Может кому-нибудь пригодится.
    5 дек 12, 11:29    [13579764]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    так зашёл
    Guest
    AnaceH,

    первой:

    плохо написана рекурсия...
    сте табличку pairs нужно обязательно запихнуть во времянку,
    а так она на каждом шаге ЗАНОВО перещитывается!
    Или хотя бы сделать принудительный спул.

    типа такого:
    pairs_new as(select 0t,* from pairs union all select * from pairs_new where t<0)

    это казалось бы бессмысленная запись "сфотает" таблицу и не будет больше перещитывать.

    второе:
    что-то вы перемудрили с LIKE в рекурсии, достаточно так:

    declare @Pair varchar(6) = 'NOKSEK'
    DECLARE @C1 varchar(3) = LEFT(@Pair,3)
    DECLARE @C2 varchar(3) = RIGHT(@Pair,3)

    declare @curs table(C1 varchar(3), C2 varchar(3), CE float, primary key clustered(C1, C2));
    insert @curs(C1, C2, CE)
    values ('NOK', 'SIK', 1.1)
    , ('NOK', 'SUK', 1.2)
    , ('NOK', 'SAK', 1.3)
    , ('SAK', 'SEK', 1.4)
    , ('SUK', 'SOK', 1.5)
    , ('SOK', 'SEK', 1.6)

    ;with cte as(

    select 1 n, c2, ce from @curs where C1 = @C1

    union all

    select n+1, C.C2, cte.CE*C.CE
    from cte, @curs C
    where cte.C2 = C.C1

    )
    select top 1 ce
    from cte
    where c2=@c2
    order by n

    третье

    Вместо страшного куска по вычислению уникальных свежих пар валют, можно написать быстрый вариант в одно чтение:

    SELECT Currency1, Currency2, AskOpen
    FROM(
      SELECT 
        ROW_NUMBER()OVER(
          PARTITION BY SORT.Currency1, SORT.Currency2--для каждой уникальной пары
          ORDER BY a.CandleDateTime DESC)N,          --выбираем самую свежею запись 
        SORT.Currency1,
        SORT.Currency2,
        SORT.AskOpen
        /*, PairID*/ --я так понимаю этот столбец не нужен в дальнейшем...
                     --иначе не понятно какую пару из двух выбирать
      from dbo.eConCandles1Md a   
        JOIN bo.vw_eConPairs p ON a.PairID = p.PairID
        CROSS APPLY(SELECT
          CASE WHEN Currency1 < Currency2 THEN Currency1 ELSE Currency2 END Currency1,
          CASE WHEN Currency1 < Currency2 THEN Currency2 ELSE Currency1 END Currency2,
          CASE WHEN Currency1 < Currency2 THEN a.AskOpen ELSE 1/a.AskOpen END AskOpen      
        )SORT --тут добываем сортированные пзначения для пар
      WHERE a.CandleDateTime <= @TickTime
    )T CROSS JOIN (SELECT*FROM(VALUES(0),(1))x(x))x--а теперь располовиним записи, чтобы были и туда и обратно
    WHERE N=1 --самая свежая для каждой пары
    


    Четвертое

    сомневаюсь, что если всё написать правильно рекурсия будет тормозить, просто в текущем варианте очень плохо написана.
    Но вариант с циклом стоит сравнить.

    Пятое.

    Рекурсию остановить можно. Но для этого нужно соединять не с таблицей а со строкой или с xml, в которую заранее записаны данные из таблицы.
    Таким образом на каждом шаге у нас будет вся информация для того чтобы остановить. Иначе никак.
    Но сомневаюсь что нервозатраты при этом оправдает прирост производительности:)
    Я браться за такое не готов:)

    Итого:

    рекомендую переписать рекурсию, а вычисленные пары предварительно ЗАПИСАТЬ во временную таблицу!
    крепить на каждой итерации каждый раз ЗАНОВО расчитываемую СТЕ таблицу - основная ошибка, которая отталкивает людей от рекурсии. На самом деле довольно часто она нереально быстрее циклов и курсоров. особенно если, например, в цикле один маленький insert, который повторяется 10 000 раз, можно заменить на один большой insert с рекурсией - разница колоссальна!:)


    Надеюсь помог.
    5 дек 12, 12:38    [13580405]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    так зашёл
    Guest
    AnaceH,

    max(case p.Currency2 when @Currency2 then 2 else a end) over(partition by 1)
    


    Нет не работает,

    Ранговые функции к сожалению работают в рекурсии только в пределах текущей обрабатываемой строки и прикреплённым к ней.
    Это особенность МС-рекурсии.
    несколько раз сталкивался обидно было...
    Вот посмотрите пример(на втором шаге flag равен и 1 и 2, хотя стоит over)

    declare @Pair varchar(6) = 'NOKSEK'
    DECLARE @C1 varchar(3) = LEFT(@Pair,3)
    DECLARE @C2 varchar(3) = RIGHT(@Pair,3) 
    
    declare @curs table(C1 varchar(3), C2 varchar(3), CE float, primary key clustered(C1, C2));
    insert @curs(C1, C2, CE)
    values ('NOK', 'SIK', 1.1)
    , ('NOK', 'SUK', 1.2)
    , ('NOK', 'SAK', 1.3)
    , ('SAK', 'SEK', 1.4)
    , ('SUK', 'SOK', 1.5)
    , ('SOK', 'SEK', 1.6)
    
    ;with cte as(
    
    select 1 n, c2, ce, 0 flag from @curs where C1 = @C1
    
    union all
    
    select n+1, C.C2, cte.CE*C.CE,MAX(case when C.C2=@c2 then 1 else 0 end)OVER()
    from cte, @curs C
    where cte.C2 = C.C1
    
    )
    select * 
    from cte 
    order by n
    
    5 дек 12, 12:46    [13580481]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    так зашёл
    Guest
    nc2ceflag
    1SAK1.30
    1SIK1.10
    1SUK1.20
    2SOK1.80
    2SEK1.821
    3SEK2.881
    5 дек 12, 12:51    [13580524]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    AnaceH
    Member

    Откуда:
    Сообщений: 109
    так зашёл,

    Беда с этим рекурсивным цте. Судя по всему обработка рекурсии идет по дереву, где родительская нода - строка из ссылки на цте, а дочернии - множество строк, образованные от одной родительской. Агрегат, сработавший для одной из нод, дублируется среди сестер и братьев (по результатам тестов). То есть моя задача будет решена корректно в том случае, если на момент нахождения полной цепочки NOK-\...\-SEK была только одна родительская нода. В моем случае это было NOK-EUR, и среди связок EUR-XXX была EUR-SEK. В этом случае у всех EUR-XXX а = 2 и рекурсия завершается. А вот когда родительских нод больше одной, а = 2 будет не у всех дочерних нод, и они продолжат рекурсию.

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

    Можно по поводу пятого пункта подробно? Оно конечно понятно про нервозатраты и прочее, но уже просто интересна технология.
    5 дек 12, 20:55    [13584288]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    так зашёл
    Guest
    AnaceH,

    Ну меня в посте кстати пару ошибок есть.

    Кстати поведение sql рекурсии вполне понятно.
    Она не делает одиш шаг целиком, потом второй третий итп.(так бы тратилось слишком много памяти)
    А она берёт первую строчку, делает итерацию для неё, потом опять от первой и так пока до конца не дойдёт(до условия остановки)
    И только потом начинает обрабатывать вторую строчку стартового набора.

    Вот пример наглядно это демонстрирует:

    declare @Pair varchar(6) = 'NOKSEK'
    DECLARE @C1 varchar(3) = LEFT(@Pair,3)
    DECLARE @C2 varchar(3) = RIGHT(@Pair,3) 
    
    declare @curs table(C1 varchar(3), C2 varchar(3), CE float, primary key clustered(C1, C2));
    insert @curs(C1, C2, CE)
    values ('NOK', 'SIK', 1.1)
    , ('NOK', 'SUK', 1.2)
    , ('NOK', 'SAK', 1.3)
    , ('SAK', 'SEK', 1.4)
    , ('SUK', 'SOK', 1.5)
    , ('SOK', 'SEK', 1.6)
    , ('SEK', 'NOK', 0.1)
    
    ;with cte as(
    
    select 1 n, c2, ce, cast('/'+c1+'/'+c2 as varchar(8000))path
    from @curs 
    where C1 = @C1
    
    union all
    
    select n+1, C.C2, cte.CE*C.CE, cast(path+'/'+c.C2 as varchar(8000))
    from cte, @curs C
    where cte.C2 = C.C1
    --and path not like '%/'+c.C2+'%'
    and N<20
    
    )
    
    select top 1 with ties n, ce 
    from cte 
    where c2=@c2 
    order by c2
    --order by n
    
    option(maxrecursion 0)
    


    Порядок вывода строк в результате - это порядок нахождения оных рекурсией.

    А вообще это задача не для sql.

    Я бы наверно сделал процедуру которая общитывает отношение каждой валюты к рублю и записывает в таблицу.
    И запускал перерасчет периодически, либо джобом раз в сутки, либо триггером при изменении какой-то валюты.
    А вызов нужной информации либо бы в функцию запихал, либо во вьюху.
    6 дек 12, 11:37    [13586607]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    так зашёл
    Guest
    Вернёмся к исходному вопросу:
    AnaceH
    aleks2,

    Допустим, а решения моей задачи с помощью цте нет? Нельзя никак прервать выполнение кроме как использовать top 1 без order by? И, опять-таки, насколько допустимо/недопустимо использовать top 1 без order by в данном случае?


    Ни в коем случае нельзя полагаться!

    Предыдущий мой пот даёт следующий результат:(первые 50 строчек)
    +
    rnnce
    132.88
    270.82944
    3110.23887872
    4150.06879707136
    5190.01981355655168
    6180.01252106698752
    7140.04347592704
    8180.01252106698752
    9170.00791261872128
    10200.00144009660727296
    11100.15095808
    12140.04347592704
    13180.01252106698752
    14170.00791261872128
    15200.00144009660727296
    16130.02747437056
    17170.00791261872128
    18200.00144009660727296
    19160.00500033544192
    20200.00144009660727296
    21190.00091006105042944
    2260.52416
    23100.15095808
    24140.04347592704
    25180.01252106698752
    26170.00791261872128
    27200.00144009660727296
    28130.02747437056
    29170.00791261872128
    30200.00144009660727296
    31160.00500033544192
    32200.00144009660727296
    33190.00091006105042944
    3490.09539712
    35130.02747437056
    36170.00791261872128
    37200.00144009660727296
    38160.00500033544192
    39200.00144009660727296
    40190.00091006105042944
    41120.01736227584
    42160.00500033544192
    43200.00144009660727296
    44190.00091006105042944
    45150.00315993420288
    46190.00091006105042944
    47180.00057510802492416
    4821.82
    4960.52416
    50100.15095808


    кратчайший путь имеет уровень 2, но находим мы его только 48ым результатом.
    по-этому Вам очень везло, что top 1 возвращал кратчайший путь:)
    6 дек 12, 12:22    [13587100]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    так зашёл
    Guest
    так зашёл,

    еtop 1 with ties конечно лишний:) это я что-то другое проверял и не потёр.
    6 дек 12, 12:37    [13587261]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    invm
    Member

    Откуда: Москва
    Сообщений: 9836
    Прервать рекурсию с помощью ранжирующей функции таки можно:
    with x as
    (
     select 1 as n, 1 as s
     
     union all
     
     select
      t.n + 1, t.s + t.n + 1
     from
      (select n, sum(n) over () as s from x) t
     where
      t.s < 10 and
      t.n < 102
    )
    select * from x;
    
    Правда не думаю, что ТСу это сильно поможет...
    6 дек 12, 12:56    [13587472]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    так зашёл
    Guest
    invm
    Прервать рекурсию с помощью ранжирующей функции таки можно:
    with x as
    (
     select 1 as n, 1 as s
     
     union all
     
     select
      t.n + 1, t.s + t.n + 1
     from
      (select n, sum(n) over () as s from x) t
     where
      t.s < 10 and
      t.n < 102
    )
    select * from x;
    
    Правда не думаю, что ТСу это сильно поможет...


    Да нельзя! Рассказали же уже почему... Окно в пределах одной обрабатываемой строки и к ней присоединённых. На этапе выполнения она понятия не имеет что на этом шаге будет твориться в других строках, потому что там ещё ничего не считалось.
    Остановить просто невозможно.
    6 дек 12, 13:33    [13587837]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    invm
    Member

    Откуда: Москва
    Сообщений: 9836
    так зашёл
    Да нельзя! Рассказали же уже почему...
    Опять проверять лень? :) Уж казалось бы и писать самому ничего не нужно -- скрипт готовый есть...
    6 дек 12, 13:46    [13587922]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    invm
    Member

    Откуда: Москва
    Сообщений: 9836
    Да, фокус не удался. Проверять с sum было некорректно...
    6 дек 12, 13:52    [13587957]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    pegoopik
    Member

    Откуда: Новосибирск
    Сообщений: 54
    invm,

    Если сильно хочется чтобы оконные в рекурсии заработали, можно всё поместить в xml, разбирать его, делать итерацию(при этом что угодно можно накрутить) и обратно, собрав изменённую, передавать в следующую итерацию.

    как-то так:
    +
    WITH Links AS(
      SELECT 1 p1,2 p2
      UNION SELECT 2,3
      UNION SELECT 3,4
      UNION SELECT 4,2
      UNION SELECT 3,7
      UNION SELECT 2,6
      UNION SELECT 6,7
    )
    ,Cxml AS(
    SELECT CAST((SELECT p1 as[@p1], p2 as[@p2] FROM Links FOR XML PATH('x'))AS XML)S
    )
    ,CTE AS(
    SELECT 1 N, S FROM Cxml
    
    UNION ALL
    
    SELECT N+1, CAST(P.S AS XML)
    FROM CTE W
    CROSS APPLY(
        SELECT (SELECT T.c.value('@p1','int')+1 AS [@p1], T.c.value('@p2','int')+1 AS [@p2] 
        FROM W.S.nodes('/x') T(c)  
        FOR XML PATH('x'))S
    )P
    WHERE N<10
    )
    SELECT N, P1, P2
    FROM CTE W CROSS APPLY(
        SELECT T.c.value('@p1','int') AS p1, T.c.value('@p2','int') AS p2 
        FROM W.S.nodes('/x') T(c)
      )P
    ORDER BY 1
    


    Но кажется это будет работать медленно:)
    6 дек 12, 14:47    [13588379]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    invm
    Member

    Откуда: Москва
    Сообщений: 9836
    pegoopik
    invm,

    Если сильно хочется чтобы оконные в рекурсии заработали, можно всё поместить в xml
    Спасибо. Тоже посещала такая мысль, но даже не стал проверять, потому что
    pegoopik
    Но кажется это будет работать медленно:)
    :)
    6 дек 12, 15:52    [13588929]     Ответить | Цитировать Сообщить модератору
     Re: Поиск кратчайшего пути, рекурсивный cte  [new]
    NIIIK
    Member

    Откуда: Россия, Ростовская область, г. Таганрог
    Сообщений: 1295
    invm
    pegoopik
    invm,

    Если сильно хочется чтобы оконные в рекурсии заработали, можно всё поместить в xml
    Спасибо. Тоже посещала такая мысль, но даже не стал проверять, потому что
    pegoopik
    Но кажется это будет работать медленно:)
    :)


    Задача должна решаться просто.
    Если задача решается сложно и "костыльно" - где-то что-то не так.

    Может быть вам стоит "замутить" предсохранённый результат каким-нить способом или эти правила/курсы довольно часто меняются?

    Да и "предподсчитывать" можно только когда какая-нить пара непосредственно понадобилась.

    Кстати, в валютах, если я правильно понял, маловероятно что будет "много уровней" в большенстве случаев либо есть прямой обмен либо через одну валюту а-ля доллар/евро/фунт.

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

    Конечно если эти цифры меняются постоянно и вы не можете определить "время жизни" каждой записи, то такой подход не подойдёт.
    Но на данный момент сложилось поверхностное впечатление что вы делаете что-то "не с нуля". Т. е. уже таблица есть, задача "Стоит задача - расчет произвольного курса валют." появилась потом и структура придумывалась не для этого.

    Если у вас всё равно будет необходимость "расчитывать на лету", то постарайтесь использова всякие "иерархические типы данных". Они хотя бы быстрее будут работать и там всегда можно определить уровень вложенности.
    Может быть я "не шарю", но что-то мне кажется что много уровней там использовать изначально не следует (почему я сказал ранее в примере).

    PS.
    Прересчёт валют можно "вколхозить" триггером есть нет возможности менять процедуры и т. п.
    6 дек 12, 16:19    [13589169]     Ответить | Цитировать Сообщить модератору
    Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
    Все форумы / Microsoft SQL Server Ответить