...

суббота, 19 марта 2016 г.

На GitHub опубликован исходный код компактного гипервизора

Алгоритмы — это лишь одна из переменных в уравнении

[unable to retrieve full-text content]

За что могут высечь плетьми в цифровую эпоху? Как GitHub соблюдает DMCA, RFC 7725 и что за HTTP 451?

Сегодня стартует официальная часть в Ставрополе

image
Сегодня в 10:00МСК стартует официальная часть <hackathon_weekend/> — первого хакатона в истории Ставропольского края! Тема: «Разработка мобильного или web приложения для жителей города».

Параллельно хакатону пройдет серия лекций\мастер-классов от приглашенных специалистов.

Расписание и темы мастер-классов по ссылке: http://ift.tt/1VkUCog (время Московское).

Силами партнеров будет организована трансляция как самих лекций, так и аудиторий, в которых проходит непосредственно хакатон.

Конференц-зал:

Аудитории хакеров:

Комментарии (0)

Let's block ads! (Why?)

пятница, 18 марта 2016 г.

Универсальный скрипт переключения 2-х каналов интернета Mikrotik

Около 2,5 лет назад писал статью на тему автоматического переключения канала Интернет на резервный. Скрипт, конечно, и по сей день работает «на отлично», но его внешний вид и некоторые нюансы…

Итак, встала задача улучшить скрипт, максимально устранив побочные эффекты. Что ж, приступим.

image

В нашем распоряжении Mikrotik RB850Gx2, для которого мы будем писать скрипт (его работоспособность также проверена на моделях RB450G и RB951G-2HnD).

Для начала, добавим новый скрипт
image

Присвойте скрипту имя, например, script-check-inet

Что же будем в нем использовать?

Итак, для начала определим необходимые переменные:

:local firstInterface "pppoe-rostelecom";
:local secondInterface "eth2-MTS";
:local pingTo "8.8.8.8";
:local prefix ">>> ";


где:
$firstInterface — имя нашего PPPoE-соединения основной линии связи.
$secondInterface — имя нашего Ethernet-соединения резервной линии.
$pingTo — IP-адрес ресурса, который будем «пинать».
$prefix — будем использовать для вывода логов, чтобы нам было виден нужный текст.

При изменении дистанции роута без очистки ARP таблицы будут возникать ошибки и так как в нашем коде есть несколько мест, откуда необходимо вызвать очистку данной таблицы, оформим код в функцию:

:local clearArp do={
    :local dumplist [/ip arp find]
    :foreach i in=$dumplist do={
        /ip arp remove $i
    }
    :log info ($prefix . "ARP cleaned");
}

Далее, для уменьшения строк кода, мы используем конструкцию `/ip route {}`, внутри которой нельзя вызывать другие корневые команды, например, `/interface pppoe-client...`. Поэтому мы создадим еще одну функцию, отвечающую за переподключение PPPoE-соединения:

# Function to reconnect PPPoE connection
:local reconnectPPPoE do={
    /interface pppoe-client set $nameInterface disable=yes;
    :delay 1s;
    /interface pppoe-client set $nameInterface disable=no;
}

В нашем случае в качестве основной линии используется «Ростелеком», который имеет «фишку» в периодическом отключении Интернета при том, что внутренняя их линия работает без сбоев. Это достигли опытным путем, используя SIP-сервер от Ростелеком, который так ни разу и не упал.
В общем, создали функцию переподключения соединения. Идем дальше.

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

Итак, проверяем активны ли интерфейсы и если нет — активируем их:

# Check FIRST interface
/interface pppoe-client {
    :if ( [get $firstInterface disable] = true) do={
        set $firstInterface disable=no;
        :delay 5s;
    }
}

# Check SECOND interface
/interface ethernet {
    :if ( [get $secondInterface disable] = true) do={
        set $secondInterface disable=no;
    }
}

Но это еще не все! Дальше мы проверим выставленные дистанции роутов:

/ip route {
    # Set objects to variables
    :set firstInterface [find gateway=$firstInterface];
    :set secondInterface [find gateway=$secondInterface];

    # Check routes
    :if ( [get $firstInterface distance] != 2 ) do={
        set $firstInterface distance=2;
        :log info ($prefix . "Distance for " . [get $firstInterface gateway] . " corrected");
    }

    :if ( [get $secondInterface distance] != 1 && [get $secondInterface distance] != 3) do={
        set $secondInterface distance=3;
        :log info ($prefix . "Distance for " . [get $secondInterface gateway] . " corrected");
    }

# ... body ...
}

Так как основная часть работает в `/ip route`, мы добавили «защиту от дураков» в ее начало.
В нашем случае используем 2 роута с `dst. address` равным `0.0.0.0/0`, шлюзом по имени интерфейса и «какой-то» дистанцией.

Что делает скрипт:

Вначале он присваивает переменным объекты для каждого из роутов, чтобы меньше кода писать.
Затем, проверяем дистанцию основного роута (Ростелеком). Мы используем значение «2».

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

Проверили дистанции и выставили нужные. Что дальше?

Проверка пингом


Так как интерфейс может быть неактивен, то в первоначальном условии используем конструкцию не только проверки пинга, но и статуса интерфейса:
/ip route {
    # ...
    :if ( [get $firstInterface active] = false or [/ping $pingTo interface=[get $firstInterface gateway] count=5] = 0) do={
        # ...
    }
    # ...
}

То есть, если у интерфейс выключен или ни один пакет пинга не прошел — считаем, что Интернет отсох.

Обратите внимание на строку `[/ping $pingTo interface=[get $firstInterface gateway] count=5]`, где `interface=...` — это жестко указанный интерфейс, через который будем проверять пинг. Так как «падает» основной, то и укажем его имя. Этот метод исключает необходимость добавления правил блокировки трафика определенного канала с определенным IP-адресом на вкладке файервола.

    :if ( [get $firstInterface active] = false or [/ping $pingTo interface=[get $firstInterface gateway] count=5] = 0) do={
        :log info ($prefix . "FIRST NO INTERNET!!!");

        # Change distance
        :if ( [get $secondInterface distance] != 1 ) do={
            set $secondInterface distance=1;
            :log info ($prefix . "Distance for " . [get $secondInterface gateway] . " changed");
            $clearArp;
        }

        $reconnectPPPoE nameInterface=[get $firstInterface gateway];

    }

Вначале выводим лог, что Инета нет, после чего изменяем дистанцию резервного канала и чистим таблицу ARP, вызвав функцию.
После этого вызываем функцию переподключения PPPoE-соединения. Так как имя соединения мы указываем в одном месте (чтобы не плодить переменные), функция написана с учетом принятия переменной, содержащей имя интерфейса. Таким образом, при вызове функции в параметр `nameInterface` мы передаем имя нужного нам PPPoE-интерфейса.

Интернет «появился», или как все вернуть назад


На этом-то этапе мы и заюзаем функцию `if else`:
/ip route {
    # ...
    :if ( [get $firstInterface active] = false or [/ping $pingTo interface=[get $firstInterface gateway] count=5] = 0) do={
        # ...
    } else={
        :log info ($prefix . "FIRST INTERNET CONNECTED");

        # Change distance
        :if ( [get $secondInterface distance] != 3 ) do={
            set $secondInterface distance=3;
            :log info ($prefix . "Distance for " . [get $secondInterface gateway] . " changed");
            $clearArp;
        }
    }
    # ...
}

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

Как запускать

Создадим запись в шедулере
image

image

В поле `Name` введите имя записи, чтобы не запутаться.
Поле `Start Time` я выставил `00:00:00` для запуска ровно в полночь.
Интервал — 30 секунд
В поле `On Event` вписываем имя нашего скрипта — `script-check-inet`
И жмем «ОК».

Вот, собственно, и все!

Ниже под спойлером приведен полный код скрипта.

Полный код скрипта
# Set local variables
:local firstInterface "pppoe-rostelecom";
:local secondInterface "eth2-MTS";
:local pingTo "8.8.8.8";
:local prefix ">>> ";

# Function to cleaning ARP table
:local clearArp do={
    :local dumplist [/ip arp find]
    :foreach i in=$dumplist do={
        /ip arp remove $i
    }
    :log info ($prefix . "ARP cleaned");
}

# Function to reconnect PPPoE connection
:local reconnectPPPoE do={
    /interface pppoe-client set $nameInterface disable=yes;
    :delay 1s;
    /interface pppoe-client set $nameInterface disable=no;
}

:log info ($prefix . "START PING to $pingTo");

# Check FIRST interface
/interface pppoe-client {
    :if ( [get $firstInterface disable] = true) do={
        set $firstInterface disable=no;
        :delay 5s;
    }
}

# Check SECOND interface
/interface ethernet {
    :if ( [get $secondInterface disable] = true) do={
        set $secondInterface disable=no;
    }
}

/ip route {
    # Set objects to variables
    :set firstInterface [find gateway=$firstInterface];
    :set secondInterface [find gateway=$secondInterface];

    # Check routes
    :if ( [get $firstInterface distance] != 2 ) do={
        set $firstInterface distance=2;
        :log info ($prefix . "Distance for " . [get $firstInterface gateway] . " corrected");
    }

    :if ( [get $secondInterface distance] != 1 && [get $secondInterface distance] != 3) do={
        set $secondInterface distance=3;
        :log info ($prefix . "Distance for " . [get $secondInterface gateway] . " corrected");
    }


    # Check Internet
    :if ( [get $firstInterface active] = false or [/ping $pingTo interface=[get $firstInterface gateway] count=5] = 0) do={
        :log info ($prefix . "FIRST NO INTERNET!!!");

        # Change distance
        :if ( [get $secondInterface distance] != 1 ) do={
            set $secondInterface distance=1;
            :log info ($prefix . "Distance for " . [get $secondInterface gateway] . " changed");
            $clearArp;
        }

        $reconnectPPPoE nameInterface=[get $firstInterface gateway];

    } else={
        :log info ($prefix . "FIRST INTERNET CONNECTED");

        # Change distance
        :if ( [get $secondInterface distance] != 3 ) do={
            set $secondInterface distance=3;
            :log info ($prefix . "Distance for " . [get $secondInterface gateway] . " changed");
            $clearArp;
        }
    }
}

:log info ($prefix . "END PING to $pingTo");


Комментарии (0)

Let's block ads! (Why?)

Прерывания для самых маленьких

Релиз CLion 2016.1: новые инструменты и новые языки

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

У нас сегодня отличные новости — вышел очередной релиз нашей кросс-платорфменной среды для разработки на C и C++, CLion 2016.1.

Версия 2016.1


Вы, наверное, немного удивлены номером версии. Ближайшие релизы других наших десктопных инструментов, кстати, имеет такую же версию, начиная с IntelliJ IDEA 2016.1. В чем же смысл? Если коротко, то теперь все продукты в рамках пакета JetBrains All Products (то есть все десктопные инструменты) получают обновления примерно в одно и тоже время несколько раз в год. Таким образом, версия — это просто год и последовательный номер “пачки” релизов. Основные возможности, реализованные в платформе, попадают во все IDE одновременно, и такая унификация версий позволяет легче ориенироваться в платформенных изменениях.

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

А теперь — непосредственно о новых возможностях!

C++ парсер и улучшения по работе с кодом на C++


Долгое время CLion поддерживал C++11 с ограничениями: некорректно обрабатывались variadic templates, constexpr, user-defined литералы. В этой версии мы взялись за то, что, как нам показалось, “мешает” большинству наших пользователей — variadic templates. Код, подчеркнутый красным, некорректные нотификации от анализатора кода, неверное автодополнение и другие проблемы зачастую были связаны именно с этой возможностью C++11. Реализация variadic templates позволила закрыть порядка сотни багов в нашем трекере! В частности, спешим обрадовать пользователей Qt библиотеки — вызовы connect теперь обрабатываются корректно, а встроенный анализатор кода не предупреждает о некорректных типах:

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

Помимо прочего, мы наконец добились корректной работы автоматического импортирования для символов из STL (к сожалению, еще остаются проблемы при работе с MinGW-w64). Теперь, если соответствующий заголовочный файл не подключен, а символ уже используется, CLion предлагает добавить нужную директиву #include:

Если в CLion поставить курсор на какой-нибудь символ и вызвать окно документации (Ctrl+Q для Linux/Windows, F1 для OS X), можно посмотреть определение соответствующего символа и место, где он определен. В новой версии окно документации поддерживает гиперссылки на связанные топики, что существенно облегчает процесс чтения и понимания кода:

Отдельно упомянем новые возможности кодогенерации в коде на C++. Раньше для создания новых функций было две возможности — Override и Implement. Теперь появилась еще и Generate Definitions. Чем же они отличаются? По сути, мы выделили из Implement создание тела функции, а в Implement оставили только возможность генерации определения для чисто-виртуальных функций базовых классов. Новая функция доступна из меню генерации (Alt+Insert на Windows/Linux, ⌘N на OS X), напрямую (Shift+Ctrl+D на Windows/Linux, ⇧⌘D на OS X) и через intention actions (Alt+Enter):

Но главное даже не это. Самым важным улучшение является возможность генерировать функции in-place (не важно, через Override/Implement или через Generate Definitions), то есть там, где стоит курсор. Хотите получить тело функции в заголовочном файле — вызывайте функцию в соответствующем классе в этом заголовочном файле, хотите в .cpp файле — идите туда и вызывайте генерацию там. При наличии нескольких вариантов CLion уточнит, где именно вы хотите получить определение функции:

Управление директориями


CLion полагается на структуру проекта, которую задает CMake. То есть включены или не включены файлы в проект, где искать файлы из #include директив и т. д. А что, если среди файлов, которые стоит иметь включенными в проект, находятся еще и файлы логов или артифакты сборки? Как объяснить CLion, что не надо тратить время на индексацию таких директорий? Или как исключить библиотеку из контекста, в котором работают рефакторинги (вряд ли вам хочется, чтобы рефакторинги повлияли на код библиотеки, который, хоть и лежит внутри вашего проекта, но все же является сторонним)?

Для всех этих целей и реализована новая возможность Mark directory as:

Она дает возможность вручную разметить директории соответствующим образом. Выбор повлияет на работу:

  • автодополнения и автоимпорта
  • кодогенерации
  • навигации на файл/класс/символ по его имени
  • поиска по указанному пути
  • рефакторингов

Так, например, рефакторинги и кодогенерация не будут работать в исключенных из проекта директориях (Excluded) или в библиотеках (Library Files). А навигация и поиск имеют специальные опции для отображения результатов поиска по библиотекам.
Чуть более подробно это расписано в отдельном посте в нашем англоязычном блоге.

В дополнение к этому, если вы разрабатываете проект на одной машине, а собираете/запускаете на другой, в CLion 2016.1 появилась возможность настроить автоматическую синхронизацию файлов по FTP, FTPS или SFTP.

Отладчик


Одна из самых долгожданных возможностей — отладка процесса, запущенного на локальной машине из IDE. Конечно, многие спросят, а как же удаленная отладка? Пока нет, но до нее мы тоже доберемся!

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

Новые языки


В CLion 2016.1 появилась встроенная поддержка Python, а также доступен для установки плагин для поддержки Swift. Если у вас смешанный проект на Python/C/C++ или вас интересует Swift IDE на Linux, то милости просим! В плагинах поддержаны:
  • стандартные для наших IDE возможности редактора (подсветка, автодополнение, форматирование)
  • навигация по коду и поиск
  • анализатор кода (для Python)
  • рефакторинги
  • отладка

Подробнее про возможности плагинов см. в нашем блоге: Python, Swift. А для короткого ознакомления предлагаем два видео:

И многое другое


В этот релиз также вошли следующие изменения:
  • Новая команда для сброса CMake Cache. Позволяет почистить CMake Cache и при этом не сбрасывать кеши и индексы самой IDE.
  • Поддержка multiple working trees для Git.
  • Автоматическое создание Google Test конфигураций при загрузке проекта при наличии в проекте CMake таргета, слинкованного с gtest библиотекой.
  • Кастомный билд JRE на Linux с исправлениями от команды JetBrains.

И, наконец, небольшое видео, демонстрирующее новые возможности CLion 2016.1:

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

Ваша команда JetBrains CLion
The Drive to Develop

Комментарии (0)

Let's block ads! (Why?)

[Из песочницы] Замечательные zippers, или как я научился не волноваться и полюбил древовидные структуры данных

Известно, что дерево – довольно сложная структура. И если чтение успешно реализуется рекурсией (которая не лишена своих проблем), то с изменением дела обстоят совсем не хорошо.

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

Классическое концептуальное объяснение зиппера, выглядит как-то так: это взгляд изнутри на древовидную структуру как бы вывернутую наизнанку, вроде вывернутой перчатки.

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

У автора «потом» уже наступило. Эта статья – попытка дать альтернативное объяснение зипперов (не путать с объяснением для альтернативно одаренных, хотя…) такое, что позволит быстро понять и немедленно начать использовать зипперы в практических задачах.

Рассмотрим, как развивалась идея.

Допустим, у нас есть некоторая последовательность неважно каких данных. Пусть это будет вектор (массив).

Вот вектор с элементами-символами, с которым нам нужно работать. Пускай нам нужно гулять по нему влево и вправо и считывать символы. Естественным образом возникает идея некоторого «окошечка» шириной в один элемент, которое мы можем смещать вправо и влево.

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

Мы можем пойти дальше и создать такой API этого компонента:

  • ШагВлево
  • ШагВправо
  • ТекущееЗначение
  • ПозицияСлева
  • ПозицияСправа
  • КрайнийСлева?
  • КрайнийСправа?
  • ЗаменитьТекущееЗначение
  • ВставитьЗначениеСлева
  • ВставитьЗначениеСправа
  • УдалитьТекущееЗначение

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

А что с деревьями? Почему бы не придумать что-то аналогичное для деревьев? Легко!

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

  • ШагВлево
  • ШагВправо
  • ШагВверх
  • ШагВниз
  • ТекущееЗначение
  • КорневоеЗначение
  • ДочерниеЗначения
  • ПозицияСлева
  • ПозицияСправа
  • ПозицияСверху
  • КрайнийСлева?
  • КрайнийСправа?
  • Корень?
  • Лист?
  • ЗаменитьТекущееЗначение
  • ВставитьЗначениеСлева
  • ВставитьЗначениеСправа
  • УдалитьТекущееЗначение

Дамы и господа, разрешите представить… Zipper!

Очевидно, что приведенный API не полон, естественно нужно добавить два метода для depth first поиска: Предыдущий и Следующий, которые будут сдвигать окошечко вперед и назад согласно правилам поиска. Можно добавить метод ДобавитьДочернееЗначение, для удобства. В общем, мы плавно переходим к деталям реализации, чего делать не собирались.

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

А где же пресловутая вывернутая на изнанку перчатка?

Да вот же она! Если мы заменим методы ПозицияСлева, ПозицияСправа, ПозицияСверху на ЗначенияСлева, ЗначенияСправа, ЗначенияСверху, то мы получим «взгляд на дерево изнутри»: имеется текущее значение и

  • ЗначенияСлева
  • ЗначенияСправа
  • ЗначенияСверху
  • ДочерниеЗначения

Чем не вывернутая перчатка?

Можно переходить к практике.

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

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

Наша платформа – clojure(script) – персистентные структуры предоставляет. Мало того, она предоставляет и сами зипперы: пространство имен clojure.zip, рекомендую ознакомиться с исходным кодом – простая, чистенькая реализация.

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

А что на счет зипперов?

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

(zipper branch? children make-node root)

  • branch? – функция, по переданному ей узлу определяет ветка он в принципе или нет (может ли иметь дочерние узлы);
  • children – функция, по переданной ей ветке возвращает коллекцию дочерних узлов;
  • make-node – функция, по переданным ей узлу и коллекции дочерних возвращает ветку дерева, то есть узел с переданными дочерними;
  • root – корневой узел, то есть собственно наше дерево.

Используя эту функцию мы можем создать зиппер работающий с нашей конкретной структурой. Допустим, у нас есть такое небольшое деревце:
(def sample-tree 
 {:tag :div
  :content [
     {:tag :span :content ["С добрым утром"]}
     {:tag :span :content ["страна!"]}
  ]})


Создадим зиппер:
(def sample-z 
  (zipper
    (fn [node] (not (string? node)))   ; если не строчка то ветка
    (fn [node] (vec(:content node)))  ; берем :content у узла и приводим к вектору (мало ли может nil передадут)
    (fn [node children] (assoc node :content (vec children))) ; пишем в :content узла переданную коллекцию детей
    sample-tree)) ; наше деревце


Как нам получить полный текст дерева?
(loop [z sample-z result ""] ; цикл с переменными z и result
  (if (z/end? z) ; если дошли до конца дерева
    result  ; отдаем результат
    (recur (z/next z) (if (z/branch? z) result (str result (z/node z)))))) ; иначе продолжаем цикл с новыми значениями


Результат выполнения: “С добрым утромстрана!” Отметим, что обход дерева сделан итеративно, а не рекурсивно.

Нам бы вставить запятую с пробелом после обращения. Сказано – сделано!

(def new-z 
  (->
    sample-z
    z/next
    (z/insert-right {:tag :span :content [", "]})))


new-z это измененный зиппер. Если нам нужно собственно измененное дерево:
(def new-tree
  (z/root new-z))


Хотя базовый API реализован в виде функций пространства сlojure.zip, бывает полезно заглянуть в сам зиппер, а для этого нужно понимать, что он из себя представляет. В данной реализации это просто вектор из двух компонентов: текущий узел дерева и мапа описывающая его положение (та самая перчатка) с ключами:
  • :l – узлы слева
  • :r – узлы справа
  • :pnodes – узлы сверху (путь до корня)
  • :ppath – копия родительской «перчатки»

И немножечко терминологии: zipper – это концепт, идея. Конкретный инстанс (как new-z в нашем примере) принято называть локацией, что очень логично.

На этом все. Да поможет эта статья страждущему функциональному древосеку на его нелегком пути! Спасибо за внимание.

Комментарии (0)

Let's block ads! (Why?)

ICQ Contest. Итоги конкурса на редизайн мобильного приложения

ХаброСтатистика — в какое время лучше публиковать статью на хабре?

Нетехническая программа PHDays, или От хакеров до художников один шаг

Хакеры и художники — казалось бы, что может быть общего между ними, ведь это совершенно разные миры? Однако и те и другие не понаслышке знают, что такое вдохновение и творческий процесс. Мы решили повторить прошлогодний опыт и собираем на площадке международного форума по практической безопасности Positive Hack Days VI хакеров, художников и всех творческих людей. Рассказываем, что будет за кулисами технической программы.

Для посетителей и участников PHDays пройдет выставка иллюстраций Алексея Андреева — художника из Санкт-Петербурга. Его работы, выполненные в технике digital painting, очень полюбились посетителям прошлогоднего форума. Художник вновь приглашает всех отправиться в путешествие в фантастический мир: привычные глазу объекты и явления предстают в новом свете, и кажется, что все происходящее — правда, что это и есть самая настоящая жизнь. Фантазийные сюжеты, обаятельные герои и невероятное правдоподобие — вот, пожалуй, три главные составляющие картин Андреева.

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

Как и раньше, будет работать игровая зона. Советские игровые автоматы, классика олдскула — «Магистраль», «Морской бой», «Авторалли-М». А также полюбившиеся всем в 90-х годах Sega, Dendy и PlayStation. Подзарядиться энергией перед многочасовыми виртуальными боями или перед новой порцией докладов можно будет в автомате с космической едой. Да-да, той самой, в тюбике, которой питаются космонавты на орбите.

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

Любители высокого искусства встретятся с удивительными арт-объектами. Летопись PHDays на панно из дискет, хакерский манифест на большом экране, оптические инсталляции, рассмотреть которые можно только со строго определенного расстояния… Обмануть зрение и в прямом смысле слова услышать, как работает мозг, — все это и многое другое можно будет на PHDays VI.

Не останется в стороне и литература. В этом году снова пройдут чтения, в рамках конкурса киберпанковских рассказов «Взломанное будущее». Рассказы, вышедшие в финал, зачитают бессменные участники форума, создатели культовой радиопередачи «Модель для сборки». Они создадут подходящую атмосферу: чтение пройдет в сопровождении современной электронной музыки. Кстати, у каждого из вас еще есть возможность стать участником конкурса: рассказы принимаются до 15 апреля 2016 года по адресу cyberpunk@ptsecurity.com.

Напомним, что PHDays VI уже не за горами — он состоится 17 и 18 мая 2016 года в Центре международной торговли в Москве. На форуме соберутся со всего мира специалисты по безопасности и хакеры, представители госструктур, бизнесмены, молодые ученые и журналисты. Не упустите шанс принять участие! Купить билеты можно на странице http://ift.tt/1NBx1Jh. Чтобы бесплатно участвовать в форуме, вы можете выступить с исследованием в области ИБ (вторая волна Call for Papers продлится до 31 марта), стать участником одного из хакерских конкурсов (регистрация и отборочные соревнования откроются ближе к маю) или выйти в финал конкурса рассказов.

Комментарии (0)

Let's block ads! (Why?)

[Перевод] MCMC-сэмплинг для тех, кто учился, но ничего не понял

Рассказывая о вероятностном программировании и Байесовской статистике, я обычно не уделяю особого внимания тому, как, на самом деле, выполняется вероятностный вывод, рассматривая его как некий «чёрный ящик». Вся прелесть вероятностного программирования заключается в том, что, на самом деле, для того, чтобы строить модели, не обязательно понимать, как именно делается вывод. Но это знание, безусловно, весьма полезно.


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

Тут я мог бы сказать: «Всё очень просто. MCMC генерирует сэмплы из апостериорного распределения вероятностей, создавая обратимую цепь Маркова, равновесное распределение которой – это целевое апостериорное распределение. Вопросы?».

Объяснение это верное, но много ли от него пользы для непосвящённого? Меня больше всего раздражает в том, как учат математике и статистике, то, что никто никогда не говорит об интуитивно понятных идеях, лежащих в основе всяческих понятий. А эти идеи обычно довольно просты. С таких занятий можно вынести трёхэтажные математические формулы, но не понимание того, как всё устроено. Меня учили именно так, а я хотел понять. Я бессчётные часы бился головой о математические стены, прежде чем наступал момент очередного прозрения, прежде чем очередная «Эврика!» срывалась с моих губ. После того, как мне удавалось разобраться, то, что раньше виделось сложным, оказывалось на удивление простым. То, что раньше пугало нагромождением математических знаков, становилось полезным инструментом.

Этот материал – попытка интуитивно понятного объяснения MCMC-сэмплинга (в частности, алгоритма Метрополиса). Мы будем использовать примеры кода вместо формул или математических выкладок. В конечном итоге, без формул не обойтись, но лично я считаю, что лучше всего начинать с примеров и достичь интуитивного понимания вопроса, прежде чем переходить к языку математики.

Проблема и её неинтуитивное решение


Взглянем на формулу Байеса:

У нас есть P(θ|x) – то, что нас интересует, а именно – апостериорная вероятность, или распределение вероятностей параметров модели θ, вычисленная после того, как приняты во внимание данные x, взятые из наблюдений. Для того, чтобы получить то, что нам нужно, надо перемножить априорную вероятность P(θ), то есть – то, что мы думаем о θ до проведения экспериментов, до получения данных, и функцию правдоподобия P(x|θ), то есть – то, что мы думаем о том, как распределены данные. Числитель дроби найти очень легко.

Теперь присмотримся к знаменателю P(x), который ещё называют свидетельством, то есть – свидетельством того, что данные х, были сгенерированы этой моделью. Вычислить его можно, проинтегрировав все возможные значения параметров:


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

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

Продолжая размышления, можно заявить: «Ладно, тогда давайте сконструируем цепь Маркова, равновесное распределение которой совпадает с нашим апостериорным распределением». Я, конечно, шучу. Большинство людей так не выразится, очень уж безумно это звучит. Если вычислить напрямую нельзя, взять сэмплы из распределения тоже нельзя, то построить цепь Маркова с вышеозначенными свойствами – задача и вовсе неподъёмная.

И вот здесь нас ждёт удивительное открытие. Сделать это, на самом деле, очень легко. Существует целый класс алгоритмов для решения таких задач: методы Монте-Карло в Марковских цепях (Markov Chain Monte Carlo, MCMC). Сущность этих алгоритмов – создание цепи Маркова для выполнения аппроксимации методом Монте-Карло.

Постановка задачи


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

Листинг 1


%matplotlib inline

import numpy as np
import scipy as sp
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns

from scipy.stats import norm

sns.set_style('white')
sns.set_context('talk')

np.random.seed(123)

Теперь сгенерируем данные. Это будут 100 точек, нормально распределённых вокруг нуля. Наша цель заключается в том, чтобы оценить апостериорное распределение средней mu (предполагается, что мы знаем, что среднеквадратическое отклонение равно 1).

Листинг 2


data = np.random.randn(20)

Теперь построим гистограмму.

Листинг 3


ax = plt.subplot()
sns.distplot(data, kde=False, ax=ax)
_ = ax.set(title='Histogram of observed data', xlabel='x', ylabel='# observations');

Гистограмма наблюдаемых данных

Теперь нужно описать модель. Мы рассматриваем простой случай, поэтому предполагаем, что данные распределены нормально, то есть, функция правдоподобия модели так же распределена нормально. Как вы, должно быть, знаете, у нормального распределения есть два параметра – это математическое ожидание (среднее значение) μ и среднеквадратическое отклонение σ. Для простоты, будем считать, что мы знаем, что σ=1. Мы хотим вывести апостериорную вероятность для μ. Для каждого искомого параметра нужно выбрать априорное распределение вероятностей. Для простоты, допустим, что нормальное распределение будет априорным распределением для μ. Таким образом, на языке статистики, модель будет выглядеть так:

μ∼Normal(0,1)
x|μ∼Normal(x;μ,1)

Что особенно удобно – для этой модели, на самом деле, можно вычислить апостериорное распределение вероятностей аналитически. Дело в том, что для нормальной функции правдоподобия с известным среднеквадратическим отклонением, нормальное априорное распределение вероятностей для mu является сопряжённым априорным распределением. То есть, наше апостериорное распределение будет следовать тому же распределению, что и априорное. В итоге, мы знаем, что апостериорное распределение для μ так же является нормальным. В Википедии несложно найти методику расчёта параметров для апостериорного распределения. Математическое описание этого можно найти здесь.

Листинг 4


def calc_posterior_analytical(data, x, mu_0, sigma_0):
    sigma = 1.
    n = len(data)
    mu_post = (mu_0 / sigma_0**2 + data.sum() / sigma**2) / (1. / sigma_0**2 + n / sigma**2)
    sigma_post = (1. / sigma_0**2 + n / sigma**2)**-1
    return norm(mu_post, np.sqrt(sigma_post)).pdf(x)

ax = plt.subplot()
x = np.linspace(-1, 1, 500)
posterior_analytical = calc_posterior_analytical(data, x, 0., 1.)
ax.plot(x, posterior_analytical)
ax.set(xlabel='mu', ylabel='belief', title='Analytical posterior');
sns.despine()

Апостериорное распределение, найденное аналитически

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

Код, как путь к пониманию сущности MCMC-сэмплинга


Теперь поговорим о сэмплировании. Во-первых, нужно найти начальную позицию параметра (её можно выбрать случайным образом). Давайте зададим её произвольно следующим образом:
mu_current = 1.

Затем предлагается переместиться, «прыгнуть» из этой позиции в какое-то другое место (это уже относится к цепям Маркова). Эту новую позицию можно выбрать и «методом тыка», и руководствуясь какими-то глубокими соображениями. Сэмплер в алгоритме Метрополиса прост, как пять копеек: он выбирает образец из нормального распределения с центром в текущем значении mu (переменная mu_current) с неким среднеквадратическим отклонением (proposal_width), которое определяет ширину диапазона, из которого выбираются предлагаемые значения. Здесь мы используем scipy.stats.norm. Надо сказать, что вышеупомянутое нормальное распределение не имеет ничего общего с тем, что используется в модели.
proposal = norm(mu_current, proposal_width).rvs()

Следующий шаг – оценка того, подходящее ли место выбрано для перехода. Если полученное нормальное распределение с предложенным mu объясняет данные лучше, чем при предыдущем mu, то в выбранном направлении, безусловно, стоит двигаться. Но что значит «лучше объясняет данные»? Мы определяем это понятие, вычисляя вероятность данных, учитывая функцию правдоподобия (нормальную) с предложенными значениями параметров (предложенное mu и sigma, значение которого зафиксировано и равно 1). Расчёты тут простые. Достаточно вычислить вероятность для каждой точки данных с помощью команды scipy.stats.normal(mu, sigma).pdf(data) и затем перемножить индивидуальные вероятности, то есть – найти значение функции правдоподобия. Обычно в таком случае пользуются логарифмическим распределением вероятностей, но здесь мы это опускаем.
likelihood_current = norm(mu_current, 1).pdf(data).prod()
likelihood_proposal = norm(mu_proposal, 1).pdf(data).prod()

# Вычисление априорного распределения вероятности для текущего и предложенного mu        
prior_current = norm(mu_prior_mu, mu_prior_sd).pdf(mu_current)
prior_proposal = norm(mu_prior_mu, mu_prior_sd).pdf(mu_proposal)

# Числитель формулы Байеса
p_current = likelihood_current * prior_current
p_proposal = likelihood_proposal * prior_proposal

До этого момента мы, на самом деле, пользовались алгоритмом восхождения к вершине, который лишь предлагает перемещения в случайных направлениях и принимает новое положение только если mu_proposal имеет более высокий уровень правдоподобия, нежели mu_current. В конечном итоге мы дойдём до варианта mu = 0 (или к значению, близкому к этому), откуда двигаться будет уже некуда. Однако, мы хотим получить апостериорное распределение, поэтому должны иногда соглашаться на перемещения в другом направлении. Главный секрет здесь заключается в том, что разделив p_proposal на p_current, мы получим вероятность принятия предложения.
p_accept = p_proposal / p_current

Можно заметить, что если p_proposal больше, чем p_current, полученная вероятность будет больше 1, и такое предложение мы, определённо, примем. Однако, если p_current больше чем p_proposal, скажем, в два раза, шанс перехода будет составлять уже 50%:
accept = np.random.rand() < p_accept

if accept:
    # Обновляем позицию
    cur_pos = proposal

Эта простая процедура даёт нам сэмплы из апостериорного распределения.

Зачем это всё?


Оглянемся назад и отметим, что введение в систему вероятности принятия предлагаемой позиции перехода – это причина, по которой всё это работает и позволяет нам избежать интегрирования. Это хорошо видно, если вычислять уровень принятия предложения для нормализованного апостериорного распределения и наблюдать за тем, как он соотносится с уровнем принятия предложения для ненормализованного апостериорного распределения (скажем, μ0 – это текущая позиция, а μ это предлагаемая новая позиция):

Если это объяснить, то, деля ту апостериорную вероятность, которая получилась для предлагаемого параметра, на ту, что вычислена для текущего параметра, мы избавляемся от уже надоевшего P(x), которое посчитать не в состоянии. Можно интуитивно понять, что мы делим полное апостериорное распределение вероятностей в одной позиции на то же самое в другой позиции (вполне обычная операция). Таким образом мы посещаем области с более высоким уровнем апостериорного распределения вероятностей сравнительно более часто, чем области с низким уровнем.

Складываем полную картину


Соберём вышесказанное воедино.

Листинг 5


def sampler(data, samples=4, mu_init=.5, proposal_width=.5, plot=False, mu_prior_mu=0, mu_prior_sd=1.):
    mu_current = mu_init
    posterior = [mu_current]
    for i in range(samples):
        # предлагаем новую позицию
        mu_proposal = norm(mu_current, proposal_width).rvs()

        # Вычисляем правдоподобие, перемножая вероятности для каждой точки данных
        likelihood_current = norm(mu_current, 1).pdf(data).prod()
        likelihood_proposal = norm(mu_proposal, 1).pdf(data).prod()
        
        # Вычисляем априорное распределение вероятностей для текущего и предлагаемого mu        
        prior_current = norm(mu_prior_mu, mu_prior_sd).pdf(mu_current)
        prior_proposal = norm(mu_prior_mu, mu_prior_sd).pdf(mu_proposal)
        
        p_current = likelihood_current * prior_current
        p_proposal = likelihood_proposal * prior_proposal
        
        # Принять предложенную точку?
        p_accept = p_proposal / p_current
        
        # Обычно сюда было бы включено априорное распределение вероятностей, здесь это опущено для простоты 
        accept = np.random.rand() < p_accept
        
        if plot:
            plot_proposal(mu_current, mu_proposal, mu_prior_mu, mu_prior_sd, data, accept, posterior, i)
        
        if accept:
            # Обновляем позицию
            mu_current = mu_proposal
        
        posterior.append(mu_current)
        
    return posterior

# Функция визуализации
def plot_proposal(mu_current, mu_proposal, mu_prior_mu, mu_prior_sd, data, accepted, trace, i):
    from copy import copy
    trace = copy(trace)
    fig, (ax1, ax2, ax3, ax4) = plt.subplots(ncols=4, figsize=(16, 4))
    fig.suptitle('Iteration %i' % (i + 1))
    x = np.linspace(-3, 3, 5000)
    color = 'g' if accepted else 'r'
        
    # Визуализация априорного распределения вероятностей
    prior_current = norm(mu_prior_mu, mu_prior_sd).pdf(mu_current)
    prior_proposal = norm(mu_prior_mu, mu_prior_sd).pdf(mu_proposal)
    prior = norm(mu_prior_mu, mu_prior_sd).pdf(x)
    ax1.plot(x, prior)
    ax1.plot([mu_current] * 2, [0, prior_current], marker='o', color='b')
    ax1.plot([mu_proposal] * 2, [0, prior_proposal], marker='o', color=color)
    ax1.annotate("", xy=(mu_proposal, 0.2), xytext=(mu_current, 0.2),
                 arrowprops=dict(arrowstyle="->", lw=2.))
    ax1.set(ylabel='Probability Density', title='current: prior(mu=%.2f) = %.2f\nproposal: prior(mu=%.2f) = %.2f' % (mu_current, prior_current, mu_proposal, prior_proposal))
    
    # Правдоподобие
    likelihood_current = norm(mu_current, 1).pdf(data).prod()
    likelihood_proposal = norm(mu_proposal, 1).pdf(data).prod()
    y = norm(loc=mu_proposal, scale=1).pdf(x)
    sns.distplot(data, kde=False, norm_hist=True, ax=ax2)
    ax2.plot(x, y, color=color)
    ax2.axvline(mu_current, color='b', linestyle='--', label='mu_current')
    ax2.axvline(mu_proposal, color=color, linestyle='--', label='mu_proposal')
    #ax2.title('Proposal {}'.format('accepted' if accepted else 'rejected'))
    ax2.annotate("", xy=(mu_proposal, 0.2), xytext=(mu_current, 0.2),
                 arrowprops=dict(arrowstyle="->", lw=2.))
    ax2.set(title='likelihood(mu=%.2f) = %.2f\nlikelihood(mu=%.2f) = %.2f' % (mu_current, 1e14*likelihood_current, mu_proposal, 1e14*likelihood_proposal))
    
    # Апостериорное распределение вероятностей
    posterior_analytical = calc_posterior_analytical(data, x, mu_prior_mu, mu_prior_sd)
    ax3.plot(x, posterior_analytical)
    posterior_current = calc_posterior_analytical(data, mu_current, mu_prior_mu, mu_prior_sd)
    posterior_proposal = calc_posterior_analytical(data, mu_proposal, mu_prior_mu, mu_prior_sd)
    ax3.plot([mu_current] * 2, [0, posterior_current], marker='o', color='b')
    ax3.plot([mu_proposal] * 2, [0, posterior_proposal], marker='o', color=color)
    ax3.annotate("", xy=(mu_proposal, 0.2), xytext=(mu_current, 0.2),
                 arrowprops=dict(arrowstyle="->", lw=2.))
    #x3.set(title=r'prior x likelihood $\propto$ posterior')
    ax3.set(title='posterior(mu=%.2f) = %.5f\nposterior(mu=%.2f) = %.5f' % (mu_current, posterior_current, mu_proposal, posterior_proposal))
    
    if accepted:
        trace.append(mu_proposal)
    else:
        trace.append(mu_current)
    ax4.plot(trace)
    ax4.set(xlabel='iteration', ylabel='mu', title='trace')
    plt.tight_layout()
    #plt.legend()

Визуализация MCMC


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

В первом столбце показано априорное распределение вероятностей, то есть – наши предположения о μ до ознакомления с данными. Как можно видеть, это распределение не меняется, мы лишь показываем здесь предложения нового значения μ. Вертикальные синие линии – это текущее μ. А предлагаемое μ отображается либо зелёным, либо красным цветом (это, соответственно, принятые и отвергнутые предложения).

Во втором столбце – функция правдоподобия и то, что мы используем для того, чтобы оценить, насколько хорошо модель объясняет данные. Здесь можно заметить, что график меняется в соответствии с предлагаемым μ. Там же отображается и синяя гистограмма – сами данные. Сплошная линия выводится либо зелёным, либо красным цветом – это график функции правдоподобия при mu, предложенном на текущем шаге. Чисто интуитивно понятно, что чем сильнее функция правдоподобия перекрывается с графическим отображением данных – тем лучше модель объясняет данные и тем выше будет результирующая вероятность. Точечная линия того же цвета – это предложенное mu, точечная синяя линия – это текущее mu.

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

В четвёртой колонке представлен след выборки, то есть – значения μ, сэмплы, полученные на основе модели. Здесь мы показываем каждый сэмпл, вне зависимости от того, был ли он принят или отвергнут (в таком случае линия не меняется).

Обратите внимание на то, что мы всегда двигаемся к сравнительно более правдоподобным значениям μ (в плане плотности их апостериорного распределения вероятности) и лишь иногда – к сравнительно менее правдоподобным значениям μ. Например, как в итерации №1 (номера итераций можно видеть в верхней части каждого ряда изображений по центру.

Листинг 6


np.random.seed(123)
sampler(data, samples=8, mu_init=-1., plot=True);








Визуализация MCMC

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

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

Листинг 7


posterior = sampler(data, samples=15000, mu_init=1.)
fig, ax = plt.subplots()
ax.plot(posterior)
_ = ax.set(xlabel='sample', ylabel='mu');


Визуализация 15000 сэмплов

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

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

Листинг 8


ax = plt.subplot()
sns.distplot(posterior[500:], ax=ax, label='estimated posterior')
x = np.linspace(-.5, .5, 500)
post = calc_posterior_analytical(data, x, 0, 1)
ax.plot(x, post, 'g', label='analytic posterior')
_ = ax.set(xlabel='mu', ylabel='belief');
ax.legend();


Аналитическое и оценочное апостериорные распределения вероятностей

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

Ширина диапазона для выборки предлагаемых значений


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

Вот, например, что мы получили, установив параметр proposal_width в значение 0,01.

Листинг 9


posterior_small = sampler(data, samples=5000, mu_init=1., proposal_width=.01)
fig, ax = plt.subplots()
ax.plot(posterior_small);
_ = ax.set(xlabel='sample', ylabel='mu');


Результат использования слишком маленького диапазона

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

Листинг 10


posterior_large = sampler(data, samples=5000, mu_init=1., proposal_width=3.)
fig, ax = plt.subplots()
ax.plot(posterior_large); plt.xlabel('sample'); plt.ylabel('mu');
_ = ax.set(xlabel='sample', ylabel='mu');


Результат использования слишком большого диапазона

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

Листинг 11


sns.distplot(posterior_small[1000:], label='Small step size')
sns.distplot(posterior_large[1000:], label='Large step size');
_ = plt.legend();


Маленький и большой размер шага

С использованием большого количества итераций, то, что у нас получится, в конечном счёте, будет выглядеть как настоящее апостериорное распределение. Главное то, что нам нужно, чтобы сэмплы были независимы друг от друга. В данном случае это, очевидно, не так. Для того, чтобы оценить эффективность нашего сэмплера, можно воспользоваться показателем автокорреляции. То есть – узнать, как образец i коррелирует с образцом i-1, i-2, и так далее.

Листинг 12


from pymc3.stats import autocorr
lags = np.arange(1, 100)
fig, ax = plt.subplots()
ax.plot(lags, [autocorr(posterior_large, l) for l in lags], label='large step size')
ax.plot(lags, [autocorr(posterior_small, l) for l in lags], label='small step size')
ax.plot(lags, [autocorr(posterior, l) for l in lags], label='medium step size')
ax.legend(loc=0)
_ = ax.set(xlabel='lag', ylabel='autocorrelation', ylim=(-.1, 1))


Автокорреляция для маленького, среднего и большого размера шага

Очевидно то, что хотелось бы иметь интеллектуальный способ автоматического определения подходящего размера шага. Один из обычно используемых методов заключается в такой подстройке интервала, из которого выбирают значения, чтобы примерно 50% предложений отбрасывалось. Что интересно, другие алгоритмы MCMC, вроде Гибридного метода Монте-Карло (Hamiltonian Monte Carlo) очень похожи на тот, о котором мы говорили. Главная их особенность заключается в том, что они ведут себя «умнее», когда выдвигают предложения для следующего «прыжка».

Переходим к более сложным моделям


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

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

Листинг 13


import pymc3 as pm

with pm.Model():
    mu = pm.Normal('mu', 0, 1)
    sigma = 1.
    returns = pm.Normal('returns', mu=mu, sd=sigma, observed=data)
    
    step = pm.Metropolis()
    trace = pm.sample(15000, step)
    
sns.distplot(trace[2000:]['mu'], label='PyMC3 sampler');
sns.distplot(posterior[500:], label='Hand-written sampler');
plt.legend();


Результаты работы различных сэмплеров

Подведём итоги


Надеемся, мы смогли донести до вас сущность MCMC, Метрополис-сэмплера, вероятностного вывода, и теперь у вас появилось интуитивное понимание всего этого. А значит – вы готовы к чтению материалов по данному вопросу, насыщенных математическими формулами. Там вы сможете найти все те детали, которые мы обошли здесь стороной для того, чтобы не скрыть за ними самого главного.
О, а приходите к нам работать? :)
wunderfund.io — молодой фонд, который занимается высокочастотной алготорговлей. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.

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

Присоединяйтесь к нашей команде: wunderfund.io

Комментарии (0)

Let's block ads! (Why?)

L10n строк в приложениях (JavaScript)

Лучшие технологические видео Channel 9 этой недели, 18 марта


Всем привет!

Как известно, все технологические видео-материалы Microsoft вы можете найти на нашем официальном портале Channel 9. Это же касается многочисленных курсов виртуальной академии Microsoft (MVA) и всех записей с онлайн-трансляции наших мероприятий.

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

Начнем с самой громкой новости марта — презентация SQL Server 2016. Для, всех, кто не успел посмотреть мероприятие онлайн, у нас хорошие новости — записи уже доступны на Channel 9:

Tooling Improvements in SQL Server 2016

Ссылка на все эпизоды.

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

Episode 13 — Basics of .NET Core

За неделю эксперты ASP.NET Monsters успевают подготовить несколько эпизодов, где в рамках тематики шоу рассказывают и про самые горячие тренды технологий, такие как Docker:

Episode 15 — ASP.NET Core on Docker

Ссылка на все эпизоды.

Еще один регулярный канал на Channel 9 для поклонников меньше сушать и больше делать — The Maker Show. Каждую неделю эксперты проводят пошаговые демонстрации использования различных технологий, включая электронику, инструменты разработки, платы, микроконтроллеры, сенсоры, строят собственные гаджеты, 3D модели, прототипы и другие интересные вещи.

Пример How-to видео по установке Windows 10 на Raspberry Pi 2:

The Maker Show: Episode 5 — Installing Windows 10 on a Raspberry Pi 2

А вот самое свежее видео этой недели:

The Maker Show: Episode 7 — The Photon Awakens

Ссылка на все эпизоды.

Далее представляем вам запись инетерсного вебинара, где вы познакомитесь с компонентами Device Guard, требованиями к устройствам и ПО, особенностями настройки и сценариями применения этого нового решения. Device Guard – набор программно-аппаратных технологий защиты, доступный для устройств с Windows 10:

И в заключение, не так давно в Москве прошло мероприятие ALM Summit, где технологические евангелисты Microsoft и эксперты индустрии рассказывали о том, как улучшить процессы по разработке программного обеспечения, а так же о последних разработках компании Microsoft в области управления жизненным циклом. Записи докладов уже опубликованы и вы можете ознакомиться с одним из них в нашем обзоре:

Построение DevOps на основе TFS/VSTS

Ссылка на все эпизоды.

На сегодня это все. Следующая подборка интересных видео ровно через неделю!

Полезные ссылки:


Комментарии (0)

Let's block ads! (Why?)

SoftMocks: наша замена runkit для PHP 7

[unable to retrieve full-text content]


Компания Badoo одной из первых перешла на PHP 7 — мы совсем недавно писали об этом. В той статье мы говорили об изменениях в инфраструктуре тестирования и обещали подробнее рассказать о разработанной нами замене для расширения runkit под названием SoftMocks.

SoftMocks


Идея у SoftMocks очень простая и отражена в названии: нужно реализовать аналог для runkit, максимально совместимый с ним по семантике, на чистом PHP. Soft здесь подчеркивает то, что он реализован не внутри ядра PHP, а поверх него, без использования Zend API и прочего hardcore. Тот факт, что он на чистом PHP, означает, что мы можем спокойно переходить на новую версию PHP и просто добавлять поддержку нового синтаксиса, а не переписывать расширения с новой версией Zend API и ловить миллионы багов из-за различных тонкостей в семантике.
Читать дальше →

Ключ от продуктов JetBrains всем учащимся на Stepic.org

Google's beacon platform. Часть 2 — Nearby meassages API

Google's beacon platform — это решение для работы с Bluetooth маячками. Платформа работает с разными маячками от разных производителей, предоставляя разработчикам единый, простой и гибкий инструмент.

Перед прочтением этой статьи я рекомендую ознакомиться с концепцией Physical Web о которой я рассказывал в своей прошлой статье: Концепция Physical web. Bluetooth маячки. Сравнение стандартов iBeacon, AltBeacon и Eddystone.

Google's beacon platform. Часть 1 — Proximity beacon API
Google's beacon platform. Часть 2 — Nearby meassages API

Основным средством, в рамках Google's beacon platform, для работы на клиентской стороне с bluetooth маячками, является Nearby Messages API. В этой статье я расскажу как настроить проекты на а платформах Android и iOS, и добавить в приложение возможность получать и разбирать сообщения от ble-маячков.

Nearby Messages API


Nearby Messages API — это API, которое реализует парадигму publish-subscribe и позволяет разным устройствам публиковать, и подписываться на сообщения, таким образом обмениваться данными. Nearby Messages API является частью Nearby. Для обмена сообщениями устройства не обязательно должны находиться в одной сети, но должны быть подключены к интернету. В нашем случае подключение к интернету должно быть у того смартфона или планшета на котором мы хотим получать сообщения. Маячкам подключение к интернету не нужно! Nearby Messages API позволяет обмениваться сообщениями с помощью Bluetooth, Bluetooth Low Energy, Wi-Fi и даже ультразвука, но мы будем использовать только Bluetooth Low Energy что бы минимизировать потребление энергии.

Nearby Messages API на Android


Nearby Messages API доступен на устройствах с Android в библиотеке Google Play services версии 7.8.0 или выше.
Убедитесть что у вас установлена последняя версия клиентской библиотеки для Google Play на вашем хосте для разработки:
  • Откройте Android SDK Manager.
  • Перейдите в A ppearance & Behavior > System Settings > Android SDK > SDK Tools и убедитесь что установлены следующие пакеты:
    • Google Play services
    • Google Repository

Для использования Nearby Messages API, конечно же понадобится Google Account. Так же необходимо получить API ключ. Ключи для Android, iOS и Proximity Beacon API должны быть созданы в рамках одно проекта Google Developers Console. Очень советую ознакомиться с Best practices for securely using API keys
Осторожно GIF. Пример того как получить API ключ:
image

Настраиваем проект:
Открываем или создаём новый проект, открываем build.gradle файл и добавляем в него Google Play services client library как зависимость.
Содержание файла build.gradle
apply plugin: 'android'
...

dependencies {
    compile 'com.google.android.gms:play-services-nearby:8.4.0'
}


Настраиваем manifest файл в который добавляем сгенерированный ранее API ключ:
<manifest xmlns:android="http://ift.tt/nIICcg"
    package="com.google.sample.app" >
    <application ...>
        <meta-data
            android:name="com.google.android.nearby.messages.API_KEY"
            android:value="API_KEY" />
        <activity>
        ...
        </activity>
    </application>
</manifest>


Создаём в нашем приложении GoogleApiClient и добавляем Nearby Messages API
Пример кода который показывает как добавить Nearby Messages API:
Создаём в приложении GoogleApiClient:
mGoogleApiClient = new GoogleApiClient.Builder(this)
     .addApi(Nearby.MESSAGES_API)
     .addConnectionCallbacks(this)
     .addOnConnectionFailedListener(this)
     .build();


Получение сообщений


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

Nearby Messages API требует разрешения пользователя на запросы publish() и subscribe(). Поэтому приложение должно проверять на что пользователь уже дал свое согласие и если такое отсутствует, то вызывать диалог запроса разрешений.

Что бы реализовать запрос разрешения у пользователя во время исполнения вашего приложения, вы можете:

  • Присоединить result callback к вызовам publish() and subscribe().
  • Использовать Nearby.Messages.getPermissionStatus() что бы проверить статус разрешения непосредственно перед вызовом publish() или subscribe()

Реализация result callback


Для проверки статус кода ошибки в result callback необходимо вызвать status.getStatusCode(). Если получен статус код APP_NOT_OPTED_IN отобразите диалог запроса разрешений вызовом status.startResolutionForResult() и используйте onActivityResult() что бы повторно реинициировать какие-либо невыполненные запросы подписки или публикации.

Следующий пример демонстрирует простой result callback, который проверяет, какие пользователь предоставил разрешения. Если пользователь не предоставил разрешений, вызывается status.startResolutionForResult(), чтобы предложить пользователю разрешить Nearby Messages. В этом примере boolean mResolvingError используется чтобы избежать многократного запуска таких предложений:

Пример реализации result callback:
private void handleUnsuccessfulNearbyResult(Status status) {
    Log.i(TAG, "Processing error, status = " + status);
    if (mResolvingError) {
        // Already attempting to resolve an error.
        return;
    } else if (status.hasResolution()) {
        try {
            mResolvingError = true;
            status.startResolutionForResult(getActivity(),
                    Constants.REQUEST_RESOLVE_ERROR);
        } catch (IntentSender.SendIntentException e) {
            mResolvingError = false;
            Log.i(TAG, "Failed to resolve error status.", e);
        }
    } else {
        if (status.getStatusCode() == CommonStatusCodes.NETWORK_ERROR) {
            Toast.makeText(getActivity().getApplicationContext(),
                    "No connectivity, cannot proceed. Fix in 'Settings' and try again.",
                    Toast.LENGTH_LONG).show();
        } else {
            // To keep things simple, pop a toast for all other error messages.
            Toast.makeText(getActivity().getApplicationContext(), "Unsuccessful: " +
                    status.getStatusMessage(), Toast.LENGTH_LONG).show();
        }
    }
}


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

Реиницализация невыполненных запросов


Следующий пример показывает реализацию метода onActivityResult(), который вызывается после того как пользователь отреагирует на диалог запроса разрешений. В случае если пользователь ответит согласием, любые ожидающие запросы подписки или публикации будут выполнены. А данном примере вызывается метод executePendingTasks()
Реиницаиалзация невыполненных запросов:
@Override
protected void onActivityResult(int requestCode, int resultCode, Intent data) {
    super.onActivityResult(requestCode, resultCode, data);

    if (requestCode == Constants.REQUEST_RESOLVE_ERROR) {
        // User was presented with the Nearby opt-in dialog and pressed "Allow".
        mResolvingError = false;
        if (resultCode == Activity.RESULT_OK) {
            // Execute the pending subscription and publication tasks here.
            mMainFragment.executePendingTasks();
        } else if (resultCode == Activity.RESULT_CANCELED) {
            // User declined to opt-in. Reset application state here.
        } else {
            Toast.makeText(this, "Failed to resolve error with code " + resultCode,
                    Toast.LENGTH_LONG).show();
        }
    }


Так же, чтобы уменьшить задержку при сканировании маячков, рекомендуется использовать Strategy.BLE_ONLY при вызове Nearby.Messages.subscribe(). Когда эта опция установлена, Nearby Messages API не задействует Wi-Fi сканирование или классические сканирования Bluetooth. Это уменьшает задержку обнаружения маячков, поскольку система не циклирует через все возможные типы сканирования, а так же уменьшает потреблении энергии.

Подписка в активном режиме:


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

Приложение может инициировать подписку в активном режиме вызвав метод Nearby.Messages.subscribe(GoogleApiClient, MessageListener, SubscribeOptions) и установив для параметра Strategy значение BLE_ONLY.

Фрагмент кода демонстрирующий инициирование подписки в активном режиме:
// Create a new message listener.
mMessageListener = new MessageListener() {
    @Override
    public void onFound(Message message) {
        // Do something with the message.
        Log.i(TAG, "Found message: " + message);
    }

    // Called when a message is no longer detectable nearby.
    public void onLost(Message message) {
        // Take appropriate action here (update UI, etc.)
    }
}

// Subscribe to receive messages.
Log.i(TAG, "Trying to subscribe.");
// Connect the GoogleApiClient.
if (!mGoogleApiClient.isConnected()) {
    if (!mGoogleApiClient.isConnecting()) {
        mGoogleApiClient.connect();
    }
} else {
    SubscribeOptions options = new SubscribeOptions.Builder()
            .setStrategy(Strategy.BLE_ONLY)
            .setCallback(new SubscribeCallback() {
                @Override
                public void onExpired() {
                    Log.i(TAG, "No longer subscribing.");
                }
            }).build();

    Nearby.Messages.subscribe(mGoogleApiClient, mMessageListener, options)
            .setResultCallback(new ResultCallback<Status>() {
                @Override
                public void onResult(Status status) {
                    if (status.isSuccess()) {
                        Log.i(TAG, "Subscribed successfully.");
                    } else {
                        Log.i(TAG, "Could not subscribe.");
                        // Check whether consent was given;
                        // if not, prompt the user for consent.
                        handleUnsuccessfulNearbyResult(status);
                    }
                }
            });
}


Для уменьшения потребления энергии и соответственно продления срока работы аккумулятора, вызывайте Nearby.Messages.unsubscribe() в методеOnStop()вашего приложения. Когда подписка на сообщения больше не нужна, приложение должно отписаться вызвав методNearby.Messages.unsubscribe(GoogleApiClient, MessageListener)`.

Подписка в фоновом режиме


Когда приложение подписывается на сообщения в фоновом режиме, срабатывает low-power сканирование при событиях включения экрана, даже когда приложение в настоящее время не активно. Вы можете использовать эти фоновые события low-power сканирования, чтобы "разбудить" приложение в ответ на конкретное сообщение. Фоновые подписки потребляют меньше энергии, чем подписка в активном режиме, но имеют более высокую задержку и низкую надежность.

Подписка в фоновом режиме инициируется вызовом метода Nearby.Messages.subscribe(GoogleApiClient, PendingIntent,SubscribeOptions) и заданием для параметра Strategy значения BLE_ONLY.

Фрагмент кода демонстрирующий инициирование подписки в фоновом режиме:
// Subscribe to messages in the background.
private void backgroundSubscribe() {
    // Connect the GoogleApiClient.
    if (!mGoogleApiClient.isConnected()) {
        if (!mGoogleApiClient.isConnecting()) {
            mGoogleApiClient.connect();
        }
    } else {
        Log.i(TAG, "Subscribing for background updates.");
        SubscribeOptions options = new SubscribeOptions.Builder()
                .setStrategy(Strategy.BLE_ONLY)
                .build();
        Nearby.Messages.subscribe(mGoogleApiClient, getPendingIntent(), options)
                .setResultCallback(new ResultCallback<Status>() {
                    @Override
                    public void onResult(Status status) {
                        if (status.isSuccess()) {
                            Log.i(TAG, "Subscribed successfully.");
                        } else {
                            Log.i(TAG, "Could not subscribe.");
                            handleUnsuccessfulNearbyResult(status);
                        }
                    }
                });
    }
}

private PendingIntent getPendingIntent() {
    return PendingIntent.getService(getApplicationContext(), 0,
            getBackgroundSubscribeServiceIntent(), PendingIntent.FLAG_UPDATE_CURRENT);
}

private Intent getBackgroundSubscribeServiceIntent() {
    return new Intent(getApplicationContext(), BackgroundSubscribeIntentService.class);
}


Фрагмент кода демонстрирующий обработку intent'а в классе BackgroundSubscribeIntentService:
protected void onHandleIntent(Intent intent) {
    Nearby.Messages.handleIntent(intent, new MessageListener() {
        @Override
        public void onFound(Message message) {
            Log.i(TAG, "Found message via PendingIntent: " + message);
        }

        @Override
        public void onLost(Message message) {
            Log.i(TAG, "Lost message via PendingIntent: " + message);
        }
    });
}


Ну и конечно же, если подписка нам больше не нужна, мы должны отписаться вызвав Nearby.Messages.unsubscribe(GoogleApiClient, PendingIntent).

Разбор сообщений


Как мы уже знаем из первой части, каждое вложения состоит из следующих частей:
-Namespace: Идентификатор пространства имен.
-Type: Тип данных.
-Data: Значение данных вложения.
Фрагмент кода демонстрирующий использование MessageListener() для разбора сообщений:
mMessageListener = new MessageListener() {
    @Override
    public void onFound(Message message) {
        // Do something with the message here.
        Log.i(TAG, "Message found: " + message);
        Log.i(TAG, "Message string: " + new String(message.getContent()));
        Log.i(TAG, "Message namespaced type: " + message.getNamespace() +
                "/" + message.getType());
    }

    ...
};


Стоит учесть что разбор содержания зависит от формата байт. Этот пример предполагает, что сообщения закодированы в UTF-8 строку, но ваши сообщения от маячков могут быть закодированы в другой формат.
Чтобы узнать какие пространства имен связаны с вашим проектом, можно вызвать namespaces.list.

Nearby Nearby meassages API на iOS


Для создания проекта использующего Nearby Messages API for iOS нам понадобиться Xcode версии 6.3 или старше.

Google Nearby Messages API для iOS доступен как пакет(pod) CocoaPods. CocoaPods — это менеджер зависимостей с открытым исходным кодом для Swift и Objective-C Cocoa проектов. Для получения дополнительной информации советую ознакомиться с CocoaPods Getting Started guide. Если он у вас не установлен, вы можете сделать это выполнив в терминале следующую комманду:

$ sudo gem install cocoapods

Устанавливаем Nearby messages API использую CocoaPods:
  • Открываем проект или создаём новый, следует убедится что опция Use Automatic Reference Counting включена.
  • Создаём файл с именем Podfile в директории проекта. Этот файл будет определять зависимости проекта.
  • Добавляем зависимости в Podfile. Пример простого Podspec содержащего имя пакета которое для установки
    source 'http://ift.tt/1czpBWo'
    platform :ios, '7.0'
    pod 'NearbyMessages'
    
  • В терминале переходим в директорю в котрой находится Podfile
  • Для установки вместе с зависимости API указанных в Podfile необходимо выполнить комманду:
    $ pod install
    

После этого закрываем Xcode и затем двойным кликом по .xcworkspace проекта запускаем Xcode. Начиная с этого момента, вы должны использовать файл .xcworkspace для открытия проекта.

Как и в случае с Android, нам необходимо получить API ключ. Ключи для Android, iOS и Proximity Beacon API должны быть созданы в рамках одно проекта Google Developers Console. Очень советую ознакомиться с Best practices for securely using API keys

Осторожно GIF. Пример получения API ключа:
image

Теперь, когда всё настроено, мы можем создать объект messageManager и использовать API ключ созданный ранее
#import <GNSMessages.h>

GNSMessageManager *messageManager =
    [[GNSMessageManager alloc] initWithAPIKey:@"API_KEY"];

Подписка в iOS


В iOS сканирование маячков происходит только когда приложение активно. Сканирование маячков в фоновом режиме недоступно для iOS. Что бы подписаться только на BLE маячки нужно задать deviceTypesToDiscover в параметрах подписки kGNSDeviceBLEBeacon.
Фрагмент кода который показывает как это сделать:
_beaconSubscription = [_messageManager
    subscriptionWithMessageFoundHandler:myMessageFoundHandler
                     messageLostHandler:myMessageLostHandler
                            paramsBlock:^(GNSSubscriptionParams *params) {
                              params.deviceTypesToDiscover = kGNSDeviceBLEBeacon;
                            }];


Этот пример кода подписывается только на маячки нашего проекта и получает все сообщения от них.

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

Фрагмент кода который показывает как это сделать:
_beaconSubscription = [_messageManager
    subscriptionWithMessageFoundHandler:myMessageFoundHandler
                     messageLostHandler:myMessageLostHandler
                            paramsBlock:^(GNSSubscriptionParams *params) {
                              params.deviceTypesToDiscover = kGNSDeviceBLEBeacon;
                              params.messageNamespace = @"com.mycompany.mybeaconservice";
                              params.type = @"mybeacontype";
                            }];


По умолчанию, при подписке мы сканируем сразу оба типа маячков, Eddystone и iBeacon. Если у нас задействовано сканирование маячков iBeacon, пользователь получит запрос на использование геолокации. Info.plist приложения должен включать ключ NSLocationAlwaysUsageDescription с крткаим обьяcнением того, почему используеься геолокация. Советую ознакомиться с документацией Apple для деталей.

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

Фрагмент кода, который показывает как отключить сканирование iBeacon маячков для предыдущего примера:
_beaconSubscription = [_messageManager
    subscriptionWithMessageFoundHandler:myMessageFoundHandler
                     messageLostHandler:myMessageLostHandler
                            paramsBlock:^(GNSSubscriptionParams *params) {
                              params.deviceTypesToDiscover = kGNSDeviceBLEBeacon;
                              params.messageNamespace = @"com.mycompany.mybeaconservice";
                              params.type = @"mybeacontype";
                              params.beaconStrategy = [GNSBeaconStrategy strategyWithParamsBlock:^(GNSBeaconStrategyParams *params) {
                                params.includeIBeacons = NO;
                              };
                            }];



При сканировании маячков iBeacon, диалог запроса разрешений на геолокацию предшествует диалогу разрешений Nearby. Мы можем переопределить этот диалог, например, для того что бы обяьснить пользователю для чего запрашивается разрешение на геолокацию. Для этого необходимо задать permissionRequestHandler в отдельном блоке в параметрах подписки.
Фрагмент кода показывающий как это сделать:
_beaconSubscription = [_messageManager
    subscriptionWithMessageFoundHandler:myMessageFoundHandler
                     messageLostHandler:myMessageLostHandler
                            paramsBlock:^(GNSSubscriptionParams *params) {
                              params.deviceTypesToDiscover = kGNSDeviceBLEBeacon;
                              params.messageNamespace = @"com.mycompany.mybeaconservice";
                              params.type = @"mybeacontype";
                              params.beaconStrategy = [GNSBeaconStrategy strategyWithParamsBlock:^(GNSBeaconStrategyParams *params) {
                                params.includeIBeacons = NO;
                              };
                              params.permissionRequestHandler = ^(GNSPermissionHandler permissionHandler) {
                                // Show your custom dialog here, and don't forget to call permissionHandler after it is dismissed
                                permissionHandler(userGavePermission);
                              };
                            }];


Заключение


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

Комментарии (0)

Let's block ads! (Why?)

[Из песочницы] Как заставить LightShot выдавать прямые ссылки? Одним байтом

[Из песочницы] Наш опыт использования фотограмметрии при разработке компьютерной игры

image

В данной статье будет рассказано о фотограмметрии и опыте её использовании при создании контента для трёхмерной компьютерной игры во вселенной Half-Life, разработкой которой мы занимаемся уже не первый год.

Введение


Для начала немного теории для тех, кто столкнулся с этим термином впервые. Фотограмметрия — это научно-техническая дисциплина, занимающаяся определением формы, размеров, положения и иных характеристик объектов по их фотоизображениям. Существует два основных направления в фотограмметрии: создание карт и планов Земли (и других космических объектов) по снимкам (фототопография), и решение прикладных задач в архитектуре, строительстве, медицине, криминалистике и т.д. (наземная, прикладная фотограмметрия).

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

Почему мы решили использовать фотограмметрию?


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

image

О главной же причине расскажем подробнее. Действие игры «Lost Story: The Last Days of Earth» будет разворачиваться на обширной территории, игроку предстоит преодолеть десятки километров, и уже в самом начале нам стало ясно, что открытые пространства и природные локации займут как минимум половину этого путешествия.

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

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

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

Съёмки на натуре


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

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

image

В целом, съёмки на натуре не вызывают особых трудностей, и один человек за один рабочий день может качественно отснять 4-5 объектов, а если работать в паре то можно и больше 10, что довольно внушительно. Кроме зависимости от погоды обнаружился лишь ещё один неприятный момент — чтобы найти интересные объекты иногда забираешься в самую чащу леса. Там, как правило, невозможно работать даже с моноподом и приходится проявлять чудеса акробатики и растяжки.

После нескольких наших вылазок мы теперь точно знаем как именно тренировался знаменитый актёр боевиков 90x на фото выше.

Съёмки в «студии»


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

Почему я пишу «студия» в кавычках? Да потому, что съёмки проводились в домашних условиях, где мы создали импровизированную «студию» из подручных материалов! Для качественной съёмки нужно много света, которого в обычной квартире конечно же не хватает, что ж пришлось отправиться за покупками. Навестив пару фотомагазинов и пустив скупую мужскую слезу на ценники профессионального осветительного оборудования, мы не пали духом и решили действовать иначе.

image

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

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

image

Съёмки в «студии» идут медленнее, т.к. света намного меньше чем на улице и приходится использовать штатив. Тем не менее за один рабочий день можно отснять 3-4 объекта. Основной трудностью является монотонность процесса, но мы таки справились и отсняли десяток камней, а также несколько других предметов.

Обработка фото


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

В результате обработки мы получили модели с полигонажем от 9 до 13 млн треугольников и альбедо картой размером 16 384 пикселей для каждой модели (представлены ниже).

image

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

Результаты


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

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

image

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

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

«Но мох же должен быть пушистым!» — скажете вы. Верно! Вот тут то мы и вспомнили про метод времён Play Station 2, а именно про многослойную геометрию с альфа каналом. Результат нас вполне устроил: выглядит отлично, при этом ресурсов почти не требует! Вот так, работая над фотограмметрией, у нас появился метод для создания пушистых материалов, будь то мох, ворс или даже шерсть ;)

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

image

В заключении хотелось бы отметить, что по нашим подсчётам на получение одной финальной модели из фотографий у нас ушло в среднем 2-3 дня (не учитывая время на съёмку). При этом занимался этим только один 3D художник, и это впечатляет, учитывая финальное качество.

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

Комментарии (0)

Let's block ads! (Why?)