Ультра быстрый Cron с шагом в миллисекунду, или когда тестовые задания такими прикидываются17.11.2021 10:01

Давным-давно наш коллега @novarразместил на Хабре статью с описанием вот такого незатейливого ТЗ, полученного им от потенциального работодателя:

Реализовать класс для задания и расчета времени по расписанию. Расписание задано в стиле crontab (точный формат см. во вложении), требуется находить ближайшие в будущем или прошлом моменты, попадающие в это расписание. Обращаю Ваше внимание, что класс должен быть эффективным и не использовать много памяти и ресурсов даже тогда, когда в расписании задано много значений. Например очень много значений с шагом в одну миллисекунду.

Я бы прошел мимо, и уж тем более не стал бы писать целую статью (!), если бы не несколько но:

• тестовое только с виду выглядит простым

• автора с его работой работодатель грубо «послал»

• автор, а затем и @PsyHaSTe, предложили не самый оптимальный алгоритм

• да просто тот случай, когда тестовое зацепило

Хочу предложить алгоритм, приближающийся к O (1) во всех возможных ситуациях, вместо оригинального O (n). Интересующихся прошу под кат.

Ах да. Если вы тот самый работодатель, вот готовый код под ваше ТЗ. Правда на Java, а не на C#. Но вы же не думали, что всё будет так просто?

Исходное задание от работодателя

using System;

namespace Test
{

	/// 

	/// Класс для задания и расчета времени по расписанию.
	/// 
	public class Schedule
	{
		/// 

		/// Создает пустой экземпляр, который будет соответствовать
		/// расписанию типа "*.*.* * *:*:*.*" (раз в 1 мс).
		/// 
		public Schedule()
		{
		}

		/// 

		/// Создает экземпляр из строки с представлением расписания.
		/// 
		/// Строка расписания.
		/// Формат строки:
		///     yyyy.MM.dd w HH:mm:ss.fff
		///     yyyy.MM.dd HH:mm:ss.fff
		///     HH:mm:ss.fff
		///     yyyy.MM.dd w HH:mm:ss
		///     yyyy.MM.dd HH:mm:ss
		///     HH:mm:ss
		/// Где yyyy - год (2000-2100)
		///     MM - месяц (1-12)
		///     dd - число месяца (1-31 или 32). 32 означает последнее число месяца
		///     w - день недели (0-6). 0 - воскресенье, 6 - суббота
		///     HH - часы (0-23)
		///     mm - минуты (0-59)
		///     ss - секунды (0-59)
		///     fff - миллисекунды (0-999). Если не указаны, то 0
		/// Каждую часть даты/времени можно задавать в виде списков и диапазонов.
		/// Например:
		///     1,2,3-5,10-20/3
		///     означает список 1,2,3,4,5,10,13,16,19
		/// Дробью задается шаг в списке.
		/// Звездочка означает любое возможное значение.
		/// Например (для часов):
		///     */4
		///     означает 0,4,8,12,16,20
		/// Вместо списка чисел месяца можно указать 32. Это означает последнее
		/// число любого месяца.
		/// Пример:
		///     *.9.*/2 1-5 10:00:00.000
		///     означает 10:00 во все дни с пн. по пт. по нечетным числам в сентябре
		///     *:00:00
		///     означает начало любого часа
		///     *.*.01 01:30:00
		///     означает 01:30 по первым числам каждого месяца
		/// 
		public Schedule(string scheduleString)
		{
		}

		/// 

		/// Возвращает следующий ближайший к заданному времени момент в расписании или
		/// само заданное время, если оно есть в расписании.
		/// 
		/// Заданное время
		/// Ближайший момент времени в расписании
		public DateTime NearestEvent(DateTime t1)
		{
		}

		/// 

		/// Возвращает предыдущий ближайший к заданному времени момент в расписании или
		/// само заданное время, если оно есть в расписании.
		/// 
		/// Заданное время
		/// Ближайший момент времени в расписании
		public DateTime NearestPrevEvent(DateTime t1)
		{
		}

		/// 

		/// Возвращает следующий момент времени в расписании.
		/// 
		/// Время, от которого нужно отступить
		/// Следующий момент времени в расписании
		public DateTime NextEvent(DateTime t1)
		{
		}

		/// 

		/// Возвращает предыдущий момент времени в расписании.
		/// 
		/// Время, от которого нужно отступить
		/// Предыдущий момент времени в расписании
		public DateTime PrevEvent(DateTime t1)
		{
		}
	}
}

Многие не очень любят делать тестовые задания. И ваш покорный слуга — не исключение. Но! Сложные и интересные задачки только раззадоривают программистов!   Некоторые — вообще тянут на олимпиадные. А кто из вас не любит такие решать?

На первый взгляд кажется, что всё просто: сделать планировщик «а-ля крон». Вот только несколько нюансов на порядок увеличивают сложность аналогичной задачи.

• Наличие в расписание миллисекунд и возможность шага в 1 мс (!) А значит придется планировщику работать за гораздо меньшее время.

• Требование наиболее оптимального расхода памяти и эффективности (большинство сошлось во мнении, что это для функций из группы NearestEvent)

• Волшебная константа 32 — для обозначения последнего дня любого месяца

• Нами «любимые» високосные годы

А в чём проблема?

Автор оригинальной честно всё выполнил: реализовал работоспособный класс, написал модульные тесты, просчитал худшее и среднее время выполнения (я усомнюсь, что правильно).

Короче, «полный фарш» и «под ключ». Как минимум, тест на джуна прошел. А то и на мидла. Сомнений нет. Но от ревьювера внезапно пришел крайне едкий комментарий: «Ваш код говно!».

Обидно такое слышать. Тем более, когда потратил 6–8 часов на реализацию. Ведь работает же! В чувствах @novar обратился к нам: «помогите понять: что не правильно?». И жители Хабра откликнулись: раз @PsyHaSTe и, даже, два @cadovvl.

Реализация от @PsyHaSTe прекрасна. Довольно практично. В меру лаконично. Так пишет промышленный программист с большим опытом. Стиль узнаваем. Мне до него далеко. Но есть проблема: второй автор, сконцентрировавшись на красоте и читабельности кода, совсем забыл про алгоритм.

Следующий участник @cadovvlзабил на парсер (ибо там всё тривиально), и сконцентрировался на алгоритме, технически доведя его до O (1). Как результат, снизил время выполнения с 12 мкс до 300–500нс. Единственная слабость нового алгоритма — дни недели. В некоторых случаях они могут существенно его замедлить, вырождаясь в некрасивый O (n).

Наконец, ниже я приведу ещё один алгоритм, который практически не имеет слабых мест и устойчив по времени выполнения. Даже для самых изощрённых расписаний. Но сначала

Немного теории

На Хабре нередко вспыхивают споры: «нужна ли программисту математика?». Я предпочитаю держаться в стороне от бурления говн жарких дискуссий, предпочитая больше коллекционировать для себя примеры, где без математики худо. И это — не компьютерная графика, нейронные сети, звук или видео. Здесь как раз-таки всё и так понятно. А вот это задание — тот самый пример, когда знания математики пригождаются.

Что нам понадобится сегодня? Теория чисел! Нет мы не будем использовать малую теорему Ферма, символы Лежандра или функцию Мёбиуса. Но вот классы вычетов по модулю и некоторое понимание позиционных систем счисления нам пригодятся.

 Давайте посмотрим внимательно на дату. Отбросим пока дни недели. Запишем компоненты даты в порядке: год, месяц, день, час, минута, секунда, миллисекунда: YMDhmsn. Формат часто используется на практике (иногда добавляются разделители): базами данных, системами логгирования и прочими. Такая запись позволяет упорядочивать даты по возрастанию/убыванию также легко, как это мы делаем со строками.

Вам ничего не напоминает? Да это же 7-ми разрядное число позиционной системы счисления со специфическими свойствами! Специфика же тут в том, что каждый разряд имеет свое индивидуальное основание и работает в своем, индивидуальном кольце, образованном классом вычетов по модулю. Да и границы вычетов могут начинаться не с 0, как это принято в теории чисел. Ещё и модуль у некоторых разрядов плавающий (день месяца, неделя года).

Например, час принадлежит классу вычетов, образованных модулем 24. Секунды и минуты — классу вычетов по модулю 60.

Математики поправят меня, что у нас не кольца. Ибо операций умножения у нас нет. Зато есть сложение. И мы можем прибавлять или вычитать единицу (любое целое) к любому разряду, получая новые всегда корректные значения дат (доказательство сего факта оставим читателю) .

Кроме того

Мало того, такие операции, как и положено в позиционной системе, каскадно влияют на старшие разряды. Если в младшем происходит переполнение, то он возвращается на условный »0» (или на условные »9» при вычитании), а старший также инкрементируется (декрементируется). И по цепочке вверх.

Некоторые разряды имеют имена собственные (месяцы, дни недели). Но главное свойство позиционной системы у них сохраняется: «цифры» разрядов упорядочены на «числовой» оси; представлены в множестве только один раз; все «цифры» различны.

Задачи для самостоятельного решения

Всё это и делает нашу дату, именно числом позиционной системы счисления! Пусть и с «особенностями». А что дает нам такое знание?

Во-первых, правило сравнения, аналогичное правилу сравнения обычных многоразрядных чисел.

Как мы сравниваем многоразрядные числа в позиционной системе счисления? Двигаемся от старшего к младшему до тех пор, пока сравниваемые разряды эквивалентны. Если не эквивалентны — можно заканчивать: результат сравнения первых расходящихся разрядов и есть результат сравнения чисел в целом. На младшие разряды можно не смотреть (пусть читатель вновь докажет это самостоятельно, решив задание № 2).

Для семиразрядных чисел нам потребуется в худшем случае 7 проверок. Отлично. Учтём.

Во-вторых, правила сложения и вычитания.

Как происходит сложение какого-либо разряда с единицей? Да так же, как и с обычными натуральными числами. Но если в разряде происходит переполнение, то он возвращается на условный »0» (минимум), а при вычитании — на условные »9» (максимум); более старший же разряд инкрементируется / декрементируется. И по цепочке вверх.

Но повторимся: переполнение влияет на разряды выше, не трогая младшие. Этот незатейливый факт мы отметим, и используем позже в алгоритме поиска.

Инкремент семиразрядных чисел заставит в худшем случае выполнить 7 операций сложения.

Итак, у нас «наклёвывается» алгоритм, с худшей сложностью 14 операций (сравнить/сложить). Очень не плохо.

Новый алгоритм

Если бы наша задача была в том, чтобы только сравнить две даты и вернуть на 1 мс большую / меньшую, то проблем бы не было. Но наша исходная задача несколько сложнее. То что, у даты в некоторых разрядах модуль плавает — это пол беды. У нас есть ещё и расписание, которое «фильтрует» некоторые цифры в разрядах. И не всякая «валидная» дата становится «валидной» с таким фильтром. Переводя на язык множеств — совокупность дат, принадлежащих расписанию, является подмножеством всех возможных дат.

Нам нужно, как-то хитро научиться работать с цифрами разрядов. А именно:

• определять, что цифра не вышла за допустимые границы своего «кольца» (принадлежит множеству)

• определять, что цифра принадлежит допустимым значениям расписания (принадлежит подмножеству)

• возвращать следующее и предыдущее значение с учетом расписания и флаг переполнения

И если мы решим эти задачи, то операция поиска ближайших (или равных) дат в расписании сведется к сравнению или инкременту чисел нашей нестандартной позиционной системы счисления! Ну, а число таких операций мы уже подсчитали — 14 в худшем случае.

Проще говоря, нам нужен функционал, который можно описать таким интерфейсом:

interface DateElementMatcher
{
	// проверяет соответствие элемента календаря расписанию
	bool match(int value);
	// проверяет, не выходит ли значение за рамки элемента
	bool inBounds(int value);
	// получение следующего значения элемента календаря и флаг переполнения
	(bool, int) getNext(int value);
	// получение предыдующего значения элемента календаря и флаг переполнения
	(bool, int) getPrev(int value);
}

Я буду далее называть класс, реализующий данный интерфейс — матчером.

Есть правда, ещё одна сложность, с которой мы столкнёмся — количество вариантов, которым может быть задано расписание каждого элемента. Напомним, что значения элемента могут быть даны через запятую списком как отдельных чисел (10,11,12), так и их диапазонов (10–12,15–17,20–23), так и диапазонов с шагом (1–10/3,20–29/2). Помимо этого есть ещё диапазон звездочка (*) и звездочка с шагом (*/4). Только звездочка всегда задается вне списка (ибо покрывает весь диапазон значений).

Каждый способ задания расписания имеет свои особенности, позволяющие быстро решать задачи интерфейса DateElementMatcher.

Ну например, если расписание элемента задано в форме */4, то, например функция матчинга и поиска следующего значения упрощается до модульной арифметики:

match = function (x) => x % 4 == 0
next = function (x) => x — (x % 4) + 4

Согласитесь, это много лучше, чем проверять и искать по массиву. Сложность обоих операций — О (1).

Про расписание, заданное одним единственным числом или звездочкой — и говорить не приходится. Эти же операции вообще вырождаются в простое сравнение и инкремент. Про значения, заданные в форме интервала, тоже говорить не стоит. Всё тривиально.

Пусть RangedMatcher — это матчер, который мы сделаем вот для таких простых расписаний.

Чуть сложнее с расписаниями, заданными списками: 10,15–18,20–26/3,*/17. Тут нам придется выбирать, какую структуру оптимальнее всего использовать: простой массив (Array) или битовая карта (BitMap), хеш-таблица (HashMap), двуноправленный сортированный список на основе дерева (NavigableSet) или тупо комбинированный список из RangedMatcher (по такому пути пошел @cadovvl). Каждый из них имеет свои минусы и плюсы и должен быть применен «к месту», с учетом прожорливости по памяти и быстродействию.

Автор оригинальной статьи выбрал Array для всех ситуаций, включая тривиальные. Что не совсем оптимально по памяти и скорости. Я же предлагаю подойти к вопросу выбора матчера более щепетильно.

Например, диапазон 0–59 можно представить 60-байтным массивом, а можно 64-битной переменной. Операция проверки значения будет эквивалентна операции проверки бита, но вот поиск ближайших придется вести в цикле. Здесь сложность матчинга О (1), а получение ближайшего — О (n).

Вроде бы хорошо. Вот только O (n) для поиска ближайшего. А можно за О (1)? Можно. Для этого нам придется построить свою хеш-мапу на основе 64-битной переменной с двумя дополнительными массивами: массив индексов следующих элементов (next) и массив индексов предыдущих допустимых элементов (prev).

Суть проста. Пусть для расписания »1,3,4,51» в минутах нас просят найти ближайшее большее значение для 9-й минуты. Мы обращаемся к 9-му элементу массива next и сразу получаем готовый результат 51. Сложность О (1). Если выделить для каждого индекса 1 байт, то нам понадобиться максимум 120 байт на все возможные значения. Не так плохо. Но это сработает только для: дней, месяцев, минут, секунд, часов.

Для миллисекунд, с их возможным коварным разбросом значений 0–1000, лучше вернуться к BitMap и NavigableSet. Ну и для годов тоже. Хотя в реальности год вряд ли будет задаваться хитрее, чем *.

Вначале проектирования, я был уверен, что BitMap хорошо подойдет для случаев, когда покрытие диапазона возможных значений составит не менее 20% (каждый пятый); тогда цикл поиска следующего значений совершал бы в среднем не более 5 итераций (при условии однородности заполнения). А когда число возможных значений в списке меньше (или есть неоднородности), то я думал, что лучше использовать NavigableSet (дерево). И действительно, первый имеет сложность на поиск ближайшего O (N), а дерево — O (log N).

Внезапно, оказалось, что BitMap уделывает NavigableSet во всех случах. Даже когда в 1000-й карте только 1 бит установлен! На практике (для дерева) в этом убедился и @lam0×86. Так что от матчера типа «дерево» пришлось отказаться. Это выявили специальные бенчмарки.

А почему дерево друг медленнее списка?

Итак, я предлагаю реализовать всего 3 типа матчеров:

• RangedMatcher — для простых расписаний, заданных одиночным числом или диапазоном, или диапазоном с шагом или звездочкой или звездочкой с шагом;

• HashMapMatcher — для списков расписаний, заданных для дней, месяцев, минут, секунд, часов;

• BitMapMatcher — для списков расписаний, заданных для года и миллисекунд.

На самом деле

Итак. Есть 3 эффективные стратегии работы с элементами дат. Применим магию ООП: для каждой стратегии — свой матчер с единым интерфейсом.  Тогда основной алгоритм поиска дат в расписании мы можем написать так:

1. Берем текущую дату и по-разрядно от старшего к младшему проверяем на соответствие расписанию (функция match нашего интерфейса) до тех пор пока есть соответствие. Здесь мы либо упрёмся в миллисекунды (за 7 шагов), либо выйдем раньше, ибо ! match.

2. Если на 1 м этапе проверка не прошла, мы просим матчер найти ближайшее (функции next/prev). Если таковое есть — сбрасываем остальные разряды нашего числа на условный »0» (или »9») и возвращаем полученную дату. Если нету — сообщаем, что у нас «переполнение» и переходим к п. 3.

3. Если у нас хоть раз произошло «переполнение» в каком-то разряде, мы поступаем следующим образом: переходим к старшему разряду, сбрасывая все младшие на »0» (»9»), и пытаемся прибавить/отнять единицу к старшему разряду (функции next/prev матчера). Здесь мы либо получим готовый результат, который возвращаем, либо опять переполнение. Повторим п. 3 до самого старшего разряда (7 шагов).

4. Наконец вспомним про миллисекунды. Добравшись до них в п. 1, мы либо сразу возвращаем полученную дату (если нам можно вернуть эквивалентную), либо увеличиваем их на единицу (next/prev). Если у нас не было переполнения — сразу возвращаем итоговый результат. Если было — идем к п. 3.

Вот теперь всё готово для реализации нового алгоритма.

Относительно особых дат

От слов к делу

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

private Date findEvent(Date date, SearchMode mode)
{
    GregorianCalendar calendar = new GregorianCalendar();
    calendar.setTime(date);
    CalendarDigits digits = new CalendarDigits(pool, calendar, mode.toZero());

    while ( isCanSearchDown(digits, calendar, mode.canEqual()) )
    {
        digits.next();
    }

    return calendar.asDate();
}

private boolean isCanSearchDown(CalendarDigits digit, GregCalendar calendar, boolean canEqual)
{
    int value = digit.getValue(); // текущая цифра календаря

    if ( digit.isBelow(value) ) // текущее значение цифры календаря ниже минимально возможной границы в расписании
    {
        digit.initialize(); // сбросим на «0» эту и младшие цифры
        return false; // и завершим поиск
    }

    if ( digit.isAbove(value) ) // текущее значение цифры календаря выше максимально возможной границы в расписании
    {
        digit.prev(); // перейдем к более старшему разряду, увеличим его на 1, а младшие сбросим
        digit.increment();
        return false; // и завершим поиск
    }

    // текущее значение в пределах границ; но всё ещё может не соответствовать расписанию
    if ( digit.match(value) && calendar.isCorrect() ) // соответствует
    {
        boolean isLast = digit.isLast();

        // если это самая младшая цифра календаря (миллисекунды), и нам разрешено вернуть эквивалентную исходной дату, закончили поиск
        if ( isLast && canEqual ) return false;

        // продолжаем поиск для младших разрядов
        if ( !isLast ) return true;
    }

    // текущее значение цифры в пределах границ; но не соответствует расписанию
    digit.increment();// получим следующее значение для цифры из расписания, а младшие сбросим на «0»
    return false; // и завершим поиск
}

Смотрите, каким элегантным стал наш поиск. Да это цикл. Но он имеет фиксированное число итераций: 7 вперед. Определяется это, как вы догадались, числом цифр календаря. Были бы микросекунды, ничего бы не поменялось. Ну 8 итераций.

Можно было бы вообще развернуть цикл в линию. Но это привело бы к дублированию кода. Теперь вы понимаете, что цикл здесь не потому, что он требуется алгоритмом, а для того сократить код?

Хорошо. Но мы пока обошли вопрос:, а как быть с расписанием дней недели?

Как верно заметил @cadovvl, дни недели находятся на одном уровне с датой и не влияют на время. Т.е. время как бы само по себе, а дата — отдельно.

Я решил, что лучший вариант — это, после завершения основного цикла поиска даты, выполнить дополнительный поиск подбора подходящего дня недели:

private Date findEvent(Date date, SearchMode mode)
{
    GregorianCalendar calendar = new GregorianCalendar();
    calendar.setTime(date);
    CalendarDigits digits = new CalendarDigits(pool, calendar, mode.toZero());

    while ( isCanSearchDown(digits, calendar, mode.canEqual()) )
    {
        digits.next();
    }

    return fixWeekDay(digits, mode);
}

private Date fixWeekDay(CalendarDigits digits, SearchMode mode)
{
    Calendar calendar = digits.getCalendar();
    CalendarElement element = new CalendarElement(Calendar.DAY_OF_WEEK, calendar);

    while ( !weekDay.match( calendar.get(Calendar.DAY_OF_WEEK), element ) )
    {
        digits.gotoDay(); // перейдем к цифре «день месяца»
        digits.increment(mode.toZero());// и сделаем инкремент до следующего значения из расписания
    } // пока день недели не сойдется с расписанием

    return digits.getAsDate();
}

Да это цикл. Но как говорил @cadovvl — это другое. Хотя. я бы тут поспорил. Почему? Читайте ниже.

Битва алгоритмов

Думаю, что именно за выбранный алгоритм @novarполучил крайне низкую оценку. Задача решена им тупо «в лоб». Выбранный способ поиска дат прост до безобразия. Вся реализация, как и просили — в одном классе. Несколько громоздко, зато удобно. Но не торопитесь делать поспешных выводов.

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

Во-вторых, не смотря на простоту, алгоритм @novarустойчив. Мой же потребовал специальных усилий для стабилизации результатов на всяких 29-х февраля, хаков и трюков (см. реализацию класса CalendarDigits из пакета com.habr.cron.ilya).

Наконец, задача только выглядит как гипотеза Коллатца. А эффективное решение найти оказалось не просто.

Временная сложность выполнения алгоритма от @novar и @PsyHaSTeсоставляет O (N). Это хорошо видно на графиках зависимости времени выполнения функции getNextEvent от входного аргумента, при его последовательном приращении:

А вот такие же графики предлагаемого алгоритма:

Как видно, наклон усредненной линии ближе к горизонту, что свидетельствует о том, что мы приблизились к сложности O (1), стабилизировав скорость работы.

Давайте приведу сравнительные замеры по алгоритмам (в моем проекте вы можете запустить соответствующий «бенчмарк» из пакета speed):

[NoVar] */4.01.01 12:00:00.000 2012.01.01 12:00:00.001  - 120500 nsec
[Ilya] */4.01.01 12:00:00.000 2012.01.01 12:00:00.001  - 3749 nsec
[NoVar] *.*.* *:*:*.* 2021.30.09 12:00:00.002  - 1070 nsec
[Ilya] *.*.* *:*:*.* 2021.30.09 12:00:00.002  - 1207 nsec
[NoVar] *.4.6,7 * *:*:*.1,2,3-5,10-20/3 2001.01.01 00:00:00.000  - 6713 nsec
[Ilya] *.4.6,7 * *:*:*.1,2,3-5,10-20/3 2001.01.01 00:00:00.000  - 2383 nsec
[NoVar] *.4.6,7 * *:*:*.1,2,3-5,10-20/3 2080.05.05 12:00:00.000  - 13310 nsec
[Ilya] *.4.6,7 * *:*:*.1,2,3-5,10-20/3 2080.05.05 12:00:00.000  - 3948 nsec
[NoVar] 2100.12.31 23:59:59.999 2000.01.01 00:00:00.000  - 207159 nsec
[Ilya] 2100.12.31 23:59:59.999 2000.01.01 00:00:00.000  - 3584 nsec
[NoVar] 2100.12.31 23:59:59.999 2080.05.05 00:00:00.000  - 141051 nsec
[Ilya] 2100.12.31 23:59:59.999 2080.05.05 00:00:00.000  - 4075 nsec

Дисклеймер

Как и ожидалось, новый алгоритм поиска ближайшей даты значительно опережает по скорости оригинальный авторский от @novar и @PsyHaSTe. Время выполнения в некоторых (не самых крайних) случаях сократилось со 120 мкс до 1–4 мкс на моём 3Гц процессоре. Не плохо, подумал я. Собственно, этого и следовало ожидать: алгоритмическая оптимизация дает самый большой выигрыш по скорости.

Подобная реализация алгоритма от @cadovvl была в среднем до 12 раз быстрее. Но я подумал: «Это же C++! Чего с ним тягаться?». На чистом ассемблере, мне удалось бы свести алгоритм к считанным тактам, и тогда я вышел бы на десятки наносекунд. Только на нём можно точно спрогнозировать время выполнения вашей функции, когда можешь точно посчитать такты. А вот с Java предсказывать что-либо очень трудно. Разброс в измерениях одной и той же функции такой, что тут в пору верить во влияние фаз луны и популяций перепелов.

Но я вам скажу: рано пить «Боржоми» и праздновать победу.

Белая магия оптимизаций

Но вот незадача. В одном случае @novarвсегда был быстрее моего алгоритма: когда ближайшая дата на 1 мс меньше текущей.

Странно, оба алгоритма совершали одинаковое число проверок (7 — мой, 9 — от @novar). Казалось бы, мой алгоритм должен быть даже чуть быстрее. Ну хоть капелюшку. Но нет, замеры убедительно показывали, что @novarвсегда «уделывал» меня. Вот результаты типичного прогона:

[NoVar] *.*.* *:*:*.* 2021.30.09 12:00:00.002  - 1070 nsec
[Ilya] *.*.* *:*:*.* 2021.30.09 12:00:00.002  - 1207 nsec

Признаться, это закусывало. А что если подобный кейс будет самым частым? Получается простая реализация «уделывает» непростую? Стоило ли тратить время, проводить исследования, писать эту статью? Всё пропало. Да и вообще, как это алгоритм O (N) уделывает O (1)? Непорядок!

Тогда я стал выяснять, на что тратится время больше всего. С профайлером возиться не стал; поступил проще: просто отключал те части кода, которые считал подозрительными.

Странно, но на время выполнения функции эти манипуляции вообще никак не влияли. Ну т.е. как-то влияли, но из-за разбросов в измерениях этого было не видно. JVM она такая. Я уже было отчаялся, но затем, полностью отключил алгоритм поиска, тупо возвращая входную дату. Сюрприз меня поджидал не там, где я его караулил. Даже после такого наглого хода, моя функция, по-сути ни делая ничего, тратила столько же времени, что и раньше! Как так? Магия?

Не совсем. Я закоментировал не весь код функции. Остался вот такой «безобидный» кусочек:

Calendar calendar = new GregorianCalendar();
calendar.setTime(time);

Вот это да! Оказалось, что львиную долю времени исполнения отъедала родная java-имплементация Грегорианского календаря (GregorianCalendar)! А собственно, почему бы и нет?

Дело в том, что вы не можете в Java создать экземпляр грегорианского календаря, сразу же инициализировав его требуемой датой. Вначале он инициализируется системной датой, потом уже той, которой вы захотите. Ну такой вот интерфейс. Но при инициализации датой, календарь «распаковывает» её unix-представление в поля: year, month… Получается он делает это дважды. Ещё и медленно. А потом, при выходе из моей функции, ещё и обратно «упаковывает» себя в дату. Вот где падала производительность!

Сделав свою, более упрощенную имплементацию календаря, корректно работающую в пределах 2000–2100 годов, удалось повысить скорость в 7–8 раз! Теперь среднее время выполнения функции getNextEvent упало до 500 нс. Не плохо. Получается моя имплементация Schedule догнала по скорости имплементацию от @cadovvl. И это очень круто, скажу я вам. Ибо, кто бы что не говорил, старый добрый C++ куда быстрее Java, с её непредсказуемым GC и халатным обращением с памятью. Java приближается по скорости к C/C++ только в специально подогнанных (синтетических) тестах. А тут реальный кейс. И даже не простой.

[Ilya] */4.01.01 12:00:00.000 2012.01.01 12:00:00.001  - 3584 nsec
[Optimized] */4.01.01 12:00:00.000 2012.01.01 12:00:00.001  - 432 nsec
[Ilya] *.*.* *:*:*.* 2021.30.09 12:00:00.002  - 1134 nsecs
[Optimized] *.*.* *:*:*.* 2021.30.09 12:00:00.002  - 472 nsec
[Ilya] *.4.6,7 * *:*:*.1,2,3-5,10-20/3 2001.01.01 00:00:00.000  - 2250 nsec
[Optimized] *.4.6,7 * *:*:*.1,2,3-5,10-20/3 2001.01.01 00:00:00.000  - 482 nsec
[Ilya] *.4.6,7 * *:*:*.1,2,3-5,10-20/3 2080.05.05 12:00:00.000  - 3719 nsec
[Optimized] *.4.6,7 * *:*:*.1,2,3-5,10-20/3 2080.05.05 12:00:00.000  - 472 nsec
[Ilya] 2100.12.31 23:59:59.999 2000.01.01 00:00:00.000  - 3406 nsec
[Optimized] 2100.12.31 23:59:59.999 2000.01.01 00:00:00.000  - 472 nsec
[Ilya] 2100.12.31 23:59:59.999 2080.05.05 00:00:00.000  - 3617 nsec
[Optimized] 2100.12.31 23:59:59.999 2080.05.05 00:00:00.000  - 465 nsec

Чёрная магия оптимизаций

Некоторым, возможно показалось, что предложенный алгоритм не имеет худшего случая? Нет, чёрт возьми, имеет. Проклятые дни недели! Из-за них мой алгоритм (равно как и алгоритм от @cadovvl), всё-таки мог запросто выродиться в некрасивый O (n). С соответствующим замедлением. Вот типичный бенчмарк:

[NoVar] *.02.29 6 12:00:00 2021.01.01 12:00:00.000  - 806678 nsec	ожидалось 02.29.2048 г.
[Ilya] *.02.29 6 12:00:00 2021.01.01 12:00:00.000  - 90104 nsec – упс! В 180 раз больше времени!

Проблема с днями недели в том, что они выпадают из стройной картины позиционного числа. Они находятся на уровне с днями и влияют на всю дату целиком (но не на время).

Ещё примеры неудобных расписаний

А что если бы мы могли сразу ответить на вопрос:, а&

© Habrahabr.ru