Алгоритмы *

В прошлую пятницу я объяснял джуну, почему его код на отсортированном массиве работает в шесть раз быстрее, чем на неотсортированном. Тот же массив, тот же алгоритм, и те же данные. Просто в другом порядке. Джун смотрел на меня как на сумасшедшего и, честно говоря, я его понимаю.

Потому что ответ звучит безумно: процессор внутри вашего ноутбука постоянно пытается предсказать будущее. Буквально. Он гадает, какая ветка if выполнится ещё до того, как условие будет вычислено. И на отсортированных данных ему угадывать проще.

Ну, давайте разбираться.

В конце 2020 года я купил MacBook Pro 13 на процессоре Apple M1, очень хотелось испытать процессоры на архитектуре ARM. Почти сразу на чипе Apple M1 был найден вычислительный блок для матричных операций Apple AMX. Для Apple AMX не было документации, он не использовался в Apple Accelerate, но несколько энтузиастов занимались реверс-инжинирингом и анализом производительности ("https://github.com/corsix/amx"). 

В 2024 году вышли компьютеры на базе семейства процессоров Apple M4, у которых блок AMX задействован для выполнения инструкций из Scalable Matrix Extension 2 (сайт ARM недоступен в РФ) (ARM SME2). 

В статье рассмотрим использование расширения ARM SME2 на примере умножения заполненных матриц. Увидим, как выжать максимум из процессора и получить прирост производительности в десятки раз.

Это не отдельная статья, а продолжение статьи про теорию объектов в с++, почему объекты в плюсах такие какие есть. Все завершенные главы я также выкладываю на github'e в английском и русском варианте. Продолжаем разбираться в теории С++...

Отдельного разговора заслуживает идентичность объектов, потому что в реальном мире конкретные сущности обладают идентичностью и Сократ останется Сократом независимо от того, перекрасил ли он волосы, сменил адрес или умер, а государство остаётся тем же государством, даже если меняет флаг, конституцию или размер населения. 

Чтобы отразить это в программе, объекты, представляющие конкретные сущности, нуждаются в своём определении идентичности, которая отделена от текущего состояния. Удобный способ ввести такую идентичность будет сделать некий токен идентичности, уникальное значение, которое выражает "кто это", а не "в каком он сейчас состоянии". Таким токеном может быть, например, адрес объекта в памяти, индекс в массиве, или табельный номер сотрудника в кадровой системе и проверяя равенство токенов идентичности, мы фактически проверяем тождественность объектов: один и тот же объект или разные. 

На протяжении жизни программы конкретный объект может менять свои токены идентичности, потому что его могут переместить в другой участок памяти или переложить из одного контейнера в другой, или назначить ему новый идентификатор, но логическая идентичность сохраняется, если мы поддерживаем сопоставление между "старым" и "новым" токеном.

Отличительной особенностью научного подхода является отсутствие веры на слово. Любое утверждение не может считаться фактом, пока не будет установлена его истинность. А для этого необходимо задать множество вопросов, провести множество измерений, тестов, моделирований и т. д. Все, что есть во Вселенной, осязаемое или нет, может быть в той или иной степени измерено. Не исключением являются знания, которые проверяются как в школах, так и в университетах с помощью специально составленных экзаменов. С появлением генеративных ИИ не утихаю дебаты об уровне их знаний и достоверности той информации, которую они выдают на запрос. Те тесты, которые ранее считались показательными, более не могут полноценно оценить ИИ. По этой причине ученые из Техасского университета A&M (Колледж-Стейшен, Техас, США) разработали «Последний экзамен человечества» - всеобъемлющий текст знаний по различным направлениям для ИИ. Из каких вопросов состоял тест, и как себя показали самые популярные генеративные ИИ? Ответы на эти вопросы мы найдем в докладе ученых.

Мы привыкли думать о вычислениях как о битах, регистрах и арифметике. А что, если базовой единицей вычисления сделать не бит, а локальную геометрическую конфигурацию тетраэдров? В этой статье я покажу дискретный тетраэдрический движок состояний, симметрийную канонизацию, аттракторы, иерархические jump-таблицы и реальные замеры на RTX 3090 — с измеренным exact-ускорением в 554.92 раза на одной и той же задаче.

У вычислительной программы есть два ресурса: время (циклы CPU) и пространство (оперативная память). Но как они заменяют друг от друга? Правда ли задачу, которая решается в полиномиальном пространстве , можно решить за полиномиальное время ?

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

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

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

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

Ответ — да. Измеряя определённые расстояния и углы на поверхности Земли, мы можем определить, что Земля — это сфера, а не, скажем, плоская или кольцеобразная фигура, — даже без спутникового снимка.

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

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

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

В 1957 году писатель-фантаст Роберт Хайнлайн так представлял себе людей XXI века: «Делала перерасчет прочности гидропонических оранжерей, но выходило с ошибками. Дважды забывала логарифмы, так что пришлось лезть в таблицу».

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

Зато, чтобы обрести эту сверхспособность, не требуются укусы радиоактивных пауков — достаточно просто прочитать эту статью, а уж пригодится ли в жизни — решайте сами. Может быть в нужный момент калькулятора под рукой не окажется, а может быть просто захочется произвести впечатление на коллег небрежно брошенной фразой: «Корень седьмой степени из пяти это примерно 1,25». Хотите научится быстро считать? Тогда добро пожаловать под кат!

Вчера я 4 минуты стоял в подъезде и смотрел, как два лифта одновременно поехали вверх. Все два. На табло — 12, 15, 18. Я на первом. Мне на шестой. И я подумал: вот я кучу лет пишу софт, оптимизирую запросы к базе данных, кеширую всё что движется — а эти две коробки на тросах не могут разобраться, кто из них должен спуститься за мной.

Потом я погрузился в тему. И выяснил, что они не «не могут разобраться». Они математически не способны найти идеальное решение. Вообще никто не способен. Задача диспетчеризации группы лифтов — NP-трудная. То есть буквально: не существует алгоритма, который гарантированно найдёт оптимальный маршрут за разумное время.

И вот уже 60 лет лучшие инженеры мира решают эту задачу эвристиками. По сути — догадками.

Когда я пишу эту статью, то чувствую себя довольно глупо. На самом деле, это история с моралью «Прежде, чем действовать, изучи вопрос и понимай, в чём заключается твоя цель, потому что иначе потеряешь много времени».

Я продолжаю работать над проектом PSRayTracing. Как ни стараюсь я положить его на полку, время от времени слышу о чём-то «новом» и задаюсь вопросом: «а можно ли засунуть это в мой трассировщик лучей, чтобы выжать из него ещё немного скорости?». На этот раз такой темой стали аппроксимации Паде. Моя цель заключалась в обеспечении более быстрых (и точных) тригонометрических аппроксимаций.

Увы, это не помогло... однако я обнаружил нечто иное, позволившее существенно ускорить мой трассировщик!

Данная статья посвящена основе основ нейронауки — линейной алгебре. Если вы когда-либо планируйте изучать искусственные нейронные сети (и не только), то вам необходимо начать именно с этого. Причем не важно, собираетесь ли вы заниматься фундаментальными исследованиями (Data Science) или просто лепить модели в продакшн на конвейере (ML Engineering), вы обязаны знать их математику хотя бы поверхностно. Любые настройки, дообучение и применение даже готовой модели, требуют понимания основ. А по сему данное знание, как минимум, не будет избыточным.

Материал рассчитан на новичка. Если вы знаете школьную математику, то сможете освоить и мой курс. В будущем я напишу статью о линейном представлении нейросетей, где мы адаптируем полученное знание под прикладные задачи, напишем некоторые слои на Python и построим настоящую модель!

В этой статье:
* Понятие вектора;
* Векторизация данных;
* Умножение на скаляр;
* Сложение векторов;
* Норма вектора;
* Скалярное умножение;
* Векторное умножение;
* Практика с кодом;
* Домашняя работа.

Все будет объяснено на красочных примерах в игровой форме. Ничего сложного. А в конце вас ждет самостоятельная практика с кодом.

Приятного чтения!

Фильтра Калмана много не бывает! По этой теме издано несколько книг, опубликовано большое количество статей, в том числе на Хабре. Разработанный в 1960-х годах алгоритм оценки состояния динамических систем по сегодняшний день считается одним из лучших, получает все более широкое применение в различных технических системах: от радиолокации до электрокардиографии.

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

Все модели, которые я буду использовать и описывать, выполнены на языке Matlab – среде, изначально созданной для работы с матрицами. Гарантированно они будут работать на версии R2016b и выше.

Группа исследователей впервые смоделировала полный жизненный цикл живой бактериальной клетки с наномасштабным разрешением, отследив поведение каждого гена, белка и химической реакции от репликации ДНК до клеточного деления. Результаты исследования, опубликованные в журнале Cell, открывают возможность заменить сотни реальных лабораторных экспериментов одной комплексной 4D-симуляцией.

Привет, Хабр. Меня зовут Владимир, я бэкенд-разработчик. Это моя первая статья здесь — о том, как пет-проект для нишевого варианта шахмат прошёл путь от «а что, если...» до первого места в рейтинге на chess.com. Без нейронок. На чистом alpha-beta поиске, написанном на Rust.

Статья будет полезна тем, кто интересуется шахматным программированием, оптимизацией CPU-bound задач или связкой Python + Rust через PyO3.

Я был одержим процедурными картами с ещё детства, когда кидал кубики на таблицы случайных подземелий из AD&D Dungeon Master's Guide. В этом есть что-то волшебное — ты не проектируешь подземелье, а исследуешь его, помещение за помещением, а кубики решают, попадёшь ли ты в сокровищницу или в тупик с кучей крыс.

Спустя годы я решил создать собственный генератор карт. Он создаёт маленькие средневековые островные миры с дорогами, реками, побережьями, горами, лесами и деревьями. И всё это полностью процедурным образом. Генератор написан на Three.js WebGPU с TSL-шейдерами, примерно 4100 шестиугольников в 19 сетках генерируются за ~20 секунд.

Кому будет полезно

Если вы живёте в Python и одновременно используете statsmodels, lifelines, pyhf, PyMC/BlackJAX, linearmodels (или что‑то похожее).

Если вам важны воспроизводимость и понятная валидация численных оптимизаций (особенно в HEP).

Если вам интересна архитектура «одно вычислительное ядро → много задач» и практические hot paths (AOT, SIMD, zero‑copy).

Когда вы прокладываете маршрут в горах в 2ГИС или рассматриваете вид на дом в 3D, вы вряд ли задумываетесь, что под капотом карты происходит серьёзная вычислительная работа. За каждой формой рельефа — тысячи треугольников, интерполяции и алгоритмы, которые превращают цифровую модель местности в реалистичную поверхность.

Впервые рельеф мы добавили в веб‑версию 2ГИС в 2022 году. С тех пор мы не останавливались на достигнутом: доработали алгоритмы, улучшили качество исходных данных, научили дороги и здания влиять на поверхность. А недавно мы выкатили рельеф и в мобильное приложение.

В этой статье расскажем, как мы пересмотрели подход к данным, зачем нам понадобился нерегулярный меш, что общего у RTIN с Делоне и почему даже рельеф иногда приходится «чинить».

Учась в школе, я обнаружил очень простую математическую формулу, о которой не перестаю думать и сегодня. Смысл её в следующем: представьте, что у вас есть 3D-точка в воображаемом 3D-пространстве за экраном. Для проецирования этой 3D-точки на экран нужно взять её координату X, поделённую на Z, и аналогично её Y / Z. И в результате вы получите проекцию точки на экран: и . А если у вас есть множество точек в этом 3D-пространстве за экраном, и вы начнёте их анимировать и вращать их, а потом воспользуетесь этой формулой для рендеринга всех точек на экране, то это будет выглядеть, как 3D-сцена или 3D-объект. Давайте попробуем эту формулу в деле.

Привет, Хабр! Меня зовут Сергей, я работаю в компании InfoWatch разработчиком на продукте ARMA Стена (NGFW). Подробнее о том, что такое ARMA Стена, можно прочитать тут.

В этой статье я хочу поделиться опытом применения метода формальной верификации в решении практической бизнес-задачи.

Сразу оговорюсь, что в статье используется TLA+, без введения в инструмент, чтобы не увеличивать объём статьи. Подробнее про инструмент вы можете почитать на сайте создателя, тут и тут. Необходимые объяснения даются по ходу изложения.

Статья состоит из двух частей:

1) Что такое формальная верификация и где она применятся

2) Решение бизнес-задачи в NGFW

12 лет я отработал в ФНС России: начинал в районной инспекции и завершал карьеру в Управлении ФНС по субъекту. И довольно долго жил с ощущением, что «у нас налоги мягче», предпринимателю проще дышать, а где-то «там» всё устроено жестче и формальнее.

Но всё оказалось не так однозначно, как казалось изнутри системы. Теперь, находясь по другую сторону баррикад, я решил сравнить две налоговые системы: российскую ФНС и американскую IRS, и в итоге оказалось, что налоговое бремя, у нас в России, не такое уж низкое как преподносят в СМИ - оно просто иначе спрятано и иначе распределено. В России человек чаще всего видит только НДФЛ, но значительная часть нагрузки живёт «над зарплатой» - в страховых взносах работодателя, а затем догоняет нас в потреблении через НДС, который уже встроен в цену.

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

Так как тема очень большая, в этой статье я начну с фундамента - разберу архитектуру ФНС и IRS: как устроены уровни управления, где сосредоточены контроль и аналитика, а в следующей части сравню налоговую нагрузку двух стран на конкретных расчётах и покажу, где именно «прячется» налоговое бремя в России и США.