Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6 7 8   вперед  Ctrl      все
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
andrey_anonymous
Что-то я не видел.
Первым линейный перебор опубликовал господин graycode и без всяких SMJ.

22233043
18 ноя 20, 00:57    [22234286]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Это на PL/SQL.

Я про это: 22232233

Контекст:
,>линейным перебором можно обойтись только в PL/SQL

Сообщение было отредактировано: 18 ноя 20, 02:25
18 ноя 20, 02:25    [22234305]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
xtender
Member

Откуда: Мск
Сообщений: 5704
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set
18 ноя 20, 03:06    [22234308]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
xtender,


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

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

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

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

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

Это монохромная версия. Можно добавить цвета..
18 ноя 20, 03:42    [22234310]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

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


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
18 ноя 20, 04:03    [22234312]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
Почитал решения по ссылке, народ явно легких путей не ищет.

"Simplicate, and add lightness" (c)
18 ноя 20, 04:07    [22234313]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
НеофитSQL

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

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

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

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


-- порядок не задан, краска одинаковая
-- 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:


1 2 3 4 5 6 7 8
2 $ $ $ $ $ $ $
3 $ $ $ $ $ $ $ $
4 $ $ $ $ $ $ $ $
5 $ $ $ $ $ $ $ $
6 $ $
7 $
8 $

+
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 
18 ноя 20, 04:56    [22234319]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
НеофитSQL
А задачи про двухмерные заплатки никто не публиковал?

Приходилось как-то на проекте внедрения внезапно под вечер решать задачку вида "сделать из списка (с историей изменения) префиксов телефонных зон двумерную карту для быстрого определения корректной зоны вызова по параметрам (вызываемый номер, дата соединения)".
Не rocket science, хотя пару-тройку часов из жизни выкинул.
18 ноя 20, 13:10    [22234540]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
Почитал решения по ссылке, народ явно легких путей не ищет.

"Simplicate, and add lightness" (c)

А ты подставь данные из ссылки и сравни результат, ты решал какую то другую задачу.
18 ноя 20, 13:18    [22234547]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
НеофитSQL
Жаль, критерий трудно определить объективно.

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


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

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
18 ноя 20, 15:09    [22234654]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег
Собственно мой вариант таков.
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 не позволяет заглядывать в предыдущие группы.



with t (x1, x2, c, flag) as
(
              select 20, 30, 'red', 'src' from dual
union all select 20, 30, 'red', 'tgt' from dual
)



X1 X2 RESULT
20 30 red
31 30 -
Download CSV
2 rows selected.

.....
stax
18 ноя 20, 15:30    [22234670]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Stax
должно быть две строки?

Да.
18 ноя 20, 15:31    [22234671]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Stax
.....

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

PS: для проверки используйте PL/SQL вариант 22233043 ))
18 ноя 20, 15:35    [22234675]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax
должно быть две строки?
Да. Ну ты мастер тестирования!
Можешь использовать мой запрос, там верно возвращает.

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


Fix
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;
18 ноя 20, 15:38    [22234679]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
graycode,

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

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

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

.....
stax
18 ноя 20, 15:40    [22234681]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег
странно что это не всплыло в моём чудо тесте

Тестовые данные не покрывают много кейсов, а генератор на производительность вообще вырожденный и возможно это одна из причин удивительных результатов теста на производительность[/quot]
18 ноя 20, 15:43    [22234683]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

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

Здесь тот же вариант, только в исполнении в виде пакета 22233388
18 ноя 20, 15:46    [22234687]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode
возможно это одна из причин
Наша песня хороша начинай сначала.
Я вчера уже поверил в твою адекватность когда ты признал что PL/SQL и SQL приверно одного уровня по производителности.
18 ноя 20, 15:49    [22234695]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
Кобанчег

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



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

поспешил
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 с ошибкой

зы

Сообщение было отредактировано: 18 ноя 20, 15:58
18 ноя 20, 15:57    [22234704]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

Причина мне не совсем понятна, я убрал фактор сортировки, т.е. сортировок нет, просто прогоняется набор исходных данных через функцию, в функции только дерево условий, по идее должно быть быстрее, оно и быстрее но совсем незначительно, можешь объяснить причину?
18 ноя 20, 15:57    [22234705]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode
Причина мне не совсем понятна, я убрал фактор сортировки, т.е. сортировок нет
open c_refcur_t for select * from t order by x1;
?
18 ноя 20, 16:00    [22234707]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Кобанчег,

IOT, pk по всем полям начиная с x1))
18 ноя 20, 16:02    [22234709]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
graycode,

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

Может что-то еще можно выжать из твоего подхода, но практической ценности для меня не несет.
18 ноя 20, 16:07    [22234713]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
Stax
для unpivot + pivot + lead сдаюсь

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

В моём сортировку в аналитике надо сделать идентичной с MR.
over(order by x1/*, type*/)
18 ноя 20, 16:19    [22234722]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 2798
graycode
Stax,

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


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
18 ноя 20, 16:22    [22234724]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6 7 8   вперед  Ctrl      все
Все форумы / Oracle Ответить