bzq Mar 12 2018 at 15:30

Как мы делали олимпиаду по SQL (окончание)

18 min

4.4K

Sport programming*Entertaining tasksOracle*SQL*

+11

Comments 8

chemtech Mar 12 2018 at 19:44

У вас задачи Oracle-специфичны? или можно были их проводить на PostgreSQL?

bzq Mar 12 2018 at 22:23

Специфика есть, но она не особо существенная. Например, используются словарные объекты оракловой базы для получения информации типа DBA_TABLES, DBA_TAB_COLUMNS, DBA_DEPENDENCIES. В PostgreSQL должны быть свои аналогичные словарные таблицы. Оптимизация в оракловой базе явно отличается от других. И так далее. Но на другую базу переносимо. Другой вопрос в том, нужно ли это переносить на другую базу.

SLWhb Mar 16 2018 at 15:42

Участвовал, отмучился — спасибо)
Автор зверь конечно, респект.

Согласен что такой блиц был не очень справедлив, и когда мы участниками общались, все так же решили. Застопоришься на чем-нибудь — и все.
В добавок к самому заданию сами формулировки почему-то мешали сосредоточиться. Может из-за сжатого времени так ощущалось, не знаю.
После первого задания на котором слегка подвис, границы пробило и дальше пошло легче.
В любом случае кругозор эти задания расширили, хотя задания 2 этапа понравились конечно больше

bzq Mar 19 2018 at 23:29

Спасибо за добрый отзыв!

xtender Mar 20 2018 at 04:28

Молодцы, хорошая затея! :)
В 7-й задаче, я бы лучше предложил решать через PL/SCOPE, как мне кажется это было бы правильнее, чем самому парсить. Нужно было лишь откомпилить объекты с alter session set PLSCOPE_SETTINGS='IDENTIFIERS:ALL' и смотреть где CALL к нужной процедуре и REFERENCE к нужному пакету совпадают dba_identifiers.usage

Еще мне кажется, что после 8-й задачи 9-я становится лишней и не является оптимальной, т.к. оптимальным должно быть сокращение объемов только до сумм и произведений, например так:

with 
-- закомментировал тестовый генератор
 --a(n) as (select/*+ cardinality(1000) */ level-1 n from dual connect by level<=1000),
 ----------------------
 -- calc: пошли вычисления
 -- аггрегируем уникальные числа, чтобы уменьшить объемы для перебора
 x0 as (select n,count(*) cnt from a group by n order by n)
 -- за один "урезанный" селф-джойн рассчитываем и суммируем сразу и суммы и произведения:
,x1 as (
  select
     x.n + y.n as s
    ,x.n * y.n as m
   ,2*sum(x.cnt*y.cnt) cnt
  from x0 x,x0 y
  where y.n>=x.n -- возьмем только один вариант и просто умножим на 2
  group by
     x.n + y.n
    ,x.n * y.n
)
-- тут уже объем для перебора становится практически минимальным:
select sum(x1.cnt*x2.cnt) total
from x1,x1 x2
where x1.s=x2.m;

C таким вариантом, у меня на такой тестовой табличке:

create table a(n) as select ceil(dbms_random.value(0,500)) n from dual connect by level<=1e4ж

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

bzq Mar 20 2018 at 13:47

О, наконец-то появилось что-то интересное в комментариях.

Да, в восьмой задаче в таблице было 10000 записей. Подсчёт «в лоб» слишком долгий. А предварительный расчёт сумм и произведений пар (или WITH, или временной таблицей) даёт приемлемый результат. Догадаться до такой оптимизации не так уж сложно, но нужно догадаться, что оптимизация вообще нужна. Скажем, для студентов это совсем нетривиально. Опять же блиц и стресс.

Но в девятой задаче это уже не проходит и там уже нужна хорошая алгоритмическая оптимизация. Вот предложенный Вами метод действительно работает! У нас было 5000 записей в таблице. Вот наше решение:

Осторожно, решение задачи!

select sum(x*x)
  from (select count(*) x
        from vpoupkine.abacus t1
           , vpoupkine.abacus t2
     	group by t1.n + t2.n)

xtender Mar 20 2018 at 14:01

Хмъ, я не понял что именно вы в 9-й задаче считаете? Количество комбинаций чего?
Ваше решение работает на моем наборе аж 40 сек.

create table a(n) as 
select ceil(dbms_random.value(0,500)) n from dual connect by level<=1e4;

А на наборе от 0 до 9 оно возвращает аж 670 — что это такое, если даже количество сумм равно 249?

with a(n) as (select level-1 from dual connect by level<=10)
select sum(x*x)
  from (select count(*) x
        from a t1
           , a t2
        group by t1.n + t2.n)

И покажите, пожалуйста, ваше решение для 8-й задачи

bzq Mar 20 2018 at 14:44

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

Вот так оно выглядит «в лоб» и «оптимизированно»:

Код

create table abacus as
(select level as n from dual connect by level < 10);

select count(1)
  from abacus a, abacus b, abacus c, abacus d
 where a.n+b.n = c.n+d.n;
>>> 489

select sum(x*x)
  from (select count(*) x
        from abacus t1
           , abacus t2
     	group by t1.n + t2.n);
>>> 489

Вроде сходится.

Для восьмой задачи достаточно посчитать таблицу с промежуточными результатами сумм и произведений, а потом по ней уже посчитать сколько раз встречается одинаковое там и там:

Осторожно, решение восьмой задачи

create table abacus_pairs as (
select t1.n + t2.n s
     , t1.n * t2.n m 
  from abacus t1
     , abacus t2;

select count(*) 
  from abacus_pairs a
     , abacus_pairs b
 where a.s = b.m;

Выше я слегка наврал, всего 1000 записей была в таблице abacus для восьмой задачи.

Show the best of all time