Комментарии 58
... дающие корректный результат с года 0 по год 102499...
Утверждение, конечно, замечательное. И, формально, поскольку григорианский календарь введён только в 1582 году, исторические даты имеют положительный год. Однако, католики, местами, перевели и более ранние даты в григорианский календарь.
Соответственно, может иметь некоторый смысл и определение високосности григорианского года в типе `int32_t` и в интервале порядка `-9999... 9999` или типа того. Интересно, кто-нибудь такое уже смотрел?
А разве високосный год, не каждый четвертый?
Такого выражения вроде бы должно быть достаточно: !(y&3)
ПС. Да там оказывается еще другие периоды учитываются. Не знал )
возможно, я не уловил какую-нибудь иронию или ещё что-либо, поэтому спрошу прямо: те два предложения, ниже заголовка "Расширение до других битовых ширин", специально оставлены без перевода?
(вообще, конечно, после таких выкладок, вывод слегка обескураживает)
Люблю такие штуки. И спасибо за Z3. очень интересует. второй раз вижу как она реально применяется для оптимизации.
Интересно, но зачем.
После обратного квадратного корня Кармака я ничему не удивляюсь.
Сначала я такой: О! Крутая оптимизация. Заберу в свою коллекцию.
А потом задумался. А в какой задаче требуется максимально быстро проверять год на високосность? Думал думал и так и не придумал. Единственное, что приходит в голову - преобразование даты в секунды при обработке каких-то массивов данных. Но всё равно мысль буксует, зачем это надо делать быстро и даже если очень надо, не быстрее ли сделать какой-то lookup в табличку с нужным диапазоном годов и сразу получать готовые вычисления.
Но в целом я одобряю подобные извращения над битовой арифметикой. Как разминка для ума, и, иногда оно бывает очень полезным с практической точки зрения
А в какой задаче требуется максимально быстро проверять год на високосность? Думал думал и так и не придумал. Единственное, что приходит в голову - преобразование даты в секунды при обработке каких-то массивов данных.
Честно говоря. Преобразование григорианской даты в/из юлианского дня или в/из числа атомных секунд от заданой эпохи выполняется почти линейной формулой (таблица нужна только для високосных секунд).
А предикат високосного года, вроде как, нужен только для входного контроля дат февраля или расчёта номера дня в году (номера недели в году).
Так что, само по себе это просто красивая конструкция. Возможно, её аналог можно где-то ещё применить, кто знает?
Добавить N секунд (минут, дней) к дате — это не такая уж и редкая задача.
Дело не в редкости задачи, а в том, сколько раз в секунду эту задачу приходится выполнять. Конкретно эта задача - определение високосности года - если и требуется где-то, то не чаще одного раза за кадр, что явно недостаточно, чтобы заморачиваться ради сотни тактов.
Если это в запросе СУБД на миллиард строк, то, наверное, может стать важным.
Другой вопрос, что возникает много оговорок. Во-первых, даже для манипуляций с датами в чистом виде эта функция не очень нужна. Во-вторых, в классической OLTP СУБД будет гораздо больше накладных расходов на доступ к полю (в колоночных аналитических может и есть какой-то смысл).
Вы мыслите как прикладник, попробуйте мыслить как создатель вспомогательного кода. Представьте себе: вы реализовываете библиотеку общего назначения, в которой есть функция date_add(origin, seconds).
Пользователь вашей библиотеки реализует на её базе крон.
Пользователь крона просит ему показать дату, когда будет миллионое срабатывание (для метрик своих каких-нибудь).
Вот простейший сценарий, когда функция общего назначения будет вызвана миллион раз в секунду.
Пользователь крона просит ему показать дату, когда будет миллионое срабатывание
И вы считаете её перебором?
А вы знаете хитрый метод определения этой даты? Поделитесь, пожалуйста, мне очень бы пригодилось в двух моих библиотеках.
Если событие срабатывает раз в день/неделю/месяц, не вижу проблем вычислить дату n-ого срабатывания аналитически. Но не помню, насколько сложные правила можно задать в кроне - можете приветси что-нибудь нетривиальное?
Событие «каждый четверг» в феврале 2024 отрабатывало 5 раз.
Событие «каждую секунду последнего часа» отрабатывало 61 раз в ночь с 30 июня на 1 июля 1997 года.
Ну, банальные високосные годы и leap seconds - согласен, что надо подумать, но уверен, что аналитическая формула и там и там есть. Вывести автоматическую генерацию аналитической формулы из конфига крона - да, интересная задачка )
Формулы чего именно?
Момента N-ого срабатывания.
Високосные секунды добавляются «ad hoc», высочайшим распоряжением астрономических чиновников. Мы не знаем, когда будет добавлена следующая, поэтому задача с учетом високосных секунд для будущего — решения в принципе не имеет, даже перебором.
Если про них забыть, и просто перезапускать расчет, например, каждую полночь, то я практически убеждён (как человек, который очень подробно исследовал всю эту астрономию при написании вышеупомяных библиотек): даже если аналитическая формула и существует, человечеству она не известна, а если бы была известна — едва ли была бы быстрее индукции. Следующее срабатывание я считать умею.
Да, високосные секунды тогда просто игнорим. Вычислить миллионный четверг в терминах обычного юниксового таймстампа тривиально, конверсия таймстампа в год/месяц/день - есть в библиотеках, явно без перебора.
Тривиально, конечно; вот я вам и код, которым 99% библиотек пользуются, подогнал: https://github.com/coreutils/gnulib/blob/master/lib/parse-datetime.y#L1747-L2383
Явно без перебора. Или с ним всё-таки?
Только есть нюанс: этот код не умеет работать с не-ISO календарями, а для библиотеки, написанной в XXI веке — это не вариант.
"Добавить дней/секунд к дате" можно выполнять в удобном для хранения формате, храня смещение относительно какой-то точки (собственно, отсюда же системный формат unix и растёт). А преобразование в человеческую дату и обратно требует другой задачи - сколько високосных лет (29.02) прошло до этого момента. И "добавить N месяцев/лет" проще делать конвертацией сначала в структуру годы-месяцы-дни, потому что всё равно 29.02 отдельно обрабатывать.
Строго говоря, решение задачи "... сколько високосных лет (29.02) прошло..." не зависит от решения задачи проверки года на високосность.
И "добавить N месяцев/лет" проще делать конвертацией сначала в структуру годы-месяцы-дни, потому что всё равно 29.02 отдельно обрабатывать.
Не очень понятно. Проще и надёжнее преобразовать в юлианские дни или секунды, потом добавить и преобразовать назад, так все и делают (chrono::time_point/chrono::duration или datetime.datetime/datetime.timedelta). А в этом случае, 29.02 не требует отдельной обработки, там просто линейные формулы.
Можно ли этот обощённый линейный алгоритм "обогнать" для случая фиксированного и/или не очень большого интервала? Вопрос непонятный (ИМХО, сомнительный и, вероятно, отрицательный).
для хранения формате, храня
Где храня? Отвлекитесь от джейсоноукладки, представьте себе, что вы реализовываете системную функцию date_add(origin, seconds) в стандартной библиотеке какого-нибудь раста или го.
Которую пользователь вашей библиотеки может вызвать в цикле, чтобы добраться до даты в следующем году по заковыристым бизнес-правилам. Это миллион вызовов.
Ну например если вам нужно определить какой сегодня день в году. Бывает надо.
Быстро - не надо, скорее всего. А вот с ситуацией "уложить проверку високосности в минимальное количество байт" я сталкивался.
Можно заменить
(y % 100) != 0на(y % 25) != 0
(y % 400) == 0на(y % 16) == 0
непонятно откуда вы берёте такое сокращение. они дают разный результат
например
150 % 100 = 50 возвращает true так как не равно 0
150 % 25 = 0 возвращает false так как равно 0
Так проверка на 100 делается тогда, когда y делится на 4. 150 на 4 не делится.
Как бы, предусловия и взаимную простоту делителей стоит учитывать.
bool is_leap_year1(uint32_t y) {
if ((y % 4) != 0) return false;
assert(0 == y%4);
if ((y % 25) != 0) return true;
assert(0 == y%100); // Поскольку 4 и 25 взаимно просты
if ((y % 16) == 0) return true;
assert(0 != y%400); // Поскольку 16 и 25 взаимно просты
return false;
}
Бенчмарк показывает, что варианты не особо различаются по производительности (или "fast" версия даже проигрывает)
https://quick-bench.com/q/aH7Tc4TN4000UXQSitdj9aososI
Интересная статья. Подобные трюки я встречал раньше. Например, при вычислении расстояния Хэмминга, когда нужно посчитать количество отличающихся битов двух 64-битных векторов. Делать циклический сдвиг 63 раза и считывать младший бит? Долго.
__declspec(dllexport) int ph_hamming_distance(const ulong64 hash1,
const ulong64 hash2) {
ulong64 x = hash1 ^ hash2;
const ulong64 m1 = 0x5555555555555555ULL;
const ulong64 m2 = 0x3333333333333333ULL;
const ulong64 h01 = 0x0101010101010101ULL;
const ulong64 m4 = 0x0f0f0f0f0f0f0f0fULL;
x -= (x >> 1) & m1;
x = (x & m2) + ((x >> 2) & m2);
x = (x + (x >> 4)) & m4;
return int((x * h01) >> 56);
}Потом в SSE4.2 (2008) появилась команда POPCNT и надобность в подобном цирке отпала.
Еще больше трюков можно найти в исходном коде Quake. На что только не шли, чтобы избежать долгих вычислений на старых CPU! Вот так считали обратный квадратный корень:
float Q_rsqrt(float number) {
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = *(long*)&y;
i = 0x5f3759df - (i >> 1);
y = *(float*)&i;
y = y * (threehalfs - (x2 * y * y));
return y;
}На хабре про это уже писали: «Магическая константа» 0x5f3759df / Хабр
См. также: Обстоятельно о подсчёте единичных битов
А для вычисления дня недели - сколько минимум операций нужно?
Сижу, перелистываю книгу "The Practice of Programming" от B. Kernighan и R.Pike, и вижу следующее:
И тут Ваша статья. Совпадение ? Не думаю. ;)
sub isleap {
my ($year) = @_;
return 1 if ( $year % 400 == 0 ); # 400's are leap
return 0 if ( $year % 100 == 0 ); # Other centuries are not
return 1 if ( $year % 4 == 0 ); # All other 4's are leap
return 0; # Everything else is not
}Perl
Вариант DeepSeek:
#include <stdint.h>
int is_leap_year(int year) {
// Оптимизация year % 4 через битовую операцию
if (year & 3) return 0; // Не делится на 4 → не високосный
// Быстрый расчёт year % 100 через "магическую константу"
uint64_t tmp = (uint64_t)year * 1374389535ULL;
int mod100 = year - ((int)(tmp >> 37) * 100);
if (mod100 != 0) return 1; // Делится на 4, но не на 100 → високосный
// Проверка year % 400 (аналогично через константу)
tmp = (uint64_t)year * 1374389535ULL; // Та же константа работает для /400
int mod400 = year - ((int)(tmp >> 37) * 400);
return mod400 == 0;
}или
int is_leap_year(int y) { return !(y & 3) && (y - ((int)((uint64_t)y * 1374389535ULL >> 37) * 100) || !(y - ((int)((uint64_t)y * 1374389535ULL >> 37) * 400)); }
Антиресно, а DeepSeek сам лажанулся и выдал ответ для знаковых int year, mod100, mod400? Или это уже Ваша ошибка с переводом из корректных беззнаковыхuint64_t year, mod100, mod400 в некорректные знаковые?
просто для интереса сделал:
до 9999 года нашел еще такую формулу, 22 бита.
static inline bool is_leap22(uint32_t y)
{
return ((y * 1648277u) & 0x3FFFFFu) <= 5103u;
}
" Берём 400-летний период Григорианского календаря, формулируем условие «((y × M) & MASK) ≤ T ⇔ високосный» как задачу выполнимости для 400 остатков. Далее отдаём её SMT-решателю Z3 с критерием «минимизировать сумму 22-битных констант M, MASK, T». Z3 за доли секунды подбирает первую модель, потом скрипт автоматически проверяет её на всём диапазоне 0 – 9 999 лет — получаем три нужных числа. "
Звучит, конечно, привлекательно, но может какая-то путаница? По-моему врёт: https://godbolt.org/z/hr83TePq1
Стоит ли оно того?
Разве что для фана, поучения теоретического результата.
Нужно ли нам заменять, например, реализацию datetime CPython на этот трюк?
Нет — у полученной формулы отсутствует читаемость, и используется такая операция не так часто, чтобы так заморачиваться. Думаю существует намного больше мест, оптимизация которых принесет намного существенный результат. Тем более ускорение достигается не в 100% случаев.
Еще быстрее:
создать 100кб файлик и загрузить его в память. В файлике - массив бит, предварительно вычисленных, високосный ли год. Если високосный то 1, если нет то 0. Индекс бита равен номеру года. Обращаемся к массиву по индексу: leap = array[year];
Здесь все биты в t равны 1, поэтому результат равен true, если какой-то из битов B имеет в p ненулевое значение.
Пардон, но при переводе смысл изменился на противоположный:
Here all bits in t are 1, so the result is true as soon as any bit in B is unset in p.
Почему никто не написал, что тернарный оператор ? от if не отличается? Поэтому и бенчи такие странные.
Проверка високосности года в трёх командах CPU