«Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их взаимосвязях», — Линус Торвальдс

Споры о планировщике

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

Вставлять новые задачи с приоритетом (O(log n))

Запрашивать задачу с наибольшим приоритетом (O(1))

Удалять задачу с наибольшим приоритетом (O(log n))

Кто-то предложил: «Давайте используем отсортированный массив». Но вставка будет занимать O(n) — придётся сдвигать элементы.

Кто-то ещё сказал: «Возьмём связанный список». Однако поиск наибольшего выполняется за O(n) — необходимо сканировать весь список.

Третий вспомнил о двоичном дереве поиска. Но из Главы 9 мы уже знаем, что BST ужасно ведут себя с кэшем.

Споры продолжались, пока кто-то не упомянул двоичные кучи. Покончить с разногласиями позволили результаты бенчмарка

Мы уже привыкли жить в глобальном информационном мире, где, с одной стороны, довольно важно знать точное время, а с другой стороны - легко его получить, достаточно настроить на компьютере NTP, да вот хотя бы просто выполнить команду типа ntpdate pool.ntp.org.

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

В общем, спасение утопающих...
К тому же, как говорят, "любой, кто увидел Ардуино - рано или поздно делает часы или метеостанцию".
Простые часы мы делать не будем, а сделаем вполне IT-шный NTP-сервер.

В этой статье мы завершим решение задачи внешней баллистики разбором шестого и седьмого случаев. В них мы учтём уменьшение гравитации с высотой, а также кривизну Земли.

Я фронтенд-разработчик, в основном работаю с React. И в одном из своих пет-проектов я столкнулся с задачей, где нужно автоматически извлекать доминирующие цвета из изображения — для генерации палитры. Начал разбираться, какие подходы вообще существуют, как это делают другие инструменты и что из этого можно реализовать прямо в браузере без тяжёлых зависимостей и серверной обработки.

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

Всем привет! Меня зовут Григорий Дядиченко, и я разрабатываю разные проекты на заказ. Сталкивались ли вы с ситуацией, когда персонаж в вашей игре начинает немного дёргаться, если поиграть достаточно долго? Или пуля иногда пролетает сквозь тонкую стену, хотя коллайдер на месте? Если да — добро пожаловать в мир проблем float precision.

Сегодня хочется поговорить о том, почему тип float — при всей его повсеместности — может создавать тонкие и неочевидные баги в играх. Разберём, как он устроен, где именно он начинает врать, и что с этим делать.

Если вам интересна эта тема — добро пожаловать под кат!

В мире высоконагруженных .NET-приложений каждая наносекунда на счету. Когда ваш код обрабатывает миллионы запросов, даже микрооптимизации могут дать ощутимый прирост производительности. Две ключевые фичи, появившиеся в .NET 8— SearchValues<T> и FrozenSet<T>/FrozenDictionary<TKey, TValue> — позволяют выжать максимум из «горячих путей» (hot paths) благодаря умной предварительной оптимизации.

В 1931 году 25-летний Курт Гёдель написал доказательство, которое перевернуло мир математики с ног на голову. Выводы были настолько поразительными, а само доказательство настолько изящным, что это было… как-то даже забавно. Я хотел поделиться с вами его открытием.

Объединение

На протяжении последних 300 лет математики и ученые делали поразительные открытия, которые привели к появлению одной великой закономерности. Эта закономерность заключалась в объединении: идеи, которые раньше считались разрозненными и непохожими, неизменно оказывались одним и тем же!

Ньютон положил начало этому процессу в физике, когда обнаружил, что то, что удерживает нас на Земле, — это то же самое, что заставляет Землю вращаться вокруг Солнца. Люди думали, что тепло — это особый вид энергии, но оказалось, что его можно объяснить с помощью механики. Люди думали, что электричество, магнетизм и свет — это разные вещи, но Максвелл обнаружил, что их можно объяснить с помощью электромагнитного поля.

Кошмар с автозавершением

Наше префиксное дерево было в 8 раз медленнее хэш-таблицы. И оно потребляло 128 МБ памяти, в отличие от хэш-таблицы с 24 МБ.

Такого не должно было произойти. Префиксные деревья — стандартное решение для автозавершения: поиск за O(k), где k — длина строки вне зависимости от размера датасета. Идеально подходит для сопоставления префиксов. Обычно всегда используется для автозавершения, проверки правописания и таблиц IP-маршрутизации.

Мой коллега предложил использовать префиксное дерево для функции автозавершения в нашем инструменте командной строки. Поиск в нём должен был выполняться по 50 тысячам команд и опций. Учебники говорили, что это правильный выбор.

Поэтому мы реализовали префиксное дерево. Результаты бенчмарка оказались ужасными:

Префиксное дерево было в 8 раз медленнее простой хэш-таблицы. И оно использовало 128 МБ памяти, в то время как хэш-таблица — всего 24 МБ.

Где мы ошиблись?

Данный пост посвящён детальному разбору вещественного типа данных с плавающей точкой удвоенной точности double

Привет Хабр!

Если вы когда-нибудь решали школьные задачи с параллелограммом, то знаете: найти все стороны, углы, диагонали, да ещё и опустить на них высоты — возни много. А потом ещё проверить, не перепутал ли ты, где синус, а где косинус.

Оказывается, всю эту геометрию можно упаковать в одну маленькую матрицу 2×2. Буквально: берем два вектора-столбца, составляем матрицу — и в ней уже зашиты все возможные характеристики фигуры. Осталось только научиться их оттуда доставать.

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

Привет, Хабр! Меня зовут Митя, я инженер-программист в Контуре. Во время написания кода анализаторы иногда предлагают заменить привычные конструкции на pattern matching. Однако то, что призвано повысить читаемость, нередко делает код более трудным для восприятия, особенно, если не понимать, во что именно разворачиваются те или иные конструкции. И в один из дней я задался вопросом: а есть ли какие-нибудь подводные камни при использовании pattern matching и во что именно его преобразует компилятор? В этой статье — мои мысли и заметки.

Аннотация

Год Красной Лошади начинается с кода.

Первый день 2026-го. За окном — хрустальная тишина, налитая зимним светом. В комнате — только монитор и пустая командная строка. Пока город медленно просыпается после боя курантов, у нас с вами, инженеров и кодёров, есть идеальный момент: между прошлым годом и рабочими буднями зияет цифровая пустота. Давайте заполним её огнём.

Что, если вместо тысячного «Hello, World!» или очередного скучного графика, наши скрипты устроят настоящее огненное шоу? В духе наступившего года Красной Лошади — яростное, стремительное, неуправляемо-красивое. Если за окном нет праздника — мы создадим свой. Свою вселенную, где искры не гаснут, а фейерверки взрываются по нашему желанию. Прямо здесь. Прямо сейчас. Первого января, когда всё ещё можно.

Новогодняя симуляция — это не просто игрушка. Это идеальный полигон, где красота сталкивается с математикой лоб в лоб. Вы видите волшебство: ракета взмывает, замирает на миг — и взрывается снопом огненных брызг. Но под этой магией — чистая, честная физика. Дифференциальные уравнения диктуют полёт. Стохастика правит хаосом разлёта. Фракталы плетут снежинки. Это шанс доказать, что MATLAB — не сухой инструмент для расчётов, а кисть. Холст. Дирижёрская палочка для симфонии из нулей и единиц.

В этой статье мы не будем ходить вокруг да около. Мы возьмём законы Ньютона, щепотку случайных чисел и горсть пикселей — и соберём из них фейерверк. С нуля. Прямо на ваших глазах. Напишем движок, который дышит. Заставим частицы танцевать. Добавим ветру — словно от взмаха гривы той самой Красной Лошади. И в конце — самое главное — вы получите не просто скрипт. Вы получите власть над праздником. Меняйте гравитацию. Рисуйте новые узоры. Создавайте свои миры.

Год только начался. Давайте встретим его не как потребители, а как творцы. Первый взрыв — уже в следующей строке кода.

Недавно мы разбирали популярную задачу — проверяли строку на наличие цифр. Еще одна популярная задача при работе со строками — удалить из них пробельные символы. Можно представить, что нам нужно очистить пользовательский ввод: удалить пробелы вначале и конце строк в имени или удалить пробелы из телефонного номера. .NET предоставляет нам несколько возможностей для решения этой задачи, давайте рассмотрим самые популярные и попробуем найти наиболее эффективные. Заодно проверим, какие изменения произошли в новой версии .NET 10.

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

Brief: (Трансформации, углы Эйлера (pitch, yaw etc), кватернионы, Lie group, Eigen, Sophus)

Во время выполнения визуального SLAM робот постоянно перемещается в пространстве. Для того чтобы определить его текущую позицию в пространстве необходимо знать его начальную позицию и перемещение в пространстве к данному моменту времени.

Трансформации

углы Эйлера (pitch, yaw etc)

Приготовьтесь. Это не просто конспект. Это исчерпывающий путеводитель по миру матриц, созданный с одной целью: сделать эту фундаментальную область высшей математики абсолютно понятной, систематизированной и полной. От самых азов до продвинутых концепций, используемых в науке о данных и квантовой физике.

Как следует отображать на экране результат деления 3.0 на 10.0 ? Сколько цифр следует вывести, если пользователь не указал точность?

Скорее всего, вы даже не знали, что вывод на экран чисел с плавающей запятой — это сложная проблема, настолько сложная, что по ней написаны десятки научных статей, причём последний прорыв был относительно недавно, в 2016 году. На самом деле, это одна из самых сложных частей поддержки чисел с плавающей запятой в среде выполнения языка.

Давайте продолжим разговор о самой неоптимизированной в мире библиотеке эмуляции плавающей точки при помощи целочисленной арифметики.

Это вторая статья из цикла «Санпросвет о плавающей точке»:

1. Компьютеры и числа

2. Вывод чисел с плавающей точкой на экран <- вы тут

Сегодня я расскажу, как из-за случайной встречи с ANTLR я создал RCParsing, библиотеку на C# для парсинга практически любого вида синтаксиса, поддерживающую парсинг отступов из коробки. Мы разберемся, как работают разные алгоритмы парсинга и чем отличается тот, что используется у меня. Также я закину пример кода для парсинга упрощенного YAML с использованием моей библиотеки.

Доброго времени суток, господа и дамы! Иногда у некоторых людей возникает желание заняться откровенным непотребством в программировании — то, что не несет практической пользы напрямую, но помогает развлечься. В этой статье я хочу рассказать вам о лайфхаках, трюках (магических и не очень), алгоритмах на языке C!

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

Всех, кто заинтересовался — прошу под кат.

Привет, Хабр!

В экосистеме C# за последние два релиза случилось ровно то, чего многим не хватало для аккуратной работы со списками значений. В C# 12 появились collection expressions — синтаксис вида [1, 2, 3] со spread-элементами .., который конвертируется в массивы, Span, ReadOnlySpan, интерфейсы коллекций и любые правильно устроенные типы. В C# 13 к этому добавили params-коллекции: теперь params может быть не только массивом, а почти любой поддерживаемой коллекцией, включая спаны и неизменяемые контейнеры.