Комментарии 59
Мне всё-таки кажется, что нельзя. И не видел я лично нигде такого. К точке можно прибавить интервал. А как к точке прибавить точку?..
Хм, сложение дат? Microsoft Excel точно умеет прибавлять к датам числа, а вот Гугл таблицы складывают и вычитают даты возращая число дней
P.S. исправил изначально написанную неточную информацию
Число, количество дней между датами
Чем это отличается от вычитания дат?
Оставляя верхний комментарий я допустил ошибку пиша про разность дат, хотя речь шла о сумме. Но Гугл таблицы все равно умеют их складывать. Алгоритм мне не очевиден и пока я на работе - нет времени подумать над их механизмом. На выходе - число
Нмкто не запрещает так сделать, конечно, но это не то, что ожидаешь от сложения.
Если сложение возвращает количество дней, то оно, например, не будет ассоциативным:
(4 января + 3 января) + 1 января = 1 + 1 января = 2 января.
4 января + (3 января + 1 января) = 4 января + 2 = 6 января.
Алгебраистов, конечно, не испугать неассоциативным сложением, совпадающим с вычитанием, но тут эта операция выглядит лишней.
Моя ошибка с ответом
Если рассматривать дату как интервал между собственно этой датой и нулевой датой - точкой отсчета, то любые две даты вполне хорошо складываются. Можно прямо в столбик, поразрядно, как обычное 7-значное число (в представлении в системе счисления со специальными основаниями, как описано в статье), с инкрементом старшего разряда и сбросом младшего при переполнении младшего.
А что насчет алгоритма с предрасчетом N следующих точек во времени и запоминании их в циклическом буфере (очевидно, что сложность при этом абсолютно минимальная - 1 арифметическая операция и спячка), а предрасчет выполняется в отдельном низкоприоритетном потоке, когда кол-во оставшихся точек становится меньше некоего X или кол-во времени, оставшегося до последней рассчитаной точки, становится меньше чем T?
Интересно, а кого вообще ищет работодатель с такими тестовыми заданиями?
Можно обратить внимание, что в статье автор использует математику, проводит сравнения и прочее = получает лучший результат. И автором статьи проделана достаточно большая и сложная работа.
Это полноценное решение технической задачи:
получить результат (работа алгоритма)
оптимизировать получение результатам (в данном случае по времени)
Т.е. работодатель в тестовом задании на проверку уровня знаний кандидата хочет получить реально работающее решение для сложной задачи?
Процесс разработки у заказчика так построен - что бы сразу программист писал эффективный и правильный код? Замена тестирования (решения сложной задачи) на талантливого программиста? Пусть сразу сделает на отлично?
Какая то опасная стратегия у заказчика. ИМХО.
в 1 млскнду ? это сколькже ваша программа жрет процессорного времени ? наверно в топе ....
врагу не пожелаешь такую использовать
Вообще тестовые задания, требующие больше 1-2 часов разработки должны оплачиваться.
Сколько вы часов на эту задачу потратили? В месяце 20 рабочих дней, в дне - 8 часов. Вот и подсчитайте на сколько денег вас пытается нагреть будущий "работодатель". По этой причине нормальный работодатель может вам два варианта предложить:
1. Тестовое задание + NDA + символическая оплата за него в 300-400$
2. Специфические для языка проверки + задачки с leetcode и ему подобные
Всё остальное - это как минимум не уважение чужого труда
Сначала небольшое уточнение. Дата никак не может быть числом в позиционной системе счисления из-за того, что в месяце переменное число дней. И "разряды" даты не являются элементами кольца вычетов, потому что 59+1 в кольце вычетов по модулю 60 даст честный 0 без всякого флага переноса. К счастью, на алгоритм ни одна из этих ошибок не повлияли, ведь алгоритму достаточно лексикографического порядка.
По поводу же битмапы против дерева. Пожалуйста, добавьте в сравнение производительности простой упорядоченный массив диапазонов, с двоичным поиском по нему. Асимптотика тут должна быть как у дерева, но накладных расходов будет меньше.
Я попробую и позже опубликую в проекте CronHabrDemo. На всякий случай, опишите подробнее предлагаемую Вами структуру. Чтобы у нас не было расхождений во взаимопонимании.
Но у меня есть подозрение, что битмап снова выиграет, ибо упорядоченный массив диапазонов заставит "скакать" по памяти, что сильно сказывается на производительности.
Чтобы не "скакать" по памяти, можно сделать отдельные массивы для начала диапазона и окончания (поиск будет только по первому массиву идти).
class BitMapMatcher implements DigitMatcher {
private final int[] mins, maxs;
// инициализацию как-нибудь сами
private int search(int value) {
// пишу реализацию сам, потому что у стандартного алгоритма возвращаемое значение убогое
int left = -1, right = mins.length - 1;
while (left < right) {
int i = (left + right + 1) / 2; // да, я знаю про переполнение, но тут никогда не будет более 500 элементов
if (mins[i] <= value)
left = i;
else
right = i-1;
}
return left;
}
public boolean match(int value) {
int index = search(value);
return index > -1 && value <= maxs[index];
}
public int getNext(int value) {
int index = search(value);
if (index > -1 && value < maxs[index])
return value+1;
if (index+1 < mins.length)
return mins[index+1];
// тут нечего возвращать
}
public int getPrev(int value) {
int index = search(value);
if (index > -1 && value > mins[index])
return value-1;
if (index > 0)
return mins[index-1];
// тут нечего возвращать
}
}Сделал Ваш реализацию. Скоро залью на гит. По предварительным прогонам такой класс хорошо обгоняет битмап на поиске (1:4), но чуть проигрывает на матчинге (20%). Гонял для расписания миллисекунд "1-10,12-18,21-30,941-1000".
А Вы крут, если в комментариях способны написать код, который сразу работает) Я думал: концепт, а-н нет - рабочая версия) Мой почтение.
Я думал изначально реализовать подобный класс, но отказался по следующим причинам:
диапазоны должны быть упорядочены по возрастанию
диапазоны не должны пересекаться
диапазоны должны быть заданы без шага
Но с другой стороны:
их можно отсортировать, после парсинга, когда построили модель
их можно объединять, если отказаться от шага != 1
если не отказываться от шага != 1, то тогда забить на п. 2
Нужно промерить при разных комбинациях расписания: процент заполнения, степень покрытия и "кучкования" значений. Найти оптимальные значения, при которых данный класс станет выгоднее.
В принципе, да, можно запилить.
Рабочий? Там в методе getPrev надо не mins[index-1], а maxs[index-1] возвращать было :-(
Забивать на непересекающиеся диапазоны нельзя, алгоритму они требуются. Проще представить каждый диапазон с шагом как серию диапазонов длины 1. Ну и если диапазонов получается где-то более 100 (число взято с потолка, как N / log N) — есть смысл перейти на битовую карту.
Я про ваш бинарный поиск) У меня всегда с ним не складывалось: с первого раза без ошибок написать не могу. Хотя часто применяю. А getPrev вылез бы на тестах, которые я пока не стал делать, удовлетворившись getNext для замеров скорости.
Я предварительно погонял новый класс сравнивая с BitMap. Что хочу сказать? При интервалах свыше 10-ти, уверено начинает лидировать битмап. При интервалах от 2-х до 4-х ваш класс сильно обгоняет битмап на поиске, но чуть проигрывает на матчинге. Другое кол-во ещё не гонял.
Найти параметры, при которых можно уверенно сказать, что тут лучше битмап, а тут нет - трудно.
На производительность обоих классов влияют:
процент заполнения всего диапазона значениями (например, для "0-99,900-999" - 20%)
количество диапазонов в списке (два, как в примере выше, четыре: "1-3,50-79,100-200,800-810")
распределение ("кучкование") чисел по диапазону (если они распределены равномерно, и средняя длина пробега от одного значения до другого скажем от 3-х до 5-ти, то битмапа выигрывает)
Так что тут ситуация: "и хочется, и колется". Можно скрестить ужа с ёжом: объединить классы HashMapMatcher и BitMapMatcher. У первого O(1) на поиск и матчинг. Но ограничение по длине диапазона (чтобы уместить в одну 64-битную переменную).
Если интересно, я чуть позже опубликую на гитхабе классы, которыми измерял. Чтобы Вы могли сами проверить. А то вдруг я просчитался.
Ветка list-matcher https://github.com/KaminskyIlya/HabrCronDemo/tree/list-matcher
Обидка. Я забил на парсер не потому что "там всё тривиально", а потому что
Ну, парсера не будет. На этом этапе я уже достаточно сильно подустал, да и не думаю, что смогу здесь сделать какую-то революцию.
Зачем так передергивать?
Перечитаю чуть позже, но взглядом по диагонали - откуда в моем решении взялось O(n) понять не могу.
// Increment until valid date
while (bool(*this) && !is_valid_date()) {
increment_date();
}У этого цикла максимум 9 итераций в феврале с неудачным днем недели. Полагаю, вы сделали подобные вычисления в своем
В самом худшем случае мы сделаем не более 6 итераций (на практике меньше).
И вообще в статье есть какая-то какая-то мешанина с теоретической оценкой сложности алгоритма (O - символика ландау) и тесты с бенчмарками.
Оценка сложности имеет смысл только при потенциально бесконечном росте объема входных данных. Это оценка скорости роста худшего времени работы алгоритма в зависимости объема входных данных. 7 раз это тоже O(n), где n - количество дней недели, и раз у нас не предвидится рост количества дней недели, то и подобный анализ не имеет смысла.
Касательно всего остального: скачал ваш репозиторий, сделал вот такой тест:
Schedule schedule = new Schedule("2021.*.23-27,29 0-3,5 12:00:00.1");
SimpleDateFormat f = new SimpleDateFormat("dd.MM.yyyy HH:mm:ss.SSS");
f.setTimeZone(TimeZone.getTimeZone("UTC"));
Date date = f.parse("24.02.2021 11:00:00.000");Первые 5 дат:
26.02.2021 12:00:00.001
28.02.2021 12:00:00.001
23.03.2021 12:00:00.001
24.03.2021 12:00:00.001
26.03.2021 12:00:00.001
Однако 28 число не подходит под расписание. В вашем коде есть ошибки. Это просто первый пример, на который можно наткнуться при диагональном прочтении кода.
Тем не менее, заметка как минимум достойна внимания, с большим удовольствием прочитаю ее досконально, когда будет время. Спасибо за труд!
Вот еще случай для тестирования - так называемые дополнительные секунды: https://ru.wikipedia.org/wiki/%D0%94%D0%BE%D0%BF%D0%BE%D0%BB%D0%BD%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%B5%D0%BA%D1%83%D0%BD%D0%B4%D0%B0
Что упоминалось, кстати, еще у @PsyHaSTe.
Но в примере, который я привел, нет вообще ничего неординарного - обычный февраль...
У меня просто с самого начала закралось подозрение, что метод целиком не рабочий. Но чтобы сделать такое смелое заявление, нужно очень хорошо разобраться, что именно зашито внутри. Поэтому я быстро сконструировал контрпример, и пока успокоился.
Отдельные проблемы с лишними секундами можно будет потом пофиксить, если в целом концепция рабочая. Хотя от "священного Грааля" ожидаешь большего.
Коллега, Вы изумительны! Прочитать по диагонали статью, до конца не разобравшись в коде, найти ошибку! Снимаю шляпу.
Исправил: ошибка была в классе LastDayOfMonthProxy:
public boolean hasNext(int value)
{
return value < getHigh()
}public boolean hasNext(int value)
{
return value < getHigh() && match(getNext(value));
}Уже после публикации статьи, прочитывая код нашел ещё одну ошибку. Как говорил @PsyHaSTe "копипаста - зло".
Исправлю, опубликую фикс.
откуда в моем решении взялось O(n) понять не могу.
Допускаю, что где-то промахнулся в своих изысканиях. Не смог реализовать ваш алгоритм, ибо специфика C++.
А попробуйте, пожалуйста, такие расписания:
"*.02.29 6 12:00:00" для даты "01.01.2021 12:00:00.000" (ожидается "29.02.2048 12:00:00.000")
"*.*.27-32/2 1 12:14:34" для даты 31.01.2021 12:14:33.177 (ожидается "29.03.2021 12:14:34.000")
"*.*.20-32/5 5 12:14:34" для даты "31.01.2021 12:14:33.177" (ожидается "30.04.2021 12:14:34.000")
И померьте скорость, увеличивая начальную дату с шагом в секунду/миллисекунду/час.
в который раз убеждаюсь, что какие то не адекватные работодатели.
тестовое задание - это минимум задачка из универа, по лабораторной, для всего остального есть ТК. А не "дипломный проект" как у автора выше.
Интересная задача, согласен, даже хочется попробовать свои силы, пока у меня есть один вопрос по условию.
В расписании можно задавать интервалы с шагом, например 10-20/4 или */5, и мне кажется для пользователя будет вполне естественно задать любое количество пересекающихся интервалов с шагом, например так 10-20/4, 15-19/2, */5, судя по коду в статье эта ситуация не поддерживается.
Поддерживается. Есть, например, такой тест: "*.*.* * *:*:*.1,2,3-5,10-20/3". Посмотрите все тесты.
Для таких случаев используются HashMapMatcher и BitMapMatcher.
Не читал ни условий задания, ни решений. Но вот наличие аж 7ми проверок заставила написать этот комментарий.
Берём 64битное число 1-ms интервалов, прошедших с даты X (кто-то может уже подчерг схожесть с SYTEM_TIME из мира windows). Парсим даты в него. Всё!
Сравнение - одна операция. Определение длительности между двумя датами - тоже одна операция. Текущее время - число тиков с момента старта системы, приведенное к выбранной базе.
Явно, что не читали. У вас нету двух дат. У вас есть расписание и начальная дата, и вам надо сгенерировать следующую дату. И в чём вам здесь поможет 64-битное число?
Делал давно что-то вроде RTOS для 80186-совместимых контроллеров, именно INT64-счетчик миллисекунд от старта системы был удобен для планировщика.
Для отложенных событий (обычно это было пробуждение заданного потока в заданный момент времени) вычисляется будущее время срабатывания и соответствующая запись добавляется в сортированный по возрастанию времени список. Вот соответствующий старый код, не особо читаемый.
В таймерной функции планировщика просто в цикле, пока время первой записи списка <= текущему времени, отрабатываем и удаляем голову списка (например, пробуждаем все потоки, которые должны проснуться в текущую миллисекунду). С частотой 1000Гц нормально всё планировалось на не особо быстром CPU.
Арифметика же на датах - это, имхо, скорее академическая задача, чем то, что нужно реализовывать на практике.
Так ведь в задаче весь цимус в том, что нужно как-то перевести птичий язык крона в юникстайм, с учётом високосных годов, часовых поясов, коррекций UTC и прочего ада. Если была бы задача складывания двух интов, то проблемы бы не было.
Я к тому, что в практической задаче, наверное, следовало бы вынести сложную арифметику дат из цикла/таймера планировщика, и работать с сортированным списком int64-таймстампов следующих срабатываний записей. При срабатывании записи вычислять время следующего её срабатывания и опять добавлять в список.
Тогда каждый тик планировщика обычно обходился бы в O(1) и не потребовалась бы сверхоптимизация арифметики дат.
Описанный в исходной задаче API видится избыточным и ограничивающим достижимую производительность, ведь для реальной задачи реализации высокопроизводительного планировщика, имхо, хватило бы одного метода вида "получить DateTime следующего срабатывания по заданной маске относительно текущего DateTime".
Если рассматривать как чисто академическую задачу - тогда вопросов никаких)
Полностью поддерживаю, реальный планировщик, разумеется, должен питаться рафинированными таймстемпами, а парсер в реальном мире может быть сколь угодно медленным в пределах разумного. В задании ведь ни слова о том, что нужно очень быстро парсить крон.
Откуда, когда и как получать этот сортированный список int64-таймстампов? Вы в момент создания расписания не знаете начальной даты, от которой считать следующую надо. А расписание может генерировать событие каждую миллисекунду. Предлагаете весь этот неопределённый диапазон в памяти держать?
получить DateTime следующего срабатывания по заданной маске относительно текущего DateTime
То есть, вместо того, чтобы один раз распарсить строку расписания при создании объекта расписания вы предлагаете делать это при каждом тике? Что-то не вижу в таком подходе ничего высокопроизводительного.
При срабатывании записи вычислять время следующего её срабатывания и опять добавлять в список.
Сюрприз, ровно об этом эта и (почти) все предыдущие статьи и были :)
Откуда, когда и как получать этот сортированный список int64-таймстампов? Вы в момент создания расписания не знаете начальной даты, от которой считать следующую надо.
В конце каждого дня просчитывать на следующий день.
Вообще вы правы, конечно, задача в посте поставлена так, что в ней нет никаких ограничений. В реальном мире было бы понятно, что это за события, сколько их на самом деле будет. Если это реально система, генерирующая события с миллисекундной частотой по миллиону расписаний, то скорее всего, на нее не пожалели бы памяти, чтобы сделать ее максимально реалтаймовой.
А расписание может генерировать событие каждую миллисекунду
Зачем? Постановка задачи тупая. Если вам нужен быстрый крон, то он должен знать момент события, а не вычислять его каждый раз. А точные моменты из расписания должны вычисляться заранее, тогда уже особо не надо время экономить. Эта задача - пример плохого проектирования ПО.
Для этого есть генератор (см. конец статьи). Судя по бенчмаркам - генерирует следующее значение за 100нс. Но это, повторюсь, на моем компьютере и это Java, а не ассемблер.
Обратите внимание, что getNextEvent работает в среднем за 500нс, а next() у генератора, использующего точно такой же алгоритм - за 100нс.
Очередное подтверждение, что производительность сильно падает на Григорианском календаре, который я уже и так оптимизировал, пожертвовав некоторой точностью.
Если в посте подразумевался порядок по датам публикаций, то он таков (одна статья вами пропущена https://habr.com/ru/post/587748/ ?): @novar, @PsyHaSTe, @cadovvl, @mvv-rus
Прошу прощения, заработался, не увидел вашу статью в потоке.
PS Надеюсь-таки побороть свою лень и дописать еще одну статью на ту же тему — про решение того же тестового в стиле «старого доброго ООП». Точнее, само решение практически сделано и даже лежит на Github. Если кому-нибудь интересно, могу дать ссылку: там уже не полработы, а почти вся работа сделана, так что можно уже всем показывать. Но та статья посвящена другому аспекту кода — простоте, краткости и потенциальной расширяемости (ибо подозреваю, что именно это работодатель на самом деле и хотел увидеть в решении), а потому там про бенчмарки ничего нет. Про оптимизацию на уровне алгоритма — немного есть, но без цифр об оптимизации говорить смысла нет.
Положим в расписании задано время *:*:30-59. Внешняя функция, вызывающая наш планировщик получила текущую системную дату, которая была синхронизирована с мировым временем и мы имеем такое: 23:59:60.000. Т.е. та самая високосная секунда +1. Но выше мы уже определили: что в расписании указано, то и допустимо. Поэтому секунда с номером 60 недопустима. Возвращаем дату следующего события, на секунду больше: +1 00:00:00.000.
Но расписание требует секунды от 30 до 59, а вы возвращаете 0.
А вот подловили) Я ошибся, конечно. По расписанию правильнее вернуть +1 00:00:30.000. И мой алгоритм вернёт, и реализации других авторов - вернут ровно тоже.
Если использовать родную реализацию Грегорианского календаря в C# и Java (javascript, php), они вам не позволят установить 60-ю секунду: автоматически приведут дату к следующему часу. На этом у некоторых в javascript основана техника определения максимальной даты в месяце: устанавливаем 0-е марта и, вуаля, получаем последний день февраля.
В моей кастомной имплементации календаря, можно установить 60-ю секунду. Но тут сработает матчер расписания, заставив сбросить на "ноль". А нулем у нас здесь будет "30".
Прекрасная статья, побольше бы таких на хабре. Автору респект и большое спасибо!
А тут не будет "решением по умолчанию" priority queue? Ну там, бинарная куча (но вообще в Java она, наверное, есть в стандартной библиотеке)?
Потому как хэши и всё такое – думать надо, а тут сходу log(N), редко когда есть необходимость оптимизировать дальше.
Ультра быстрый Cron с шагом в миллисекунду, или когда тестовые задания такими прикидываются