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


Рисунок 1. Новый прямой метод построения открытой (бесконечной) квазислучайной последовательности с низким расхождением в треугольнике произвольной формы и размера. На рисунке показаны распределения точек в пятнадцати случайных треугольниках для первых 150 точек.

Краткий обзор

Последовательности с низким расхождением (low discrepancy), равномерно сэмплирующие/заполняющие квадрат, активно изучались почти сотню лет. БОльшую часть этих квазислучайных последовательностей можно расширить до прямоугольников простым растягиванием, не сильно повредив при этом расхождению.

Однако в этом посте мы рассмотрим интересное и важное расширение последовательностей с низким расхождением на произвольный треугольник.

Анонс WebAssembly состоялся в 2015-м — но сейчас, спустя годы, всё ещё немногие могут похвастаться им в продакшне. Тем ценнее материалы о подобном опыте: информация из первых рук о том, каково с этим жить на практике, пока что в дефиците.

На конференции HolyJS доклад об опыте использования WebAssembly получил высокие оценки зрителей, и теперь специально для Хабра подготовлена текстовая версия этого доклада (видеозапись также приложена).

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


Рисунок 1. Сравнение различных квазислучайных последовательностей с низким расхождением. Заметьте, что предлагаемая мной $$-последовательность создаёт более равномерно распределённые точки, чем все остальные методы. Более того, все остальные методы требуют тщательного подбора базовых параметров, а в случае неправильного подбора приводят к вырожденности (например справа вверху)

Рассматриваемые в статье темы

• Последовательности с низким расхождением в одном измерении
• Методы с низким расхождением в двух измерениях
• Расстояние упаковки
• Множества с многоклассовым низким расхождением
• Квазислучайные последовательности на поверхности сферы
• Квазипериодический тайлинг плоскости
• Маски дизеринга в компьютерной графике

Какое-то время назад этот пост был выложен на главной странице Hacker News. Можете прочитать там его обсуждение.

Yew — аналог React и Elm, написанный полностью на Rust и компилируемый в честный WebAssembly. В статье Денис Колодин, разработчик Yew, рассказывает о том, как можно создать фреймворк без сборщика мусора, эффективно обеспечить immutable, без необходимости копирования состояния благодаря правилам владения данными Rust, и какие есть особенности при трансляции Rust в WebAssembly.



Пост подготовлен по материалам доклада Дениса на конференции HolyJS 2018 Piter. Под катом — видео и текстовая расшифровка доклада.

Теперь, когда мы знаем основы комбинирования функций расстояний со знаком, можно использовать их для создания крутых вещей. В этом туториале мы применим их для рендеринга мягких двухмерных теней. Если вы пока не читали моих предыдущих туториалов о полях расстояний со знаком (signed distance fields, SDF), то крайне рекомендую их изучить, начав с туториала о создании простых фигур.


[В GIF возникли дополнительные артефакты при пересжатии.]

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

Метод покоординатного спуска является одним из простейших методов многомерной оптимизации и неплохо справляется с поиском локального минимума функций с относительно гладким рельефом, поэтому знакомство с методами оптимизации лучше начинать именно с него.

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

Продолжаем знакомство с методами многомерной оптимизации.

Далее предложена реализация метода наискорейшего спуска с анализом скорости выполнения, а также имплементация метода Нелдера-Мида средствами языка Julia и C++.

Пришли очередные выходные, надо написать пару десятков строк кода и нарисовать картинку, да лучше не одну. Итак, на прошлых и позапрошлых выходных я показал, как делать трассировку лучей и даже взрывать всякое. Это многих удивляет, но комьпютерная графика — очень простая вещь, пары сотен строк голого C++ вполне хватает на создание интересных картинок.

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

Всем привет!

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

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

Введение

На Habr математическое описание работы фильтра Калмана и особенности его применения рассматривались в следующих публикациях [1÷10]. В публикации [2] в простой и доходчивой форме рассмотрен алгоритм работы фильтра Калмана (ФК) в модели «пространства состояний», Следует отметить, что исследование систем контроля и управления во временной области с помощью переменных состояния широко используется в последнее время благодаря простоте проведения анализа [11].

Публикация [8] представляет значительный интерес именно для обучения. Очень эффективен методический приём автора, который начал свою статью с рассмотрения распределения случайной погрешности Гаусса, рассмотрел алгоритм ФК и закончил простой итерационной формулой для подбора коэффициента усиления ФК. Автор ограничился рассмотрением распределения Гаусса мотивируя это тем, что при достаточно больших $$ (многократных измерений) закон распределения суммы случайных величин стремится к распределению Гаусса.

Теоретически такое утверждение, безусловно, справедливо, однако на практике число измерений в каждой точке диапазона не может быть очень большим. Сам R. E. Kalman получил результаты о минимуме ковариации фильтра на базе ортогональных проекций, без предположения о гауссовости ошибок измерений [12].

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

Алгоритм Wave Function Collapse генерирует битовые изображения, локально подобные входному битовому изображению.

Локальное подобие означает, что

• (C1) Каждый паттерн NxN пикселей в выходных данных должен хотя бы раз встречаться во входных данных.
• (Слабое условие C2) Распределение паттернов NxN во входных данных должно быть подобным распределению паттернов NxN в значительно большом количестве наборов выходных данных. Другими словами, вероятность встречи определённого паттерна в выходных данных должна быть близка к плотности таких паттернов во входных данных.

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

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

Итого, как в таких условиях нарисовать вот такую картинку за 180 строчек кода?

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

Что бы не изобретать велосипед, первым делом начал копать интернет, в результате чего были найдены следующие варианты:

• ограничения доступа через сетевые службы ssh, sftp (не подошло)
• разграничение прав доступа самой операционной системой linux (не подошло, хотелось бы универсальное решение)
• использование chroot (не подошло)
• использование сторонних утилит, например SELinux (не подошло, усложняет систему).

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

Сайт The Daily WTF уже 14 лет собирает курьёзные, дикие и/или печальные истории из мира ИТ. Я перевёл несколько рассказов, показавшихся мне интересными. Все имена и названия компаний изменены. Первая часть находится здесь.

История первая. Назло бабушке...

[Оригинал]

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

Клайв блестяще прошёл интервью и спустя неделю поступил на работу. В почтовом ящике его уже ждало письмо от кого-то по имени Брэндон. Оно гласило: «Надо встретиться».

Брэндон сидел в своём офисе, приклеившись к эргономическому креслу середины 90-х и как будто став с ним одним целым. Он поднял взгляд от монитора и посмотрел на Клайва. «Ты работаешь на меня».

Краткими фразами, состоявшими из односложных слов, Брэндон объяснил, что никто из принимавших решение о найме не будет встречаться с Клайвом. Клайв несёт ответственность только перед ним.

«Ну ладно… Так, когда меня нанимали, то сказали, что нужно настроить Subversion. Мне начинать с этого?», — спросил Клайв.

«Нет».

«Можно узнать, почему? Вы предпочитаете что-то другое? Хотите обсудить варианты?»

«Нет».

Недавно (буквально два года назад) тут пробегала статья Только 10% программистов способны написать двоичный поиск. Двоичный поиск — это классический алгоритм поиска. Мало того, это еще чрезвычайно простой алгоритм, который можно очень легко описать: берем отсортированный массив, смотрим в середину, если не нашли там число, в зависимости от того, что в середине — ищем это число этим же методом либо в левой части, либо в правой, откидывая средний элемент. Для функций также, просто берем не массив, а функцию. Все очень и очень просто, алгоритм описан почти везде, все баги словлены и описаны.

Так вот, я не могу реализовать двоичный поиск. Для меня он ни капельки не тривиален. Наверное, я ненастоящий программист. А ведь так и есть, я всего-лишь студент, но ведь это не оправдание? Если точнее, я не могу реализовать хороший корректный красивый двоичный поиск. Все время у меня вылезает проблема либо с корректностью, либо с красивостью, либо и с тем, и с другим. Так что, да, заголовок немного желтоват.
Прежде чем читать этот топик, напишите свою версию бинарного поиска — для отсортированного массива. Причем, в зависимости от параметра, поиск должен выдавать или первый элемент, или любой из дублирующих. Еще для сравнения, напишите бинарный поиск для функций

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

И в один прекрасный день МВД Украины открыло доступ к реестру транспортных средств. Теперь по номерному знаку стало возможным проверять некоторую информацию про автомобиль (марку, модель, год выпуска, цвет и т.д. )! Скучная рутина линейного программирования померкла перед новой свехзадачей — считывать номера по всей базе фото и валидировать эти данные с теми, что указывал пользователь. Сами знаете как это бывает «глаза загорелись» — вызов принят, все остальные задачи на время стали скучны и монотонны… Мы принялись за работу и получили неплохие результаты, чем, собственно и решили поделиться с сообществом.

Для справки: на сайт AUTO.RIA.com, в день добавляется около 100 000 фото.

Датасаентисты давно уже знают и умеют решать подобные задачи, поэтому мы с dimabendera написали эту статью именно для программистов. Если вы не боитесь словосочетания «сверточные сети» и умеете писать «Hello World» на питоне — милости просим под кат…

В целом ответ – да. Особенно, когда есть мозги и знание теоремы Байеса.

Напомню, что среднее и дисперсию можно считать только, если у вас имеется определенное количества событий. В старых методичках СССР РТМ (руководящий технический материал) говорилось, что чтобы считать среднее и дисперсию необходимо 29 измерений. Сейчас в ВУЗах немного округлили и используют число 30 измерений. С чем это связано – вопрос философский. Почему я не могу просто взять и посчитать среднее, если у меня есть 5 измерений? По идее ничто не мешает, только среднее получается нестабильным. После еще одного измерения и пересчета оно может сильно измениться и полагаться на него можно начиная где-то с 30 измерений. Но и после 31го измерения оно тоже пошатнется, только уже не так заметно. Плюс добавляется проблема, что и среднее можно считать по разному и получать разные значения. То есть из большой выборки можно выбрать первые 30 и посчитать среднее, потом выбрать другие 30 и тд … и получить много средних, которые тоже можно усреднять. Истинное среднее бывает недостижимо на практике, так как всегда имеем конечное количество измерений. В таком случае среднее является статистической величиной со своим средним и дисперсией. То есть измеряя среднее на практике мы имеем в виду «предположительное среднее», которое может быть близко к идеальному теоретическом значению.

Попробуем разобраться в вопросе, на входе мы имеем некоторое количество фактов и хотим на выходе построить представление об источнике этих фактов. Будем строить мат модель и использовать теорию Байеса для связки модели и фактов.

Мы решили подготовить серию дайджестов с обзорами наиболее популярных open source проектов. В список попали самые обсуждаемые на Hacker News решения с открытым исходным кодом. Тема первой подборки — инструменты и сервисы для работы с логами и базами данных.

Уровни сложности чтения

• Я слишком молод, чтобы думать

  
  
  • Введение и правила игры
  • Как они это делают?
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

• Сделай мне умно

  
  
  • Введение и правила игры
  • Как они это делают?
  • При чём тут карточки?
  • Проективные плоскости малых порядков
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

• Кошмар

  
  
  • Введение и правила игры
  • Как они это делают?
  • Конечная геометрия для грудничков
  • При чём тут карточки?
  • Проективные плоскости малых порядков
  • Как построить проективную плоскость?
  • Матрица инцидентности для игры Доббль
  • Каких двух карточек не хватает в комплекте игры?
  • Почему в игре на 2 карточки меньше максимально возможного количества?
  • Благодарности
  
  

Введение и правила игры

Несколько лет назад я купил игру Доббль (Dobble, оригинальное название “Spot It!”). Это очень простая, быстрая и весёлая игра, которую я считаю одной из лучших настольных игр вообще.