Разбор полётов
В те дни души были смелыми, ставки – высокими, мужчины были настоящими мужчинами, женщины – настоящими женщинами, и мохнатые зверюшки с Альфы Центавра – настоящими мохнатыми зверюшками с Альфа Центавра. И все пускались навстречу неизвестности, навстречу ужасным опасностям, великим свершениям, и определению неопределенных форм глагола, чего никогда доселе не делали.
Дуглас Адамс, Путеводитель автостопом по галактике
Статья с условием задачи была опубликована почти в полдень, первые комментарии с работающими запросами появились уже спустя пару часов с хвостиком (прошу прощения за эээ… некоторую вольность в выражениях к хвостатым обитателям Вселенной), а первое правильно работающее решение уже к вечеру! Кто другой сказал бы, что вот, мол, везёт же некоторым — на работе ничего не делают, только хабр читают, да задачки решают… Но мы так не скажем! Мы скажем, что есть в природе правильные админы, у которых всё настроено и отстроено, и не требует при штатной эксплуатации ручного вмешательства, позволяя в освободившееся время разминать ум! И ещё скажем, что представители Западного завитка Галактики проявили небывалый интерес к приведённой задаче (по непроверенным данным отклонение составило более трёх сигм)! Общее количество индивидуумов, написавших запросы, оказалось равным почти двум десяткам, количество комментариев уверенно перевалило за сотню. И это (прикинь!) без всякой политоты, без флеймов, без троллинга и практически без набросов… Мы конечно надеялись на отклик в душах землян, именно про их офисное рабство и сформулирована задача, но такой резонанс…
Но, вернёмся ближе к теме. Некоторые детали решений, которые запомнились.
Первое работающее решение от the_unbridled_goose появилось уже через два часа после публикации задачи. Решение было красивым: разложить исходные периоды на часы, выкинуть из них нерабочие и посчитать сумму оставшихся, но, увы, неполным. Довести его до конца, увы, так и не получилось. Первое же полностью рабочее решение появилось к концу рабочего дня агломерации Московского региона третьей планеты Солнечной системы (XareH 18:17). Интересным оказался подход, когда длительность рабочего времени периода определялась следующим образом: считаем общее количество дней, вычитаем выходные и праздники, прибавляем дополнительные рабочие дни и результат умножаем на длительность рабочего дня в часах (OrmEugensson). Встречались также решения под MS SQL (uaggster), под Oracle (Mazdik) с последующим переводом на PostgreSQL (Mazdik, StrangerInTheKy). Был вариант с парсингом и автоматическим формированием рабочего календаря (valery1707), были домашние заготовки (Megacinder). По меньшей мере трое индивидуумов зарегистрировались, чтобы опубликовать свои решения (но это неточно, только догадки), а ещё несколько вышли из тени (написали наконец-то свои первые комментарии на Хабре).
Остальных не перечисляю поимённо (все решения присутствуют в комментариях к исходной статье), но большое Вам спасибо за проявленный интерес и участие. А также особое спасибо за упор
И, наконец, обещанный победитель, который получит приглашение на PGConf.Russia 2020 – это eranthis (пройдите пожалуйста в кассу, в личных сообщениях вас ждёт сюрприз). Пожалуй что именно его решение (ссылка) показалось мне самым интересным по компактности и выразительности.
Ещё раз спасибо всем участникам! Stay tuned!..
P.S. Разбор задачи с решением, как я и обещал, будет, но чуть позже. Уже пишу, но времени не хватает.
Комментарии (23)
OrmEugensson
26.06.2019 16:43Своё решение писал, исходя из предпосылки — что, если у нас будут периоды длительностью в тысячи лет (ну или хотя бы в сотни)? :)
vav180480_2
26.06.2019 17:07я свое решение потестил 3019 годом (очень частая ошибка кстати, у нас так клиента подключили и он около года работал бесплатно:)), рухнуло и ругнулось на память, да:) Но в задаче четко прописано — рабочее время, так что границы некие есть.
StrangerInTheKy
27.06.2019 00:17Круто, почаще бы такие штуки видеть.
Я работал с постгресом на заре свой карьеры, был тогда полным чайником, а потом жизнь заставила перейти на оракл. Теперь потихонечку начинаю использовать постгрес для своих проектов, очень познавательно и полезно получается — сразу кучу всего увидел.
nikotin77
27.06.2019 15:47Пожалуй что именно его решение (ссылка) показалось мне самым интересным по компактности и выразительности.
Но не по производительности.
Его решение работает в 10 раз медленнее, чем, например, мое.
Без претензий на лавры, PostgreSQL вообще не мой родной.vav180480_2
27.06.2019 17:11А ваше решение работает на 10% медленнее чем моё и дело там не в постгресе:)
bzq Автор
27.06.2019 17:51Интереса ради померял оба ваших решения на скорость. Да, ваши запросы действительно на (десятичный) порядок быстрее. 10% не уловил, более-менее равная производительность на количестве периодов около 3 тыс. Ну может чуть быстрее, но это уже сравнимо с погрешностями измерений.
Но пожалуй производительность тут не была основным критерием, если только запрос не тормозил слишком уж чрезмерно. Интереса ради я написал запрос, который работает быстрее ваших ещё на (десятичный) порядок, избавившись от суммы по интервалам, и получив скорость работы линейно зависящую только от количества периодов. Видимо придётся добавить в разбор задачи слова про производительность.nikotin77
27.06.2019 18:28Интереса ради я написал запрос, который работает быстрее ваших ещё на (десятичный) порядок, избавившись от суммы по интервалам, и получив скорость работы линейно зависящую только от количества интервалов. Видимо придётся добавить в разбор задачи слова про производительность.
Вот на это интересно посмотреть, буду ждать.bzq Автор
27.06.2019 19:35Не ждите слишком многого. Разбор решения будет интересен скорее тем, кто не представляет себе, как такие задачи вообще решаются. Для Вас, соответственно, это будет слишком тривиально.
StrangerInTheKy
27.06.2019 21:28Видимо придётся добавить в разбор задачи слова про производительность.
Конечно, на вкус и цвет все фломастеры разные, но на мое имхо, производительность в БД — это самое интересное.
OrmEugensson
28.06.2019 10:43Интереса ради я написал запрос, который работает быстрее ваших ещё на (десятичный) порядок, избавившись от суммы по интервалам, и получив скорость работы линейно зависящую только от количества интервалов. Видимо придётся добавить в разбор задачи слова про производительность.
Так моё ж решение так и работает, или я что-то не понимаю?bzq Автор
28.06.2019 13:11Да, Вы пошли именно в этом направлении, но немного не дошли до конца. Можно посчитать один раз количество рабочих часов на каждый день в календаре и дальше уже брать готовый ответ, не считая каждый раз количества рабочих и выходных дней, попадающих в период.
Вот так, например:with recursive calendar(d, is_working) as ( select '2017-12-31'::date, 0 union all select d+1 , case when extract(dow from d+1) not in (0,6) and d+1 <> all('{2019-01-01,2019-01-02,2019-01-03,2019-01-04,2019-01-07,2019-01-08,2019-03-08,2019-05-01,2019-05-02,2019-05-03,2019-05-09,2019-05-10,2019-06-12,2019-11-04,2018-01-01,2018-01-02,2018-01-03,2018-01-04,2018-01-05,2018-01-08,2018-02-23,2018-03-08,2018-03-09,2018-04-30,2018-05-01,2018-05-02,2018-05-09,2018-06-11,2018-06-12,2018-11-05,2018-12-31}') or d+1 = any('{2018-04-28,2018-06-09,2018-12-29}') then 1 else 0 end from calendar where d < '2020-01-01' ), calendar_w(d, is_working, work_hours_acc) as ( select d, is_working , sum(is_working*'9 hours'::interval) over (order by d range between unbounded preceding and current row) from calendar ) select p.* , c2.work_hours_acc - c1.work_hours_acc + ('19:00:00'::time - least(greatest(p.start_time::time,'10:00:00'::time),'19:00:00'::time)) * c1.is_working - ('19:00:00'::time - least(greatest(p.stop_time::time, '10:00:00'::time),'19:00:00'::time)) * c2.is_working as work_hours from periods p, calendar_w c1, calendar_w c2 where c1.d = p.start_time::date and c2.d = p.stop_time::dateOrmEugensson
28.06.2019 13:50Да, Вы пошли именно в этом направлении, но немного не дошли до конца
хм. В моём решении смысл был другой — избавиться от перехода от данных {одна строка на период} к данным {одна строка на дату} и от последующей агрегации. В решении приведенном сверху вы красиво избавились от агрегации и от увеличения количества данных на каждую строку, но все равно осталась необходимость увеличения количества данных один раз.
В моём решении сложности добавляет то, что необходимо проверять попадание праздников в период. То есть у меня сложность была, грубо говоря (если для простоты считать, что джойн выполняется за константу независимую от объема данных), O(количество праздников * количество периодов), а у Вас O(количество дней между минимальной и максимальной допустимой датой + 2 * количество периодов). То есть, скорее всего, с небольшим количеством праздников или с периодами длиной в сто лет, думаю, моё решение будет работать быстрее, но с большим количеством периодов в интервале двух годов и/или большим количеством праздников — будет быстрее работать Ваше.bzq Автор
28.06.2019 19:42Я посчитал сразу количество рабочих часов на каждую дату и расчёт длительности для периодов в рабочих часах стал одной операцией вычитания. А у Вас в результате остались итерации по каждому из периодов. Посмотрите на планы исполнения мой и Ваш. Именно по этой причине я и сказал, что Вы не дошли до конца. В философском смысле. Уж если от внутреннего цикла избавляться, то полностью, чего уж там.
И, кстати, именно Ваше решение сподвигло меня на эти размышления и в конечном итоге реализацию такого подхода, как самого оптимального по времени.
nikotin77
27.06.2019 18:26А ваше решение работает на 10% медленнее чем моё и дело там не в постгресе:)
Тут можно сравнить более объективно:
Ваше решение
Мое
И у Вас ошибка где-то, не сходится сумма…vav180480_2
28.06.2019 06:51И у Вас ошибка где-то, не сходится сумма…
… или у вас;)vav180480_2
28.06.2019 11:36… или у вас;)
Ага, вы озаботились вставить 4000 одинаковых строк заявок, но не озаботились вставить одинаковые выходные и одинаковые перенесенные рабочие дни. Я озаботился в итоге тютелька в тютельку. И насчет «объективных» сравнений, у меня быстрее посчитает одну конкретную заявку, т.к. запрос проще и быстрее пройдет разбор, у вас посчитает быстрее общую сумму большого массива заявок. С чего вы взяли что ваша задача (подсчет общей суммы массива), более актуальнее моей (подсчет для конкретной заявки)?nikotin77
28.06.2019 13:25Я лишь взял Ваше решение по вашей же ссылке. Почему у вас там оказался неверный набор выходных и праздников — спросите у себя.
Так что тут неизвестно кто первый не озаботился. :)
Ваше решение мне нравится лаконичностью, понятностью и чистотой.
Решение от OrmEugensson более мудреное и сложное, но и гораздо более производительное, чем наши с вами.
С чего вы взяли что ваша задача (подсчет общей суммы массива), более актуальнее моей (подсчет для конкретной заявки)?
Мне такие кейсы встречаются чаще. Как-то даже не пришло в голову иначе протестировать.vav180480_2
28.06.2019 15:02Мне такие кейсы встречаются чаще. Как-то даже не пришло в голову иначе протестировать.
В реальной рабочей системе у вас есть заявка в состоянииях 1) «открыта» когда она заведена и в ней можно править исходные данные, время начала и время окончания 2) «закрыта» когда уже ничего нельзя править в исходных данных. Внимание вопрос, в какой момент будет рассчитываться рабочее время заявки? В момент ее закрытия, в ходе операции закрытия над конкретной ОДНОЙ заявкой с конкретным ID. При этом мы в РЕАЛЬНОМ ВРЕМЕНИ имеем актуальную информацию об отработанном времени и соответственно наших затратах на оное, при этом временные затраты на этот расчет заявок будут растянуты во времени, закрыли — тут же посчитали, затратив минимум ресурсов. Или мы просто переведем ее в состояние «закрыта» а потом, неизвестно когда, будем рассчитывать отработанное время больших массивов заявок, при этом мы должны ввести третье состояние «рассчитана», чтобы не пересчитывать два раза, при этом у нас нет актуальных данных в каждый момент времени, а есть только данные последнего массового расчета предыдущего массива, при этом система понесет пиковую нагрузку в момент массового перерасчета и редактирования записей, может что то подвесить или с чем то сконфликтовать. Странные у вас кейсы:) А так то в оракле точно (в посгресе не помню), есть подсказки оптимизатору на ускоренный возврат либо первой записи либо всех записей, потому как и то и это важны в определенных ситуациях. В нашем случае оптимально иметь 2 состояния заявки вместо 3, и рассчитывать время в момент закрытия. Т.е. тестирование быстродействия это не только на массиве записей (когда время разбора запроса относительно не велико), но и на одной записи (когда время разбора относительно велико и именно оно определяет быстродействие) В нашем случае нужно тестировать быстродействие именно на одной записи, т.к. в реальной боевой системе оптимальнее считать именно по одной заявке.
bzq Автор
28.06.2019 12:47Не занимайтесь демагогией. Ваше решение даёт неправильный результат, потому что Вы не все даты из рабочего календаря включили в свой запрос. И чтобы получить правильный результат, надо сперва вдумчиво Ваш запрос дописать. Я на это указывал ещё в комментариях к предыдущей статье. Мне во время проверки приходилось делать исправления (что, признаться, несколько раздражало), так как я вроде бы был заводилой всей этой движухи, а прочим окружающим этим заниматься совершенно неинтересно.
vav180480_2
28.06.2019 13:06-1Демагогия, это когда говорят «у ВАС ошибка» вместо «у НАС не сходятся результаты». А чтобы не надо было вдумчиво дописывать, нудно сначала вдумчиво дать ВСЕ исходные данные. В частности вы обязали ВСЕХ искать перечень праздников и переносов, вместо того чтобы САМОМУ все сделать, выложить или дать ссылку. Т.е. вместо того чтобы затратить лишние 30минут, вы заставили ВСЕХ это проделать, в итоге человечество потеряло X*30минут времени, где X-количество участников, причем из-за того что источники у всех были разные, разными были и перечни праздников (например не граждане РФ по инерции могли взять праздники и переносы Украины), а потом вы же создали СЕБЕ сложности при сверке, затратив гораздо больше чем 30минут. Т.е. все как обычно, переложили на программистов то что должен изначально делать постановщик, плохо стало в итоге всем. Я из просмотра альтернативных решений извлек свои уроки, вы из неправильной и не полной постановки задачи, думаю должны извлечь свои;)
uaggster
28.06.2019 20:49Мда… Это не
бубль-гумнифига не iso.
Впрочем, меня обнадеживает, что я практически все понял, всего то раза три загуглив :-)
… можно тешить себя надеждой, что когда приспичит — смогу пересесть.
vav180480_2
Поддерживаю выбор, мне решение понравилось в том смысле что я не знал что есть нечто подобное типам *range, т.е. образовательный момент во всем конкурсе — главный, кто что то новое узнал тот тоже победил:)
bzq Автор
Спасибо за поддержку. Выбирать в самом деле было сложно.