powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Пятничная задача: Красное и черное
176 сообщений из 176, показаны все 8 страниц
Пятничная задача: Красное и черное
    #40017941
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это очередная вариация на тему интервалов. Мне подобное на форуме не попадалось, но сорри если баян.

Есть интервалы двух цветов и требуется получить результирующую разбивку как показано ниже.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
with t (x1, x2, c) as
(
select 1, 4, 'red' from dual
union all select 7, 10, 'red' from dual
union all select 13, 16, 'red' from dual
union all select 3, 14, 'black' from dual
union all select 16, 19, 'black' from dual
union all select 18, 22, 'red' from dual
union all select 22, 25, 'black' from dual
union all select 26, 28, 'red' from dual
union all select 29, 30, 'black' from dual
union all select 32, 33, 'black' from dual
)
select ...
/

        X1         X2 RESULT
---------- ---------- -------
         1          2 red
         3          4 overlap
         5          6 black
         7         10 overlap
        11         12 black
        13         14 overlap
        15         15 red
        16         16 overlap
        17         17 black
        18         19 overlap
        20         21 red
        22         22 overlap
        23         25 black
        26         28 red
        29         30 black
        31         31 none
        32         33 black

17 rows selected.

Входные интервалы каждого отдельного цвета не пересекаются и не соприкасаются.

Картинка вероятно нагляднее покажет как получен результат.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40017949
Фотография env
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег,

Верхняя и нижняя граница всегда определены имеющимися интервалами?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40017961
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
env,

Не совсем понял вопрос. На выходе должен быть диапазон от начала первого до конца последнего.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40017971
Фотография env
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег,

Напрашивается решение через непрерывный список от min до max и start of group, но это видимо слишком простое и очевидное.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
with t (x1, x2, c) as
(
select 1, 4, 'red' from dual
union all select 7, 10, 'red' from dual
union all select 13, 16, 'red' from dual
union all select 3, 14, 'black' from dual
union all select 16, 19, 'black' from dual
union all select 18, 22, 'red' from dual
union all select 22, 25, 'black' from dual
union all select 26, 28, 'red' from dual
union all select 29, 30, 'black' from dual
union all select 32, 33, 'black' from dual
),
minmax as (
    select
        min(x1)     mn,
        max(x2)     mx
    from
        t
), 
nums as (
    select
        mn + level - 1 n
    from
        minmax
    connect by
        level <= mx - mn + 1
), 
vect as (
    select
        n,
        decode(count(distinct t.c), 1, max(c), 0, 'none', 'overlap') c
    from
        nums,
        t
    where
        nums.n between t.x1 (+) and t.x2 (+)
    group by
        nums.n
), 
sog as (
    select
        n,
        c,
        decode(c, lag(c, 1, c) over(order by n), 0, 1) g
    from
        vect
), 
grp as (
    select
        n,
        c,
        sum(g) over(order by n) gr
    from
        sog
)
select
    min(n),
    max(n),
    max(c)
from
    grp
group by
    gr
order by
    gr;

    MIN(N)     MAX(N) MAX(C)
---------- ---------- -------
         1          2 red
         3          4 overlap
         5          6 black
         7         10 overlap
        11         12 black
        13         14 overlap
        15         15 red
        16         16 overlap
        17         17 black
        18         19 overlap
        20         21 red
        22         22 overlap
        23         25 black
        26         28 red
        29         30 black
        31         31 none
        32         33 black

...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40017975
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег,

red =1
black=2
суммируем с перекрытием
3-overlap
0-прозрачный


.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40017977
Вячеслав Любомудров
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
model + overlap ?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40017981
Фотография Elic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
если баян
join с подинтервальчиками .
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40017982
Вячеслав Любомудров
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, насколько помню была какая-то не[полностью]документированная функция типа именно overlap для работы с датами и числами
Или только датами/диапазонами(?)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40017988
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax
Кобанчег,

red =1
black=2
суммируем с перекрытием
3-overlap
0-прозрачный


зі
нашел
https://www.sql.ru/forum/1297132/razdelit-na-neperesekaushhiesya-intervaly-dat-otrezki-s-ssumirovaniem-summy-v-peresecheniyah

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40017996
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
env
Кобанчег,

Напрашивается решение через непрерывный список от min до max и start of group, но это видимо слишком простое и очевидное.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
with t (x1, x2, c) as
(
select 1, 4, 'red' from dual
union all select 7, 10, 'red' from dual
union all select 13, 16, 'red' from dual
union all select 3, 14, 'black' from dual
union all select 16, 19, 'black' from dual
union all select 18, 22, 'red' from dual
union all select 22, 25, 'black' from dual
union all select 26, 28, 'red' from dual
union all select 29, 30, 'black' from dual
union all select 32, 33, 'black' from dual
),
minmax as (
    select
        min(x1)     mn,
        max(x2)     mx
    from
        t
), 
nums as (
    select
        mn + level - 1 n
    from
        minmax
    connect by
        level <= mx - mn + 1
), 
vect as (
    select
        n,
        decode(count(distinct t.c), 1, max(c), 0, 'none', 'overlap') c
    from
        nums,
        t
    where
        nums.n between t.x1 (+) and t.x2 (+)
    group by
        nums.n
), 
sog as (
    select
        n,
        c,
        decode(c, lag(c, 1, c) over(order by n), 0, 1) g
    from
        vect
), 
grp as (
    select
        n,
        c,
        sum(g) over(order by n) gr
    from
        sog
)
select
    min(n),
    max(n),
    max(c)
from
    grp
group by
    gr
order by
    gr;

    MIN(N)     MAX(N) MAX(C)
---------- ---------- -------
         1          2 red
         3          4 overlap
         5          6 black
         7         10 overlap
        11         12 black
        13         14 overlap
        15         15 red
        16         16 overlap
        17         17 black
        18         19 overlap
        20         21 red
        22         22 overlap
        23         25 black
        26         28 red
        29         30 black
        31         31 none
        32         33 black

Да, это весьма неэффективно и завязано на натуральные числа.
Интервалы могут быть произвольной длины и не обязательно с целыми границами.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018000
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax
Stax
Кобанчег,

red =1
black=2
суммируем с перекрытием
3-overlap
0-прозрачный


зі
нашел
https://www.sql.ru/forum/1297132/razdelit-na-neperesekaushhiesya-intervaly-dat-otrezki-s-ssumirovaniem-summy-v-peresecheniyah

.....
stax
Идея понятна, но можно без джойнов и подзапросов.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018003
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Elic
Кобанчег
если баян
join с подинтервальчиками .
Наиболее эффективно без джойнов.
Но некоторая баянистость просматривается, да.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018009
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вячеслав Любомудров
model + overlap ?
В тяжелой артиллерии нет особой необходимости.
Вячеслав Любомудров
Кстати, насколько помню была какая-то не[полностью]документированная функция типа именно overlap для работы с датами и числами
Или только датами/диапазонами(?)
overlap s

Но недокументированное это неспортивно (и для данной задачи нет надобности).
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018016
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег

Наиболее эффективно без джойнов.
Но некоторая баянистость просматривается, да.


unpivot можно?

для
union all select 7, 10, 'red' from dual
union all select 10, 14, 'black' from dual

10 10 overlap?

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018018
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax
unpivot можно?
Да всё что угодно можно.
Stax
10 10 overlap?
Да.

PS. На самом деле мне стоило состряпать более адекватный пример с real numbers
(тогда бы 10 10 было касание а не перекрытие на единицу) но уже есть как есть.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018022
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
завязано на натуральные числа
Должен признать что моя постановка именно это и подразумевает, но всё равно генерить диапазоны connect by - не самый удачный вариант.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018271
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег,

была идейка red full outer join black on пересекаются
но плюнул перебирать случаи пересечений
.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018281
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Stax
Кобанчег,

red =1
black=2
суммируем с перекрытием
3-overlap
0-прозрачный


.....
stax

Суммировать хорошая идея, правда как без трансформации запроса это делать я не знаю.

Вижу примерно следующий алгоритм, x1 и x2 в один столбец, каждый признак (red, black) отдельным столбцом, для начала периода (x1) признаку +1, там где кончается период (x2) признаку -1, если накопительная сумма с учетом периода больше нуля значит признак в периоде (в вертикальном виде, период это две ближайшие строки) включен, если нет значит выключен, потом преобразовать обратно в периоды.

PS: реализовывать лень)))
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018325
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax
Кобанчег,

была идейка red full outer join black on пересекаются
но плюнул перебирать случаи пересечений
.....
stax
Да, при том подходе надо скурпулёзно все перебирать и солжно для понимания и поддержки имхо.

Более просто и эффективно развернуть все отрезки в один ряд (cross join/pivot) и определить что есть что в результате (аналитика/pattern matching).

В общем мое решение выглядит так
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
select x1, x2, result
from t unpivot (x for type in (x1, x2))
match_recognize
(
  order by x, type
  measures
    case when type = 'X2' and next(type) = 'X1' and next(x) - x =1 then 1 end touch,
    case when next(x) = x and next(type) = type then 1 end same_bound,
    x + decode(type, 'X2', 1, 0) x1,
    next(x) - decode(next(type), 'X1', 1, 0) x2,
    decode(sum(decode(c, 'red', 1, 'black', 2) * decode(type, 'X1', 1, 'X2', -1)),
           1, 'red', 2, 'black', 3, 'overlap', 'none') result    
  all rows per match
  pattern (x+)
  define x as next(x) is not null
)
where touch is null and same_bound is null



touch используется для фильтра когда конец одного соприкасается с началом другого,
а same_bound для исключения из результата первой из точек когда начала либо концы совпадают.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018328
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В общем эта была разминка, теперь предлагается задачка посложнее.

Необходимо наложить интервалы из источника на приемник с приоритетом из источника (если есть пересечение).

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
with t (x1, x2, c, flag) as
(
select 1, 4, 'red', 'src' from dual
union all select 7, 10, 'yellow', 'src' from dual
union all select 13, 16, 'red', 'src' from dual
--union all select 3, 14, 'black' from dual
union all select 3, 7, 'black', 'tgt' from dual
union all select 9, 11, 'black', 'tgt' from dual
union all select 13, 14, 'black', 'tgt' from dual
--
union all select 16, 19, 'blue', 'tgt' from dual
union all select 18, 22, 'green', 'src' from dual
union all select 22, 25, 'black', 'tgt' from dual
union all select 26, 28, 'red', 'src' from dual
union all select 29, 30, 'red', 'tgt' from dual
union all select 32, 33, 'black', 'tgt' from dual
)
select ...
/

        X1         X2 RESULT
---------- ---------- ------
         1          4 red
         5          6 black
         7         10 yellow
        11         11 black
        12         12
        13         16 red
        17         17 blue
        18         22 green
        23         25 black
        26         30 red
        31         31
        32         33 black

12 rows selected.

Здесь не удастся выкрутиться с decode + sum ибо цветов потенциально неограниченное множество.

И снова картинка для наглядности.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018332
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode

PS: реализовывать лень)))


https://www.sql.ru/forum/1297132/razdelit-na-neperesekaushhiesya-intervaly-dat-otrezki-s-ssumirovaniem-summy-v-peresecheniyah

ета задачка даж проще, токо одно пересечение

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018367
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
del
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018404
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег
В общем мое решение выглядит так

Это называется без тяжелой артиллерии?

Я думал без тяжелой артиллерии выглядит примерно так:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
with t (x1, x2, c) as
(
select 1, 4, 'red' from dual
union all select 7, 10, 'red' from dual
union all select 13, 16, 'red' from dual
union all select 3, 14, 'black' from dual
union all select 16, 19, 'black' from dual
union all select 18, 22, 'red' from dual
union all select 22, 25, 'black' from dual
union all select 26, 28, 'red' from dual
union all select 29, 30, 'black' from dual
union all select 32, 33, 'black' from dual
)
, t1 (x, red, black) as
(
select x1 as x, decode(c, 'red', 1, 0), decode(c, 'black', 1, 0) from t
union all
select x2 + 1 as x, decode(c, 'red', -1, 0), decode(c, 'black', -1, 0) from t
)
, t2 (x, red, black) as
(
select distinct x
     , sum(red) over (order by x range unbounded preceding)
     , sum(black) over (order by x range unbounded preceding)
  from t1
)
, t3 (x1, x2, c) as
(
select x
     , lead(x) over (order by x) - 1
     , case when red > 0 and black > 0 then 'overlap'
            when red > 0 then 'red'
            when black > 0 then 'black'
            else 'none' end
  from t2
)
select * from t3 where x2 is not null order by x1
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018406
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Одно из решений.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
p(r,clr,cln) as
(
select 0, null, null from dual union all
select r+1,
       nvl((select max(c) from t where flag='src' and r+1 between x1 and x2),
           (select max(c) from t where flag='tgt' and r+1 between x1 and x2)),
       nvl((select max(c) from t where flag='src' and r+2 between x1 and x2),
           (select max(c) from t where flag='tgt' and r+2 between x1 and x2))
  from p where r < (select max(x2) from t)
)
select nvl(lag(r) over (order by r),1) as y1,
       r as y2,
       clr
from p where sys_op_map_nonnull(clr) != sys_op_map_nonnull(cln)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018409
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег
Здесь не удастся выкрутиться с decode + sum ибо цветов потенциально неограниченное множество.

не так изящно конечно и наверное можно упростить, но выкрутиться можно))
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
, t1 (x, c_src, c_tgt, gr_src, gr_tgt) as
(
select x1 as x
     , decode(flag, 'src', c, ''), decode(flag, 'tgt', c, '')
     , decode(flag, 'src', 1, 0), decode(flag, 'tgt', 1, 0)
from t
union all
select x2 + 1 as x
     , '', ''
     , decode(flag, 'src', 1, 0), decode(flag, 'tgt', 1, 0)
  from t
)
, t2 (x, c_src, c_tgt, gr_src, gr_tgt) as
(
select x, c_src, c_tgt
     , sum(gr_src) over (order by x range unbounded preceding)
     , sum(gr_tgt) over (order by x range unbounded preceding)
  from t1
)
, t3 (x, c) as
(
select x
     , coalesce(min(c_src) keep (dense_rank first order by x) over (partition by gr_src),
                min(c_tgt) keep (dense_rank first order by x) over (partition by gr_tgt))
  from t2
)
, t4 (x, c) as
(
select min(x), min(c) from (
    select x, c, sum(sog) over (order by x) as gr from (
        select x, c
             , case nvl(c, 'none') when nvl(lag(c) over (order by x), 'none') then 0 else 1 end as sog
          from t3))
group by gr
)
, t5 (x1, x2, c) as
(
select x
     , lead(x) over (order by x) - 1
     , c
  from t4
)
select * from t5 where x2 is not null order by x1
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018414
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
Это называется без тяжелой артиллерии?
Тяжесть модели в ее прожорливости к CPU & RAM. Cоответсвенно пользоваться ею когда она тривиально заменяется аналитикой/pattern matching это не самая лучшая идея.

Если продолжить разговор про перфоманс далее, то даже однослойная аналитика уступает в производительности match_recognize а у тебя два WINDOW SORT.

В плане других замечаний - не лучшая мысль сканировать исходную таблицу дважды.
Код: plsql
1.
2.
3.
select x1 as x, decode(c, 'red', 1, 0), decode(c, 'black', 1, 0) from t
union all
select x2 + 1 as x, decode(c, 'red', -1, 0), decode(c, 'black', -1, 0) from t

cross join будет быстрее, а unpivot еще быстрее.

Код: plsql
1.
range unbounded preceding

Нет особого смысла указывать то, что и так по умолчанию.

В остальном, в решении всё разложено по полочкам, вполне прилично.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018417
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
Одно из решений.
Это, конечно, креативно, но более неэффективного подхода придумать сложно.
Сгенерировать диапазон от начала первого до конца последнего можно было (но генерировать вообще не стоит) и с помощью connect by + nvl по двум скалярам.
В недокументированных функциях тоже никакого смысла нет.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018419
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег
НеофитSQL
Одно из решений.
Это, конечно, креативно, но более неэффективного подхода придумать сложно.
Сгенерировать диапазон от начала первого до конца последнего можно было (но генерировать вообще не стоит) и с помощью connect by + nvl по двум скалярам.
В недокументированных функциях тоже никакого смысла нет.


Вы перечислили несколько недостатков моего решения, там наверное еще десяток можно насчитать :)

Я не знаю как применить connect by в этом контексте, и использовал корявое формирование диапазонов надеясь, что кто-то знает как это делать правильно и эффективно.

Вы можете мне показать, как из этого:

Код: plsql
1.
2.
3.
4.
5.
6.
7.
with t (n, c) as
(
select 1, 'red' from dual
union all select 2, 'red' from dual
union all select 3, 'blue' from dual
union all select 4, 'red' from dual
}



Сделать такое:

1 2 red
3 3 blue
4 4 red

?

Числа последовательные, без дырок. Граничные условия не важны интересен принцип
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018420
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
не так изящно конечно и наверное можно упростить, но выкрутиться можно

Если я ничего не упустил в
Код: plsql
1.
keep (dense_rank first order by x)

смысла нет, там можно просто min.

У меня с аналитикой что-то аналогичное.
По сути итоговый цвет получается с помощью
Код: plsql
1.
nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c))

остальное - вариация на тему start of group.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
, tt as
(
select x1,
       nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result,
       lag(nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c))) over(order by x1) prev_result
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
select *
  from (select min(x1) x1,
               lead(min(x1)) over(order by grp) - 1 x2,
               min(result) result
          from (select tt.*, sum(decode(result, prev_result, 0, 1)) over(order by x1) grp from tt)
         group by grp)
 where x2 is not null


Но еще была попытка изящно решить с помощью pattern matching.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018421
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL,

Если воспользоваться генератором из запроса env то можно дописать как-то так
(но здесь не нужен генератор и коррелированные скаляры тоже не нужны)
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
select min(n) x1, max(n) x2, result
  from (select t.*,
               n - row_number() over(partition by result order by n) grp
          from (select t.*,
                       nvl((select max(c) from t where flag = 'src' and n between x1 and x2),
                           (select max(c) from t where flag = 'tgt' and n between x1 and x2)) result
                  from nums t) t)
 group by result, grp
 order by 1
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018424
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Я пропустил упражнение-разминку, ответы еще принимаются?

Код: plsql
1.
2.
3.
4.
5.
6.
7.
select y1,y2,nvl(c,'none') from 
  (select lag(x) over (order by x) as y1, x-1 as y2, 
          (select nvl(listagg(c,',') within group (order by c),'none')
           from t where x-0.5 between x1 and x2+1) as c
    from (select x1 x from t union select x2+1 x from t))
 where y1 is not null
 order by y1
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018425
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег
НеофитSQL,

Если воспользоваться генератором из запроса env то можно дописать как-то так
(но здесь не нужен генератор и коррелированные скаляры тоже не нужны)


Спасибо, напомнили про connect-by для генерации чисел, я редко его вижу.

Я спросил про connect-by, думая про задачу схлопывания интервалов.
Вы это назвали "beginning of group". Есть ли оконное выражение, которое позволяет обрабатывать повторяющуеся группы, как partition by позволяет обрабатывать уникальные группы?

Например, в следующем отсортитованном резалтсете есть три группы (апельсины:2, яблоки:2 и апельсины:1)
апельсин 2
апельсин 3
яблоко 1
яблоко 1
апельсин 1

Как в таком случае эти группы извлечь? Есть специальный оператор, или придется ловить начало группы, подглядывая соседние строчки?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018447
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег
Тяжесть модели в ее прожорливости к CPU & RAM. Cоответсвенно пользоваться ею когда она тривиально заменяется аналитикой/pattern matching это не самая лучшая идея.

Если продолжить разговор про перфоманс далее, то даже однослойная аналитика уступает в производительности match_recognize а у тебя два WINDOW SORT.

Видимо я неправильно понял задачу, я исходил из посыла что все кроме трансформации исходного запроса и аналитики запрещено.

Если подходить с точки зрения производительности, то все вышеперечисленное проигрывает решению на PL/SQL, в котором даже unpivot не нужен.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018454
Фотография Elic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
Если подходить с точки зрения производительности,
Не нужно. Пятничные задачи они, скорее в "синтаксисе", в потенциях.
Монохромность изначальной постановки понизила градус полезности.

Как автор признал, задача-баян. Необходимость решать её не сопровождаемыми способами немотивирована.
Если в задаче подразумевались -лярды данных, то об этом не было заявлено.

В свете всего этого лучшее решение - сопровождаемое. Т.е. уровень вхождения в который меньше/проще.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018475
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
Я пропустил упражнение-разминку, ответы еще принимаются?
Конечно, принимаются.
Только полезно читать другие ответы перед публикацией своего.
Возможно придёт понимание что в коррелированном скаляре нет смысла абсолютно никакого.
НеофитSQL
Вы это назвали "beginning of group". Есть ли оконное выражение, которое позволяет обрабатывать повторяющуеся группы, как partition by позволяет обрабатывать уникальные группы?
На форуме это вроде называют start of group.
Ты пробовал запустить 22232251 ?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018477
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
Видимо я неправильно понял задачу, я исходил из посыла что все кроме трансформации исходного запроса и аналитики запрещено.
Странный посыл. Было замечено только что
1) модель не самое подходящее средство
2) решается без подзапросов и соединений
Казалось бы причем здесь вообще трансформации.
Даже при наличии подзапросов они могут быть а могут и не быть.
graycode
Если подходить с точки зрения производительности, то все вышеперечисленное проигрывает решению на PL/SQL, в котором даже unpivot не нужен.
И ты сможешь его продемонстрировать?
Я даже потружусь нагенерить данных чтоб показать несостоятельность этого заявления.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018483
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Elic
Как автор признал, задача-баян.
А что относительно расширенной постановки? Сможешь дать конкретную ссылку на решение?
Elic
Необходимость решать её не сопровождаемыми способами немотивирована.
Если в задаче подразумевались -лярды данных, то об этом не было заявлено.

В свете всего этого лучшее решение - сопровождаемое. Т.е. уровень вхождения в который меньше/проще.
Если тебе по стариковски, понять многослойную аналитику проще чем pattern matching это не значит что стоит переносить сие восприятие на остальных.
На pattern matching, впрочем, свет тоже клином не сошелся.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018495
Фотография Elic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
Если тебе по стариковски, понять многослойную аналитику проще чем pattern matching это не значит что стоит переносить сие восприятие на остальных.
Выводы из-за отсутствия информации - всегда ложные.

Кобанчег
На pattern matching, впрочем, свет тоже клином не сошелся.
Если честно, то я не совсем понял в чём вызов.
Сопровождабельно решается джойном. Огласи систему ценностей.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018497
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Elic
Выводы из-за отсутствия информации - всегда ложные.
Вот не могу не согласиться.
Ты не поверишь, но я даже бегло читал читал эту книгу. А что предлагается из нее почерпнуть?
Elic
Огласи систему ценностей.
Перфоманс плюс сопровождаемость, пожалуй.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018500
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Elic
Если честно, то я не совсем понял в чём вызов.
Вызова нет, тема была создана чтоб другие поразмялись... и вдруг какая новая идея всплывёт.
Для меня вызов был решить однопроходно в SQL, но еще до создания темы я пришел к тому что это невозможно.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018511
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Собственно мой вариант таков.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
select *
  from
(
select x1,
       nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
match_recognize
(
  order by x1
  measures
    first(x.x1) x1,
    next(x.x1) - 1 x2,
    x.result result
  pattern (x+)
  define
    x as first(nvl(result, '~')) = nvl(result, '~') and next(x1) is not null
)

MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTOMATON + WINDOW SORT + UNPIVOT

При попытке решить однопроходно с match recognize упираешься в то, что "активный" цвет для текущей группы определяется по всему набору а match recognize не позволяет заглядывать в предыдущие группы.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018515
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Под однопрохоность в контексте задачи понимается
одно сканирование таблицы (это неизбежно)
+
одна операция SORT сверху (это тоже неизбежно ибо порядок все определяет).

В моем решении как видно две сортировки.

В решении graycode WINDOW SORT * 5 + WINDOW BUFFER + HASH GROUP BY + 2 сканирования таблицы
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018516
Фотография Elic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
что предлагается из нее почерпнуть?
Ким в доходчивой форме объясняет"шаблонные" фичи в том числе и "старпёрам"
technical reviewer :)


Кобанчег
Вызова нет, тема была создана чтоб другие поразмялись... и вдруг какая новая идея всплывёт.
Для меня вызов был решить однопроходно в SQL,
Однопроходность с точки зрения пятничности - это меньше букв. А это, как правило, в ущерб сопровождаемости и производительности.
Подтверждаешь ухудшение пятничности?
Я, как старпёр, дотошен :\
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018526
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Elic,

Про однопроходность написано сообщением выше, критерии тоже озвучены. Мы не code golf тут занимаемся. ;)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018605
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Жаль, критерий трудно определить объективно.

У меня получилось так. Обилие вложенных селектов и оконных функций кажется неэффективным, но зато нет подчиненных селектов, которые считаются злом.

Теперь пойду смотреть как другие решили.

Интересно, какого размера нужен дата сет, чтобы померять сравнительную производительность разных подходов?

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
p as (
select * from (
  select x, flag, decode(z,'X1',c,'-') c, z
    from (select x1, x2+1 x2, c, flag from t) tt
 unpivot (x for z in (x1,x2))) 
 pivot (max(c) for flag in ('src' s,'tgt' t))
),
q as (
select x x1, lead(x) over (order by x) -1 x2, c from (
  select x, c, lag(c) over (order by x) cp from (
    select x, decode(s,'-',t,s) c from (
      select x,
             last_value(s ignore nulls) over (order by x) s,
             last_value(t ignore nulls) over (order by x) t
        from p
      )
    )
  )
 where c != nvl(cp,' ')
)
select x1,x2,c from q
 where x1 <= x2  
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018607
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Заодно хочу сказать большое спасибо участникам форума за вклад в развитие новичков, включая меня.
Я еще месяц назад такой код со словарем не смог бы прочитать.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018642
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег

graycode
Если подходить с точки зрения производительности, то все вышеперечисленное проигрывает решению на PL/SQL, в котором даже unpivot не нужен.
И ты сможешь его продемонстрировать?
Я даже потружусь нагенерить данных чтоб показать несостоятельность этого заявления.


Я такого же мнения, что и graycode. Мне было бы интересно устроить гонки опубликованных подходов против компилированного Pl/SQL. Там все решится в один цикл без аналитических функций, повторных сортировок или временных таблиц в памяти.

PL/SQL процедуру я напишу, если будут данные.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018693
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
В общем эта была разминка, теперь предлагается задачка посложнее.

Необходимо наложить интервалы из источника на приемник с приоритетом из источника (если есть пересечение).


я так понимаю доминантный ето src, отределяется в строке, а не цветом

цветов много, поетому пересечений может быть больше двух

такое
union all select 7, 20, 'yellow', 'src' from dual
union all select 10, 30, 'red', 'src' from dual
union all select 8, 35, 'black', 'tgt' from dual
union all select 33, 40, 'yellow', 'tgt' from dual
возможно ?

ps
чтоб исключить соблазн генерации connect by, диапазаны ето даты или дробные

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018928
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег
И ты сможешь его продемонстрировать?
Я даже потружусь нагенерить данных чтоб показать несостоятельность этого заявления.


Вроде нигде с условиями не накосячил))
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
create type res_rec_t as object (x1 number, x2 number, res varchar2(50));
/
create type res_tab_t as table of res_rec_t;
/
create type src_rec_t as object (x1 number, x2 number, c varchar2(50), flag varchar2(50));
/

create or replace function f_superimpose(p_refcur sys_refcursor) return res_tab_t pipelined is
    l_res        res_rec_t;
    l_src        src_rec_t;
    l_curr_flag  varchar2(50);
begin
    fetch p_refcur into l_src;
    if p_refcur%NOTFOUND then 
        return;
    end if;
    
    l_res := res_rec_t(l_src.x1, l_src.x2, l_src.c);
    l_curr_flag := l_src.flag;

    loop
        fetch p_refcur into l_src;
        exit when p_refcur%NOTFOUND;
        
        -- разрыв
        if l_src.x1 - l_res.x2 > 1 then
            pipe row (l_res);
            l_res.x1 := l_res.x2 + 1;
            l_res.x2 := l_src.x1 - 1;
            l_res.res := '';
            pipe row (l_res);
            l_res.x1  := l_src.x1;
            l_res.x2  := l_src.x2;
            l_res.res := l_src.c;
            l_curr_flag := l_src.flag;
            continue;
        end if;
        
        -- касание
        if l_src.x1 - l_res.x2 = 1 then
            if l_src.c = l_res.res then
                l_res.x2  := l_src.x2;
                l_curr_flag := l_src.flag;
            else
                pipe row (l_res);
                l_res.x1  := l_src.x1;
                l_res.x2  := l_src.x2;
                l_res.res := l_src.c;
                l_curr_flag := l_src.flag;
            end if;
            continue;
        end if;

        -- пересечение
        if l_src.x1 - l_res.x2 < 1 then
            if l_curr_flag = 'src' then
                if l_src.x2 > l_res.x2 then
                    if l_src.c = l_res.res then
                        l_res.x2  := l_src.x2;
                        l_curr_flag := l_src.flag;
                    else
                        pipe row (l_res);
                        l_res.x1  := l_res.x2 + 1;
                        l_res.x2  := l_src.x2;
                        l_res.res := l_src.c;
                        l_curr_flag := l_src.flag;
                    end if;
                end if;
            elsif l_curr_flag = 'tgt' then
                if l_src.x2 >= l_res.x2 then
                    if l_src.c = l_res.res then
                        l_res.x2  := l_src.x2;
                        l_curr_flag := l_src.flag;
                    else
                        if l_src.x1 > l_res.x1 then
                            l_res.x2 := l_src.x1 - 1;
                            pipe row (l_res);
                        end if;
                        l_res.x1  := l_src.x1;
                        l_res.x2  := l_src.x2;
                        l_res.res := l_src.c;
                        l_curr_flag := l_src.flag;
                    end if;
                else
                    if l_src.c != l_res.res then
                        if l_src.x1 > l_res.x1 then
                            pipe row (res_rec_t(l_res.x1, l_src.x1 - 1, l_res.res));
                        end if;
                        pipe row (res_rec_t(l_src.x1, l_src.x2, l_src.c));
                        l_res.x1 := l_src.x2 + 1;
                    end if;
                end if;
            end if;
        end if;
    end loop;

    pipe row (l_res);
    close p_refcur;
end;
/

select * from table(f_superimpose(cursor(
with t (x1, x2, c, flag) as
(
select 1, 4, 'red', 'src' from dual
union all select 7, 10, 'yellow', 'src' from dual
union all select 13, 16, 'red', 'src' from dual
union all select 3, 7, 'black', 'tgt' from dual
union all select 9, 11, 'black', 'tgt' from dual
union all select 13, 14, 'black', 'tgt' from dual
union all select 16, 19, 'blue', 'tgt' from dual
union all select 18, 22, 'green', 'src' from dual
union all select 22, 25, 'black', 'tgt' from dual
union all select 26, 28, 'red', 'src' from dual
union all select 29, 30, 'red', 'tgt' from dual
union all select 32, 33, 'black', 'tgt' from dual
)
select src_rec_t(x1, x2, c, flag) from t order by x1, flag
)));

...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40018937
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL
Интересно, какого размера нужен дата сет, чтобы померять сравнительную производительность разных подходов?

По хорошему нужна реальная асимптота, поэтому разного размера и самый главный момент, это то что в сложных системах, в которых параллельно работает много автоматических процессов, чистый эксперимент на производительность провести невозможно.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019075
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
graycode
НеофитSQL
Интересно, какого размера нужен дата сет, чтобы померять сравнительную производительность разных подходов?

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


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

П.С. Удивился длине процедуры, я почему-то думал что решение циклом будет намного короче.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019107
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL
"Невозможно сравнить скорость" это не не ответ для того, кто сказал что сделает быстрее :)
Если разница в разы в десятке замеров в разных ситуациях. я думаю понятно какое из решений быстрее.

Я к тому, что полученные циферки времени выполнения нужно рассматривать критически.

НеофитSQL
П.С. Удивился длине процедуры, я почему-то думал что решение циклом будет намного короче.

Перебрал варианты в лоб, можешь поискать закономерности и свернуть алгоритм в более короткий вид, главное чтобы в нем разобраться можно было))
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019114
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
Обилие вложенных селектов и оконных функций кажется неэффективным
На самом деле это вариант очень приличный!
Группировка пивотом позволила обойтись одной и той же сортировкой в аналитике на всех уровнях (order by x) ,
в результате чего у тебя только один WINDOW SORT и два WINDOW BUFFER.
Мелкий баг - decode(s,'-',t,s) может быть null если диапазоны начинаются с target.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019115
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax
цветов много, поетому пересечений может быть больше двух
Диапазоны source не пересекаются и не соприкасаются. То же самое для target.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019123
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
Вроде нигде с условиями не накосячил
Ну респект за усердие.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
create table t(x1 int, x2 int, c varchar2(10), flag varchar2(3));

exec dbms_random.seed(111);

declare
  strt   constant int := 0;
  offset constant int := 100;
  len    constant int := 100;
  colors constant int := 9;
  qty    constant int := 1e6;
  x1 int;
  x2 int;
  c  varchar2(4000);
begin
  for r in (select 'src' flag from dual union all select 'tgt' from dual) loop
    x2 := strt;
    for i in 1 .. qty loop
      x1 := 1 + x2 + trunc(dbms_random.value(1, offset + 1));
      x2 := x1 + trunc(dbms_random.value(1, len + 1));
      c  := 'COL' || trunc(dbms_random.value(1, colors + 1));
      insert into t values (x1, x2, c, r.flag);
    end loop;
  end loop;
end;
/

commit;



ctest.sql
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
set timing off
column hash format 999999999999999999999999999999

alter session set workarea_size_policy = manual;
alter session set sort_area_size = 2147483647;

set timing on

----------------------------------------------------------------------------------------------------

prompt ==========> graycode

with t1 (x, c_src, c_tgt, gr_src, gr_tgt) as
(
select x1 as x
     , decode(flag, 'src', c, ''), decode(flag, 'tgt', c, '')
     , decode(flag, 'src', 1, 0), decode(flag, 'tgt', 1, 0)
from t
union all
select x2 + 1 as x
     , '', ''
     , decode(flag, 'src', 1, 0), decode(flag, 'tgt', 1, 0)
  from t
)
, t2 (x, c_src, c_tgt, gr_src, gr_tgt) as
(
select x, c_src, c_tgt
     , sum(gr_src) over (order by x range unbounded preceding)
     , sum(gr_tgt) over (order by x range unbounded preceding)
  from t1
)
, t3 (x, c) as
(
select x
     , coalesce(min(c_src) keep (dense_rank first order by x) over (partition by gr_src),
                min(c_tgt) keep (dense_rank first order by x) over (partition by gr_tgt))
  from t2
)
, t4 (x, c) as
(
select min(x), min(c) from (
    select x, c, sum(sog) over (order by x) as gr from (
        select x, c
             , case nvl(c, 'none') when nvl(lag(c) over (order by x), 'none') then 0 else 1 end as sog
          from t3))
group by gr
)
, t5 (x1, x2, c) as
(
select x
     , lead(x) over (order by x) - 1
     , c
  from t4
)
select sum(x1*x2) hash from t5;

----------------------------------------------------------------------------------------------------

prompt ==========> kaban analyt

with tt as
(
select x1,
       nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result,
       lag(nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c))) over(order by x1) prev_result
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
select sum(x1*x2) hash
  from (select min(x1) x1,
               lead(min(x1)) over(order by grp) - 1 x2,
               min(result) result
          from (select tt.*, sum(decode(result, prev_result, 0, 1)) over(order by x1) grp from tt)
         group by grp)
 where x2 is not null;

----------------------------------------------------------------------------------------------------

prompt ==========> kaban pattern matching

select sum(x1*x2) hash
from
(
select t.*,
       nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
match_recognize
(
  order by x1
  measures
    first(x.x1) x1,
    next(x.x1) - 1 x2,
    x.result result
  pattern (x+)
  define
    x as first(nvl(result, '~')) = nvl(result, '~') and next(x1) is not null
);

----------------------------------------------------------------------------------------------------

prompt ==========> neofit

with p as (
select * from (
  select x, flag, decode(z,'X1',c,'-') c, z
    from (select x1, x2+1 x2, c, flag from t) tt
 unpivot (x for z in (x1,x2))) 
 pivot (max(c) for flag in ('src' s,'tgt' t))
),
q as (
select x x1, lead(x) over (order by x) -1 x2, c from (
  select x, c, lag(c) over (order by x) cp from (
    select x, decode(nvl(s,'-'),'-',t,s) c from (
      select x,
             last_value(s ignore nulls) over (order by x) s,
             last_value(t ignore nulls) over (order by x) t
        from p
      )
    )
  )
 where c != nvl(cp,' ')
)
select sum(x1*x2) hash from q
 where x1 <= x2;

----------------------------------------------------------------------------------------------------

prompt ==========> graycode plsql

select sum(x1*x2) hash
  from table(f_superimpose(cursor (select src_rec_t(x1, x2, c, flag)
                              from t
                             order by x1, flag)));



Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
SQL>@ctest.sql

Session altered.


Session altered.

==========> graycode

                           HASH
-------------------------------
         9910778652543263460375

Elapsed: 00:00:21.78
==========> kaban analyt

                           HASH
-------------------------------
         9910778652543263460375

Elapsed: 00:00:17.14
==========> kaban pattern matching

                           HASH
-------------------------------
         9910778652543263460375

Elapsed: 00:00:12.04
==========> neofit

                           HASH
-------------------------------
         9910778652543263460375

Elapsed: 00:00:12.48
==========> graycode plsql

                           HASH
-------------------------------
         9910778652543263460375

Elapsed: 00:00:17.53


То есть у неофита та же производительность что у моего финального.
У pl/sql та же производительность что у моего с аналитикой.
Твой с аналитикой самый медленный - ну там слишком дофига сортировок.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019126
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Там еще в начале теста можно было вставить
Код: plsql
1.
2.
3.
4.
5.
6.
7.
SQL> select count(*) cnt from t;

       CNT
----------
   2000000

Elapsed: 00:00:00.01

Чтоб показать что на ввод-вывод ресурсы не тратятся.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019137
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег,

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

PS: pl/sql вариант конечно нужно переписать без объектной обертки, не знаю сколько она отъедает.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019143
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
o! o!

я тоже хочу PL/SQL сделать!

Спасибо за тесты, очень образовательно.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019144
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode,

Поставь ровнее, я ж только за.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019147
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег,

Ты сам взялся за тесты производительности))

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

И ой, прошу прощения, не все вычистил, там кое что совсем лишнее, flag в сортировке не нужен для работы функции))
Код: plsql
1.
2.
3.
4.
select sum(x1*x2) hash
  from table(f_superimpose(cursor (select src_rec_t(x1, x2, c, flag)
                              from t
                             order by x1, flag)));
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019151
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode,

В тесте важно избежать физических чтений таблицы и ухода в темп на сортировках.
Можно было еще чуть минимизировать расходы на получения хеша.
Всё остальное - лирика.

В реальных данных все намного сложнее и это была лишь примитивная симуляция.

Не та эта задача где PL/SQL блещет как ты ни крути. :)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019154
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег,

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

Хочешь реально оценить, поставь эксперимент грамотно.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019157
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode,

А кто-то говорил про отличия на порядки?
Если хочешь увидеть на порядки - потести варианты с коррелированными подзапросами.

Ты волен делать какие угодно выводы на основании таймингов или показать свой тест, но подобная демагогия это слив.

Можешь еще увеличивать число до 3e6, 5e6 и так далее пока не начнет вылезать в темп. И строить асимптоты.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019159
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode,

Пример когда PL/SQL рулит - 11567017 .
Но там альтернатива была только модель.
С графиками. Думаю тебе должно понравиться. :)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019167
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег,

Слив, это методика эксперимента))

Вот с графиками красиво и ... PL/SQL рулит ...

Переписал в виде пакета, без объектной обертки должно быть быстрее.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
create or replace package dropme_pkg as
    type res_rec_t is record (x1 t.x1%type, x2 t.x2%type, res t.c%type);
    type res_tab_t is table of res_rec_t;
    type refcur_t is ref cursor return t%rowtype;
    function f_superimpose return res_tab_t pipelined;
end dropme_pkg;
/

create or replace package body dropme_pkg as
    function f_superimpose return res_tab_t pipelined is
        c_refcur_t   refcur_t;
        l_res        res_rec_t;
        l_res_tmp    res_rec_t;
        l_src        t%rowtype;
        l_curr_flag  t.flag%type;
    begin
        open c_refcur_t for select * from t order by x1;
    
        fetch c_refcur_t into l_src;
        if c_refcur_t%NOTFOUND then 
            return;
        end if;
        
        l_res := res_rec_t(l_src.x1, l_src.x2, l_src.c);
        l_curr_flag := l_src.flag;

        loop
            fetch c_refcur_t into l_src;
            exit when c_refcur_t%NOTFOUND;
            
            -- разрыв
            if l_src.x1 - l_res.x2 > 1 then
                pipe row (l_res);
                l_res.x1 := l_res.x2 + 1;
                l_res.x2 := l_src.x1 - 1;
                l_res.res := '';
                pipe row (l_res);
                l_res.x1  := l_src.x1;
                l_res.x2  := l_src.x2;
                l_res.res := l_src.c;
                l_curr_flag := l_src.flag;
                continue;
            end if;
            
            -- касание
            if l_src.x1 - l_res.x2 = 1 then
                if l_src.c = l_res.res then
                    l_res.x2  := l_src.x2;
                    l_curr_flag := l_src.flag;
                else
                    pipe row (l_res);
                    l_res.x1  := l_src.x1;
                    l_res.x2  := l_src.x2;
                    l_res.res := l_src.c;
                    l_curr_flag := l_src.flag;
                end if;
                continue;
            end if;

            -- пересечение
            if l_src.x1 - l_res.x2 < 1 then
                if l_curr_flag = 'src' then
                    if l_src.x2 > l_res.x2 then
                        if l_src.c = l_res.res then
                            l_res.x2  := l_src.x2;
                            l_curr_flag := l_src.flag;
                        else
                            pipe row (l_res);
                            l_res.x1  := l_res.x2 + 1;
                            l_res.x2  := l_src.x2;
                            l_res.res := l_src.c;
                            l_curr_flag := l_src.flag;
                        end if;
                    end if;
                elsif l_curr_flag = 'tgt' then
                    if l_src.x2 >= l_res.x2 then
                        if l_src.c = l_res.res then
                            l_res.x2  := l_src.x2;
                            l_curr_flag := l_src.flag;
                        else
                            if l_src.x1 > l_res.x1 then
                                l_res.x2 := l_src.x1 - 1;
                                pipe row (l_res);
                            end if;
                            l_res.x1  := l_src.x1;
                            l_res.x2  := l_src.x2;
                            l_res.res := l_src.c;
                            l_curr_flag := l_src.flag;
                        end if;
                    else
                        if l_src.c != l_res.res then
                            if l_src.x1 > l_res.x1 then
                                l_res_tmp.x1  := l_res.x1;
                                l_res_tmp.x2  := l_src.x1 - 1;
                                l_res_tmp.res := l_res.res;
                                pipe row (l_res_tmp);
                            end if;
                            l_res_tmp.x1  := l_src.x1;
                            l_res_tmp.x2  := l_src.x2;
                            l_res_tmp.res := l_src.c;
                            pipe row (l_res_tmp);
                            l_res.x1 := l_src.x2 + 1;
                        end if;
                    end if;
                end if;
            end if;
        end loop;

        pipe row (l_res);
        close c_refcur_t;
    end;
end dropme_pkg;
/

select * from table(dropme_pkg.f_superimpose)

...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019175
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
Переписал в виде пакета
В этом не было особой необходимости, Оракл всё равно под капотом для таких функций создает типы SYS_PLSQL_%
Пакет бы пригодился когда понадобилось бы параллелить функцию и объявлять strong ref cursor. ;)
graycode
без объектной обертки должно быть быстрее
А это улучшение, да.
Теперь на уровне ведущих эскуэльных подходов.
Мир, равенство, братсво.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019179
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег,

Я твой тест из другого топика скоммуниздил и переделал под нашу задачу и что то не получаются твои результаты, ты бы позапускал и не один раз и на разном количестве записей ...

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
declare
    l_timestamp timestamp;
    l_i         interval day to second;
    res         number;
begin
    l_timestamp := localtimestamp;

    select sum(x1*x2) into res
    from
    (
    select t.*,
           nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result
      from (select x1,
                   sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
                   sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
                   last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
                   last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
              from (select c,
                           flag,
                           type,
                           x + decode(type, 'X2', 1, 0) x1,
                           decode(type, 'X1', 1, 'X2', -1) sign
                      from t unpivot(x for type in(x1, x2)))) t
    )
    match_recognize
    (
      order by x1
      measures
        first(x.x1) x1,
        next(x.x1) - 1 x2,
        x.result result
      pattern (x+)
      define
        x as first(nvl(result, '~')) = nvl(result, '~') and next(x1) is not null
    );

    l_i := localtimestamp - l_timestamp;
    dbms_output.put_line('kaban pattern matching - ' || res || ' - ' ||
                         to_char(extract(second from l_i) * 1000 +
                                 extract(minute from l_i) * 60000));

    ----------------------------------------------------------------------------

    l_timestamp := localtimestamp;

    with tt as
    (
    select x1,
           nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result,
           lag(nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c))) over(order by x1) prev_result
      from (select x1,
                   sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
                   sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
                   last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
                   last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
              from (select c,
                           flag,
                           type,
                           x + decode(type, 'X2', 1, 0) x1,
                           decode(type, 'X1', 1, 'X2', -1) sign
                      from t unpivot(x for type in(x1, x2)))) t
    )
    select sum(x1*x2) into res
      from (select min(x1) x1,
                   lead(min(x1)) over(order by grp) - 1 x2,
                   min(result) result
              from (select tt.*, sum(decode(result, prev_result, 0, 1)) over(order by x1) grp from tt)
             group by grp)
     where x2 is not null;

    l_i := localtimestamp - l_timestamp;
    dbms_output.put_line('kaban analyt - ' || res || ' - ' ||
                         to_char(extract(second from l_i) * 1000 +
                                 extract(minute from l_i) * 60000));
  

    ----------------------------------------------------------------------------

    l_timestamp := localtimestamp;

    with p as (
    select * from (
      select x, flag, decode(z,'X1',c,'-') c, z
        from (select x1, x2+1 x2, c, flag from t) tt
     unpivot (x for z in (x1,x2))) 
     pivot (max(c) for flag in ('src' s,'tgt' t))
    ),
    q as (
    select x x1, lead(x) over (order by x) -1 x2, c from (
      select x, c, lag(c) over (order by x) cp from (
        select x, decode(nvl(s,'-'),'-',t,s) c from (
          select x,
                 last_value(s ignore nulls) over (order by x) s,
                 last_value(t ignore nulls) over (order by x) t
            from p
          )
        )
      )
     where c != nvl(cp,' ')
    )
    select sum(x1*x2) into res from q
     where x1 <= x2;

    l_i := localtimestamp - l_timestamp;
    dbms_output.put_line('neofit - ' || res || ' - ' ||
                         to_char(extract(second from l_i) * 1000 +
                                 extract(minute from l_i) * 60000));

    ----------------------------------------------------------------------------

    l_timestamp := localtimestamp;

    select sum(x1*x2) into res from table(dropme_pkg.f_superimpose);

    l_i := localtimestamp - l_timestamp;
    dbms_output.put_line('graycode plsql - ' || res || ' - ' ||
                         to_char(extract(second from l_i) * 1000 +
                                 extract(minute from l_i) * 60000));

end;

...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019184
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег,

У тебя в том топике еще и bulk collect ...

НеофитSQL
я тоже хочу PL/SQL сделать!

Сделай не пайплайнед, а как у Кобанчег , в топике на который он ссылку дал.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019222
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
graycode
Кобанчег,

У тебя в том топике еще и bulk collect ...

НеофитSQL
я тоже хочу PL/SQL сделать!

Сделай не пайплайнед, а как у Кобанчег , в топике на который он ссылку дал.


Я уже написал пайплайном, на вашем примере.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
create or replace function f_overlay(cur sys_refcursor) return res_tab_t pipelined is
  l_src     src_rec_t;
  l_back    src_rec_t := src_rec_t(0,0,null,null);
  l_last    res_rec_t;
  r         res_rec_t;
  function RangeUntil( x in number, c in varchar2 ) return res_rec_t is
    ret res_rec_t;
  begin
    if x <= l_last.x2 then return null; end if;
    
    if nvl(c,'clear') = nvl(l_last.res,'clear') then
      l_last.x2 := x;
      return null;
    end if;

    ret := res_rec_t(l_last.x1,l_last.x2-1,l_last.res);
    l_last.x1 := l_last.x2;
    l_last.x2 := x;
    l_last.res  := c;
    return ret;
  end;
begin
  loop
    fetch cur into l_src;
    exit when cur%NOTFOUND;
    l_src.x2 := l_src.x2+1;
    
    if l_last is null then 
      l_last := res_rec_t(l_src.x1, l_src.x1, l_src.c);
    end if;

    if l_src.flag = 'src' then
      r := RangeUntil( least(l_back.x2, l_src.x1), l_back.c );   if r is not null then pipe row (r); end if;
      r := RangeUntil( l_src.x1, null );                         if r is not null then pipe row (r); end if;
      r := RangeUntil( l_src.x2, l_src.c );                      if r is not null then pipe row (r); end if;
    else
      r := RangeUntil( l_back.x2, l_back.c );                    if r is not null then pipe row (r); end if;
      r := RangeUntil( l_src.x1, null );                         if r is not null then pipe row (r); end if;
      l_back := l_src;
    end if;
  end loop;
  close cur;

  r := RangeUntil( l_src.x2, l_src.c );  if r is not null then pipe row (r); end if;
  r := RangeUntil( l_src.x2+1, null );   if r is not null then pipe row (r); end if;
end;


Долго ломал голову как сделать условный pipe row (чтобы пустые строчки не плевало), но так и не смог.
Поэтому в правой части много повторяющегося кода.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019224
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Без пайплайна возможно быстрее. Надеюсь Кобанчег или другие бенчмаркнут.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
create or replace function f_overlay(cur sys_refcursor) return res_tab_t is
  l_src     src_rec_t;
  l_back    src_rec_t := src_rec_t(0,0,null,null);
  l_last    res_rec_t;
  rett      res_tab_t := res_tab_t();

  procedure RangeUntil( x in number, c in varchar2 ) is
  begin
    if x <= l_last.x2 then return; end if;
    
    if nvl(c,'clear') = nvl(l_last.res,'clear') then
      l_last.x2 := x;
      return;
    end if;

    rett.extend;
    rett(rett.last) := res_rec_t(l_last.x1,l_last.x2-1,l_last.res);
    l_last.x1 := l_last.x2;
    l_last.x2 := x;
    l_last.res  := c;
  end;

begin
  loop
    fetch cur into l_src;
    exit when cur%NOTFOUND;
    l_src.x2 := l_src.x2+1;
    
    if l_last is null then 
      l_last := res_rec_t(l_src.x1, l_src.x1, l_src.c);
    end if;

    if l_src.flag = 'src' then
      RangeUntil( least(l_back.x2, l_src.x1), l_back.c );
      RangeUntil( l_src.x1, null );
      RangeUntil( l_src.x2, l_src.c );
    else
      RangeUntil( l_back.x2, l_back.c );
      RangeUntil( l_src.x1, null );
      l_back := l_src;
    end if;
  end loop;
  close cur;

  RangeUntil( l_src.x2, l_src.c );
  RangeUntil( l_src.x2+1, null );
  return rett;
end;

...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019364
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL
Без пайплайна возможно быстрее. Надеюсь Кобанчег или другие бенчмаркнут.

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

PS: в реальных задачах нужно учитывать что коллекция будет содержать все данные таблицы и находиться она будет в UGA.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019373
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
пайплайном мы по одной строчке перегоняем входящий отсортированный набор данных в выходной набор данных

Точно? :)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019430
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
andrey_anonymous
Точно? :)

Мы точно не ползаем по исходному набору и не модифицируем его, мы читаем по строке, формируем новую в PL/SQL и отдаем обратно в SQL, где поверх еще идет суммирование, в SQL решениях одно исполняющее ядро SQL и возможность по максимуму использовать исходный набор данных не перекачивая его через сторонние структуры построчно.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019437
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
graycode
НеофитSQL
Без пайплайна возможно быстрее. Надеюсь Кобанчег или другие бенчмаркнут.

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

PS: в реальных задачах нужно учитывать что коллекция будет содержать все данные таблицы и находиться она будет в UGA.


Если набор данных ужЕ в памяти, быстрее вызвать внешнюю функцию на сях :)

по поводу обработки коллекции in-place, там довольно неочевидная (для меня) оценка размера результата.
Вроде бы худший случай это 2N если нужно выводить незакрашенные интервалы, и 2N-1 если их можно пропускать.
(N- число строк в исходной таблице)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019444
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег,

Погонял на таблице разного размера и генерации, однозначного победителя из трех вариантов kaban pattern matching, neofit, graycode plsql не выявил, лидером оказывается то один то другой то третий, причем pattern matching всегда очень близко к pl/sql варианту, neofit уходит то в плюс то в минус процентов на двадцать. Честно говоря от pl/sql варианта ожидал лучших результатов.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019455
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL,

Оценить размер результата сложно, там помимо пропусков может быть увеличение, например идет интервал tgt, а в его середине интервал src, на входе два интервала, на выходе три, если два интервала src в середине tgt, то исходных три интервала, а на выходе 5.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019459
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
мы читаем по строке, формируем новую в PL/SQL и отдаем обратно в SQL

Ну и откуда вывод, что выдача происходит по одной строке?
Из statement PIPE ROW?
Ну-ну.
Что до чтения - тут вообще странно Вас читать.
Ничто не мешает ни явному bulk collect, ни неявному (оптимизация курсорного цикла на PLSQL Optimizer Level 2).
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019476
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
graycode
Кобанчег,

Погонял на таблице разного размера и генерации, однозначного победителя из трех вариантов kaban pattern matching, neofit, graycode plsql не выявил, лидером оказывается то один то другой то третий, причем pattern matching всегда очень близко к pl/sql варианту, neofit уходит то в плюс то в минус процентов на двадцать. Честно говоря от pl/sql варианта ожидал лучших результатов.


Pl/SQL компилированный, я надеюсь?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019481
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
graycode
НеофитSQL,

Оценить размер результата сложно, там помимо пропусков может быть увеличение, например идет интервал tgt, а в его середине интервал src, на входе два интервала, на выходе три, если два интервала src в середине tgt, то исходных три интервала, а на выходе 5.


Да, я уже решил полным перебором. Ответ 2N (2N-1 если не показывать пробелы) правильный.

Удвоение не так уж плохо. Тогда можно аллокировать массив двойной длины, собрать отсортированные по x1 данные в его вторую половину, оставляя первую пустой и не затирая непрочитанных данных обработать в том же пространстве.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019517
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL
Pl/SQL компилированный, я надеюсь?

Нет, так что еще есть пространство для оптимизации))
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019526
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
andrey_anonymous,

Еще не факт что пакетная обработка даст серьезный прирост производительности в этой задаче, потребление памяти даст точно))

SQL: сумма(вычисления(сортировка(исходные данные)))

PL/SQL: сортировка(исходные данные) -> черный ящик (PL/SQL вычисления) -> Сумма(результирующий набор из черного ящика построчно или пакетом/пакетами)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019529
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode,

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

что касается pl/sql против нет - ну, с Марса, имхо, так видится:
в случае pl/sql - ~nLog(n) для стартовой сортировки + ~nLog(n) сам алгоритм построения результата.

SQL, может быть, в виде pattern matching к этому подберется, если повезет с алгоритмами в его нутрях.
Join надо будет попотеть заставлять оставаться в рамках роста nLog(n) на больших бъемах.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019532
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
booby

что касается pl/sql против нет - ну, с Марса, имхо, так видится:
в случае pl/sql - ~nLog(n) для стартовой сортировки + ~nLog(n) сам алгоритм построения результата.


Построение результата должно быть линейным, т.к. простой цикл без учета длины данных.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019538
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
booby
то, что было показано, в твоем pl/sql коде в частности, подозрительно,
поскольку, на беглый взгляд, плохо учитывает возможность множественного пересеченения каждого из исходных отрезков с порождением множества результатов пересечения из одного исходного отрезка.

Не очень понял что имеется ввиду, у нас src это приоритетные отрезки, поэтому если на них накладываются отрезки tgt, то отрезки tgt частью попадающей на src просто игнорируются, остается только выступающая за src часть, а друг с другом src пересекаться не могут по условию задачи, да и приоритета по цветам у нас нет, пересечение отрезков src отрезками tgt обрабатывается.

booby
~nLog(n) сам алгоритм построения результата.

В цикле по отсортированной входной выборке только дерево условных операторов, т.е. ~(n), откуда логарифм?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019556
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode,

вы тут две задачи обсуждаете, формулировку второй я вообще не понял, правда и не вчитывался...

в общем, даже не важно про первую или вторую это задачу:
автору нас src это приоритетные отрезки, поэтому если на них накладываются отрезки tgt, то отрезки tgt частью попадающей на src просто игнорируются, остается только выступающая за src часть

здесь умолчанием подразумевается,что а) у src нет пересечений,
б) входной набор "правильно" сортирован и, значит, в) tgt относящийся к "другому" src не приедет преждевременно.

сколько, кстати, кусков от src должно остаться после наложения всех tgt, и почему следующий tgt не может резать внахлест уже разрезанное предыдущим?

Т.е. слишком много ифов зашито в первичную сортировку.
А так по виду - классическая задача на заметание, в любом случае, решаемая за ~nLog(n)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019569
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
А так по виду - классическая задача на заметание, в любом случае, решаемая за ~nLog(n)

На базе SMJ вполне делается за две сортировки плюс линейный перебор.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019574
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
andrey_anonymous,

что такое SMJ?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019580
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
andrey_anonymous,
что такое SMJ?

Sort Merge Join :)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019586
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
andrey_anonymous
booby
andrey_anonymous,
что такое SMJ?

Sort Merge Join :)

понял, это ты к тому, для join тоже можно гарантию nLog(n) обеспечить...
Ок.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019593
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
booby
здесь умолчанием подразумевается,что а) у src нет пересечений,
б) входной набор "правильно" сортирован и, значит, в) tgt относящийся к "другому" src не приедет преждевременно.

Входной набор сортируется ~nLog(n), дальше идет цикл ~(n), пересечений src-src и tgt-tgt быть не может.

tgt относящийся к "другому" src может приехать и это не важно, проверки отрабатывают эту ситуацию, поскольку блоки приезжают в порядке x1, просто корректируется верхняя текущая граница x2 и ее тип, если следующим приезжает блок src, то он просто срезает текущую x2 по свой x1, так что тут все вполне линейно считается.

booby
сколько, кстати, кусков от src должно остаться после наложения всех tgt, и почему следующий tgt не может резать внахлест уже разрезанное предыдущим?

Автор задачи дал немного странные названия, src не режется, он приоритетный, т.е. src режет, но не наоборот, блоки одного типа не могут пересекаться.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019597
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
понял, это ты к тому, для join тоже можно гарантию nLog(n) обеспечить...
Ок.

Это я к тому, что при наличии предварительно отсортированных наборов сам SMJ линеен и, вообще говоря, подходит под решение задачи.
Наличие пресортированных наборов можно обеспечить индексным доступом и тем самым решить за линейное время.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019601
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
... пересечений src-src и tgt-tgt быть не может.

....

с чего бы это?
чтобы задачу упростить?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019604
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby

чтобы задачу упростить?

Задача аннулирования самопересечений достаточно тривиальна и не очень интересна в контексте.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019628
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
andrey_anonymous
На базе SMJ вполне делается за две сортировки плюс линейный перебор.
Казалось бы, зачем джойн когда можно без оного и эффективнее.
Более того, если делать через джойн, то линейным перебором можно обойтись только в PL/SQL, SQL-но придется использовать еще один джойн (или pivot).
Я ж так понимаю речь про такое ядро
Код: plsql
1.
2.
3.
4.
5.
select *
  from (select * from t where flag = 'tgt') t
  full join (select * from t where flag = 'src') s
    on s.x1 <= t.x2
   and t.x1 <= s.x2

?
Ну так это уступает тому, что уже было показано.
У меня то есть финальный вариант но я не видел смысла его выкладывать в виду неконкуретноспособности.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019635
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег

У меня то есть финальный вариант


для

select 10, 20, 'blue', 'tgt' from dual union all
select 15, 25, 'blue', 'src' from dual

результат одна строка 10, 25, 'blue' ?

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019636
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax,

Да.

PS. Если что можно же ответ сверять с имеющимися вариантами.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019638
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Хм, сделал таблицу IOT с pk по всем полям, теперь pl/sql стабильно чуть быстрее, но именно чуть чуть, т.е. все равно все три варианта равноценны в практическом плане и вариант неофита лучше варианта pattern matching.

PS: pl/sql native и Optimizer Level 2
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019713
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
линейным перебором можно обойтись только в PL/SQL

Ага
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019724
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
andrey_anonymous
Кобанчег
линейным перебором можно обойтись только в PL/SQL

Ага


Да ну, я же публиковал линейный перебор в самом начале на SQL.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019744
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
andrey_anonymous
пропущено...
Ага

Да ну, я же публиковал линейный перебор в самом начале на SQL.

Что-то я не видел.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019754
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
andrey_anonymous
Что-то я не видел.
Первым линейный перебор опубликовал господин graycode и без всяких SMJ.

22233043
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019767
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Это на PL/SQL.

Я про это: 22232233

Контекст:
,>линейным перебором можно обойтись только в PL/SQL
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019770
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019772
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
xtender,


Мне эта видится проще,тут N слоев одиночных заплаток, перебор комбинаций меньше.

Соответственно и решение короче. Но задачка тоже классная, я попробую решить не глядя в ссылку.

А задачи про двухмерные заплатки никто не публиковал?

Например:
Каждая строка задаёт х1,х2,у1,у2 координаты покрашенного прямоугольника. Определить:
- площадь покрашенной поверхности
- максимальный полностью закрашенный прямоугольник
- максимальное число слоев на поверхности
- площадь поверхности содержащая ровно N слоев краски

Для супер одаренных:
- наибольший полностью закрашенный круг (центр и радиус)

Это монохромная версия. Можно добавить цвета..
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019774
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set


Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
with t(lvl,x1,x2) as (
select 1,10,11 from dual union all
select 2,10,12 from dual union all
select 3, 8,13 from dual union all
select 4, 9,14 from dual union all
select 5, 3,15 from dual union all
select 6, 4,16 from dual union all
select 7, 5,17 from dual
)
select * from (
  select lvl, x1, nvl(lag(x1) over (order by lvl),x2) x2 from t union all
  select lvl, lag(x2) over (order by lvl) x1, x2 from t
) where x1 < x2 order by x1
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019775
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Почитал решения по ссылке, народ явно легких путей не ищет.

"Simplicate, and add lightness" (c)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019780
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL

А задачи про двухмерные заплатки никто не публиковал?

Например:
Каждая строка задаёт х1,х2,у1,у2 координаты покрашенного прямоугольника. Определить:
- площадь покрашенной поверхности
- максимальный полностью закрашенный прямоугольник
- максимальное число слоев на поверхности
- площадь поверхности содержащая ровно N слоев краски

Для супер одаренных:
- наибольший полностью закрашенный круг (центр и радиус)

Это монохромная версия. Можно добавить цвета..


Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
-- порядок не задан, краска одинаковая
-- x,y - координаты границ а не номера колонок, 
-- т.е. 5-5 это пустой отрезок, а не один интервал
with t(x1,x2,y1,y2) as (
select 1, 5, 3, 5 from dual union all
select 2, 6, 2, 4 from dual union all
select 1, 7, 3, 6 from dual union all
select 4, 8, 2, 3 from dual union all
select 5, 6, 4, 9 from dual union all
select 5, 9, 2, 6 from dual union all
select 7, 8, 5, 7 from dual
)
select ...



С фотошопом я не дружу, поэтому иллюстрация в ASCII:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
	1  2  3  4  5  6  7  8
2	   $  $  $  $  $  $  $
3	$  $  $  $  $  $  $  $
4	$  $  $  $  $  $  $  $
5	$  $  $  $  $  $  $  $
6	            $     $   
7	            $         
8	            $         

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
xx as (
select level x from dual where level >= (select min(x1) from t) 
connect by level < (select max(x2) from t) 
),
yy as (
select level y from dual where level >= (select min(y1) from t) 
connect by level < (select max(y2) from t) 
)
select null "row", (select listagg(x,'  ') within group (order by x) from xx) "columns"
  from dual union all
select y, (select listagg(decode(
   (select count(*) from t where x>=x1 and x<x2 and y>=y1 and y<y2),0,' ','$')
           ,'  ') within group (order by x) from xx) 
  from yy 

...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019902
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
А задачи про двухмерные заплатки никто не публиковал?

Приходилось как-то на проекте внедрения внезапно под вечер решать задачку вида "сделать из списка (с историей изменения) префиксов телефонных зон двумерную карту для быстрого определения корректной зоны вызова по параметрам (вызываемый номер, дата соединения)".
Не rocket science, хотя пару-тройку часов из жизни выкинул.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019905
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL
Почитал решения по ссылке, народ явно легких путей не ищет.

"Simplicate, and add lightness" (c)

А ты подставь данные из ссылки и сравни результат, ты решал какую то другую задачу.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019967
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
Жаль, критерий трудно определить объективно.

У меня получилось так.


должно быть две строки?

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
with t (x1, x2, c, flag) as
(
              select 10, 30, 'blue', 'src' from dual
union all select 20, 30, 'red', 'tgt' from dual
union all select 31, 35, 'red', 'tgt' from dual
)
,p as (
select * from (
  select x, flag, decode(z,'X1',c,'-') c, z
    from (select x1, x2+1 x2, c, flag from t) tt
 unpivot (x for z in (x1,x2))) 
 pivot (max(c) for flag in ('src' s,'tgt' t))
),
q as (
select x x1, lead(x) over (order by x) -1 x2, c from (
  select x, c, lag(c) over (order by x) cp from (
    select x, decode(s,'-',t,s) c from (
      select x,
             last_value(s ignore nulls) over (order by x) s,
             last_value(t ignore nulls) over (order by x) t
        from p
      )
    )
  )
 where c != nvl(cp,' ')
)
select x1,x2,c from q
 where x1 <= x2  
/

SQL> /

        X1         X2 C
---------- ---------- ----
        10         30 blue



.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019978
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
Собственно мой вариант таков.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
select *
  from
(
select x1,
       nvl(decode(src_active, 1, src_c), decode(tgt_active, 1, tgt_c)) result
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1, type) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1, type) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1, type) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1, type) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
match_recognize
(
  order by x1
  measures
    first(x.x1) x1,
    next(x.x1) - 1 x2,
    x.result result
  pattern (x+)
  define
    x as first(nvl(result, '~')) = nvl(result, '~') and next(x1) is not null
)

MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTOMATON + WINDOW SORT + UNPIVOT

При попытке решить однопроходно с match recognize упираешься в то, что "активный" цвет для текущей группы определяется по всему набору а match recognize не позволяет заглядывать в предыдущие группы.



Код: plsql
1.
2.
3.
4.
5.
with t (x1, x2, c, flag) as
(
              select 20, 30, 'red', 'src' from dual
union all select 20, 30, 'red', 'tgt' from dual
)



Код: plaintext
1.
2.
3.
4.
5.
X1	X2	RESULT
20	30	red
31	30	 - 
Download CSV
2 rows selected.

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019979
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Stax
должно быть две строки?

Да.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019982
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Stax
.....

Всех замочил)))

PS: для проверки используйте PL/SQL вариант 22233043 ))
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019985
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax
должно быть две строки?
Да. Ну ты мастер тестирования!
Можешь использовать мой запрос, там верно возвращает.

Я в его решении поправил один баг, получается есть еще (странно что это не всплыло в моём чудо тесте)
Кобанчег
Мелкий баг - decode(s,'-',t,s) может быть null если диапазоны начинаются с target.


Fix
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
with p as (
select * from (
  select x, flag, decode(z,'X1',c,'-') c--, z
    from (select x1, x2+1 x2, c, flag from t) tt
 unpivot (x for z in (x1,x2))) 
 pivot (max(c) for flag in ('src' s,'tgt' t))
),
q as (
select x x1, lead(x) over (order by x) -1 x2, c from (
  select x, c, lag(c) over (order by x) cp from (
    select x, decode(nvl(s,'-'),'-',t,s) c from (
      select x,
             last_value(s ignore nulls) over (order by x) s,
             last_value(t ignore nulls) over (order by x) t
        from p
      )
    )
  )
 where c != nvl(cp,' ')
)
select sum(x1*x2) hash from q
 where x1 <= x2;
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019986
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode,

у НеофитSQL-а одна, косяк

Ваш вариант не тестировал (что-то лень обьекты создавать)

если дойдут руки, заменю pipe на dbms_output и мож потестю

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019988
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег
странно что это не всплыло в моём чудо тесте

Тестовые данные не покрывают много кейсов, а генератор на производительность вообще вырожденный и возможно это одна из причин удивительных результатов теста на производительность[/quot]
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019992
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Stax,

Здесь тот же вариант, только в исполнении в виде пакета 22233388
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40019999
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
возможно это одна из причин
Наша песня хороша начинай сначала.
Я вчера уже поверил в твою адекватность когда ты признал что PL/SQL и SQL приверно одного уровня по производителности.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020002
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег

Можешь использовать мой запрос, там верно возвращает.



для unpivot + pivot + lead сдаюсь

поспешил
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
SQL> ed
Wrote file afiedt.buf

  1  with t (x1, x2, c, flag) as
  2  (
  3                select 10, 30, 'blue', 'src' from dual
  4  union all select 20, 30, 'red', 'tgt' from dual
  5  union all select 31, 35, 'red', 'tgt' from dual
  6  )
  7  ,p as (
  8  select * from (
  9    select x, flag, decode(z,'X1',c,'-') c, z
 10      from (select x1, x2+1 x2, c, flag from t) tt
 11   unpivot (x for z in (x1,x2)))
 12   pivot (max(c) for flag in ('src' s,'tgt' t))
 13  ),
 14  q as (
 15  select x x1, lead(x) over (order by x) -1 x2, c from (
 16    select x, c, lag(c) over (order by x) cp from (
 17      select x, decode(s,'-',t,s) c from (
 18        select x,
 19               last_value(s ignore nulls) over (order by x) s,
 20               last_value(t ignore nulls) over (order by x) t
 21          from p
 22        )
 23      )
 24    )
 25   where c != nvl(cp,' ')
 26  )
 27  select x1,x2,c from q
 28*  where x1 <= x2
SQL> /

        X1         X2 C
---------- ---------- ----
        10         30 blue

SQL>




зі
match_recognize с ошибкой

зы
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020003
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег,

Причина мне не совсем понятна, я убрал фактор сортировки, т.е. сортировок нет, просто прогоняется набор исходных данных через функцию, в функции только дерево условий, по идее должно быть быстрее, оно и быстрее но совсем незначительно, можешь объяснить причину?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020005
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
Причина мне не совсем понятна, я убрал фактор сортировки, т.е. сортировок нет
Код: plsql
1.
open c_refcur_t for select * from t order by x1;

?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020006
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег,

IOT, pk по всем полям начиная с x1))
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020010
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode,

Ну тогда смотри куда уходит время в dbms_hprof + dbms_sqltune.report_sql_monitor

Может что-то еще можно выжать из твоего подхода, но практической ценности для меня не несет.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020017
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax
для unpivot + pivot + lead сдаюсь

поспешил
Ты fix тут увидел?
22234679

В моём сортировку в аналитике надо сделать идентичной с MR.
Код: plsql
1.
over(order by x1/*, type*/)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020018
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
graycode
Stax,

Здесь тот же вариант, только в исполнении в виде пакета 22233388


Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
SQL> create or replace package dropme_pkg as
  2      type res_rec_t is record (x1 t.x1%type, x2 t.x2%type, res t.c%type);
  3      type res_tab_t is table of res_rec_t;
  4      type refcur_t is ref cursor return t%rowtype;
  5      function f_superimpose return res_tab_t pipelined;
  6  end dropme_pkg;
  7  /

Package created.

...
104  end dropme_pkg;
105  /

Warning: Package Body created with compilation errors.

SQL> show err
Errors for PACKAGE BODY DROPME_PKG:

LINE/COL ERROR
-------- -----------------------------------------------------------------
16/9     PL/SQL: Statement ignored
16/18    PLS-00222: no function with name 'RES_REC_T' exists in this scope
SQL> l 16
 16*         l_res := res_rec_t(l_src.x1, l_src.x2, l_src.c);
SQL>



.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020024
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег

Ты fix тут увидел?

увидел, сдался тестировать

видать в буффере был древний(без фикса) вариант, и я уже не присмотрелся

звиняйте, поспешил

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020038
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set


Немного изменил условия, интервалы в целых числах, как в предыдущих задачах и добавил немного данных:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
0   1   2   3   4   5   6   7   8...9...10...11...12...13...14....20.23...25

|--------------------------------------a------------------------------------|
        |---b---|                                                            
    |---c---|                                                                
                |---d---|                                                    
            |---e---|                                                        
                            |-f-|                                            
                                    |---------g--------|                     
                                         |--h---|                            
                                                 |--i--|                     
                                                       |--j--|               
                                                                   |-k-|     


Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
with t (lvl, x1, x2) as
(
select 'a', 0, 25 from dual union all
select 'b', 2, 4 from dual union all
select 'c', 1, 3 from dual union all
select 'd', 4, 6 from dual union all
select 'e', 3, 5 from dual union all
select 'f', 7, 8 from dual union all
select 'g', 9, 13 from dual union all
select 'h', 10, 11 from dual union all
select 'i', 12, 13 from dual union all
select 'j', 13, 14 from dual union all
select 'k', 20, 23 from dual
)



Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
select *magic* from t;
-- result:
+------+-------------+-----------+
| a    |           0 |         0 |
| c    |           1 |         1 |
| e    |           3 |         5 |
| d    |           6 |         6 |
| f    |           7 |         8 |
| g    |           9 |         9 |
| h    |          10 |        11 |
| i    |          12 |        12 |
| j    |          13 |        14 |
| a    |          15 |        19 |
| k    |          20 |        23 |
| a    |          24 |        25 |
+------+-------------+-----------+


Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender).
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020047
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Stax
НеофитSQL
Жаль, критерий трудно определить объективно.

У меня получилось так.


должно быть две строки?

.....
stax


Нарушено условие задачи, интервалы одного уровня касаются.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020056
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
graycode
Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender).
имхо для больших наборов с большим количеством цветом наиболее эффективное решение было бы unpivot + sort + pl/sql цикл с ассоциативными массивами для не закончившихся интервалов (и удалением закончившихся). Сейчас пока некогда, да и довольно просто реализуется, так что попозже наваяю, если кто-то не сподобится сделать это раньше.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020057
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Stax,

Пакет под тестирование производительности был сделан, таблица здесь 22233322
Код: plsql
1.
create table t(x1 int, x2 int, c varchar2(10), flag varchar2(3));


Сам тест кандидатов на лучшее время выполнения 22233403 .
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020059
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
graycode
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set


Немного изменил условия, интервалы в целых числах, как в предыдущих задачах и добавил немного данных:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
0   1   2   3   4   5   6   7   8...9...10...11...12...13...14....20.23...25

|--------------------------------------a------------------------------------|
        |---b---|                                                            
    |---c---|                                                                
                |---d---|                                                    
            |---e---|                                                        
                            |-f-|                                            
                                    |---------g--------|                     
                                         |--h---|                            
                                                 |--i--|                     
                                                       |--j--|               
                                                                   |-k-|     


Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
with t (lvl, x1, x2) as
(
select 'a', 0, 25 from dual union all
select 'b', 2, 4 from dual union all
select 'c', 1, 3 from dual union all
select 'd', 4, 6 from dual union all
select 'e', 3, 5 from dual union all
select 'f', 7, 8 from dual union all
select 'g', 9, 13 from dual union all
select 'h', 10, 11 from dual union all
select 'i', 12, 13 from dual union all
select 'j', 13, 14 from dual union all
select 'k', 20, 23 from dual
)



Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
select *magic* from t;
-- result:
+------+-------------+-----------+
| a    |           0 |         0 |
| c    |           1 |         1 |
| e    |           3 |         5 |
| d    |           6 |         6 |
| f    |           7 |         8 |
| g    |           9 |         9 |
| h    |          10 |        11 |
| i    |          12 |        12 |
| j    |          13 |        14 |
| a    |          15 |        19 |
| k    |          20 |        23 |
| a    |          24 |        25 |
+------+-------------+-----------+


Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender).

Ответ в первой строчке должен быть а-0-1.
В этой задаче отрезки задаются границами интервалов (см картинку).
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020064
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL
Ответ в первой строчке должен быть а-0-1.
В этой задаче отрезки задаются границами интервалов (см картинку).

Так я написал, что немного изменил условия, сделал их как в предыдущих задачах, т.е. интервалы 0-1 и 1-3 пересекаются, рассматривай их как блоки из кубиков.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020070
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
graycode
НеофитSQL
Ответ в первой строчке должен быть а-0-1.
В этой задаче отрезки задаются границами интервалов (см картинку).

Так я написал, что немного изменил условия, сделал их как в предыдущих задачах, т.е. интервалы 0-1 и 1-3 пересекаются, рассматривай их как блоки из кубиков.


Зря изменил. Координаты для науки, кубики для детей :)

Теперь на иллюстрации длины отрезков не совпадают, и ответ все равно неверный.

По координатам должно быть: c[1-3] (так в оригинале)
По "кубикам" должно быть: c(1,2)
У тебя в ответе: c(1,1)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020078
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
Почти линейный PL/SQL к 22232077
Кобанчег
задачка посложнее.


Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
declare
  type varchars is table of varchar2(10);
  type avarchars is table of varchar2(10) index by varchar2(10);

  a_colors avarchars;
  idx varchar2(10); 
  x number;
  
  cursor c_data is 
      with t (x1, x2, c, flag) as
      (
                select 1, 4, 'red', 'src' from dual
      union all select 7, 10, 'yellow', 'src' from dual
      union all select 13, 16, 'red', 'src' from dual
      --union all select 3, 14, 'black' from dual
      union all select 3, 7, 'black', 'tgt' from dual
      union all select 9, 11, 'black', 'tgt' from dual
      union all select 13, 14, 'black', 'tgt' from dual
      --
      union all select 16, 19, 'blue', 'tgt' from dual
      union all select 18, 22, 'green', 'src' from dual
      union all select 22, 25, 'black', 'tgt' from dual
      union all select 26, 28, 'red', 'src' from dual
      union all select 29, 30, 'red', 'tgt' from dual
      union all select 32, 33, 'black', 'tgt' from dual
      )
      select *
      from t
      unpivot (x for type in (x1 as 1, x2 as 2))
      order by x, type;
      
   function iterate( idx in out nocopy varchar2, arr in out nocopy avarchars) 
      return boolean
   as pragma inline;
   begin
      if idx is null
         then idx:=arr.first; 
         else idx:=arr.next(idx);
      end if;
      return idx is not null;
   end;
 
  function keys(a in out nocopy avarchars) return varchars as
     res varchars:=varchars();
     idx varchar2(10);
     pragma inline;
  begin
     while iterate(idx,a) loop
        res.extend;
        res(res.count):=idx;
     end loop;
     return res;
  end;
begin
   for r in c_data loop
      if r.type=1 then
         a_colors(r.c):=r.c;
         x:=r.x;
      else
         a_colors.delete(r.c);
         x:=r.x+1;
      end if;
      
      dbms_output.put(x||': '||a_colors.count()||' colors:');
      while iterate(idx, a_colors) loop
         dbms_output.put(' '||a_colors(idx));
      end loop;
      dbms_output.put_line('.');
   end loop;
end;


output
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
1: 1 colors: red.
3: 2 colors: black red.
5: 1 colors: black.
7: 2 colors: black yellow.
8: 1 colors: yellow.
9: 2 colors: black yellow.
11: 1 colors: black.
12: 0 colors:.
13: 1 colors: black.
13: 2 colors: black red.
15: 1 colors: red.
16: 2 colors: blue red.
17: 1 colors: blue.
18: 2 colors: blue green.
20: 1 colors: green.
22: 2 colors: black green.
23: 1 colors: black.
26: 0 colors:.
26: 1 colors: red.
29: 0 colors:.
29: 1 colors: red.
31: 0 colors:.
32: 1 colors: black.
34: 0 colors:.

...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020081
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Есть простое, в четыре строчки, решение для частного случая, когда при закрашивании не формируются дырки.

Общее решение пока не придумал. И по слоям, и по координатам накапливается state.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020082
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
graycode
Немного изменил условия
зачем? в чем смысл?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020086
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
xtender,

В пятничных задачах есть смысл?

На тетрис похоже))
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020091
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
graycode
xtender,

В пятничных задачах есть смысл?

На тетрис похоже))
я не понял смысла изменения, если от перевода в целые становится лишь легче, а изменение окончаний вообще странно...
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020092
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL
По "кубикам" должно быть: c(1,2)
У тебя в ответе: c(1,1)

Да, ошибся должно быть c(1,2).
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020103
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Правильный ответ для задачи по отрезкам с координатами:
Также подправил картинку, а то левая часть была отрезками, а правая - "кубиками"

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
0   1   2   3   4   5   6   7   8...9...10...11...12...13...14...20...23...25

|--------------------------------------a----------------------------------|
        |---b---|                                                            
    |---c---|                                                                
                |---d---|                                                    
            |---e---|                                                        
                            |-f-|                                            
                                    |---------g--------|                     
                                        |--h-|                            
                                                  |--i-|                     
                                                       |--j-|               
                                                                  |--k-|

LVL	X1	X2
a	0	1
c	1	3
e	3	5
d	5	6
a	6	7
f	7	8
a	8	9
g	9	10
h	10	11
g	11	12
i	12	13
j	13	14
a	14	20
k	20	23
a	23	25

Исходные данные (от graycode), плюс мое решение "в лоб" для проверки:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
with t (lvl, x1, x2) as
(
select 'a',  0, 25 from dual union all
select 'b',  2,  4 from dual union all
select 'c',  1,  3 from dual union all
select 'd',  4,  6 from dual union all
select 'e',  3,  5 from dual union all
select 'f',  7,  8 from dual union all
select 'g',  9, 13 from dual union all
select 'h', 10, 11 from dual union all
select 'i', 12, 13 from dual union all
select 'j', 13, 14 from dual union all
select 'k', 20, 23 from dual
),
p (lvl,x1,x2) as (
select lvl, x, lead(x) over (order by x) from (
  select * from (
    select x, lvl, lag(lvl) over (order by x) plvl from (
      select x, (select max(lvl) from t where x>=x1 and x <x2) lvl from (
        select level-1 x from dual where level-1 >= (select min(x1) from t) 
          connect by level <= (select max(x2) from t)+2) 
      ) 
    ) where nvl(lvl,'-') != nvl(plvl,'-')
  )
)
select * from p where lvl is not null
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020135
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL,

Так если координаты, зачем кубики нагенерил?))

PS: решения с генерацией диапазона не очень интересны даже для кубиков, а для координат не подходят вообще.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020152
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
graycode
НеофитSQL,

Так если координаты, зачем кубики нагенерил?))

PS: решения с генерацией диапазона не очень интересны даже для кубиков, а для координат не подходят вообще.


Не кубики, а пробные значения :-Р

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

Кубики в постановке задачи элементарно переводятся в отрезки:
Х1-х2. -> [х1,х2+1)

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

Для работы с данными отрезки лучше, для распечатки можно перевести в кубики, в зависимости от того кто читать будет.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020154
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL,

Не, тут уж или крестик или трусы)))
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020158
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
graycode,


Лол, хорошо. +0.5 для подобных.


В pl/sql решается просто вдоль Х через стэк глубиной lvl.
В sql нащупывается рекурсивное решение, но пока не сделал
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020216
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
Нарушено условие задачи, интервалы одного уровня касаются.
Перечитай условие. Подумай ещё. Посмотри в чем фикс. Всё же было обсуждено.
graycode
Сам тест кандидатов на лучшее время выполнения 22233403 .
Я конечно рад, что ты так проникся моим тестом 9-ти летней давности, но ты видимо так и не понял про сортировки и темп.
В той задаче были совсем другие объемы и поэтому не было надобности в alter session которые имеются в новом тесте.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020220
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
xtender
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set
Смотря в чем измерять сложность. Однозначно это более общий вариант, но "общесть" отрубает многие приёмы которые можно было бы применять в частном случае.
xtender
Почти линейный PL/SQL к 22232077
Кобанчег
задачка посложнее.
Но ведь это абсолютный overkill когда число "слоёв" фиксировано.
output
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
select *
from
(
select x1,
       decode(src_active, 1, src_c) || decode(src_active+tgt_active, 2, ', ') || decode(tgt_active, 1, tgt_c) colors
  from (select x1,
               sum(decode(flag, 'src', sign)) over(order by x1) src_active,
               sum(decode(flag, 'tgt', sign)) over(order by x1) tgt_active,
               last_value(decode(flag, 'src', c) ignore nulls) over(order by x1) src_c,
               last_value(decode(flag, 'tgt', c) ignore nulls) over(order by x1) tgt_c
          from (select c,
                       flag,
                       type,
                       x + decode(type, 'X2', 1, 0) x1,
                       decode(type, 'X1', 1, 'X2', -1) sign
                  from t unpivot(x for type in(x1, x2)))) t
)
/

        X1 COLORS
---------- --------------
         1 red
         3 red, black
         5 black
         7 yellow, black
         8 yellow
         9 yellow, black
        11 black
        12
        13 red, black
        13 red, black
        15 red
        16 red, blue
        17 blue
        18 green, blue
        20 green
        22 green, black
        23 black
        26 red
        26 red
        29 red
        29 red
        31
        32 black
        34

24 rows selected.

...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020223
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Challenge just for fun

Решить задачу отсюда
https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set

Не используя соединений или коррелированных подзапросов.

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

У меня более одного варианта.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020234
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
Challenge just for fun

Решить задачу отсюда
https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set

Не используя соединений или коррелированных подзапросов.

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

У меня более одного варианта.


и
1) а,b и b,c не пересекаются? соприкасаются? можно/надо слить в один a,c?
2) возможен ли диапазон a,a (зависит от ответа на п1)
3) одного цвета соприкасающиеся обьеденяем?
4) "чистый" sql или/и pl/sql?
итд

ps
у Неофита больше интервальчиков, мож и на его with тестировать
pss
жаль graycode забанили от публикаций

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020257
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax
1) а,b и b,c не пересекаются? соприкасаются? можно/надо слить в один a,c?
Соприкасаются (но не пересекаются) и сливаются.
Мы тут говорим про действительные числа уже.
Stax
2) возможен ли диапазон a,a (зависит от ответа на п1)
Я думаю это некорректные данные. По логике подразумевается что отрезки типа [start..end) то есть конец не входит.
Stax
3) одного цвета соприкасающиеся обьеденяем?
Да
Stax
4) "чистый" sql или/и pl/sql?
Чистый эксуэль конечно же!

Stax
жаль graycode забанили от публикаций
Да, совершенно непонятно за что забанили. Никаких предупреждений.
Более того это вообще может быть рандомный модератор любого форума.
Ну наверное самому забаненому что-то ясно.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020259
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax,

Я тестировал на этом наборе
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
with ranges (name, range_start, range_end) as
(
select 'a', 0, 7 from dual
union all select 'b', 2, 4 from dual
union all select 'c', 1, 3 from dual
union all select 'd', 4, 6 from dual
union all select 'e', 3, 5 from dual
--
union all select 'x', 3, 3.1 from dual
union all select 'y', 3.5, 3.7 from dual
union all select 'z', 3.9, 5.1 from dual
union all select 'a', 8, 9 from dual
)


Последний отрезок ломает решения икстендера потому что до него дырка, но легко допиливается.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020272
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
Последний отрезок ломает решения икстендера потому что до него дырка, но легко допиливается.
Ничего он не ломает, это провокация!
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020275
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег,

у икстендера есть главный/0 интервал покрывающий все, типа min()-x,max()+y цвета хаки
тогда дырок не будет

не знаю часть условия ли ето, или случайно

если я правильно понял то заливка уникальными цветами range_name

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020281
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax,

Да. У икстендера надо пустые интервалы выкинуть из результата.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020597
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег
Challenge just for fun

Решить задачу отсюда
https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set

Не используя соединений или коррелированных подзапросов.

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

У меня более одного варианта.


У меня число приоритетов до 38 попугаев, т.к. я не сумел listagg() использовать в оконном режиме.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
p as (
select c, x x1, lead(x) over (order by x ) x2 from (
  select c, x from (
    select c, lag(c) over (order by x) cp, x from (
      select chr(trunc(log(10,1+sum(c) over (order by x)))) c, x from (
        select  power(10,ascii(lvl)) c, x1 x from t union all
        select -power(10,ascii(lvl)) c, x2 x from t
      )
    )
  ) where nvl(c,'-') != nvl(cp,'-')
)
)
select * from p where x1 < x2 order by x1
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020602
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег
НеофитSQL
Нарушено условие задачи, интервалы одного уровня касаются.
Перечитай условие. Подумай ещё. Посмотри в чем фикс. Всё же было обсуждено.


Перечитал, действительно. О несоприкосновении говорилось в разминке, но не во второй задаче. С фиксом понятно.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020611
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
НеофитSQL

У меня число приоритетов до 38 попугаев, т.к. я не сумел listagg() использовать в оконном режиме.


Оно таки и не работает с окнами..
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020643
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
О несоприкосновении говорилось
Изначально в разрезе красное/черное, а потом подразумевалсь в разрезе src/tgt.
Но Stax уточнил 22233313 .
Твой запрос поломало касание src и tgt - это допустимо.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020656
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Нарушено условие задачи, интервалы одного уровня касаются.

Stax
НеофитSQL
Жаль, критерий трудно определить объективно.

У меня получилось так.


должно быть две строки?

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
with t (x1, x2, c, flag) as
(
              select 10, 30, 'blue', 'src' from dual
union all select 20, 30, 'red', 'tgt' from dual
union all select 31, 35, 'red', 'tgt' from dual
)
,p as (
select * from (
  select x, flag, decode(z,'X1',c,'-') c, z
    from (select x1, x2+1 x2, c, flag from t) tt
 unpivot (x for z in (x1,x2))) 
 pivot (max(c) for flag in ('src' s,'tgt' t))
),
q as (
select x x1, lead(x) over (order by x) -1 x2, c from (
  select x, c, lag(c) over (order by x) cp from (
    select x, decode(s,'-',t,s) c from (
      select x,
             last_value(s ignore nulls) over (order by x) s,
             last_value(t ignore nulls) over (order by x) t
        from p
      )
    )
  )
 where c != nvl(cp,' ')
)
select x1,x2,c from q
 where x1 <= x2  
/

SQL> /

        X1         X2 C
---------- ---------- ----
        10         30 blue



.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020663
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL,

Да, верно.
Это заодно и объясняет почему тест производительности не выявил различий.
Данные были нагенерированы без таких случаев.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020805
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пятница, господа!

Челендж еще активен
Кобанчег
Challenge just for fun

Решить задачу отсюда
https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set

Не используя соединений или коррелированных подзапросов.

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

У меня более одного варианта.


Данные для тестирования
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
with ranges (name, range_start, range_end) as
(
select 'a', 0, 7 from dual
union all select 'b', 2, 4 from dual
union all select 'c', 1, 3 from dual
union all select 'd', 4, 6 from dual
union all select 'e', 3, 6 from dual
--
union all select 'x', 3, 3.1 from dual
union all select 'y', 3.5, 3.7 from dual
union all select 'z', 3.9, 5.1 from dual
union all select 'a', 8, 9 from dual
union all select 'a', 8, 9.9 from dual
)



Constraints
(name, range_start, range_end) - уникально
(range_end > range_start)
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020811
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
Кобанчег
- число приоритетов неограничено
name может быть от a,...,z,aa,...,az,...,zzzzzzzzzzzzz?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020813
Фотография Sayan Malakshinov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Модератор форума
Кобанчег,

model, рекурсивные запросы?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020815
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
xtender
Кобанчег,

model, рекурсивные запросы?
Затрудняюсь представить как можно обойтись без джойна в рекурсивном члене.

Модель - конено, почему бы нет. Ну разве что итеративная модель - это не спортивно.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020819
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
xtender
Кобанчег
- число приоритетов неограничено
name может быть от a,...,z,aa,...,az,...,zzzzzzzzzzzzz?
Не вижу смысла ограничивать, но если с какими-то подобнми особенностями получается что-то изящное - интересно было бы посмотреть.
Ну на единичную длину закладываться не стоит.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020831
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
xtender
пропущено...
name может быть от a,...,z,aa,...,az,...,zzzzzzzzzzzzz?
Не вижу смысла ограничивать, но если с какими-то подобнми особенностями получается что-то изящное - интересно было бы посмотреть.
Ну на единичную длину закладываться не стоит.

имхо
удобнее было-б уровень задавать числами (int), цвет varchar2(хх)

....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020844
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Stax,

Мне кажется примерно индифферентно для чего делать max.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020845
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кобанчег
Stax,

Мне кажется примерно индифферентно для чего делать max.

a
aa
ab
c
d
...
z

мне удобнее числа
и легче тестовые добавлять (+ не надо помнить алфавит)

в етой пятничной наверное менять не надо, у народа наработки уже на буквах

.....
stax
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020880
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Собственно варианты следующие.

Раз

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
select *
  from (select x, max(decode(y, 1, name)) name
          from (select *
                  from (select x, name, sum(r) r
                          from ranges unpivot(x for r in(range_start as '1', range_end as '-1'))
                         group by x, name)
                 model dimension by(x, name) measures(r, 0 y)
                 rules upsert all
                 (
                   y[x, for name in (select distinct name from ranges)] = sign(sum(r)[x <= cv(x), name = cv(name)])
                 ))
         group by x)
match_recognize
(
  order by x
  measures
    first(x) range_start,
    next(x) range_end,
    name name
  pattern (x+)
  define x as first(name) = name
)
order by 1, 2

for loop + upsert all помогает получить все имена для каждого перехода.
Дальше берем max и склеиваем с помощью MR.

for loop однако требует отдельного обращения к таблице. По идее Оракл это мог бы брать из памяти.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
------------------------------------------------------------------------
| Id  | Operation                                             | Name   |
------------------------------------------------------------------------
|   0 | SELECT STATEMENT                                      |        |
|   1 |  SORT ORDER BY                                        |        |
|   2 |   VIEW                                                |        |
|   3 |    MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTOMATON|        |
|   4 |     VIEW                                              |        |
|   5 |      HASH GROUP BY                                    |        |
|   6 |       VIEW                                            |        |
|   7 |        BUFFER SORT                                    |        |
|   8 |         SQL MODEL ORDERED                             |        |
|   9 |          HASH GROUP BY                                |        |
|  10 |           VIEW                                        |        |
|  11 |            UNPIVOT                                    |        |
|  12 |             TABLE ACCESS FULL                         | RANGES |
|  13 |          BUFFER SORT                                  |        |
|  14 |           HASH UNIQUE                                 |        |
|  15 |            TABLE ACCESS FULL                          | RANGES |
------------------------------------------------------------------------

22 rows selected.



Два

Получаем оригинальные и "нарезанные" интервалы.
Моделью возвращаем "нарезанные" с определенными новыми именами (return updated rows).
Последним шагом снова склеиваем через MR.

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
select *
  from (select *
          from (select range_start, range_end, name, 'original' type
                  from ranges
                union all
                select x as range_start, lead(x) over(order by x) as range_end, null, 'derived'
                  from (select distinct x
                          from ranges unpivot(x for r in(range_start, range_end))))
  model
  return updated rows
  dimension by (range_start, range_end, type)
  measures (name)
  rules
  (
    name[range_start, range_end, 'derived'] = max(name)[range_start < cv(range_end), range_end > cv(range_start), type = 'original']
  )
)
match_recognize
(
  order by range_start
  measures
    first(range_start) range_start,
    range_end range_end,
    name name
  pattern (x+)
  define x as first(name) = name
)
order by 1, 2



Если заморочиться можно обойтись одним обращением к таблице + двойной UNPIVOT + MODEL + MATCH RECOGNIZE

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
select *
  from (select *
          from (select name,
                       type,
                       x1 range_start,
                       nvl(x2, lead(x1) over(partition by type order by x1)) range_end
                  from (select distinct name, x x1, x2, type
                          from (select decode(type, 'original', name) name,
                                       range_start,
                                       decode(type, 'derived', range_end) range_end,
                                       decode(type, 'original', range_end) x2,
                                       type
                                  from (select r.*, 1 dummy from ranges r)
                                  unpivot (dummy for type in (dummy as 'original', dummy as 'derived'))
                                )
                          unpivot (x for r in (range_start, range_end))
                        )
                )
          model
          return updated rows
          dimension by (range_start, range_end, type)
          measures (name)
          rules
          (
            name[range_start, range_end, 'derived'] = max(name)[range_start < cv(range_end), range_end > cv(range_start), type = 'original']
          )
       )
match_recognize
(
  order by range_start
  measures
    first(range_start) range_start,
    range_end range_end,
    name name
  pattern (x+)
  define x as first(name) = name
)
order by 1, 2


Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
------------------------------------------------------------------------
| Id  | Operation                                             | Name   |
------------------------------------------------------------------------
|   0 | SELECT STATEMENT                                      |        |
|   1 |  SORT ORDER BY                                        |        |
|   2 |   VIEW                                                |        |
|   3 |    MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTOMATON|        |
|   4 |     VIEW                                              |        |
|   5 |      BUFFER SORT                                      |        |
|   6 |       SQL MODEL ORDERED                               |        |
|   7 |        VIEW                                           |        |
|   8 |         WINDOW SORT                                   |        |
|   9 |          VIEW                                         |        |
|  10 |           HASH UNIQUE                                 |        |
|  11 |            VIEW                                       |        |
|  12 |             UNPIVOT                                   |        |
|  13 |              VIEW                                     |        |
|  14 |               UNPIVOT                                 |        |
|  15 |                TABLE ACCESS FULL                      | RANGES |
------------------------------------------------------------------------


...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020882
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
with ranges (name, range_start, range_end) as
(
          select 'a', 0, 7 from dual
union all select 'b', 2, 4 from dual
union all select 'c', 1, 3 from dual
union all select 'd', 4, 6 from dual
union all select 'e', 3, 5 from dual
),
p (r,c,a,b) as (
          select dense_rank() over (order by name), name, range_start, range_end   from ranges
union all select dense_rank() over (order by name), null, -100500,     range_start from ranges
union all select dense_rank() over (order by name), null, range_end,   +100500     from ranges
),
cte (n, clr, x, y) as (
select max(r)+1, null, -100500, +100500 from p union all
select n-1, c, greatest(x,a), least(y,b)
  from cte e, p 
 where n > 1 and r=n-1 and clr is null and x < y
)
select * from cte where x < y and clr is not null order by x



Вместо 100500 можно +/- бесконечность (быстрее) или min(start)/max(end) (медленнее).
Приоритет вычисляется по значению name, как в оригинальной задаче.
Кобанчег, у тебя в последней строчке 'e',3,6 вместо 'е',3,5 - намеренно или опечатка?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020883
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Сравним скорость, или подождем PL/SQL варианта?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020884
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
Кобанчег, у тебя в последней строчке 'e',3,6 вместо 'е',3,5 - намеренно или опечатка?
Опечатка скорее. Предполагалось исходные данные оставить как есть.
Но "опечатка" была использована ранее для тестирования.
НеофитSQL
Код: plsql
1.
from cte e, p

Я вижу джойн, а ты?
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020885
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
НеофитSQL
Сравним скорость, или подождем PL/SQL варианта?
Если хотя бы отдалённо понимать принцип работы, то абсолютно очевидно что PL/SQL здесь несомненный лидер.
SQL-но и безджойно было "just for fun".

PS. Икстендер публиковал PL/SQL подход.
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020890
Фотография Кобанчег
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну и по приколу линейный проход.
Но это не спортивно ибо xmlquery (которым вообще-то можно реализовать какие-угодно джойны)
+ ограничение на длину конкатенации + предполагается что входные имена не содержат запятых.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
SQL> with ranges (name, range_start, range_end) as
  2  (
  3  select 'a', 0, 7 from dual
  4  union all select 'b', 2, 4 from dual
  5  union all select 'c', 1, 3 from dual
  6  union all select 'd', 4, 5 from dual
  7  union all select 'e', 3, 5 from dual
  8  --
  9  union all select 'x', 3, 3.1 from dual
 10  union all select 'y', 3.5, 3.7 from dual
 11  union all select 'z', 3.9, 5.1 from dual
 12  union all select 'a', 8, 9 from dual
 13  union all select 'a', 8, 9.9 from dual
 14  )
 15  select --+ no_xml_query_rewrite
 16    x, s str, xmlcast(xmlquery('max(tokenize(.,","))' passing(t.s) returning content) as varchar2(4000)) name
 17    from
 18  (
 19    select x, max(s) keep (dense_rank last order by name) s
 20      from
 21    (
 22      select *
 23        from (select x, name, sum(sum(r)) over (partition by name order by x) r
 24                from ranges unpivot(x for r in(range_start as '1', range_end as '-1'))
 25               group by x, name)
 26      model
 27      dimension by(row_number() over (order by x, name) i)
 28      measures(x, name, r, cast('' as varchar2(4000)) s)
 29      rules
 30      (
 31        s[i] = case
 32                 when r[cv()] = 0 then replace(s[cv()-1], name[cv()] || ',')
 33                 else
 34                   case
 35                     when nvl(instr(s[cv()-1], name[cv()] || ','), 0) > 0 then s[cv()-1]
 36                     else s[cv()-1] || name[cv()] || ','
 37                   end
 38               end
 39      )
 40    )
 41    group by x
 42  ) t
 43  order by 1;

         X STR        NAME
---------- ---------- ----------
         0 a,         a
         1 a,c,       c
         2 a,c,b,     c
         3 a,b,e,x,   x
       3.1 a,b,e,     e
       3.5 a,b,e,y,   y
       3.7 a,b,e,     e
       3.9 a,b,e,z,   z
         4 a,e,z,d,   z
         5 a,z,       z
       5.1 a,         a
         7
         8 a,         a
         9 a,         a
       9.9

15 rows selected.

...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40020919
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кобанчег

НеофитSQL
Код: plsql
1.
from cte e, p

Я вижу джойн, а ты?


Я его написал :)

Понадеялся что джойн по константе исполняется эффективно.

Не всякий "from a, b" стоит циклов, бывают бесплатные или дешёвые. Например, "from a,b where b.rowid=x" ничего не должен стоить.

Больше беспокоит многопроходность.
В худшем случае мой алгоритм дает О(n*n) шагов и 3n памяти.

В лучшем, O(n).
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40021505
НеофитSQL
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Сделал пару быстрых проверок на таблице из 10К строк.
Самое простое решение с подчиненным циклом оказалось довольно медленным, несмотря на наличие индексов:

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
-- без агрегации групп, формат вывода как у xtender
SQL> select x, (select max(color) from test_ranges where range_start <= x and range_end > x) from
  2  (select range_start x from test_ranges union select range_end from test_ranges) order by x;

20000 rows selected.

Elapsed: 00:02:59.52

Execution Plan
----------------------------------------------------------

| Id  | Operation                         | Name             | Rows  | Bytes |TempSpc| Cost (%CPU)|

---------------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT                  |                  |  1999K|    24M|     | 28455   (2)|
|   1 |  SORT AGGREGATE                   |                  |     1 |    49 |     |            |
|   2 |   TABLE ACCESS BY INDEX ROWID     | TEST_RANGES      |  2500 |   119K|     |   981   (1)|
|   3 |    BITMAP CONVERSION TO ROWIDS    |                  |       |       |     |            |
|   4 |     BITMAP AND                    |                  |       |       |     |            |
|   5 |      BITMAP CONVERSION FROM ROWIDS|                  |       |       |     |            |
|   6 |       SORT ORDER BY               |                  |       |       | 800K|            |
|   7 |        INDEX RANGE SCAN           | TEST_RANGES_IDX1 |       |       |     |    43   (0)|
|   8 |      BITMAP CONVERSION FROM ROWIDS|                  |       |       |     |            |
|   9 |       SORT ORDER BY               |                  |       |       | 800K|            |
|  10 |        INDEX RANGE SCAN           | TEST_RANGES_IDX2 |       |       |     |    44   (0)|
|  11 |  SORT ORDER BY                    |                  |  1999K|    24M|  38M| 28455   (2)|
|  12 |   VIEW                            |                  |  1999K|    24M|     | 18871   (1)|
|  13 |    SORT UNIQUE                    |                  |  1999K|    41M|  53M| 18871  (51)|
|  14 |     UNION-ALL                     |                  |       |       |     |            |
|  15 |      TABLE ACCESS FULL            | TEST_RANGES      |   999K|    20M|     |  2753   (1)|
|  16 |      TABLE ACCESS FULL            | TEST_RANGES      |   999K|    20M|     |  2754   (1)|

Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
   45481209  consistent gets
          0  physical reads
          0  redo size
     653151  bytes sent via SQL*Net to client
      15023  bytes received via SQL*Net from client
       1335  SQL*Net roundtrips to/from client
      40002  sorts (memory)
          0  sorts (disk)
      20000  rows processed



Рекурсивное решение:
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
SQL> with p (r,c,a,b) as (
  2            select color, color, range_start, range_end from test_ranges
  3  union all select color, null, null, range_start       from test_ranges
  4  union all select color, null, range_end, null         from test_ranges
  5  ),
  6  cte (n, clr, x, y) as (
  7  select max(color)+1, null, min(range_start), max(range_end) from test_ranges union all
  8  select n-1, c, nvl2(a,greatest(x,a),x), nvl2(b,least(y,b),y)
  9    from cte e, p
 10   where n > 1 and r=n-1 and clr is null and x < y
 11  )
 12  select * from cte where x < y and clr is not null order by x;

31 rows selected.

Elapsed: 00:00:46.25

Execution Plan
----------------------------------------------------------

| Id  | Operation                                  | Name        | Rows  | Bytes | Cost (%CPU)|

-----------------------------------------------------------------------------------------------

|   0 | SELECT STATEMENT                           |             |     4 |   208 | 13793   (1)|
|   1 |  SORT ORDER BY                             |             |     4 |   208 | 13793   (1)|
|   2 |   VIEW                                     |             |     4 |   208 | 13792   (1)|
|   3 |    UNION ALL (RECURSIVE WITH) BREADTH FIRST|             |       | |            |
|   4 |     SORT AGGREGATE                         |             |     1 |    49 |            |
|   5 |      TABLE ACCESS FULL                     | TEST_RANGES |   999K|    46M|  2754   (1)|
|   6 |     HASH JOIN                              |             |     3 |   312 | 11038   (1)|
|   7 |      RECURSIVE WITH PUMP                   |             |       | |            |
|   8 |      VIEW                                  |             |  2999K|   148M|  8262   (1)|
|   9 |       UNION-ALL                            |             |       | |            |
|  10 |        TABLE ACCESS FULL                   | TEST_RANGES |   999K|    46M|  2754   (1)|
|  11 |        TABLE ACCESS FULL                   | TEST_RANGES |   999K|    25M|  2753   (1)|
|  12 |        TABLE ACCESS FULL                   | TEST_RANGES |   999K|    25M|  2754   (1)|

--------------------------------------------------------------------------------
Statistics
----------------------------------------------------------
          2  recursive calls
      60582  db block gets
    2389761  consistent gets
          0  physical reads
          0  redo size
       2341  bytes sent via SQL*Net to client
        382  bytes received via SQL*Net from client
          4  SQL*Net roundtrips to/from client
       8049  sorts (memory)
          0  sorts (disk)
         31  rows processed



Как заполнялась тест таблица:

Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
SQL> insert into test_ranges select level, dbms_random.value(0,10), null from dual connect by level <= 10000;
10000 rows inserted
Executed in 0,156 seconds

SQL> update test_ranges set range_end=dbms_random.value(range_start,10);
10000 rows updated
Executed in 0,578 seconds

SQL> alter index test_ranges_idx1 rebuild online;

Index altered.

Elapsed: 00:00:00.09
SQL> alter index test_ranges_idx2 rebuild online;

Index altered.

Elapsed: 00:00:00.11
...
Рейтинг: 0 / 0
Пятничная задача: Красное и черное
    #40021588
Вячеслав Любомудров
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Можно попробовать запретить использование планов с виртуальным преобразованием в виртуальные битовые индексы и обратно (это крайне было полезно в 9-ке, но, возможно, не утратило актуальности и в новых версиях)
alter session set "_b_tree_bitmap_plans"=false
...
Рейтинг: 0 / 0
176 сообщений из 176, показаны все 8 страниц
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Пятничная задача: Красное и черное
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]