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

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

Оценить размер результата сложно, там помимо пропусков может быть увеличение, например идет интервал tgt, а в его середине интервал src, на входе два интервала, на выходе три, если два интервала src в середине tgt, то исходных три интервала, а на выходе 5.
17 ноя 20, 14:33    [22233782]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
graycode
мы читаем по строке, формируем новую в PL/SQL и отдаем обратно в SQL

Ну и откуда вывод, что выдача происходит по одной строке?
Из statement PIPE ROW?
Ну-ну.
Что до чтения - тут вообще странно Вас читать.
Ничто не мешает ни явному bulk collect, ни неявному (оптимизация курсорного цикла на PLSQL Optimizer Level 2).
17 ноя 20, 14:39    [22233789]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

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

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


Pl/SQL компилированный, я надеюсь?
17 ноя 20, 14:58    [22233819]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

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

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


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

Удвоение не так уж плохо. Тогда можно аллокировать массив двойной длины, собрать отсортированные по x1 данные в его вторую половину, оставляя первую пустой и не затирая непрочитанных данных обработать в том же пространстве.
17 ноя 20, 15:03    [22233830]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
НеофитSQL
Pl/SQL компилированный, я надеюсь?

Нет, так что еще есть пространство для оптимизации))
17 ноя 20, 15:38    [22233880]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

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

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

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

PL/SQL: сортировка(исходные данные) -> черный ящик (PL/SQL вычисления) -> Сумма(результирующий набор из черного ящика построчно или пакетом/пакетами)
17 ноя 20, 15:45    [22233891]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
booby
Member

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

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

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

SQL, может быть, в виде pattern matching к этому подберется, если повезет с алгоритмами в его нутрях.
Join надо будет попотеть заставлять оставаться в рамках роста nLog(n) на больших бъемах.
17 ноя 20, 15:58    [22233903]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

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

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


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

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

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

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

В цикле по отсортированной входной выборке только дерево условных операторов, т.е. ~(n), откуда логарифм?
17 ноя 20, 16:14    [22233919]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
booby
Member

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

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

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


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

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

Т.е. слишком много ифов зашито в первичную сортировку.
А так по виду - классическая задача на заметание, в любом случае, решаемая за ~nLog(n)

Сообщение было отредактировано: 17 ноя 20, 16:37
17 ноя 20, 16:42    [22233949]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
booby
А так по виду - классическая задача на заметание, в любом случае, решаемая за ~nLog(n)

На базе SMJ вполне делается за две сортировки плюс линейный перебор.
17 ноя 20, 17:03    [22233968]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
booby
Member

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

что такое SMJ?
17 ноя 20, 17:11    [22233976]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
booby
andrey_anonymous,
что такое SMJ?

Sort Merge Join :)
17 ноя 20, 17:22    [22233991]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
booby
Member

Откуда:
Сообщений: 2257
andrey_anonymous
booby
andrey_anonymous,
что такое SMJ?

Sort Merge Join :)

понял, это ты к тому, для join тоже можно гарантию nLog(n) обеспечить...
Ок.
17 ноя 20, 17:32    [22234000]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

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

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

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

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

Автор задачи дал немного странные названия, src не режется, он приоритетный, т.е. src режет, но не наоборот, блоки одного типа не могут пересекаться.
17 ноя 20, 17:42    [22234011]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
booby
понял, это ты к тому, для join тоже можно гарантию nLog(n) обеспечить...
Ок.

Это я к тому, что при наличии предварительно отсортированных наборов сам SMJ линеен и, вообще говоря, подходит под решение задачи.
Наличие пресортированных наборов можно обеспечить индексным доступом и тем самым решить за линейное время.
17 ноя 20, 17:45    [22234016]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
booby
Member

Откуда:
Сообщений: 2257
graycode
... пересечений src-src и tgt-tgt быть не может.

....

с чего бы это?
чтобы задачу упростить?
17 ноя 20, 17:50    [22234022]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
booby

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

Задача аннулирования самопересечений достаточно тривиальна и не очень интересна в контексте.
17 ноя 20, 17:52    [22234026]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

Откуда: Рахів
Сообщений: 841
andrey_anonymous
На базе SMJ вполне делается за две сортировки плюс линейный перебор.
Казалось бы, зачем джойн когда можно без оного и эффективнее.
Более того, если делать через джойн, то линейным перебором можно обойтись только в PL/SQL, SQL-но придется использовать еще один джойн (или pivot).
Я ж так понимаю речь про такое ядро
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
?
Ну так это уступает тому, что уже было показано.
У меня то есть финальный вариант но я не видел смысла его выкладывать в виду неконкуретноспособности.
17 ноя 20, 18:58    [22234084]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Stax
Member

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

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


для

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

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

.....
stax
17 ноя 20, 19:11    [22234095]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
Кобанчег
Member

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

Да.

PS. Если что можно же ответ сверять с имеющимися вариантами.
17 ноя 20, 19:13    [22234096]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
graycode
Member

Откуда:
Сообщений: 468
Хм, сделал таблицу IOT с pk по всем полям, теперь pl/sql стабильно чуть быстрее, но именно чуть чуть, т.е. все равно все три варианта равноценны в практическом плане и вариант неофита лучше варианта pattern matching.

PS: pl/sql native и Optimizer Level 2
17 ноя 20, 19:14    [22234098]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
Кобанчег
линейным перебором можно обойтись только в PL/SQL

Ага
17 ноя 20, 22:24    [22234225]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
НеофитSQL
Member

Откуда: Маями
Сообщений: 760
andrey_anonymous
Кобанчег
линейным перебором можно обойтись только в PL/SQL

Ага


Да ну, я же публиковал линейный перебор в самом начале на SQL.
17 ноя 20, 23:07    [22234246]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задача: Красное и черное  [new]
andrey_anonymous
Member

Откуда: Москва
Сообщений: 18398
НеофитSQL
andrey_anonymous
пропущено...
Ага

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

Что-то я не видел.
18 ноя 20, 00:33    [22234273]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 [4] 5 6 7 8   вперед  Ctrl      все
Все форумы / Oracle Ответить