ReSQL.ru
     
powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Пятничная задача: Красное и черное
25 сообщений из 176, страница 4 из 8
  4  все
Пятничная задача: Красное и черное
    #40019455
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
graycode
Гость
НеофитSQL,

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

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

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


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

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


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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

Sort Merge Join :)

понял, это ты к тому, для join тоже можно гарантию nLog(n) обеспечить...
Ок.
...
Рейтинг: 0 / 0
17.11.2020, 17:32
| Ответить | Цитировать | Написать  
Пятничная задача: Красное и черное
    #40019593
graycode
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
17.11.2020, 17:42
| Ответить | Цитировать | Написать  
Пятничная задача: Красное и черное
    #40019597
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
andrey_anonymous
Участник
booby
понял, это ты к тому, для join тоже можно гарантию nLog(n) обеспечить...
Ок.

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

....

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

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

Задача аннулирования самопересечений достаточно тривиальна и не очень интересна в контексте.
...
Рейтинг: 0 / 0
17.11.2020, 17:52
| Ответить | Цитировать | Написать  
Пятничная задача: Красное и черное
    #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
17.11.2020, 18:58
| Ответить | Цитировать | Написать  
Пятничная задача: Красное и черное
    #40019635
Фотография Stax
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Stax
Участник
Кобанчег

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


для

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

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

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

Да.

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

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

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

Ага


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

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

Что-то я не видел.
...
Рейтинг: 0 / 0
18.11.2020, 00:33
| Ответить | Цитировать | Написать  
25 сообщений из 176, страница 4 из 8
  4  все
Форумы / Oracle [игнор отключен] [закрыт для гостей] / Пятничная задача: Красное и черное
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=52&msg=40019455&tid=1880676]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 147ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 59ms
get tp. blocked users:
 1ms
others: 12ms
total:  256ms
созд. / загр.: 256ms
x
x
Закрыть


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