Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 57
Вообще забавно, но на практике, эффективнее использовать что-то типа
function getDays(month)
{
switch (month) {
case 1:
case 3:
case 5:
case 7:
case 8:
case 10:
case 12:
days = 31;
break;
case 4:
case 6:
case 9:
case 11:
days = 30;
break;
case 2:
days = 28;
break;
default:
days = -1;
}
return days;
}
при этом, в февральской ветке можно добавить проверку на високосность.
function getDays(month)
{
switch (month) {
case 1:
case 3:
case 5:
case 7:
case 8:
case 10:
case 12:
days = 31;
break;
case 4:
case 6:
case 9:
case 11:
days = 30;
break;
case 2:
days = 28;
break;
default:
days = -1;
}
return days;
}
при этом, в февральской ветке можно добавить проверку на високосность.
или [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31][month — 1]
Можно ещё
А вышеупомянутый вариант со switch'ом будет всё-таки разика в полтора медленнее… хотя так ли это всё важно?
28 + ((0x2eeeecc >> (2*month)) & 3). Ваш вариант выиграет на x86-64, мой — на x86 просто, хотя разница там копеечная.А вышеупомянутый вариант со switch'ом будет всё-таки разика в полтора медленнее… хотя так ли это всё важно?
Почему это switch будет медленный? Ныне компиляторы оптимизируют switch только в путь. В данном случае свитч скорее всего будет оптимизирован в таблицу и соответственно будет иметь константную сложность.
не быстрее: ветвления,… вычисление адреса, выборка,…
Не будет тут switch оптимизирован в таблицу. Обработку defaut'а в таблицу всё равно не засунешь, её всё равно придётся отдельно делать, в с учётом того, что вариантов немного компилятор, скорее всего, сгенерирует одно-два сравнения сверх этого.
Ни до моего варианта, ни до варианта deNULL'а ни один известных мне компилятор не додумался.
Ни до моего варианта, ни до варианта deNULL'а ни один известных мне компилятор не додумался.
Ваш вариант самый крутой, умножение заменить сдвигом еще. Вариант с массивом чисел самый очевидный, но закодировать количества дней в 32-битное число — просто и гениально, в стиле олдскульной оптимизации, когда каждый байт был на счету.
Почему-то никто не обратил внимания на ошибку в константе.
days = 28 + ((0x3bbeecc >> (month * 2)) & 3);
Я пытался понять это самостоятельно и нашёл несколько упоминаний подобного метода на других сайтах, но к своему невежеству так и не выяснил: откуда взялось число 0x3bbeecc?
К 28 надо прибавить 0, 2 или 3 — это занимает два бита. Отсюда получается 2 в множителе и 3 в маске.
А дальше просто упаковать все добавки в одно целое:
12 11 10 09 08 07 06 05 04 03 02 01 00 - номер месяца
11 10 11 10 11 11 10 11 10 11 00 11 00 - перечисляем количество дней для добавкиИ получаем 0x3bbeecc
Если не учитывать високосность, то для практики проще всего что-то такое:
function getDays(m){
return m === 2 ? 28 : 30 + (m > 7 ? m+1 : m) % 2;
}
Требую вариант с преобразованием Фурье ))
Самый простой способ запомнить (без всяких костяшек и мнемонических правил) — помнить о двух цезарях.
При Юлие Цезаре всё было просто: все нечётные месяцы были по 31 дню. Потом пришёл Август; в августе стало 31 день, и начиная с августа чётные месяцы стали по 31 дню.
При Юлие Цезаре всё было просто: все нечётные месяцы были по 31 дню. Потом пришёл Август; в августе стало 31 день, и начиная с августа чётные месяцы стали по 31 дню.
Занятно, но сам с детства использовал «правило костяшек». Если считать костяшки пальцев на руках и выемки между ними слева направо, то костяшка будет указывать на 31 день, а выемка на 30(или 28 в феврале). При этом переход с левой руки на правую как раз попадет на июль-август.
Ещё можно помнить о Тиберие, который — по легенде* — пресёк традицию переименования месяцев в честь императоров.
* Когда к Тиберию пришёл сенат с заискивающим предложением назвать в его честь месяц в календаре, тот, засмеявшись, бросил им в ответ:
— Глупцы! Что же вы предложите 13-му императору?!
* Когда к Тиберию пришёл сенат с заискивающим предложением назвать в его честь месяц в календаре, тот, засмеявшись, бросил им в ответ:
— Глупцы! Что же вы предложите 13-му императору?!
И вы действительно считаете что это запомнить проще чем костяшки?
Проведите эксперимент: нужно определить сколько дней в ноябре. Ноябрь -> 11-й месяц -> нечётный и больше 7 => 30 дней. В уме быстрее выйдет, чем все костяшки пересчитывать.
Каждый по своему это считает. Для меня есть четыре с половиной «реперные» точки: январь и декабрь (все знают что начинает и кончается год «длинными» месяцами) и вышеупомянутые «июль» и «август» (которые тоже оба длинные потому что император Август не хотел, чтобы его месяц был короче, чем у предшественника). Ну и февраль, как «очень особый» случай (там и от года количество дней зависит). Ну и чего там осталось? 2-3 шага от любой реперной точки — и мы добираемся до любого месяца.
Ваш метод хорош, если помнить какой по номеру каждый месяц, но я таких людей немного знаю. Особенно если учесть что названия врут (судя по названию тот же Ноябрь как бы должен бы быть девятым, да? правда на чётность это не влияет, но всё же...). Всё равно считать нужно откуда-то, а «реперных точек» меньше (что январь первый и декабрь последний, двенадцатый, все знают, а вот что посредине — уже нужно «на пальцах» считать).
Так-то самый быстрый способ — просто запомнить где сколько дней, но если мы тут что-то обсуждаем, то, похоже, что с запоминаем у нас всё не слишком хорошо, не так ли?
Ваш метод хорош, если помнить какой по номеру каждый месяц, но я таких людей немного знаю. Особенно если учесть что названия врут (судя по названию тот же Ноябрь как бы должен бы быть девятым, да? правда на чётность это не влияет, но всё же...). Всё равно считать нужно откуда-то, а «реперных точек» меньше (что январь первый и декабрь последний, двенадцатый, все знают, а вот что посредине — уже нужно «на пальцах» считать).
Так-то самый быстрый способ — просто запомнить где сколько дней, но если мы тут что-то обсуждаем, то, похоже, что с запоминаем у нас всё не слишком хорошо, не так ли?
Это круто!
Можно также воспользоваться интерполяцией Лагранжа:
sage: PolynomialRing(QQ, 'x').lagrange_polynomial(zip(range(1, 13), (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)))
-11/907200*x^11 + 163/181440*x^10 - 37/1260*x^9 + 13481/24192*x^8 - 2055371/302400*x^7 + 240683/4320*x^6 - 28268521/90720*x^5 + 85774775/72576*x^4 - 446998571/151200*x^3 + 46351537/10080*x^2 - 221017/56*x + 1416
Или, если смущают дроби, можно сделать по модулю например 37:
sage: PolynomialRing(GF(37), 'x').lagrange_polynomial(zip(range(1, 13), (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)), algorithm="neville")[-1]
16*x^11 + 12*x^10 + 4*x^8 + 21*x^7 + 29*x^6 + 10*x^5 + 12*x^4 + 34*x^3 + 26*x^2 + 5*x + 10
Интересно, насколько хорошо справится с задачей генетический алгоритм, если скормить ему достаточно квадратных скобок, операций взятия остатка и небольших целых чисел
Плохо потому что компактные варианты требуют больших целых чисел.
31-[2*{3/7*(x-1)}]-2*[1/(1+(x-2)^2)]
Другой механизм описан в книге Романовского «Микрокалькуляторы в рассказах и играх». Пара «месяц-год» переводится к нумерации «с марта» (март = 1, февраль = 12), а затем [30,59*месяц] + день − 30.
Правда, ПМК — зверь особый, ветвление там работает медленнее и расходует больше команд, чем умножение. А целую часть даже на Б3-34 можно вычислить через КИПr; r — любой свободный регистр памяти не менее 7 (0…3 автодекрементные, 4…6 автоинкрементные).
Правда, ПМК — зверь особый, ветвление там работает медленнее и расходует больше команд, чем умножение. А целую часть даже на Б3-34 можно вычислить через КИПr; r — любой свободный регистр памяти не менее 7 (0…3 автодекрементные, 4…6 автоинкрементные).
Немного офтопа. Я ухитрялся на МК-61 на экзамене обращать матрицу 3×3. Заняло это всю память, для вычисления миноров по-чёрному использовались автоинкремент и автодекремент — поэтому матрица вписывалась не в логичные регистры 1…9, а в 7, 8, 9, 1, 2, 3, A, B, C.
Насколько я помню, существовали и алгоритмы и для матриц 4x4. Только они были уже интерактивные — эпизодически запрашивали ввод данных, не умещавшихся в памяти. Для МК-52 были возможны и ещё более сложные алгоритмы, не влезающие в 104 (вроде) ячейки оперативной памяти — там была возможность ручной подгрузки программ из энергонезависимой памяти. Были также и библиотеки программ и во внешних ПЗУ. Также можно было сохранять/восстанавливать данные оперативной памяти. Но необходимость делать это вбивая адреса вручную, ручное переключение режимов записи и чрезвычайно долгий процесс сохранения/восстановления убивал все желание работать. Старались обходится более отзывчивыми алгоритмами, разбиением задач на части и записью/восстановлением данных с помощью карандаша и бумаги.
Давно думал написать статью на Хабр в духе «как сделать вычисление дня недели по дате на советском программируемом калькуляторе в 40-50 шагов памяти», но посчитал, что мелко и никому не интересно. А тут только из одного месяца такое развели :-)
Ну теперь-то вы сделаете статью?
Мой алгоритм для вычисления в уме:
habrahabr.ru/post/217389
habrahabr.ru/post/217389
30^(x&1)^(x/8)^(4/x&2)
Красиво!
На шарпе можно скобки убрать:
На шарпе можно скобки убрать:
30 ^ m & 1 ^ m / 8 ^ 4 / m & 2;
Для сравнения, в предложенной в статье формуле 9 операций
28 + (m + m / 8) % 2 + 2 % m + 1 / m * 2;
Есть несколько вариантов с 6 действиями:
((m+m/8)|30)-(4/m&2)
31-(102/m&1)-(4/m&2)
((~8)>>m&30)|(3-102/m&5)
Соптимизировать до пяти ни один не удалось.
~8 за действие не считается — это константа.
((m+m/8)|30)-(4/m&2)
31-(102/m&1)-(4/m&2)
((~8)>>m&30)|(3-102/m&5)
Соптимизировать до пяти ни один не удалось.
~8 за действие не считается — это константа.
Может я чего не понимаю в колбасных обрезках, но в предложенной мною (и исправленной withkittens) формуле всего четыре действия… или там как-то по другому считать нужно?
Я тоже не понимаю. В формуле со сдвигом их действительно четыре. Возможно, смущает слишком магическая константа?
Ваше решение хорошее. Но, решение включает полную таблицу, пусть и свернутую в 32битную константу. Поиск альтернативных функций интересен сам по себе, как реализация переборных алгоритмов.
Если бы не февраль, то:
Можно вот так еще:
31
-
(3) * (m == 2)
+
(1) * (m == 2) * ((y % 4 == 0) - (y % 100 == 0) + (y % 400 == 0))
-
(1) * (m == 4 || m == 6 || m == 9 || m == 11)
Вы уверены, что хорошо проверили свои выкладки?
Функция
Спокойно утверждает 2100 год как високосный, не смотря на оговорку о том, что это не так.
И далее, функция
Ведет себя так же некорректно:
Функция
Спокойно утверждает 2100 год как високосный, не смотря на оговорку о том, что это не так.
И далее, функция
Ведет себя так же некорректно:
f(2,2100)===29 //true
Вы правы, я вижу ошибку. Я поспешно воспользовался этой формулой. Вместо неё следовало использовать следующую формулу:
ideone.com/VDHV3z
Я внесу соответствующие исправления в пост.
(1 - (y % 4 + 2) % (y % 4 + 1)) * ((y % 100 + 2) % (y % 100 + 1)) + (1 - (y % 400 + 2) % (y % 400 + 1))ideone.com/VDHV3z
Я внесу соответствующие исправления в пост.
Октябрь 1582?
Благодаря комментарию keksmen исправлена ошибка в формуле определения високосного года (g(y)) и исправлена итоговая формула.
С високосным годом (для C/C++):
31-(102/m&1)-((4/m&2)>>((!y%4)-(!y%100)+(!y%400)))
Операция !y — это не условный переход. В зависимости от желания компилятора он компилируется либо в
либо в
31-(102/m&1)-((4/m&2)>>((!y%4)-(!y%100)+(!y%400)))
Операция !y — это не условный переход. В зависимости от желания компилятора он компилируется либо в
neg ecx
sbb eax,eax
inc eax
либо в
xor eax,eax
test ecx,ecx
sete al
Удостоверьтесь, что не допустили ошибки. Когда я выполняю ваш код, в феврале всегда 28 дней.
ideone.com/QaTplf
ideone.com/QaTplf
Date.prototype.isLeapYear = function () {
var y = this.getFullYear();
return !(y % 4) && !!(y % 100) || !(y % 400)
};
Date.prototype.getDaysInMonth = function () {
// adapted from ZX-Spectrum BIOS :-)
return 28 + ((this.isLeapYear() << 2 | 15662003) >> (this.getMonth() << 1) & 3)
};
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Формула подсчёта количества дней в месяце