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

Еще одна статья о CUDA — зачем?

На Хабре было уже немало хороших статей по CUDA — раз, два и другие. Однако, поиск комбинации «CUDA scan» выдал всего 2 статьи никак не связанные с, собственно, алгоритмом scan на GPU — а это один из самых базовых алгоритмов. Поэтому, вдохновившись только что просмотренным курсом на Udacity — Intro to Parallel Programming, я и решился написать более полную серию статей о CUDA. Сразу скажу, что серия будет основываться именно на этом курсе, и если у вас есть время — намного полезнее будет пройти его.

Со времени предыдущего поста из жизни lock-free контейнеров прошло немало времени. Я рассчитывал быстро написать продолжение трактата об очередях, но вышла заминка: о чем писать, я знал, но реализации на C++ этих подходов у меня не было. «Не годится писать о том, что сам не попробовал», — подумал я, и в результате я попытался реализовать в libcds новые алгоритмы очередей.
Сейчас настал момент, когда я могу аргументированно продолжить свой цикл. В данной статье закончим с очередями.

Кратко напомню, на чем я остановился. Были рассмотрены несколько интересных алгоритмов lock-free очередей, а под занавес приведены результаты их работы на некоторых синтетических тестах. Главный вывод — всё плохо! Надежды на то, что lock-free подход на магическом compare-and-swap (CAS) даст нам пусть не линейный, но хотя бы какой-то рост производительности с увеличением числа потоков, не оправдались. Очереди не масштабируются. В чем причина?..

Вступление

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

Я, автор, Юра Перов, занимаюсь вероятностным программированием в течение уже двух лет в рамках своей основной учебно-научной деятельности. Продуктивное знакомство с вероятностным программированием у меня сложилось, когда будучи студентом Института математики и фундаментальной информатики Сибирского федерального университета, я проходил стажировку в Лаборатории компьютерных наук и искусственного интеллекта в Массачусетском технологическом институте под руководством профессора Джошуа Тененбаума и доктора Викаша Мансингхи, а затем продолжилось на Факультете технических наук Оксфордского университета, где на данный момент я являюсь студентом-магистром под руководством профессора Френка Вуда.

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

«Обычное» программирование

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

Привет, друг! В этот раз я опять подниму вопрос о графике в ААА-играх. Я уже разобрал методику HDRR (не путать с HDRI) тут и чуть-чуть поговорил о коррекции цвета. Сегодня я расскажу, что такое SSLR (так же известная как SSPR, SSR): Screen Space Local Reflections. Кому интересно — под кат.

Наследование, при кажущейся простоте, часто приводит к сложным, сопротивляющимся изменениям структурам. Иерархии классов растут как самый настоящий лес.
Целью наследование является привязка кода (набора методов) к минимальному набору свойств сущности (как правило — объекта), которые он обеспечивает и которые ему требуются. Это упрощает повторное использование, тестирование и анализ кода. Но наборы свойств со временем становятся очень большими, начинают пересекаться нетривиальным образом. И в структуре классов появляются миксины и прочее множественное наследование.
Внести изменения в глубине иерархии становится проблематично, приходится думать заранее о «внедрении зависимостей», разрабатывать и использовать сложные инструменты рефакторинга.

Возможно ли всего этого избежать? Стоит попытаться — пусть методы будут привязаны к множеству характерных свойств объекта (тегов), а иерархия наследования выстраивается автоматически по вложенности этих множеств.

Пусть мы разрабатывает иерархию для игровых персонажей. Часть кода будет общая для всех персонажей — она привязана к пустому набору свойств. Код, отвечающий за их отображение будет представлен в виде вариантов для OpenGL и DirectX разных версий. Что-то будет зависеть от расы персонажа, что-то от наличия и вида магических способностей и тп. Теги персонажа первичны. Они перечисляются явно, а не наследуются. А реализация наследуется в зависимости от набора тегов (по вложенности). Таким образом умение стрелять из ПЗРК не окажется у кенгуру, потому что его унаследовали от пехотинца.

Идея такого подхода была предложена Дмитрием Кимом. Автор не стал ее воплощать в код, я попробую исправить это упущение.
Реализация такого подхода на Clojure, как обычно, на github.

Вы придумали крутую идею, записали потрясающее промо-видео, потратили несколько месяцев на подготовку, неделю оформляли страницу, запустили кампанию в ожидании головокружительного успеха и…



ничего не произошло…

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

Устройство для мониторинга параметров домашней среды с передачей данных по Wi-Fi.



В статье описывается устройство для измерения, индикации на встроенном дисплее и передачи в сеть по Wi-Fi параметров окружающей среды:

• уровень СО2 (углекислый газ)
• уровень СО (угарный газ)
• содержание паров этилового спирта (С2Н5ОН)
• уровень горючих газов (LPG)
• уровень аммиака (NH3)
• содержание водорода(H2)
• значения атмосферного давления
• влажности и температуры воздуха
• уровня освещенности
• уровня магнитного поля по трем осям
• уровня гравитации по трем осям
• уровня ускорений по трем осям
• температуры произвольного количества цифровых датчиков температуры типа DS18B20.

Введение

Несколько дней назад я открыл для себя замечательный ЯП Clojure — один из современных диалектов Lisp, особенностью которого является хорошая реализация средств многопоточности, компиляция в байткод jvm, соответственно возможность использования java — библиотек, jit-компиляция и т.д. Про Clojure можно почитать например тут. Но в этой статье речь пойдёт о метапрограммировании. Lisp устроен таким образом, что данные и код в нём — одно и то же. Объявления функций, макросов, вызовы функций, развёртывание макросов — в Lisp это всё просто списки, возможно вложенные друг в друга.

(defn square [foo] (* foo foo))
(defmacro show-it [foo] `(println ~foo))

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

Приглашаем вас на двухдневный хакатон по разработке игр GamesJamMicrosoft.

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

Вышла недавно статья на Хабре о том, как можно самому создать на функциональном языке такие структуры как Очередь (первый зашёл, первый вышел) и Дек (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов). Посмотрел я на этот код и понял, что он жутко неэффективен — сложность порядка O(n). Быстро сообразить, как создать структуры с O(1) у меня не вышло, поэтому я открыл код библиотечной реализации. Но там была не лёгкая и понятная реализация, а <много кода>. Это было описание пальчиковых деревьев, необходимость и элегантность которых для этой структуры данных хорошо раскрывается текущей статьёй.

Пальчиковые деревья

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

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

Пальчиковые деревья (Часть 1. Представление)
Пальчиковые деревья (часть 2. Операции)
Пальчиковые деревья (Часть 3. Применение)

Разрабатывая структуру данных

Основа и мотивация пальчиковых деревьев пришла от 2-3 деревьев. 2-3 деревья — это деревья, которые могут иметь две или три ветви в каждой внутренней вершине и которые имеют все свои листья на одном и том же уровне. В то время, как бинарное дерево одинаковой глубины d должны быть 2^d листьев, 2-3 деревья гораздо более гибкие, и могут быть использованы для хранения любого числа элементов (количество не должно быть степенью двойки).
Рассмотрим следующее 2-3 дерево:



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

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

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

В новости было дано общее понятие самой концепции. Сейчас профессор Стратклайдского университета Дункан Грэхем (Duncan Graham), специалист по наночастицам и научный советник в организации Cancer Research UK, решил прояснить ситуацию по этому проекту, а также по интересующим многих вопросу использованию нанотехнологий для диагностики и лечения онкозаболеваний.

Дж. С. Херц уверена, что разрекламированные фитнес-трекеры — всего лишь ненужный тренд, который мешает развитию носимых устройств для тех, кто в них действительно нуждается. Мы перевели её материал, опубликованный на Wired.com.



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

Data Matrix является двумерным матричным штрих кодом, состоящим из светлых и темных участков. С помощью такого штрих кода можно закодировать достаточно большой объем информации (2-3Кб). Часто Data Matrix применяется при маркировке небольших предметов, например микросхем, а также в пищевой, оборонной промышленности, рекламе и других сферах.

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

При создании Data Matrix нам понадобится обратиться к арифметике полей Галуа и кодам Рида-Соломона. Рассмотрим этот процесс на простом примере.

В этой публикации я постараюсь предельно просто рассказать, как можно легко и быстро сделать динамическое освещение в 2D игре на XNA; без шейдеров, карт нормалей и вообще, без дополнительных ресурсов. Целью у нас будет красивая игровая сцена с ночным небом, темным задним фоном, освещенным фонарями, передним фоном и игровым меню. Количество источников света не ограничено (в разумных пределах, конечно), форма произвольная. Освещается только передний фон. Читателю желательно иметь элементарные навыки работы с XNA, поскольку будет много кода.

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

Мы (@ali_aliev и avenat) с удовольствием представляем вашему вниманию перевод интерактивного учебника «Problem Solving with Algorithms and Data Structures» от Брэда Миллера (Brad Miller) и Дэвида Ранума (David Ranum) из Luther College, что в Айове, США.

О чём?

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

Авторы рассказывают о таких структурах данных, как стеки, очереди (в том числе с приоритетом), деки, хэш-таблицы, списки, деревья и графы. Последним двум вообще посвящены весьма не маленькие главы. Изложение не просто описательное: для каждой структуры предлагается вариант (а иногда и не один) её реализации на Python. Упор, естественно, делается на объектно-ориентированное программирование: создаётся класс, к нему пишутся методы, некоторые из которых авторы оставляют читателям для самостоятельной доработки. Затем идут примеры использования рассмотренной структуры и описание алгоритмов с её участием.

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

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

Чтобы сделать 3D-модель или распечатать уже готовую на 3D-принтере, надо просто следовать инструкции. Никаких навыков и способностей не требуется. Главное — просто следовать простой инструкции.

На выставке проходящего в Москве форума наткнулся на интересный проект из категории носимой электроники. Это футболка, делающая электрокардиограмму. Я уже не раз писал о подобных проектах (например, тут) но о российском — впервые.



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

Всё самое интересное и важное, как обычно, остаётся незамеченным. Между тем в российском краудфандинге случился настоящий прорыв: с помощью народного инвестирования в стране впервые будет издана серьёзная научно-популярная книга. 32-летний кемеровчанин Павел Шубин, тонкий и глубокий исследователь всех перипетий покорения космоса, провёл на «Бумстартере» стремительную, полную взлётов и падений крауд-кампанию, собрал почти миллион рублей и сейчас готовит свой труд «Венера: неукротимая планета» к печати. И это лишь первая книжка из задуманной трилогии!



Прозвучавшие во врезе слова «прорыв», «впервые» и «серьёзная» не натяжка (поправьте нас, если мы заблуждаемся). Рядом с блистательными научпоп-томиками, издаваемыми под присмотром фонда «Династия», скоро можно будет поставить не менее замечательную, не менее настоящую книгу. С той лишь разницей, что опубликована она будет не профессиональным издательством, а безвестным математиком из глубинки. А деньги на неё собраны читателями-технарями, изголодавшимися по хорошей научно-популярной литературе. О том, как проходила крауд-кампания, что ей предшествовало, почему несколько десятков (!) издательств не заметили книги, мы и поговорим сейчас с Павлом Шубиным (@shubinpavel). Не забыв, разумеется, попросить его поделиться советами с научпоп-авторами, которые только присматриваются к краудфандингу.

И в чём же, всё-таки, состоит основная проблема создания сильного искусственного интеллекта? «Конечно же, в отсутствии необходимого аппаратного обеспечения достаточной мощности» – скажет кто-то. И будет, конечно же, прав. Ведь если на данный момент попытаться создать хоть чуть-чуть похожий на мозг человека компьютер с триллионами нервных клеток, каждую из которых можно сравнить с отдельным компьютером со своими функциями и свойствами, то мы получим «робомозг» размером с дом. Но если представить, что прогресс всё-таки дошел до момента, когда создание подобной машины лишь вопрос денег и свободного времени, то можно поразмышлять и об алгоритме работы такой машины. Что я и сделал.

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