|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Это очередная вариация на тему интервалов. Мне подобное на форуме не попадалось, но сорри если баян. Есть интервалы двух цветов и требуется получить результирующую разбивку как показано ниже. Код: 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.
Входные интервалы каждого отдельного цвета не пересекаются и не соприкасаются. Картинка вероятно нагляднее покажет как получен результат. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 14:42 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, Верхняя и нижняя граница всегда определены имеющимися интервалами? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 15:09 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
env, Не совсем понял вопрос. На выходе должен быть диапазон от начала первого до конца последнего. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 15:21 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, Напрашивается решение через непрерывный список от 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 15:51 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, red =1 black=2 суммируем с перекрытием 3-overlap 0-прозрачный ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 15:56 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
model + overlap ? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 15:58 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег если баян ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 16:00 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кстати, насколько помню была какая-то не[полностью]документированная функция типа именно overlap для работы с датами и числами Или только датами/диапазонами(?) ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 16:01 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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 ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 16:08 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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.
Интервалы могут быть произвольной длины и не обязательно с целыми границами. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 16:19 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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 ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 16:23 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Elic Кобанчег если баян Но некоторая баянистость просматривается, да. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 16:25 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Вячеслав Любомудров model + overlap ? Вячеслав Любомудров Кстати, насколько помню была какая-то не[полностью]документированная функция типа именно overlap для работы с датами и числами Или только датами/диапазонами(?) Но недокументированное это неспортивно (и для данной задачи нет надобности). ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 16:29 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег Наиболее эффективно без джойнов. Но некоторая баянистость просматривается, да. unpivot можно? для union all select 7, 10, 'red' from dual union all select 10, 14, 'black' from dual 10 10 overlap? ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 16:36 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax unpivot можно? Stax 10 10 overlap? PS. На самом деле мне стоило состряпать более адекватный пример с real numbers (тогда бы 10 10 было касание а не перекрытие на единицу) но уже есть как есть. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 16:43 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег завязано на натуральные числа ... |
|||
:
Нравится:
Не нравится:
|
|||
13.11.2020, 16:47 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, была идейка red full outer join black on пересекаются но плюнул перебирать случаи пересечений ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
14.11.2020, 12:11 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax Кобанчег, red =1 black=2 суммируем с перекрытием 3-overlap 0-прозрачный ..... stax Суммировать хорошая идея, правда как без трансформации запроса это делать я не знаю. Вижу примерно следующий алгоритм, x1 и x2 в один столбец, каждый признак (red, black) отдельным столбцом, для начала периода (x1) признаку +1, там где кончается период (x2) признаку -1, если накопительная сумма с учетом периода больше нуля значит признак в периоде (в вертикальном виде, период это две ближайшие строки) включен, если нет значит выключен, потом преобразовать обратно в периоды. PS: реализовывать лень))) ... |
|||
:
Нравится:
Не нравится:
|
|||
14.11.2020, 12:41 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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.
touch используется для фильтра когда конец одного соприкасается с началом другого, а same_bound для исключения из результата первой из точек когда начала либо концы совпадают. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.11.2020, 15:38 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
В общем эта была разминка, теперь предлагается задачка посложнее. Необходимо наложить интервалы из источника на приемник с приоритетом из источника (если есть пересечение). Код: 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.
Здесь не удастся выкрутиться с decode + sum ибо цветов потенциально неограниченное множество. И снова картинка для наглядности. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.11.2020, 16:06 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode PS: реализовывать лень))) https://www.sql.ru/forum/1297132/razdelit-na-neperesekaushhiesya-intervaly-dat-otrezki-s-ssumirovaniem-summy-v-peresecheniyah ета задачка даж проще, токо одно пересечение ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
14.11.2020, 16:17 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
del ... |
|||
:
Нравится:
Не нравится:
|
|||
14.11.2020, 19:53 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег В общем мое решение выглядит так Это называется без тяжелой артиллерии? Я думал без тяжелой артиллерии выглядит примерно так: Код: 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 00:53 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Одно из решений. Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 01:01 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег Здесь не удастся выкрутиться с 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 01:04 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode Это называется без тяжелой артиллерии? Если продолжить разговор про перфоманс далее, то даже однослойная аналитика уступает в производительности match_recognize а у тебя два WINDOW SORT. В плане других замечаний - не лучшая мысль сканировать исходную таблицу дважды. Код: plsql 1. 2. 3.
cross join будет быстрее, а unpivot еще быстрее. Код: plsql 1.
Нет особого смысла указывать то, что и так по умолчанию. В остальном, в решении всё разложено по полочкам, вполне прилично. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 01:39 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Одно из решений. Сгенерировать диапазон от начала первого до конца последнего можно было (но генерировать вообще не стоит) и с помощью connect by + nvl по двум скалярам. В недокументированных функциях тоже никакого смысла нет. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 02:00 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег НеофитSQL Одно из решений. Сгенерировать диапазон от начала первого до конца последнего можно было (но генерировать вообще не стоит) и с помощью connect by + nvl по двум скалярам. В недокументированных функциях тоже никакого смысла нет. Вы перечислили несколько недостатков моего решения, там наверное еще десяток можно насчитать :) Я не знаю как применить connect by в этом контексте, и использовал корявое формирование диапазонов надеясь, что кто-то знает как это делать правильно и эффективно. Вы можете мне показать, как из этого: Код: plsql 1. 2. 3. 4. 5. 6. 7.
Сделать такое: 1 2 red 3 3 blue 4 4 red ? Числа последовательные, без дырок. Граничные условия не важны интересен принцип ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 02:18 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode не так изящно конечно и наверное можно упростить, но выкрутиться можно Если я ничего не упустил в Код: plsql 1.
смысла нет, там можно просто min. У меня с аналитикой что-то аналогичное. По сути итоговый цвет получается с помощью Код: plsql 1.
остальное - вариация на тему 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.
Но еще была попытка изящно решить с помощью pattern matching. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 02:58 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL, Если воспользоваться генератором из запроса env то можно дописать как-то так (но здесь не нужен генератор и коррелированные скаляры тоже не нужны) Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9.
... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 03:04 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Я пропустил упражнение-разминку, ответы еще принимаются? Код: plsql 1. 2. 3. 4. 5. 6. 7.
... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 04:18 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег НеофитSQL, Если воспользоваться генератором из запроса env то можно дописать как-то так (но здесь не нужен генератор и коррелированные скаляры тоже не нужны) Спасибо, напомнили про connect-by для генерации чисел, я редко его вижу. Я спросил про connect-by, думая про задачу схлопывания интервалов. Вы это назвали "beginning of group". Есть ли оконное выражение, которое позволяет обрабатывать повторяющуеся группы, как partition by позволяет обрабатывать уникальные группы? Например, в следующем отсортитованном резалтсете есть три группы (апельсины:2, яблоки:2 и апельсины:1) апельсин 2 апельсин 3 яблоко 1 яблоко 1 апельсин 1 Как в таком случае эти группы извлечь? Есть специальный оператор, или придется ловить начало группы, подглядывая соседние строчки? ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 04:37 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег Тяжесть модели в ее прожорливости к CPU & RAM. Cоответсвенно пользоваться ею когда она тривиально заменяется аналитикой/pattern matching это не самая лучшая идея. Если продолжить разговор про перфоманс далее, то даже однослойная аналитика уступает в производительности match_recognize а у тебя два WINDOW SORT. Видимо я неправильно понял задачу, я исходил из посыла что все кроме трансформации исходного запроса и аналитики запрещено. Если подходить с точки зрения производительности, то все вышеперечисленное проигрывает решению на PL/SQL, в котором даже unpivot не нужен. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 11:40 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode Если подходить с точки зрения производительности, Монохромность изначальной постановки понизила градус полезности. Как автор признал, задача-баян. Необходимость решать её не сопровождаемыми способами немотивирована. Если в задаче подразумевались -лярды данных, то об этом не было заявлено. В свете всего этого лучшее решение - сопровождаемое. Т.е. уровень вхождения в который меньше/проще. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 12:02 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Я пропустил упражнение-разминку, ответы еще принимаются? Только полезно читать другие ответы перед публикацией своего. Возможно придёт понимание что в коррелированном скаляре нет смысла абсолютно никакого. НеофитSQL Вы это назвали "beginning of group". Есть ли оконное выражение, которое позволяет обрабатывать повторяющуеся группы, как partition by позволяет обрабатывать уникальные группы? Ты пробовал запустить 22232251 ? ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 13:35 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode Видимо я неправильно понял задачу, я исходил из посыла что все кроме трансформации исходного запроса и аналитики запрещено. 1) модель не самое подходящее средство 2) решается без подзапросов и соединений Казалось бы причем здесь вообще трансформации. Даже при наличии подзапросов они могут быть а могут и не быть. graycode Если подходить с точки зрения производительности, то все вышеперечисленное проигрывает решению на PL/SQL, в котором даже unpivot не нужен. Я даже потружусь нагенерить данных чтоб показать несостоятельность этого заявления. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 13:43 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Elic Как автор признал, задача-баян. Elic Необходимость решать её не сопровождаемыми способами немотивирована. Если в задаче подразумевались -лярды данных, то об этом не было заявлено. В свете всего этого лучшее решение - сопровождаемое. Т.е. уровень вхождения в который меньше/проще. На pattern matching, впрочем, свет тоже клином не сошелся. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 13:51 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег Если тебе по стариковски, понять многослойную аналитику проще чем pattern matching это не значит что стоит переносить сие восприятие на остальных. Кобанчег На pattern matching, впрочем, свет тоже клином не сошелся. Сопровождабельно решается джойном. Огласи систему ценностей. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 14:19 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Elic Выводы из-за отсутствия информации - всегда ложные. Ты не поверишь, но я даже бегло читал читал эту книгу. А что предлагается из нее почерпнуть? Elic Огласи систему ценностей. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 14:38 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Elic Если честно, то я не совсем понял в чём вызов. Для меня вызов был решить однопроходно в SQL, но еще до создания темы я пришел к тому что это невозможно. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 14:46 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Собственно мой вариант таков. Код: 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.
MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTOMATON + WINDOW SORT + UNPIVOT При попытке решить однопроходно с match recognize упираешься в то, что "активный" цвет для текущей группы определяется по всему набору а match recognize не позволяет заглядывать в предыдущие группы. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 15:28 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Под однопрохоность в контексте задачи понимается одно сканирование таблицы (это неизбежно) + одна операция SORT сверху (это тоже неизбежно ибо порядок все определяет). В моем решении как видно две сортировки. В решении graycode WINDOW SORT * 5 + WINDOW BUFFER + HASH GROUP BY + 2 сканирования таблицы ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 15:34 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег что предлагается из нее почерпнуть? technical reviewer :) Кобанчег Вызова нет, тема была создана чтоб другие поразмялись... и вдруг какая новая идея всплывёт. Для меня вызов был решить однопроходно в SQL, Подтверждаешь ухудшение пятничности? Я, как старпёр, дотошен :\ ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 15:35 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Elic, Про однопроходность написано сообщением выше, критерии тоже озвучены. Мы не code golf тут занимаемся. ;) ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 16:04 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Жаль, критерий трудно определить объективно. У меня получилось так. Обилие вложенных селектов и оконных функций кажется неэффективным, но зато нет подчиненных селектов, которые считаются злом. Теперь пойду смотреть как другие решили. Интересно, какого размера нужен дата сет, чтобы померять сравнительную производительность разных подходов? Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22.
... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 22:12 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Заодно хочу сказать большое спасибо участникам форума за вклад в развитие новичков, включая меня. Я еще месяц назад такой код со словарем не смог бы прочитать. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.11.2020, 22:13 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег graycode Если подходить с точки зрения производительности, то все вышеперечисленное проигрывает решению на PL/SQL, в котором даже unpivot не нужен. Я даже потружусь нагенерить данных чтоб показать несостоятельность этого заявления. Я такого же мнения, что и graycode. Мне было бы интересно устроить гонки опубликованных подходов против компилированного Pl/SQL. Там все решится в один цикл без аналитических функций, повторных сортировок или временных таблиц в памяти. PL/SQL процедуру я напишу, если будут данные. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 02:41 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег В общем эта была разминка, теперь предлагается задачка посложнее. Необходимо наложить интервалы из источника на приемник с приоритетом из источника (если есть пересечение). я так понимаю доминантный ето 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 ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 10:40 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег И ты сможешь его продемонстрировать? Я даже потружусь нагенерить данных чтоб показать несостоятельность этого заявления. Вроде нигде с условиями не накосячил)) Код: 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 16:00 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Интересно, какого размера нужен дата сет, чтобы померять сравнительную производительность разных подходов? По хорошему нужна реальная асимптота, поэтому разного размера и самый главный момент, это то что в сложных системах, в которых параллельно работает много автоматических процессов, чистый эксперимент на производительность провести невозможно. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 16:14 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode НеофитSQL Интересно, какого размера нужен дата сет, чтобы померять сравнительную производительность разных подходов? По хорошему нужна реальная асимптота, поэтому разного размера и самый главный момент, это то что в сложных системах, в которых параллельно работает много автоматических процессов, чистый эксперимент на производительность провести невозможно. "Невозможно сравнить скорость" это не не ответ для того, кто сказал что сделает быстрее :) Если разница в разы в десятке замеров в разных ситуациях. я думаю понятно какое из решений быстрее. А если разница проценты, то наверное одинаково. П.С. Удивился длине процедуры, я почему-то думал что решение циклом будет намного короче. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 19:09 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL "Невозможно сравнить скорость" это не не ответ для того, кто сказал что сделает быстрее :) Если разница в разы в десятке замеров в разных ситуациях. я думаю понятно какое из решений быстрее. Я к тому, что полученные циферки времени выполнения нужно рассматривать критически. НеофитSQL П.С. Удивился длине процедуры, я почему-то думал что решение циклом будет намного короче. Перебрал варианты в лоб, можешь поискать закономерности и свернуть алгоритм в более короткий вид, главное чтобы в нем разобраться можно было)) ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 19:46 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Обилие вложенных селектов и оконных функций кажется неэффективным Группировка пивотом позволила обойтись одной и той же сортировкой в аналитике на всех уровнях (order by x) , в результате чего у тебя только один WINDOW SORT и два WINDOW BUFFER. Мелкий баг - decode(s,'-',t,s) может быть null если диапазоны начинаются с target. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 19:58 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax цветов много, поетому пересечений может быть больше двух ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 19:59 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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.
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.
Код: 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.
То есть у неофита та же производительность что у моего финального. У pl/sql та же производительность что у моего с аналитикой. Твой с аналитикой самый медленный - ну там слишком дофига сортировок. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 20:22 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Там еще в начале теста можно было вставить Код: plsql 1. 2. 3. 4. 5. 6. 7.
Чтоб показать что на ввод-вывод ресурсы не тратятся. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 20:25 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, Как раз то о чем я говорил, подобные результаты нужно оценивать критически, эксперимент поставлен весьма криво, собственно и доверять этим результатам не стоит. PS: pl/sql вариант конечно нужно переписать без объектной обертки, не знаю сколько она отъедает. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 21:15 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
o! o! я тоже хочу PL/SQL сделать! Спасибо за тесты, очень образовательно. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 21:41 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode, Поставь ровнее, я ж только за. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 21:43 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, Ты сам взялся за тесты производительности)) Проводить тесты нужно независимо, т.е. не друг за другом, состояние системы перед каждым тестом нужно приводить в исходное состояние и очень желательно нивелировать влияние физических чтений исходной таблицы с диска, кроме того то что ты продемонстрировал вообще одного порядка, т.е. реально оно все выполнилось за одинаковое время, нужно было довести время выполнения хотя бы до трех минут (как известно чем больше N тем сильнее расходятся асимптоты). И ой, прошу прощения, не все вычистил, там кое что совсем лишнее, flag в сортировке не нужен для работы функции)) Код: plsql 1. 2. 3. 4.
... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 21:51 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode, В тесте важно избежать физических чтений таблицы и ухода в темп на сортировках. Можно было еще чуть минимизировать расходы на получения хеша. Всё остальное - лирика. В реальных данных все намного сложнее и это была лишь примитивная симуляция. Не та эта задача где PL/SQL блещет как ты ни крути. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 22:01 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, Еще раз, ты своим экспериментом продемонстрировал ... ничего, т.е. получил одинаковое время (одного порядка) и даже мой самый медленный и корявый вариант по твоему эксперименту не отличается от остальных)) Хочешь реально оценить, поставь эксперимент грамотно. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 22:05 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode, А кто-то говорил про отличия на порядки? Если хочешь увидеть на порядки - потести варианты с коррелированными подзапросами. Ты волен делать какие угодно выводы на основании таймингов или показать свой тест, но подобная демагогия это слив. Можешь еще увеличивать число до 3e6, 5e6 и так далее пока не начнет вылезать в темп. И строить асимптоты. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 22:28 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode, Пример когда PL/SQL рулит - 11567017 . Но там альтернатива была только модель. С графиками. Думаю тебе должно понравиться. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 22:40 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, Слив, это методика эксперимента)) Вот с графиками красиво и ... 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 23:14 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode Переписал в виде пакета Пакет бы пригодился когда понадобилось бы параллелить функцию и объявлять strong ref cursor. ;) graycode без объектной обертки должно быть быстрее Теперь на уровне ведущих эскуэльных подходов. Мир, равенство, братсво. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 23:35 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, Я твой тест из другого топика скоммуниздил и переделал под нашу задачу и что то не получаются твои результаты, ты бы позапускал и не один раз и на разном количестве записей ... Код: 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
16.11.2020, 23:47 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, У тебя в том топике еще и bulk collect ... НеофитSQL я тоже хочу PL/SQL сделать! Сделай не пайплайнед, а как у Кобанчег , в топике на который он ссылку дал. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 00:08 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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.
Долго ломал голову как сделать условный pipe row (чтобы пустые строчки не плевало), но так и не смог. Поэтому в правой части много повторяющегося кода. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 02:08 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Без пайплайна возможно быстрее. Надеюсь Кобанчег или другие бенчмаркнут. Код: 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 02:25 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Без пайплайна возможно быстрее. Надеюсь Кобанчег или другие бенчмаркнут. С пайплайном мы по одной строчке перегоняем входящий отсортированный набор данных в выходной набор данных по которому потом еще идет суммирование, если весь входной набор отправить в коллекцию bulk collect-ом, обработать эту коллекцию не создавая новую и отдать ее в качестве результата, должно получиться быстрее. PS: в реальных задачах нужно учитывать что коллекция будет содержать все данные таблицы и находиться она будет в UGA. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 12:47 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode пайплайном мы по одной строчке перегоняем входящий отсортированный набор данных в выходной набор данных Точно? :) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 13:03 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
andrey_anonymous Точно? :) Мы точно не ползаем по исходному набору и не модифицируем его, мы читаем по строке, формируем новую в PL/SQL и отдаем обратно в SQL, где поверх еще идет суммирование, в SQL решениях одно исполняющее ядро SQL и возможность по максимуму использовать исходный набор данных не перекачивая его через сторонние структуры построчно. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 14:17 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode НеофитSQL Без пайплайна возможно быстрее. Надеюсь Кобанчег или другие бенчмаркнут. С пайплайном мы по одной строчке перегоняем входящий отсортированный набор данных в выходной набор данных по которому потом еще идет суммирование, если весь входной набор отправить в коллекцию bulk collect-ом, обработать эту коллекцию не создавая новую и отдать ее в качестве результата, должно получиться быстрее. PS: в реальных задачах нужно учитывать что коллекция будет содержать все данные таблицы и находиться она будет в UGA. Если набор данных ужЕ в памяти, быстрее вызвать внешнюю функцию на сях :) по поводу обработки коллекции in-place, там довольно неочевидная (для меня) оценка размера результата. Вроде бы худший случай это 2N если нужно выводить незакрашенные интервалы, и 2N-1 если их можно пропускать. (N- число строк в исходной таблице) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 14:25 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, Погонял на таблице разного размера и генерации, однозначного победителя из трех вариантов kaban pattern matching, neofit, graycode plsql не выявил, лидером оказывается то один то другой то третий, причем pattern matching всегда очень близко к pl/sql варианту, neofit уходит то в плюс то в минус процентов на двадцать. Честно говоря от pl/sql варианта ожидал лучших результатов. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 14:28 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL, Оценить размер результата сложно, там помимо пропусков может быть увеличение, например идет интервал tgt, а в его середине интервал src, на входе два интервала, на выходе три, если два интервала src в середине tgt, то исходных три интервала, а на выходе 5. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 14:33 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode мы читаем по строке, формируем новую в PL/SQL и отдаем обратно в SQL Ну и откуда вывод, что выдача происходит по одной строке? Из statement PIPE ROW? Ну-ну. Что до чтения - тут вообще странно Вас читать. Ничто не мешает ни явному bulk collect, ни неявному (оптимизация курсорного цикла на PLSQL Optimizer Level 2). ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 14:39 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode Кобанчег, Погонял на таблице разного размера и генерации, однозначного победителя из трех вариантов kaban pattern matching, neofit, graycode plsql не выявил, лидером оказывается то один то другой то третий, причем pattern matching всегда очень близко к pl/sql варианту, neofit уходит то в плюс то в минус процентов на двадцать. Честно говоря от pl/sql варианта ожидал лучших результатов. Pl/SQL компилированный, я надеюсь? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 14:58 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode НеофитSQL, Оценить размер результата сложно, там помимо пропусков может быть увеличение, например идет интервал tgt, а в его середине интервал src, на входе два интервала, на выходе три, если два интервала src в середине tgt, то исходных три интервала, а на выходе 5. Да, я уже решил полным перебором. Ответ 2N (2N-1 если не показывать пробелы) правильный. Удвоение не так уж плохо. Тогда можно аллокировать массив двойной длины, собрать отсортированные по x1 данные в его вторую половину, оставляя первую пустой и не затирая непрочитанных данных обработать в том же пространстве. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 15:03 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Pl/SQL компилированный, я надеюсь? Нет, так что еще есть пространство для оптимизации)) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 15:38 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
andrey_anonymous, Еще не факт что пакетная обработка даст серьезный прирост производительности в этой задаче, потребление памяти даст точно)) SQL: сумма(вычисления(сортировка(исходные данные))) PL/SQL: сортировка(исходные данные) -> черный ящик (PL/SQL вычисления) -> Сумма(результирующий набор из черного ящика построчно или пакетом/пакетами) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 15:45 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode, я не очень следил за содержанием... то, что было показано, в твоем pl/sql коде в частности, подозрительно, поскольку, на беглый взгляд, плохо учитывает возможность множественного пересеченения каждого из исходных отрезков с порождением множества результатов пересечения из одного исходного отрезка. что касается pl/sql против нет - ну, с Марса, имхо, так видится: в случае pl/sql - ~nLog(n) для стартовой сортировки + ~nLog(n) сам алгоритм построения результата. SQL, может быть, в виде pattern matching к этому подберется, если повезет с алгоритмами в его нутрях. Join надо будет попотеть заставлять оставаться в рамках роста nLog(n) на больших бъемах. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 15:58 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
booby что касается pl/sql против нет - ну, с Марса, имхо, так видится: в случае pl/sql - ~nLog(n) для стартовой сортировки + ~nLog(n) сам алгоритм построения результата. Построение результата должно быть линейным, т.к. простой цикл без учета длины данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 16:07 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
booby то, что было показано, в твоем pl/sql коде в частности, подозрительно, поскольку, на беглый взгляд, плохо учитывает возможность множественного пересеченения каждого из исходных отрезков с порождением множества результатов пересечения из одного исходного отрезка. Не очень понял что имеется ввиду, у нас src это приоритетные отрезки, поэтому если на них накладываются отрезки tgt, то отрезки tgt частью попадающей на src просто игнорируются, остается только выступающая за src часть, а друг с другом src пересекаться не могут по условию задачи, да и приоритета по цветам у нас нет, пересечение отрезков src отрезками tgt обрабатывается. booby ~nLog(n) сам алгоритм построения результата. В цикле по отсортированной входной выборке только дерево условных операторов, т.е. ~(n), откуда логарифм? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 16:14 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode, вы тут две задачи обсуждаете, формулировку второй я вообще не понял, правда и не вчитывался... в общем, даже не важно про первую или вторую это задачу: автору нас src это приоритетные отрезки, поэтому если на них накладываются отрезки tgt, то отрезки tgt частью попадающей на src просто игнорируются, остается только выступающая за src часть здесь умолчанием подразумевается,что а) у src нет пересечений, б) входной набор "правильно" сортирован и, значит, в) tgt относящийся к "другому" src не приедет преждевременно. сколько, кстати, кусков от src должно остаться после наложения всех tgt, и почему следующий tgt не может резать внахлест уже разрезанное предыдущим? Т.е. слишком много ифов зашито в первичную сортировку. А так по виду - классическая задача на заметание, в любом случае, решаемая за ~nLog(n) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 16:42 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
booby А так по виду - классическая задача на заметание, в любом случае, решаемая за ~nLog(n) На базе SMJ вполне делается за две сортировки плюс линейный перебор. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 17:03 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
andrey_anonymous, что такое SMJ? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 17:11 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
booby andrey_anonymous, что такое SMJ? Sort Merge Join :) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 17:22 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
andrey_anonymous booby andrey_anonymous, что такое SMJ? Sort Merge Join :) понял, это ты к тому, для join тоже можно гарантию nLog(n) обеспечить... Ок. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 17:32 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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.11.2020, 17:42 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
booby понял, это ты к тому, для join тоже можно гарантию nLog(n) обеспечить... Ок. Это я к тому, что при наличии предварительно отсортированных наборов сам SMJ линеен и, вообще говоря, подходит под решение задачи. Наличие пресортированных наборов можно обеспечить индексным доступом и тем самым решить за линейное время. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 17:45 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode ... пересечений src-src и tgt-tgt быть не может. .... с чего бы это? чтобы задачу упростить? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 17:50 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
booby чтобы задачу упростить? Задача аннулирования самопересечений достаточно тривиальна и не очень интересна в контексте. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 17:52 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
andrey_anonymous На базе SMJ вполне делается за две сортировки плюс линейный перебор. Более того, если делать через джойн, то линейным перебором можно обойтись только в PL/SQL, SQL-но придется использовать еще один джойн (или pivot). Я ж так понимаю речь про такое ядро Код: plsql 1. 2. 3. 4. 5.
? Ну так это уступает тому, что уже было показано. У меня то есть финальный вариант но я не видел смысла его выкладывать в виду неконкуретноспособности. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 18:58 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег У меня то есть финальный вариант для select 10, 20, 'blue', 'tgt' from dual union all select 15, 25, 'blue', 'src' from dual результат одна строка 10, 25, 'blue' ? ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 19:11 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax, Да. PS. Если что можно же ответ сверять с имеющимися вариантами. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 19:13 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Хм, сделал таблицу IOT с pk по всем полям, теперь pl/sql стабильно чуть быстрее, но именно чуть чуть, т.е. все равно все три варианта равноценны в практическом плане и вариант неофита лучше варианта pattern matching. PS: pl/sql native и Optimizer Level 2 ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 19:14 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег линейным перебором можно обойтись только в PL/SQL Ага ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 22:24 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
andrey_anonymous Кобанчег линейным перебором можно обойтись только в PL/SQL Ага Да ну, я же публиковал линейный перебор в самом начале на SQL. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.11.2020, 23:07 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL andrey_anonymous пропущено... Ага Да ну, я же публиковал линейный перебор в самом начале на SQL. Что-то я не видел. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 00:33 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
andrey_anonymous Что-то я не видел. 22233043 ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 00:57 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 02:25 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 03:06 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
xtender, Мне эта видится проще,тут N слоев одиночных заплаток, перебор комбинаций меньше. Соответственно и решение короче. Но задачка тоже классная, я попробую решить не глядя в ссылку. А задачи про двухмерные заплатки никто не публиковал? Например: Каждая строка задаёт х1,х2,у1,у2 координаты покрашенного прямоугольника. Определить: - площадь покрашенной поверхности - максимальный полностью закрашенный прямоугольник - максимальное число слоев на поверхности - площадь поверхности содержащая ровно N слоев краски Для супер одаренных: - наибольший полностью закрашенный круг (центр и радиус) Это монохромная версия. Можно добавить цвета.. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 03:42 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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.
... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 04:03 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Почитал решения по ссылке, народ явно легких путей не ищет. "Simplicate, and add lightness" (c) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 04:07 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL А задачи про двухмерные заплатки никто не публиковал? Например: Каждая строка задаёт х1,х2,у1,у2 координаты покрашенного прямоугольника. Определить: - площадь покрашенной поверхности - максимальный полностью закрашенный прямоугольник - максимальное число слоев на поверхности - площадь поверхности содержащая ровно N слоев краски Для супер одаренных: - наибольший полностью закрашенный круг (центр и радиус) Это монохромная версия. Можно добавить цвета.. Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
С фотошопом я не дружу, поэтому иллюстрация в ASCII: Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8.
Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 04:56 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL А задачи про двухмерные заплатки никто не публиковал? Приходилось как-то на проекте внедрения внезапно под вечер решать задачку вида "сделать из списка (с историей изменения) префиксов телефонных зон двумерную карту для быстрого определения корректной зоны вызова по параметрам (вызываемый номер, дата соединения)". Не rocket science, хотя пару-тройку часов из жизни выкинул. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 13:10 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Почитал решения по ссылке, народ явно легких путей не ищет. "Simplicate, and add lightness" (c) А ты подставь данные из ссылки и сравни результат, ты решал какую то другую задачу. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 13:18 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Неофит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.
..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:09 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег Собственно мой вариант таков. Код: 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.
MATCH RECOGNIZE SORT DETERMINISTIC FINITE AUTOMATON + WINDOW SORT + UNPIVOT При попытке решить однопроходно с match recognize упираешься в то, что "активный" цвет для текущей группы определяется по всему набору а match recognize не позволяет заглядывать в предыдущие группы. Код: plsql 1. 2. 3. 4. 5.
Код: plaintext 1. 2. 3. 4. 5.
..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:30 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax должно быть две строки? Да. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:31 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:35 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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.
... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:38 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode, у НеофитSQL-а одна, косяк Ваш вариант не тестировал (что-то лень обьекты создавать) если дойдут руки, заменю pipe на dbms_output и мож потестю ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:40 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег странно что это не всплыло в моём чудо тесте Тестовые данные не покрывают много кейсов, а генератор на производительность вообще вырожденный и возможно это одна из причин удивительных результатов теста на производительность[/quot] ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:43 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:46 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode возможно это одна из причин Я вчера уже поверил в твою адекватность когда ты признал что PL/SQL и SQL приверно одного уровня по производителности. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:49 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег Можешь использовать мой запрос, там верно возвращает. для 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.
зі match_recognize с ошибкой зы ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:57 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, Причина мне не совсем понятна, я убрал фактор сортировки, т.е. сортировок нет, просто прогоняется набор исходных данных через функцию, в функции только дерево условий, по идее должно быть быстрее, оно и быстрее но совсем незначительно, можешь объяснить причину? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 15:57 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode Причина мне не совсем понятна, я убрал фактор сортировки, т.е. сортировок нет Код: plsql 1.
? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 16:00 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, IOT, pk по всем полям начиная с x1)) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 16:02 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode, Ну тогда смотри куда уходит время в dbms_hprof + dbms_sqltune.report_sql_monitor Может что-то еще можно выжать из твоего подхода, но практической ценности для меня не несет. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 16:07 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax для unpivot + pivot + lead сдаюсь поспешил 22234679 В моём сортировку в аналитике надо сделать идентичной с MR. Код: plsql 1.
... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 16:19 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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.
..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 16:22 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег Ты fix тут увидел? увидел, сдался тестировать видать в буффере был древний(без фикса) вариант, и я уже не присмотрелся звиняйте, поспешил ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 16:30 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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.
Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender). ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 17:00 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax НеофитSQL Жаль, критерий трудно определить объективно. У меня получилось так. должно быть две строки? ..... stax Нарушено условие задачи, интервалы одного уровня касаются. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 17:38 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender). ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 17:45 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax, Пакет под тестирование производительности был сделан, таблица здесь 22233322 Код: plsql 1.
Сам тест кандидатов на лучшее время выполнения 22233403 . ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 17:46 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
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.
Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
Линейных решений не вижу, из того что вижу, возможно два разных перебора, перебор интервалов на дне стакана в момент когда падает новый блок или получение всех интервалов с последующим нахождением самого нижнего блока над отрезком по вертикали (то что реализовано у xtender). Ответ в первой строчке должен быть а-0-1. В этой задаче отрезки задаются границами интервалов (см картинку). ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 17:46 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Ответ в первой строчке должен быть а-0-1. В этой задаче отрезки задаются границами интервалов (см картинку). Так я написал, что немного изменил условия, сделал их как в предыдущих задачах, т.е. интервалы 0-1 и 1-3 пересекаются, рассматривай их как блоки из кубиков. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 17:52 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode НеофитSQL Ответ в первой строчке должен быть а-0-1. В этой задаче отрезки задаются границами интервалов (см картинку). Так я написал, что немного изменил условия, сделал их как в предыдущих задачах, т.е. интервалы 0-1 и 1-3 пересекаются, рассматривай их как блоки из кубиков. Зря изменил. Координаты для науки, кубики для детей :) Теперь на иллюстрации длины отрезков не совпадают, и ответ все равно неверный. По координатам должно быть: c[1-3] (так в оригинале) По "кубикам" должно быть: c(1,2) У тебя в ответе: c(1,1) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 18:22 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Почти линейный 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.
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.
... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 18:41 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Есть простое, в четыре строчки, решение для частного случая, когда при закрашивании не формируются дырки. Общее решение пока не придумал. И по слоям, и по координатам накапливается state. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 18:43 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode Немного изменил условия ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 18:44 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
xtender, В пятничных задачах есть смысл? На тетрис похоже)) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 18:48 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode xtender, В пятничных задачах есть смысл? На тетрис похоже)) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 19:05 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL По "кубикам" должно быть: c(1,2) У тебя в ответе: c(1,1) Да, ошибся должно быть c(1,2). ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 19:10 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Правильный ответ для задачи по отрезкам с координатами: Также подправил картинку, а то левая часть была отрезками, а правая - "кубиками" Код: 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.
Исходные данные (от 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 19:51 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL, Так если координаты, зачем кубики нагенерил?)) PS: решения с генерацией диапазона не очень интересны даже для кубиков, а для координат не подходят вообще. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 21:26 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode НеофитSQL, Так если координаты, зачем кубики нагенерил?)) PS: решения с генерацией диапазона не очень интересны даже для кубиков, а для координат не подходят вообще. Не кубики, а пробные значения :-Р Интервалы пространства и времени имеют практическую ценность для произвольной точности, кубики упрощают задачу до целых чисел. Кубики в постановке задачи элементарно переводятся в отрезки: Х1-х2. -> [х1,х2+1) Если отрезки целочисленные, обратное преобразование также есть, вычесть единичку. Для работы с данными отрезки лучше, для распечатки можно перевести в кубики, в зависимости от того кто читать будет. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 22:36 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL, Не, тут уж или крестик или трусы))) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 22:39 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
graycode, Лол, хорошо. +0.5 для подобных. В pl/sql решается просто вдоль Х через стэк глубиной lvl. В sql нащупывается рекурсивное решение, но пока не сделал ... |
|||
:
Нравится:
Не нравится:
|
|||
18.11.2020, 22:55 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Нарушено условие задачи, интервалы одного уровня касаются. graycode Сам тест кандидатов на лучшее время выполнения 22233403 . В той задаче были совсем другие объемы и поэтому не было надобности в alter session которые имеются в новом тесте. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 08:52 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
xtender Кажется, я уже решал обе такие задачки, сходу только вспомнить и найти не смог, но нашёл чуть более сложный вариант усложненной задачки: https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set xtender Почти линейный PL/SQL к 22232077 Кобанчег задачка посложнее. 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 09:03 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Challenge just for fun Решить задачу отсюда https://stackoverflow.com/questions/64137899/flatten-list-of-ranges-to-single-result-range-set Не используя соединений или коррелированных подзапросов. Ну и без завязывания на частные случаи. То есть - границы не обязательно целочисленные - никакой генерации - число приоритетов неограничено - никакого хардкодига итд У меня более одного варианта. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 09:09 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег 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 ... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 09:57 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax 1) а,b и b,c не пересекаются? соприкасаются? можно/надо слить в один a,c? Мы тут говорим про действительные числа уже. Stax 2) возможен ли диапазон a,a (зависит от ответа на п1) Stax 3) одного цвета соприкасающиеся обьеденяем? Stax 4) "чистый" sql или/и pl/sql? Stax жаль graycode забанили от публикаций Более того это вообще может быть рандомный модератор любого форума. Ну наверное самому забаненому что-то ясно. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 10:48 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax, Я тестировал на этом наборе Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
Последний отрезок ломает решения икстендера потому что до него дырка, но легко допиливается. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 10:50 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег Последний отрезок ломает решения икстендера потому что до него дырка, но легко допиливается. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 11:05 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, у икстендера есть главный/0 интервал покрывающий все, типа min()-x,max()+y цвета хаки тогда дырок не будет не знаю часть условия ли ето, или случайно если я правильно понял то заливка уникальными цветами range_name ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 11:10 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax, Да. У икстендера надо пустые интервалы выкинуть из результата. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 11:25 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 20:53 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег НеофитSQL Нарушено условие задачи, интервалы одного уровня касаются. Перечитал, действительно. О несоприкосновении говорилось в разминке, но не во второй задаче. С фиксом понятно. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 20:58 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL У меня число приоритетов до 38 попугаев, т.к. я не сумел listagg() использовать в оконном режиме. Оно таки и не работает с окнами.. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.11.2020, 21:44 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL О несоприкосновении говорилось Но Stax уточнил 22233313 . Твой запрос поломало касание src и tgt - это допустимо. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 00:10 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Нарушено условие задачи, интервалы одного уровня касаются. 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.
..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 02:50 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL, Да, верно. Это заодно и объясняет почему тест производительности не выявил различий. Данные были нагенерированы без таких случаев. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 04:30 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Пятница, господа! Челендж еще активен Кобанчег 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.
Constraints (name, range_start, range_end) - уникально (range_end > range_start) ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 15:22 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег - число приоритетов неограничено ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 15:35 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег, model, рекурсивные запросы? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 15:35 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
xtender Кобанчег, model, рекурсивные запросы? Модель - конено, почему бы нет. Ну разве что итеративная модель - это не спортивно. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 15:42 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
xtender Кобанчег - число приоритетов неограничено Ну на единичную длину закладываться не стоит. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 15:46 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег xtender пропущено... name может быть от a,...,z,aa,...,az,...,zzzzzzzzzzzzz? Ну на единичную длину закладываться не стоит. имхо удобнее было-б уровень задавать числами (int), цвет varchar2(хх) .... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 16:17 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Stax, Мне кажется примерно индифферентно для чего делать max. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 16:59 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег Stax, Мне кажется примерно индифферентно для чего делать max. a aa ab c d ... z мне удобнее числа и легче тестовые добавлять (+ не надо помнить алфавит) в етой пятничной наверное менять не надо, у народа наработки уже на буквах ..... stax ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 17:06 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Собственно варианты следующие. Раз Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23.
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.
Два Получаем оригинальные и "нарезанные" интервалы. Моделью возвращаем "нарезанные" с определенными новыми именами (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.
Если заморочиться можно обойтись одним обращением к таблице + двойной 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.
Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 19:39 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
Вместо 100500 можно +/- бесконечность (быстрее) или min(start)/max(end) (медленнее). Приоритет вычисляется по значению name, как в оригинальной задаче. Кобанчег, у тебя в последней строчке 'e',3,6 вместо 'е',3,5 - намеренно или опечатка? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 19:42 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Сравним скорость, или подождем PL/SQL варианта? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 19:43 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Кобанчег, у тебя в последней строчке 'e',3,6 вместо 'е',3,5 - намеренно или опечатка? Но "опечатка" была использована ранее для тестирования. НеофитSQL Код: plsql 1.
... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 19:45 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
НеофитSQL Сравним скорость, или подождем PL/SQL варианта? SQL-но и безджойно было "just for fun". PS. Икстендер публиковал PL/SQL подход. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 19:49 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Ну и по приколу линейный проход. Но это не спортивно ибо 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.
... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 20:00 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Кобанчег НеофитSQL Код: plsql 1.
Я его написал :) Понадеялся что джойн по константе исполняется эффективно. Не всякий "from a, b" стоит циклов, бывают бесплатные или дешёвые. Например, "from a,b where b.rowid=x" ничего не должен стоить. Больше беспокоит многопроходность. В худшем случае мой алгоритм дает О(n*n) шагов и 3n памяти. В лучшем, O(n). ... |
|||
:
Нравится:
Не нравится:
|
|||
20.11.2020, 22:37 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Сделал пару быстрых проверок на таблице из 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.
Рекурсивное решение: Код: 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.
Как заполнялась тест таблица: Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18.
... |
|||
:
Нравится:
Не нравится:
|
|||
23.11.2020, 18:47 |
|
Пятничная задача: Красное и черное
|
|||
---|---|---|---|
#18+
Можно попробовать запретить использование планов с виртуальным преобразованием в виртуальные битовые индексы и обратно (это крайне было полезно в 9-ке, но, возможно, не утратило актуальности и в новых версиях) alter session set "_b_tree_bitmap_plans"=false ... |
|||
:
Нравится:
Не нравится:
|
|||
24.11.2020, 01:19 |
|
|
start [/forum/topic.php?all=1&fid=52&tid=1880676]: |
0ms |
get settings: |
7ms |
get forum list: |
12ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
134ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
158ms |
get tp. blocked users: |
2ms |
others: | 298ms |
total: | 631ms |
0 / 0 |