Алгоритмы *

Полгода назад мне захотелось создать лучший генератор псевдослучайных чисел (ГПСЧ) с какой-нибудь необычной архитектурой. Я думал, что начало будет лёгким, а по мере работы задача станет медленно усложняться. И думал, смогу ли я научиться всему достаточно быстро, чтобы справиться с самым сложным.

К моему удивлению, сложность возрастала не линейно. Побайтовое тестирование по критерию хи-квадрат оказалось очень трудным! Позднее столь же трудно было пройти тесты diehard. Я опубликовал текущие результаты, чтобы понять, какие ещё трудности меня ожидают. Однако тест PractRand в тот раз пройти не удалось.

Затем было очень трудно прохождение теста BigCrush.

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

За 10 лет существования ivi мы собрали базу из 90000 видео разной длины, размера и качества. Каждую неделю появляются сотни новых. У нас есть гигабайты метаданных, которые полезны для рекомендаций, упрощают навигацию по сервису и настройку рекламы. Но извлекать информацию непосредственно из видео мы начали только два года назад.

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

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

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

Очень часто при цифровой обработке сигналов необходимо вычислить длину вектора, обычно это делается по формуле A=SQRТ(X^2+Y^2). Здесь возвести в квадрат значение не сложно, но операция вычисления квадратного корня не является простой операцией, особенно для микроконтроллеров. Кроме того, алгоритмы вычисления корня выполняются не стабильное время, и для алгоритмов, в которых таких вычислений много, становится сложно прогнозировать время, необходимое для вычислений.

С такой задачей столкнулся и я. О том, как я отказался от процедуры вычисления корня, читайте ниже.

В этой статье описана реализация конвейеров в ядре Unix. Я был несколько разочарован, что недавняя статья под названием «Как работают конвейеры в Unix?» оказалась не про внутреннее устройство. Мне стало интересно, и я зарылся в старые источники, чтобы найти ответ.

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

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

В этой статье я расскажу:

• Что за задача такая, о которой идет речь;
• Подробнее об интегральных изображениях;
• Как использовать интегральные изображения для приближенного решения гравитационной задачи N тел применительно к дискретному полю импульсов (масс-скоростей);
• Какой недостаток имеет это решение и как его исправить;
• И, наконец, как за константное время вычислить центр масс для произвольного региона.

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

В статье очень подробно объясняется, как работают Zip-файлы и схема сжатия: LZ77-сжатие, алгоритм Хаффмана, алгоритм Deflate и прочее. Вы узнаете историю развития технологии и посмотрите довольно эффективные примеры реализации, написанные с нуля на С. Исходный код лежит тут: hwzip-1.0.zip.

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



Иммутабельные структуры данных не меняют своих значений. Чтобы что-то с ними сделать, нужно создавать новые значения. Старые же значения остаются на прежнем месте, поэтому их можно без проблем и блокировок читать из разных потоков. В итоге ресурсы можно совместно использовать более рационально и упорядоченно, ведь старые и новые значения могут использовать общие данные. Благодаря этому их куда быстрей сравнить между собой и компактно хранить историю операций с возможностью отмены. Все это отлично ложится на многопоточные и интерактивные системы: такие структуры данных упрощают архитектуру десктопных приложений и позволяют сервисам лучше масштабироваться. Иммутабельные структуры — секрет успеха Clojure и Scala, и даже сообщество JavaScript теперь пользуется их преимуществами, ведь у них есть библиотека Immutable.js, написанная в недрах компании Facebook.

Под катом — видео и перевод доклада Juan Puente с конференции C++ Russia 2019 Moscow. Хуан рассказывает про Immer — библиотеку иммутабельных структур для C++. В посте:

• архитектурные преимущества иммутабельности;
• создание эффективного персистентного векторного типа на основе RRB-деревьев;
• разбор архитектуры на примере простого текстового редактора.

В этой статье я хочу поговорить о методах смешивания растеризуемой геометрии. Классические модели смешивания полупрозрачных объектов — Alpha, Additive, Multiplicative — объединяет один и тот же принцип отрисовки: последовательно рисуем один примитив за другим, смешивая получаемые на выходе фрагментного шейдера пиксели с тем, что находится в текущем буфере. Каждый новый примитив обновляет область буфера, в которую рисуется; в случае с альфа-смешиванием объекты, которые находятся выше, заслоняют ранее отрисованные. Но что если хочется что-то сделать с группой объектов, рисуемых поверх сцены, — например, обрезать их по маске или подсветить? Тут сразу в голову приходят два решения: или внести изменения в их материал (т.е. изменить шейдер, расширить набор текстур), к примеру, добавив проекцию еще одной текстуры, которая будет отвечать за маску прозрачности. Однако если у нас много разношерстных объектов, менять каждый уникальный материал неудобно и чревато ошибками. Второй вариант — нарисовать все интересующие нас объекты в отдельный полноэкранный таргет и рисовать уже его на финальную сцену. Тут мы можем сделать с его содержимым все, что захотим, но это требует выделения лишней памяти и, что самое неприятное, — переключения рендер таргетов. Это не самая «дешевая» операция на мобильных устройствах, которую будет необходимо выполнить дважды. А если захочется вот так работать с несколькими слоями?

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

(КДПВ – см. аннотацию к диаграмме в конце)

Как быть, если дерево поиска разрослось на всю оперативку и вот-вот подопрет корнями соседние стойки в серверной? Что делать с инвертированным индексом, жадным до ресурсов? Завязывать ли с разработкой под Android, если пользователю прилетает «Память телефона заполнена», а приложение едва на половине загрузки важного контейнера?

В целом, можно ли сжать структуру данных, чтобы она занимала заметно меньше места, но не теряла присущих ей достоинств? Чтобы доступ к хэш-таблице оставался быстрым, а сбалансированное дерево сохраняло свои свойства. Да, можно! Для этого и появилось направление информатики «Succinct data structures», исследующее компактное представление структур данных. Оно развивается с конца 80-х годов и прямо сейчас переживает расцвет в лучах славы big data и highload.

А тем временем на Хабре найдется ли герой, способный пересковоговорить три раза подряд
[səkˈsɪŋkt]?

Вторая часть: Принципы работы видеокодека

---

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

Если рассматривать итоговый цвет как комбинацию т.н. основных цветов (красного, зеленого и синего), в нашей трёхмерной матрице определяем три плоскости: первая для красного цвета, вторая для зеленого и последняя для синего.

Будем называть каждую точку в этой матрице пикселем (элементом изображения). Каждый пиксель содержит информацию об интенсивности (обычно в виде числового значение) каждого цвета. Например, красный пиксель означает, что в нём 0 зеленого цвета, 0 синего и максимум красного. Пиксель розового цвета может быть сформирован с помощью комбинации трех цветов. Используя числовой диапазон от 0 до 255, розовый пиксель определяется как Красный = 255, Зелёный = 192 и Синий = 203.

Реквизиты паспорта — не просто набор цифр, в них закодирован вагон информации. Если правильно расшифровывать и сопоставлять реквизиты, подозрительные документы мгновенно всплывут на поверхность. Продукты HFLabs уже 14 лет проверяют клиентские данные в банках, страховых, телекомах и другом крупном бизнесе. Расскажу, как мы распознаем ошибки в российских паспортах.

Применение зашифрованных данных для машинного обучения без их расшифровки
В этой статье обсуждаются передовые криптографические методики. Это лишь обзор исследований, проводимых в Julia Computing. Не используйте приведённые здесь примеры в коммерческих приложениях. Всегда консультируйтесь с криптографами, прежде чем применять криптографию.

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

Тема анализа данных и Data Science в наши дни развивается с поразительной скоростью. Для того, чтобы понимать актуальность своих методов и подходов, необходимо быть в курсе работ коллег, и именно на конференциях удается получить информацию о трендах современности. К сожалению, не все мероприятия можно посетить, поэтому статьи о прошедших конференциях представляют интерес для специалистов, не нашедших времени и возможности для личного присутствия. Мы рады представить вам перевод статьи Чип Хен (Chip Huyen) о конференции ICLR 2019, посвященной передовым веяниям и подходам в области Data Science.

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

Итак, задача на сегодня: научиться простейшей обработке геометрии, чтобы, например, суметь преобразовать мою голову в истукана с острова Пасхи:

На днях прошла встреча комитета по стандартизации языка программирования C++ в городе Белфасте. От представителей стран в комитет прилетело около 400 замечаний к C++20, с половиной из них успели расправиться.

Под катом вас ждут результаты обсуждений замечаний России (да-да, ВАШИХ замечаний к C++20), некоторые замечания других стран, ну и подходящие новинки C++23 (Executors!).

В VK есть группа со следующим описанием:

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

Слева исходная картинка, загруженная 7 июня 2012, справа — какая она сейчас.

Такая разница очень подозрительна. Попробуем разобраться, что происходило в течение этих 7 лет. Для ознакомления есть статья на Медузе про эту группу, но нас будет интересовать только техническая сторона.

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

На прошлой неделе мы говорили в своём блоге об изменениях, которые позволят врагам (biters, кусакам) не наталкиваться друг на друга, но это было не единственное обновление, связанное с biter-ами. Совпало так, что в обновления этой недели вошло то, над чем мы работали предыдущие несколько недель — обновление системы поиска пути для врагов.

Поиск пути

Когда юнит хочет куда-то переместиться, ему сначала нужно понять, как туда добраться. В самом простом случае можно двигаться прямиком к цели, но на пути иногда возникают препятствия — скалы, деревья, гнёзда врагов (spawners), юниты игрока. Чтобы проложить дорогу, мы должны сообщить функции поиска пути (pathfinder) текущую и конечную позиции, а pathfinder вернёт нам (возможно, через много тактов) путь, который просто является набором промежуточных точек (waypoints), по которым должен двигаться юнит, чтобы добраться до места назначения.

Для выполнения своей работы pathfinder использует алгоритм под названием A* (произносится «A star»). Простой пример поиска пути при помощи A* показан на видео: biter хочет найти путь в обход скал. Функция поиска пути начинает исследовать карту вокруг biter-а (исследование показано белыми точками). Сначала она пытается пойти напрямик к цели, но как только достигает скал, «разливается» в обе стороны, пытаясь найти позицию из которой снова можно будет двигаться к цели.