Comments 40
Поучительно в плане оптимизации кода, но не очень понятен смысл такой длительной экстраполяции. Григорианский календарь ввели не так давно (и в разных странах по-разному), поэтому даты из 19 века и ранее всё равно надо вычислять по-другому.
Кроме того, астрономические сутки не в точности равны 86400 секунд, поэтому и с такой стороны быстро набегает погрешность.
Можно поинтересоваться, что алгортм делает, кроме того что быстро работает?
Добавляет к дате секунды, минуты?
Тайм зоны учитываются? Откуда берется актуальная иформация о зонах?
Справедливости ради, у Нери Шнайдера алгоритм тоже в tz_data не заглядывает: https://arxiv.org/pdf/2102.06959 , да преобразовываемый алгоритмом unixtime тоже таймзоны не имеет.
Это очень круто, но это не самый быстрый алгоритм :(
Самый быстрый, не знаю, придумали ли еще, такой:
Делаем статический скомпилированный массив соответствий unix_timestamp -> конкретная дата
Далее просто возвращаем дату по нужному индексу в этом массиве.
Но пока что не хватает памяти у компьютеров на этот алгоритм. Но я предсказываю, что с оптимизациями и в будущем то, что я написал станет новым самым быстрым алгоритмом.
Возможно, что с оптимизациями уже будет помещаться в память, кстати.
Только вот для отрезка в 100 000 лет в памяти это будет занимать примерно 17.6 терабайт, и чтобы реально получить от этого выигрыш нужно хранить все это в кеше процессора, так как ОЗУ довольно медленная штука на самом деле
То же самое можно сказать про сортировку - ее можно делать за линейное время. Только это не практично для больших коллекций.
Как раз для больших - очень даже практично. Радиксная сортировка.
И у нее константа такова, что в реальности quick sort оказывается зачастую быстрее.
Активно использовал её в реальном проде. Гонял тесты, чисто из любопытства. На имевшемся железе экспериментальная многопоточная сортировка (std::experimental::parallel_sort, кажись, Си++-14 это был или прототип) начинала отставать примерно на 10-20 тысяч ключей (точнее, пар ключ+нагрузка, там были варианты инт32/64/128/дабл ключ, нагрузка - один, два или три раза инт32), однопоточная сливалась ещё раньше. Многопоточный радикс в прод не пошёл, слишком грузит проц при незначительном выигрыше в скорости (там многопоточность высокая и несколько однопоточных радиксов отрабатывали интегрально быстрее). Учитывая, что сортировали десятками-сотнями миллионов - никакой квиксорт там и рядом не валялся.
Константа большая, но зависит от реализации (надо правильно привязываться к размерам кэшей проца и префетч делать). "Тупо в лоб" - что угодно будет грустно.
Так-то можно сказать, что и пузырёк - супер-пупер сортировка: три элемента быстрее не отсортируешь, а оверхед примерно нулевой! :-)
Ну так всё верно, высокая константа, разница начинает идти "в плюс" на десятках тысяч. Поэтому стандартная сортировка нигде не radix sort. Предполагается, что если у вас специальные условия, например, прям очень много данных - вы сами напишите (или возьмёте) что-то идеально подходящее.
Именно так. "У немца для всякого дела свой инструмент есть" :-)
Причём мы в итоге даже убрали из кода вилку по размеру, мол, меньше 10к сортируем стандартной сортировкой, а больше - своей. Ибо SoA, а не AoS, и для стандартной нужна обёртка, а абсолютная разница мизерная, на ТЕХ задачах - не стоящая усложнения кода, если правильно помню, меньше 20 микросекунд в худшем случае.
Вы когда-нибудь слышали об архивации файлов при помощи хэширования?
Самый мощный, знаю, уже придумали такой:
Делаем хэш 100гб файла, который будет весить всего 1кб
Далее просто на другом ПК, где нужно эти 100гб разархивировать, подбираем байты до тех пор, пока хэш полностью не совпадет.
Но пока что не хватает памяти у компьютеров на этот алгоритм. Но я предсказываю, что с оптимизациями и в будущем то, что я написал станет новым самым мощным алгоритмом.
Возможно, что с оптимизациями уже будет помещаться в память, кстати.
Вы не путайте божий дар c яичницей. Хэширование это отображение N -> 1, по хэшу не восстанавливается файл однозначно. А тут всё работает однозначно.
по хэшу не восстанавливается файл однозначно
В теории, одному хэшу соответствует много вариантов файлов, но какой процент из этих файлов будет корректно исполнятся или открываться в конкретном софте?
Механизм контрольных сумм или договорённость о формате, сводят вероятность неправильного развёртывания к чему-то не сильно отличимому от нуля.
Ну, типа, раз в 1 килобайт идёт строчка, которая записана в самом начале.
В каком смысле в теории?) Это не теория, а следует из определения.
И одному хешу соответствует не "много вариантов", а в принципе бесконечность.
Это не теория, а следует из определения.
Так это и есть теория.
Но, на практике, неизменность софта подтверждают либо хэшами md5 и sha1 , либо цифровой подписью, которая имеет ту же суть что и остальные хэши.
Да, в теории, паре хэшей md5 и sha1 может соответствовать бесконечное число файлов, которые, даже можно подобрать.
Однако, на практике, считается, что можно пренебречь шансом на то, что такой файл ещё будет и исполняемым, причём так как нужно атакующему.
А если ещё размер файла добавите, то число вариантов станет конечным, а число вариантов, которые будут иметь требуемый формат, станет очень сильно конечным.
Вот эта вот тема с коллизиями md5 хэша эффективно работает в том случае, когда атакуемая система сравнивает хэши. В том смысле, что надо подобрать такую строчку, которая при хэшировании даст нужный хэш. Тут, да, важен сам факт коллизии, а не содержимое полученное при обращении хэша.
Автор перестарался с диапазонами дат:
Возраст Земли: ~4,54 млрд лет
Сколько ещё просуществует:
как планета — ещё ~5 млрд лет
как пригодная для жизни — примерно 1–1,5 млрд лет
так что можно обойтись без 64 битного числа секунд :)
Если использовать 32-битный счетчик секунд, то его хватит только до 2038 года.
Скажем, юлианский календарь и просуществовал всего-то пару тысяч лет, так что аффтар — изрядный оптимист
Может для каких-то астрофизических расчетов и нужны такие экстремальные диапазоны, но там явно не нужна система времени, привязанная к земле, луне и даже к солнцу (то есть дни, месяцы, года).
К сожалению без 64 битного числа секунд не обойтись. Существует проблема 2038 года, когда 32х битный time_t переполнится. Собственно современные софт точно должен использовать 64 бита для представления времени (если конечно его создатели не хотят, чтобы в 2038 году он перестал работать)
К сожалению без 64 битного числа секунд не обойтись. Существует проблема 2038 года, когда 32х битный time_t переполнится. Собственно современные софт точно должен использовать 64 бита для представления времени (если конечно его создатели не хотят, чтобы в 2038 году он перестал работать)
На что спорим? :)
Алгоритм генерирует точные результаты за период ±1,89 триллиона лет, поэтому подходит для обработки полного 64-битного времени UNIX (в секундах).
А когда введут очередную "високосную секунду", и его алгоритм перестанет работать, то какую ответственность он понесёт?
Его же никто не заставлял заявлять о точном результате в будущем. Он сам это сделал. Добровольно. В расчёте на то, что пользователи поведуться и начнут использовать его продукт.
Как называется деяние, когда человек обещает то, что гарантировано не будет выполнено?
А когда введут очередную "високосную секунду", и его алгоритм перестанет работать, то какую ответственность он понесёт?
Когда в будущем введут любую високосную секунду любой алгоритм написанный сегодня отвалится.
Кстати ее могут не только добавить но и убрать. Но всем по барану на самом деле.
А когда введут очередную "високосную секунду", и его алгоритм перестанет работать
Он от этого не перестанет быть точным.
В качестве разминки для ума - интересно. Но я не представляю в каких задачах конвертация дат может стать бутылочным горлышком.
Мы можем указать побитовый сдвиг ровно на
64,
Если это c++, то такие сдвиги - UB, так что алгоритм может сломаться внезапно.
В исходниках там активно используется int128, с ним работает корректно уже лет десять как, если не больше. Правда, в исходниках есть специальные функции hi128/lo128 с очевидным функционалом. Ну и так-то понятно, что это просто высокоуровневая обёртка для старой традиции х86 использовать пару регистров для результата умножения или для делимого при делении.
Этап вычисления дня года пропущен; вместо него используется методика побитового сдвига остатка от деления года, что позволяет избавиться от деления
Что-то вспомнилось, каково было на Спектруме по координатам пикселя адрес в памяти считать, вот там без подобных фокусов действительно было не обойтись.
Скрытый текст
Прежде всего об адресации
спектрумовского экрана. Несмотря на
некоторую непоследовательность в его
строении, адрес любого байта экранной
области (#4000..#57FF) может быть задан
схемой:
010S SLLL RRRB BBBB
где: S - секция или треть (0..2);
L - номер линии символа (0..7)
R - позиция по вертикали в пределах
секции (0..7);
B - номер столбца (0..31).
Координаты любой точки (x,y) экрана в этих
обозначениях имеют такое строение:
y - 11 111 111 x - 11111 111
S R L B bit number
y = 0..191 x = 0..255
А вот как можно описать адрес экрана в
виде формулы:
adr(x,y) = 16384+2048*INT(L/8)+
+32*(L-8*INT(L/8))+256*R+C
Можно, но зачем?
Я написал алгоритм вычисления дат, который на 30–40% быстрее остальных