Здравствуйте меня зовут Дмитрий. Я занимаюсь созданием компьютерных игр на Unreal Engine в качестве хобби. Сегодня я расскажу как создать свой модуль, а потом как создать плагин в Unreal Engine 4.
Создание модуля
Итак начнем с модулей. Когда вы создаете проект, в файле проекта автоматически создается один модуль.
В принципе для простого проекта это достаточно. Но если вы читали мою предыдущую статью (а если не читали то советую сделать это прямо сейчас) можно увидеть что определенный код, который необходим для регистрации ассета, добавлении кнопок на панель свойств этого ассета, для игры нам не нужен, а нужен только для редактора. Поэтому было-бы хорошо сделать так чтобы, при сборке игры этот код в игру не включался, именно для этого и предназначена система модулей.
Любой модуль обязательно должен иметь 3 файла. Первый это заголовочный файл этого модуля <Имя модуля>.h, обычно в него включается файл Engine.h. Но стоит заметить что при включении файла Engine.h размер Precompiled header становится равен ~700mgb. Если вы создадите в своем проекте много модулей и каждый будет весить более 700mgb ни каких винчестеров не хватит, поэтому рекомендую открыть Engine.h и выбрать только то что вам надо. Кроме того в этом файле располагается интерфейс модуля. В котором можно что нибудь зарегистрировать например.
#pragma once
#include "Core.h"
#include "CoreUObject.h"
#include "Engine/EngineTypes.h"
#include "SlateCore.h"
#include "SlateBasics.h"
#include "ModuleManager.h"
DECLARE_LOG_CATEGORY_EXTERN(UICustomEditor, All, All)
class FUICustomEditorModule : public IModuleInterface
{
public:
virtual void StartupModule() override;
virtual void ShutdownModule() override;
};
Здесь я регистрирую тип ассета и изменение панели свойств, а также добавил сообщение в лог.
В конце этого файла обязательно должен быть макрос IMPLEMENT_GAME_MODULE.
Третий обязательный файл <Имя модуля>.Build.cs:
using UnrealBuildTool;
public class UICustomEditor : ModuleRules
{
public UICustomEditor(TargetInfo Target)
{
PublicDependencyModuleNames.AddRange(new string[] {
"Core",
"CoreUObject",
"InputCore"
});
PrivateDependencyModuleNames.AddRange(new string[] {
"Slate",
"SlateCore",
"PropertyEditor",
"UnrealEd",
"EditorStyle" });
PrivateDependencyModuleNames.AddRange(new string[] { "GameLibPluginRuntime","UICustom" }); //Плагин и основной модуль
}
}
В этом файле я подключаю модули необходимые для работы моего модуля (простите за тавтологию). Как видите кроме системных модулей я также подключил основной модуль и плагин(о котором я напишу ниже).
Важно: Если вы подключаете плагин к основному модулю то надо подключать его и к остальным. Иначе если вы используете объект из основного модуля в котором будет объект из плагина, то компилятор выдав ошибку о том что не может найти файл, сошлется на строчку в основном модуле но поскольку в нем вы плагин уже подключили вы не будете понимать в чем дело и что от вас требует компилятор.
Важно: Для того чтобы класс или структуру из подключенного модуля можно было использовать. Нужно:
1) Подключить заголовочный файл этого класса или структуры.
2) При определении классов и структур которые вы хотите использовать из других модулей нужно писать <имя модуля большими буквами>_API. Например:
class UICUSTOMEDITOR_API UMyObjectFactory : public UFactory
После создания этих файлов нужно положить их в папку с именем модуля в папке Source. Осталось только добавить наш модуль в файл UICustomEditor.Target.cs (в файл UICustom.Target.cs мы ни чего не добавляем поскольку модуль будет грузится только в редакторе)
OutExtraModuleNames.AddRange( new string[] { "UICustom", "UICustomEditor" } );
Модуль готов, для полезной нагрузки я использовал файлы из прошлого урока. Теперь перейдем к созданию плагина.
Создание плагина
Плагин нужно воспринимать как проект который можно вставить в другой проект. Плагин как и проект состоит из модулей и имеет свой файл проекта который имеет расширени .uplugin. Чтобы плагин подключить к проекту его надо положить в папку <директория проекта>/plugins и заново сгенерировать Visual Studio проект. После этого можно подключать модули плагина как и любые другие модули (об этом написано выше).
Соответственно для создания плагина нужно создать файл <Имя плагина>.uplugin
Если в папке плагина создать папку Resources, то положенное туда изображение, в формате png будет отображаться в менеджере плагинов.
Далее в папке плагина/Source создаем папку для каждого из модулей плагина. Создание модулей плугина не отличается от создания модулей для проекта(о чем было написано выше). Собственно все плагин готов.
Для примера я сделал парсер CVS таблиц. После подключения плагина можно наблюдать:
P.S Прошу учесть что я программист любитель, поэтому за кривость парсера просьба ногами не пинать.
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Тысячи языков программирования были изобретены за первые 50 лет развития компьютеров. Одни из них были характерными, другие следовали традиционным, эволюционным путем их предшественников.
У некоторых революционных языков наблюдалась четкая направленность, дифференцирующая их от большего количества собратьев общего назначения. LISP подходил для обработки списка. SNOBOL использовался для обработки текстовых данных. SIMSCRIPT помогал в моделировании. А язык APL предназначался для математики с акцентом на обработку множества.
APL (от А Programming Language — язык программирования) был разработан в 1957 г. профессором Гарварда Кеннетом Айверсоном (Kenneth Iverson), который в дальнейшем перешел работать в фирму IBM.
Кеннет Айверсон (1920 — 2004) — канадский ученый в области теории вычислительных систем, создатель языка программирования APL
Создание APL
Изначально APL создавался не как язык программирования, а как математическая система обозначений. Айверсон хотел разработать компактную систему записей (нотаций), чтобы описывать алгоритмы прикладной математики. Оригинальная нотация включала в себя много специфических соглашений и символов, которые предназначались для точной формулировки алгоритмов. После этого алгоритмы вручную интерпретировали на разные языки программирования.
Айверсон был нанят компанией IBM в 1960 году, чтобы работать с Адином Фалькоффом над его нотациями. Первая модифицированная версия языка с названием System/360 была реализована ими совместно с группой разработчиков IBM в 1966 г. Для этого использовали вычислительную систему IBM/360. Проект принес популярность языку программирования APL. После чего появились разные подмножества языка, как например APL/700.
Ранние разработчики языка APL, слева направо: Дик Лэтвелл, Кеннет Айверсон, Роджер Мур, Адин Фалькофф, Фил Абрамс, Ларри Брид
По этой ссылке можно скачать полную версию исходного кода для версии 1969-1972 «XM6» языка APL для System/360: http://ift.tt/1Ndbb1j
Текстовый файл содержит 37,567 линий, который включают кодекс, макрос и глобальные определения. Чтобы получить доступ к этому материалу, нужно согласиться на условия лицензии, разрешающие только некоммерческое использование и не дающие право лицензировать его для третьих лиц, публикуя копии в сети.
Символы языка APL отличаются от других языков, они ближе к стандартной математике, чем к программированию. Кроме того, символы имеют два смысла — унарную и бинарную функции, которые могут быть непохожи. Например, символ ÷, не /. Чтобы поддержать нетрадиционные символы, APL\360 использовал изготовленную на заказ клавиатуру со специальными символами в верхнем регистре.
Специальная клавиатура языка APL
Несмотря на это, в языке используются особо специфические знаки, которых нет на клавиатуре. Например, grade up изображают знаком ⍋.
Для печати программ Айверсон и Фолкофф убедили IBM спроектировать специальный «шар» для их 1050 и 2741 терминалов, использующих механизм пишущей машинки IBM Selectric.
«Шар»
Образец кода APL:
[6] L←(Lι':')↓L←,L ⍝ drop To:
[7] L←LJUST VTOM',',L ⍝ mat with one entry per row
[8] S←¯1++/∧\L≠'(' ⍝ length of address
[9] X←0⌈⌈/S
[10] L←S⌽(−(⍴L)+0,X)↑L ⍝ align the (names)
[11] A←((1↑⍴L),X)↑L ⍝ address
[12] N←0 1↓DLTB(0,X)↓L ⍝ names)
[13] N←,'⍺',N
[14] N[(N='_')/ι⍴N]←' ' ⍝ change _ to blank
[15] N←0 ¯1↓RJUST VTOM N ⍝ names
[16] S←+/∧\' '≠⌽N ⍝ length of last word in name
После этого программы могли печатать и распечатывать. Пример печатной версии программы из Языкового руководства языка APL, которое вычисляет математический детерминант матрицы:
Книга Айверсона “Язык программирования” использует графическую нотацию, которую было бы сложно использовать непосредственно в качестве языка программирования. Автор считает его расширением матричной алгебры и пользуется общими математическими условными обозначениями.
Пример программы для сортировки чисел
Особенности APL
APL — краткий язык программирования высокого уровня, который имеет свои особенности, отличающие его от большинства других языков.
Независимо от ОС и архитектуры компьютера, язык APL ориентирован на решение проблемы и описание алгоритма. Он направлен на работу с массивами.
Немаловажный элемент языка — это операторы. Они получают на вход данные и создают функции. Набор операторов ограничен и фиксирован в большинстве вариаций реализации APL, что отличает его от других функциональных языков, где функции высшего порядка создаются без ограничений. Разный синтаксис операторов и синтаксис функций.
Выражения в языке APL подсчитывается справа налево и нет никакой иерархии предшествования функции. Например, печать выражения 2×4+3 заставляет компьютер мгновенно печатать получившееся значение 14.
Язык APL обеспечивает программиста большим набором разных функций. Они используются в соответствии с простым правилом приоритета: правый аргумент бинарной функции целиком выражен справа от нее. Возможно контролировать приоритет в ином виде используя скобки. Хотя чаще всего это не требуется. Такое правило делает анализ иерархической структуры выражений во многом проще. Общее правило состоит в том, что правый аргумент любой функции — это значение выражения с правой стороны от него.
В языке присутствуют скаляры (примитивные типы данных). Логические значения моделируются числами 0 для false и 1 для true. К слову, данный прием был впервые применен именно в APL. Массивы объединяют все структуры данных: одномерные векторы, двухмерные матрицы и многомерные мультитаблицы. Изначальная ориентация функций направлена на работу с массивами, но может применяться к скалярам. Благодаря развитой системы операций над массивами удается избегать применения явных команд управления потоком выполнения программы.
В APL используется принцип boxing, который помогает с реализацией разнородных структур данных. По этому принципу любой массив можно «заключить в коробку» и рассматривать как скаляр. В таком виде операции над ним не производятся, но его возможно включать в другие массивы. После извлечения содержимого массива из «коробки», оно становится доступным.
У APL более многомерная структура, которая автоматически производит расчет выражения, скаляры могут быть свободно смешаны. Например ← 2 + 1 2 3 создает вектор 1 2 3, добавляет к нему скалярную величину 2 и создает переменную A, чтобы держать вектор, значение которого 3 4 5.
Переменные созданы автоматически, принимая размер и форму любого назначенного выражения.
У языка APL есть богатый набор встроенных функций, которые воздействуют на скаляры, векторы, множества, более многомерные объекты и их комбинации. Например, выражение суммирует числа в вектор А +/A где / — оператор “сокращения”, заставляющий функцию слева быть последовательно примененной ко всем элементам операнда справа. Выражение для вычисления среднего числа А также использует примитивную функцию ρ, чтобы определить сколько элементов находятся в A: (+/A) ÷ ρА.
Примеры таблиц с 1970 из “Руководства Пользователя APL\360” (таблица 1, 2 и 3)
Язык APL дает возможность иначе посмотреть на программирование и использовать временные высоко-размерные структуры данных в качестве промежуточных ценностей, которые тогда уменьшены, используя сильные примитивы. Известный пример — следующая короткая, но полная программа, чтобы вычислить все простые числа до R.
В программе нет петель. Операторы языка APL могут применять легкие способы ко всем видам вычислений, где обычно потребовались бы петли. Например, выражение, определяющее число элементов вектора X, которые больше 100 будет +/X>100.
Но конечно, условные операторы и петли иногда необходимы.
Похвала и критика языка APL
Как уже упоминалось, APL не был первоначально разработан как язык программирования. Вот, что сказал на эту тему Айверсон:
Изначально я создавал APL, как инструмент для написания и обучения. И хотя язык главным образом эксплуатировался в коммерческом программировании, я все также считаю, что его самое важное использование определяется, как простая, точная и выполнимая запись (нотация) для изучения широкого спектра предметов.
У языка APL есть преданные поклонники. Как например Алан Перлис (первый получатель Премии Тьюринга ACM, в 1966 г.):
Радует глаз изобретательное и красивое взаимодействие операции и контроля, которое в других языках программирования заметных только на некоторых страницах текста. Каждый начинает ценить появление и значение стиля. Многие получают свободу самовыражения в вольностях языка APL. Я раньше описывал Pascal, как «фашистский язык программирования», потому что он властный, четкий и имеющий рамки… Так вот, если Pascal фашистский, то язык APL — анархистский.
Одним из существенных минусах выделяют сложность расшифровки языка APL. Есть популярная шутка о том, что APL — это язык только одного написания, потому что даже его автор с трудом может разобрать и понять код. Ниже представлены примеры двух различных «острот» от APL, которые реализуют версии Игры «Жизнь» — клеточного автомата, придуманного английским математиком Джоном Конвеем (1970 г.).
life←{↑1 ω∨.∧3 4=+/,¯1 0 1∘.⊖¯1 0 1∘.⌽⊂ω}
Шифр не для слабонервных
Голландский ученый и программист Эдсгер Дейкстра сказал:
Язык APL — ошибка, стремящаяся к совершенству. Это язык будущего для программных методов прошлого.
Популярность языка APL начала снижаться с середины 80-х, когда начали активно развиваться другие системы математических вычислений. Они оказались более интуитивными и смогли лучше удовлетворить потребности пользователей. Тем ни менее, язык APL и языки, которые появились на его основе (такие как APL2 и J), все еще используются в программировании. В наше время APL применяется в финансовых и математических приложениях. Он поддерживается практически на всех аппаратных платформах. По данному языку каждый год проходят конференции в рамках Association for Computer Machinery.
По традиции, немного рекламы в подвале, где она никому не помешает. Напоминаем, что в связи с тем, что общая емкость сети нидерландского дата-центра, в котором мы предоставляем услуги, достигла значения 5 Тбит / с (58 точек присутствия, включения в 36 точек обмена, более, чем в 20 странах и 4213 пиринговых включений), мы предлагаем выделенные серверы в аренду по невероятно низким ценам, до конца месяца!
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Для новичка, экосистема вокруг React (как и фронтэнда в целом) может показаться запутанной. Этому есть несколько причин.
* Изначально, React был нацелен на экспертов и ранних последователей
* Facebook открывает исходный код только тех продуктов, которые использует сам, т. е. не нацеленные на проекты-меньше-чем-Facebook
* Огромное количество гайдов по React совершенно разной сложности
Здесь и далее, я предполагаю, что вы уже знакомы с HTML, CSS и JavaScript.
Существует множество противоречивых советов по React. Зачем слушать меня?
Я работал в команде Facebook, которая разработала и опубликовала React. Теперь я работаю не в Facebook, а в небольшом стартапе, поэтому могу говорить с точки зрения своей текущей позиции, а не Facebook.
Все программное обеспечение строится на определенном стеке технологий, и вам нужно понимать этот стек, чтобы создать приложение. Основная причина того, почему экосистема React'а кажется непреодолимой, это потому что она постоянно объясняется в неправильном порядке.
Вы должны учиться в этом порядке, ничего не пропуская и не изучая две вещи параллельно:
Вам не нужно это все, чтобы быть продуктивным с React. Приступайте к следующему шагу, если у вас есть проблема, которую он решает.
Также, в React-сообществе есть несколько тем, которые являются «супер-современными практиками» («bleeding edge»). Эти темы интересны, но разбираться в них сложно и они менее популярны, чем темы выше и не нужны для разработки большей части приложений.
* Инлайновые стили
* Рендер на стороне сервера
* Immutable.js
* Relay, Falcor, и т. д.
Существует заблуждение, что чтобы начать работу с React, нужен огромный инструментарий. Но это не так. В официальной документации вы найдете copy-paste HTML шаблон, который достаточно сохранить в .html файле и сразу же начать работать. Для этого шага не нужен никакой инструментарий, и не стоит приниматься за него, пока вы не будете чувствовать себя комфортно с основами React.
Я также считаю, что самый простой способ выучить React, это официальный туториал.
npm это менеджер пакетов Node.js и самый популярный способ для front-end разработчиков и дизайнеров делиться JavaScript кодом. Он включает модульную систему CommonJS и позволяет устанавливать инструменты командной строки, написанные JavaScript. Прочитайте эту статью, чтобы понять, почему и как используется CommonJS, или CommonJS Spec Wiki для большей информации о CommonJS API.
Большая часть компонентов, библиотек и инструментария в экосистеме React доступны как CommonJS модули и устанавливаются с помощью npm.
По определенному количеству технических причин, использование CommonJS модулей (то есть всего в npm) невозможно нативно в браузере. Вам понадобится JavaScript “bundler” для сборки этих модулей в .js файлы, которые затем можно будет включить в страницу тегом <script>.
Примерами JavaScript сборщиков являются webpack и browserify. Они оба являются хорошим выбором, но я предпочитаю webpack, так как он имеет определенный набор фич, упрощающих разработку крупных приложений. Так как документация может показаться запутанной, у меня есть шаблон для быстрого старта, и я написал how-to гайд по webpack для более сложных кейсов.
Стоит запомнить: CommonJS использует функцию require() для импорта модулей, из-за чего некоторые пользователи начинают думать, что это нечто связанное с библиотекой require.js. По определенному количеству технических причин, я советую избегать require.js. Этот выбор не популярен в среде React.
Кроме JSX (который вы изучили в туториале React), вы могли заметить несколько забавных синтаксических конструкций в примерах. Это называется ES6, самая последняя версия JavaScript, с которой вы еще можете быть не знакомы. Из-за новизны, ES6 еще не полностью доступен в браузерах, но ваш сборщик может транслировать его в поддерживаемый JavaScript после определенной настройки.
Вам не обязательно знать ES6 для разработки на React, вы можете выучить его попутно.
Вы также могли слышать разговоры о том, что ES6-классы являются предпочитаемым способом создания компонентов React. Это не так. Большинство людей (включая Facebook) используют React.createClass().
“Одностраничные приложения” (Single-page applications или SPA) — современная мода. Это веб-странички которые загружаются один раз, и, когда пользователь кликает по ссылке или кнопке, JavaScript, работающий на странице, обновляет адресную строку и контент, не перезагружая страницу целиком. Управление адресной строкой осуществляется router (роутером).
Самый популярный роутер в экосистеме React react-router. Если вы разрабатываете одностраничное приложение, используете его, если только у вас нет хорошей причины не делать этого.
Не используйте роутер, если вы не создаете single-page application. Большинство проектов все равно начинают с маленьких компонентов внутри имеющегося большого приложения.
Скорее всего, вы слышали о Flux. Про него имеется *тонна* дезинформации в сети.
Куча людей пытаются определиться с моделью данных и считают, что для этого им обязательно нужно использовать Flux. Это неправильный путь к внедрению Flux на свой проект. Flux должн быть добавлен только после того, как большинство компонентов уже будут созданы.
Компоненты React'а собраны в иерархию. В большинстве случаев, ваша модель данных также будет следовать этой иерархии. В этих ситуациях Flux не приносит особого выигрыша. Иногда, тем не менее, ваша модель данных не иерархична. Если ваши React компоненты получают props, которые кажутся «внешними», или у вас есть некоторое количество компонентов, которые начинают становиться сильно сложными, возможно вам стоит присмотреться к Flux.
Вы поймете, когда вам понадобится Flux. Если вы не уверены, что он вам нужен, то он вам не нужен.
Если вы решили использовать Flux, самой популярной и документированной Flux-библиотекой является Redux. Также есть *множество* альтернатив, возможно вы соблазнитесь попробовать их, но мой совет — использовать самую популярную.
Пре-React, большинство людей использовали CSS-препроцессоры типа SASS для переиспользования стилей. React делает написание переиспользуемых компонентов простым, также упрощая и написание стилей. Многие из сообщества (включая меня) экспериментируют над тем, чтобы совсем избавиться от CSS.
В силу ряда причин, это относительно безумная идея. Она усложняет написание media queries, и, возможно, есть определенные ограничния по производительности. Если вы только что начали работать с React, пишите css-стили так как вы привыкли.
Как только вы почувствуете то, как React работает, обратите внимание на альтернативные техники. Одна из популярных, это BEM. Я бы порекомендовал избавляться от CSS-препроцессора, так как React предоставляет более гибкий путь переиспользования стилей (через переиспользование компонентов) и ваш JavaScript-сборщик может генерировать гораздо более эффективные таблицы стилей для вас (доклад на эту тему на OSCON). Вместе с тем, React, как и любая другая JavaScript библиотека, сможет работать также хорошо с любым CSS-препроцессором.
Серверный рендеринг часто называется «универсальным» или «изоморфным» JS. Это означает что вы можете взять ваши React-компоненты и отрендерить их в статический HTML на сервере. Это ускоряет первоначальную загрузку страницы, так как пользователю не нужно ждать, пока скачается весь JS, чтобы увидеть UI, а React, в свою очередь, может переиспользовать HTML, сгенерированный на сервере, не рендеря ничего на клиенте повторно.
Серверный рендеринг вам понадобится, если вы посчитаете, что первичный рендер страницы слишком медленный, или чтобы улучшить ранжирование в поисковиках. Да, Google индексирует контент, рендеренный на клиенте, но по состоянию на январь 2016 каждое измерение показывало, что это негативно влияет на ранжирование, потенциально из-за производительности рендера.
Также серверный рендеринг требует большого количества инструментария для «правильной» реализации. Так как поддержка React-компонентов написанных без мысли о серверном рендеринге, в целом прозрачна, рекомендуется сначала писать приложение, а потом задумываться о нем. Вам не прийдется переписывать все ваши компоненты в случае решения о переходе.
Immutable.js предоставляет набор структур данных, которые помогают решать определенные проблемы с производительностью в React-приложениях. Это отличная библиотека, и, скорее всего, вы будете часто использовать ее с ростом вашего приложения, но она абсолютно не является требованием, пока вы не столкнетесь с проблемами производительности.
Эти технологию помогают уменьшить количество AJAX-запросов. Они все еще являются относительно экспериментальными, так что если у вас нет проблем со слишком большим количеством AJAX запросов, вам не нужны Relay или Falcor.
UPD. Немного почищен перевод первых абзацев, спасибо Benjamin Tambourine за правки
UPD2. Много мелких грамматических исправлений, спасибо wiygn
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Доброе время суток, дорогие друзья!
Первым делом хотелось бы с лучшими пожеланиями поздравить всех с минувшими новогодними праздниками!
Ранее в статье была анонсирована разработка RNDIS USB драйвера для контроллеров серии STM32F4. С тех пор библиотека постепенно развивалась и нынче доросла до первой release-версии. Библиотека под названием LRNDIS (LWIP + RNDIS) позволяет нам создавать на базе контроллера STM32F4 как устройства класса USB «модем», так и любые другие устройства с управлением через web-интерфейс. Пример управления платой stm32f4-discovery из web-браузера на Android-планшете представлен на видео:
На странице видеоролика представлена ссылка на исходные коды и HEX-файл прошивки для платы discovery, с которым вы сможете повторить данный эксперимент. В статье рассказано о том, как и когда технология доступа через WEB-интерфейс полезна, а также — как работает библиотека LRNDIS для контроллеров STM32F4. Также присутствует обучающий материал о работе USB и устройстве Ethernet-сетей. Предыстория создания библиотеки
Предыстория проекта весьма типовая. Стоял тёплый летний день. Гхм… Для заказчика стояла задача разработать устройство с сервисным интерфейсом управления.
Подробности
По мере развития прошивки было введено несколько команд управления по VCP-интерфейсу. Это значит, что после подключения USB-устройства в ОС создавался виртуальный COM-порт. Используя его, из пользовательского терминала передавались команды управления и диагностики. В ответ от устройства принимался статус выполнения и его текущее состояние.
Система вполне типовая с сервисной точки зрения: есть последовательный порт и набор команд для управления и диагностики.
Всё изменилось в короткий срок. По объективным причинам рос требуемый набор команд. Также понадобилась интерактивность вывода: некоторые параметры стало необходимо отображать в динамике. Как, например, показания магнитного датчика при проносе мимо него ферромагнетика. Для этого были введены дополнительные команды, которые, оперируя управляющими последовательностями, печатали информацию в пользовательском терминале с высокой периодичностью. Это создавало необходимое ощущение риалтаймовости наблюдения. Интерактивные команды оказались настолько удобными для инженеров, что некоторая часть команд позже была добавлена в соответствии с концепцией. И тут раздался треск. Требовалось поддержать сразу несколько групп команд: интерактивные, диагностические, команды управления. При этом периодический рефакторинг кода был связан с трудоёмкой правкой в большом количестве обрабатываемых команд. Ясно стало, что ещё должна быть пользовательская группа команд — для менее квалифицированного персонала, который будет просто следовать инструкциям по эксплуатации. Для них возникла идея написания клиентского терминала с кнопочками и флажочками… И вот тут возникли сомнения: стало ясно, что мы занимаемся сервисной частью, уделяя всё меньше внимания функциональности! А ведь пользовательская программа, запускаемая на клиентской ЭВМ, также должна обладать своими требованиями: кроссплатформенность и LTS (длительностью поддержки).
Устройство, предположим, мы закончили, а пользовательское ПО мы должны портировать и тестировать с каждой версией выпускаемых операционных систем! А как долго?
Так и родился вопрос — как избавиться от дополнительных трудозатрат?
Было принято решение использовать стандарты гарантированно длительной поддержки. Те стандарты, которые нам позволят создать клиентскую программу управления устройством, которая будет поддерживаться максимально полным набором операционных систем в настоящем и будущем времени. На первых парах были найдены недостатки популярных кроссплатформенных фрэймворков:
— java: необходимость наличия в ОС JVM, и вытекающий из противного предположения необходимость дистрибьюции виртуальной машины
— qt: периодическая необходимость версионного портирования и нюансы запуска под Android
Нет, эти сложности пугать не должны. Вопрос, пожалуй, только в трудочасах, которые мы, бывает, недооцениваем с учётом фактора длительной поддержки.
Так родилась идея сделать WEB-интерфейс для управления устройством. Он не требует разработки стороннего ПО, браузеры для отображения управляющей страницы есть во всех требуемых ОС. Потенциал оформления интерфейса огромный. Длительность поддержки в части стандартов http/html/js тоже не вызывает сомнений.
По замыслу, управление должно было работать следующим образом.
1. Подключаемое по USB устройство представляется сетевой картой
2. Клиентская ЭВМ (ПК или гаджет) получает IP-адрес для работы в сети нашего устройства
3. По запросу web-браузера на клиентской ЭВМ наше устройство отдаёт страницу
4. На странице присутствует информация о текущем состоянии и доступные элементы управления
5. При активации клиентом элементов управления, из браузера передаются соответствующие HTTP-запросы.
По сути, между браузером и устройством, ходят те же самые текстовые команды, но только в формате HTTP протокола.
Надо понимать, что это всего лишь один из вариантов из большого набора возможных решений. Он имеет свои плюсы и минусы. Так случилось, что сейчас к использованию web-интерфейсов прибегают производители в основном сугубо сетевых устройств: настройка модемов и роутеров. Посыл данной статьи — давайте применять то что, действительно, удобно. И давайте не бояться сложностей на пути: их преодоление сейчас нам сэкономит куда больше времени в будущем!
Сфера применения библиотеки
К сожалению, первый анонс в полной мере успешным не был, т.к. рассказ о сфере применения был упущен.
Попробуем немного наверстать упущенное и раскрыть эту тему.
Если мы находимся на этапе системного проектирования устройства, то следующие соображения могут склонить нас в сторону использования web-интерфейсов (вне зависимости от физического канала, Ethernet или USB):
1. Устройство должно иметь интерфейс управления и/или диагностики
2. Средства управления могут использоваться не только на этапе разработки, но и на этапе эксплуатации (ПО пользователя)
3. Квалификация пользователя может быть недостаточно высокой, что требует дружественный интерфейс управления
4. Способ «дружественного» управления должен быть доступен из под разных платформ и ОС
5. Соответствующие средства требуется поддерживать в рабочем состоянии длительное время
Дополнительным критерием может являться то, разрабатываем ли мы изначально сетевое устройство. А также: не будет ли (в противном случае) добавление в прошивку сетевого стека и web-сервера являться избыточным на фоне куда менее богатого функционала устройства. Иными словами, добавление web-интерфейса в контроллер управления лампочкой — очевидно, избыточное решение.
Если мы поверили в web-интерфейс, то следующие соображения, возможно, нам помогут в выборе физического канала связи (из Ethernet и USB перспективы).
Тип
Внутрисхемное подключение
Типовое применение
Ethernet
Ethernet PHY контроллер
— Промышленные устройства
— Бытовые устройства с сетевой функцией и доп. питанием
USB
ULPI контроллер или прямое подключение к МК
Бытовые и часть промышленных устройств. В особенности, если:
— устройства имеют не гарантированный источник питания (питание от батареи, например)
— устройства потенциально подключаемые к хосту только с USB интерфейсом (например, планшет)
— миниатюрный класс устройств
От себя добавлю — не смотря на все прелести, не посоветовал бы применять USB в промышленных узлах с требованием повышенной надёжности: часто встречается негативный опыт. Если альтернативы нет — то вопрос устойчивости требуется изучить досконально.
Исходя из приведённых пунктов, становится ясна сфера применения библиотеки: бытовые и часть промышленных устройств, которые:
— работают на базе МК STM32F4
— должны обладать дружественным интерфейсом управления
— должны управляться из под разного аппаратного и программного набора
— могут не иметь гарантированного источника питания
— должны иметь длительный период поддержки ПО управления
Возможных примеров использования технологии много даже вне области сугубо сетевых устройств.
К примеру, на данный момент есть планы по превращению stm32f4-discovery в инструмент любительской разработки с функциями портативного генератора/анализатора сигналов и осциллографа. Подключите такой помощник к телефону и посмотрите в динамике что происходит в интересующей вас цепи. Из бесплатных плюсов — не требуется собирать или устанавливать ПО; достаточно прошить HEX-файл и открыть браузер — в нём будут присутствовать все прелести GUI-интерфейса. На мой привередливый вкус — то что нужно. Конечно, инструмент не для профессиональной разработки, но известный интерес к нему присутствует.
Итак, надеюсь, разобрались. А теперь о том как работает библиотека.
Как оно работает
При ответе на этот вопрос спешить не будем. Человек, имеющий небольшой опыт взаимодействия с сетями, может вполне справедливо смутиться. Поэтому, касаясь того или иного протокола взаимодействия я буду также давать его краткое техническое описание на том уровне… которого когда-то не хватало самому.
Шаг 1. Подключаем USB-устройство.
Как говорилось раньше, на этом этапе наше устройство говорит хосту «я — сетевая карта!».
Хост (т.е. клиентская ЭВМ) после подключения к нему нашей поделки, начинает отправлять запросы.
Хосту требуется получить следующую информацию
— как изделие называется
— какой у изделия VID и PID (идентификаторы производителя и изделия, см. список)
— к какому классу и подклассу относится устройство
— по каким endpoint точкам и какими блоками следует обмениваться данными
Ну, и некоторую другую информацию. Конфигурационные пакеты при этом передаются по точке endpoint 0. Ответные пакеты от устройства с информацией о себе обычно называют «дескрипторы USB устройства».
Подробно ознакомиться о процессе опроса (энумерации) можно здесь.
Вообще, протокол USB достаточно богат… иногда даже кажется, что избыточно. Однако, это богатство вот уже много лет позволяет подключать совершенно разные устройства, даёт возможность передавать изохронные потоки, блоки данных, прерывания. В общем, всё необходимое, что может потребоваться широкому набору современных устройств. Обратная сторона медали — высокий порог входа в разработку USB-устройств.
После получения информации об устройстве, ОС хоста производит поиск подходящего драйвера для взаимодействия. В типовом случае, вроде flash-носителей (USB класс MSC) или клавиатуры с мышкой (HID класс), загружается стандартный для класса драйвер. В более «тяжёлом» случае, вроде нашей USB сетевой карты (CDC класс с RNDIS подклассом), операционная система поступает по усмотрению:
— ОС linux/android/mac, как правило, успешно пытается наладить типовой обмен
— ОС windows просит установить внешний драйвер
Наше устройство в первом случае работает сразу.
В случае ОС windows (позднее XP) можно установить стандартный драйвер фирмы Microsoft. Для Windows XP необходимо поставить inf-файл, доступный в репозитории библиотеки LRNDIS.
Шаг 2. Драйвер инициализирует RNDIS-устройство
На данной картинке изображён принцип связи с RNDIS устройством (ОС Windows).
Более подробно о нём можно почитать тут и там.
Если вкратце, то RNDIS протокол — это расширение NDIS для внешних устройств. Роль протокола — обеспечить поддержку PnP и обмен сетевыми пакетами. По сути своей, RNDIS — самостоятельный сетевой интерфейс, информационной нагрузкой которого являются кадры канального/сетевого уровней (Ethernet или IP кадры, опционально).
На приведённой схеме это реализует кубик «Минипорт Remote NDIS», который отвечает за:
— сервис общения (спросить у сетевого устройства его MAC-адрес, размер пакета, скорость работы и прочее)
— оборачивает отправляемые хостом сетевые пакеты в RNDIS заголовок
— транслирует принимаемые от устройства пакеты, выбрасывая RNDIS заголовок
Кубик «Минипорт Remote NDIS USB» отвечает за транзит RNDIS посылок, работая с драйвером USB шины.
На стороне контроллера STM32 за поддержку RNDIS протокола и работу с USB отвечает файл usbd_rndis_core.c. Он делает то же самое, что и «кубик» хоста «Минипорт Remote NDIS» — занимается приклеиванием/отклеиванием заголовков, а также отвечает на вопросы драйвера. Ответы, вроде MAC-адреса и скорости он берёт из файла usbd_rndis_core.h.
После успешной инициализации RNDIS драйвер Windows создаёт сетевой интерфейс, который в последствии отображается в «Центре управления сетями» и в области трей-индикатора.
Шаг 3. Получение IP-адреса
Итак, для чего нужна служба получения динамического адреса. Эта служба называется DHCP (протокол динамической настройки узла).
После того как хост инициализирует наше устройство, он создаёт сетевой интерфейс.
Сетевой интерфейс (если кто не знает)
Сетевой интерфейс — это программная сущность, предоставляющая доступ к ресурсам физической или виртуальной сети.
Чаще всего каждому сетевому интерфейсу хоста соответствует конкретный сетевой адаптер. Но есть множество других интерфейсов, вроде локальной петли или те, что служат для взаимодействия с виртуальной машиной. В их случае в сигнальном виде из хоста «ничего не выходит» — обмен происходит программным способом.
Каждому сетевому интерфейсу хоста должен быть сопоставлен хотябы один IP-адрес. По нему «жители сети» может обратиться к хосту.
Если «на проводе» адресовано несколько сетей (например, устройства с IP адресами 10.4.1.xx и 192.168.1.xx), то интерфейсу может назначаться два «личных» IP-адреса. Они могут выглядеть так: 10.4.1.151 и 192.168.1.200. Узнать набор сетевых интерфейсов и сопоставленных им IP-адресов в ОС Windows можно с помощью команды ipconfig и с помощью ifconfig в ОС Linux.
Для описания сетей/подсетей используется маска. Например, правильное описание сети 10.4.1.xx такое: сеть 10.4.1.0, маска 255.255.255.0. Либо, если 4-ёх байтовое число маски представить в двоичном виде и посчитать число ведущих едениц, то получится значение 24. Тогда сеть можно описать так: 10.4.1.0/24.
Подробнее об этом можно почитать в соответствующих источниках.
Известны две основные стратегии назначения IP-адреса интерфейсу: статический способ (когда пользователь сам прописывает адрес интерфейсу) и динамический (с помощью DHCP-службы).
Последний заключается в том, что при создании интерфейса на хосте активизируется служба DHCP-клиента. Она начинает посылать в сеть (конфигурация которой пока не известна) широковещательные пакеты по протоколу UDP, в надежде на то, что в сети присутствует DHCP-сервер.
Функция DHCP-сервера в общем, и в частности на нашем контроллере — ответить клиенту. В ответе контроллер «говорит»: клиент, ты в такой-то сети, держи такой-то IP-адрес, а ещё у нас имеется DNS-сервер с таким-то адресом.
После этого хост «чувствует себя» намного лучше: он назначает интерфейсу выданный IP-адрес и запоминает IP-адрес DNS-сервера.
Инициализация закончилась, теперь можно вводить имя страницы (run.stm) в браузере хоста.
Надо сказать, что поведение библиотеки LRNDIS настраивается. Службу DHCP-сервера можно исключить из сборки. Тогда на хосте придётся прописывать любой адрес, принадлежащий диапазону 192.168.7.(2-254). Такая сеть создаётся по умолчанию. Её параметры (192.168.7.0/24) также настраиваются. В примере клиенту выдаются адреса в диапазоне 192.168.7.2… 192.168.7.4 с временем лизинга 24 часа.
Более подробно по вопросу настройки библиотеки можно посмотреть в предыдущей статье.
Шаг 4. Загрузка страницы
Для загрузки страницы пользователь может ввести адрес нашего устройства 192.168.7.1 напрямую.
Однако, запоминать цифры не требуется, т.к. помимо DHCP-сервера, есть возможность собрать библиотеку с поддержкой DNS-сервера, функция которого — разрешать сетевые имена. В публикуемом примере DNS-сервер обучен разрешать имя ресурса «run.stm».
Поэтому, если в браузере написать run.stm, сетевая служба хоста отправит нашему (и не только) DNS-серверу запрос, в ответ на который сервер услужливо сообщит: доменному имени «run.stm» соответствует IP-адрес 192.168.7.1. Далее браузер хоста по известному адресу совершит TCP подключение с целью отправить HTTP запрос на получение корневой страницы.
Запрос и ответ между браузером Firefox и контроллером:
История запросов при загрузке страницы:
Из истории мы видим, что, после загрузки корневого HTML-документа браузер также загружает из контроллера другие два файла: discovery.svg и zepto.min.js. Первый — это изображение платы discovery. SVG формат выбран, т.к., являясь изображением векторной графики, мало занимает места в ПЗУ микроконтроллера. Скриптовый файл zepto.min.js включён, т.к. является урезанным аналогом знаменитого JQUERY. Надо заметить, что скрупулёзной экономии места в ПЗУ не производилось, т.к. не смотря на жертву в 35 Кб на все статические ресурсы, памяти контроллера ещё вполне достаточно. К тому же данный размер с дальнейшим увеличением сложности интерфейса обещает расти заметно медленней. Если же интерфейс разросся существенно — всегда есть выход хранить и отдавать статические ресурсы в сжатом виде — все известные браузеры на данный момент поддерживают декомпрессию «на лету».
Ещё один запрос, который отправляет браузер — это запрос /state.cgi. Он формируется скриптом из корневого HTML-документа с периодичностью 5 раз в секунду. Нужен запрос для получения в динамике текущего состояния устройства.
При приёме данного запроса, контроллер формирует и отвечает следующей строкой в JSON формате:
Она и содержит все данные о текущем состоянии устройства, которые впоследствии отображаются на странице средствами JavaScript кода.
Ну и, пожалуй, последний момент в общении с браузером — способ управления.
В примере происходит управление тремя светодиодами. Например, при щелчке на флажок красного светодиода средствами JavaScript отправляется HTTP GET запрос с передачей параметра «r» и значения 0 или 1. Полностью запрос выглядит так: /ctl.cgi?r=1
Таким или альтернативными способами можно передавать любой набор данных, будь то логическое состояние 0/1, или значение текстового поля, или уведомление о нажатии кнопки. Красота подхода заключается в том, что программная логика вовсе может не знать о элементах управления, ибо получает строго формализованные управляющие сообщения. Также можно менять и отлаживать интерфейсную часть (HTML+JS) локально со всеми удобствами, после чего однократно заливать в составе прошивки в контроллер. Локальной web-разработкой, что не мало важно, может заниматься соответствующий специалист.
О стеке LWIP
Никакого сетевого обмена устроить бы не получилось, если бы не данный сетевой стек, который и был встроен в библиотеку.
Поскольку библиотека работает под «голым» железом (без ОС и динамической аллокации памяти), то надстройка в виде сокетов для использования недоступна. Написание сетевых приложений поэтому происходит с использованием сырого API стека. По этой теме, к счастью, в сети много информации.
Также в составе пакета contributions есть множество уже готовых решений. В том числе оттуда и был использован HTTP-сервер.
В прошлой статье я давал краткое описание стека и его настройки. На данный момент был уточнён набор важных для стека определений в файле
Также была решена проблема с mem_malloc. Хоть текущая версия прошивки и не использует динамическую аллокацию, аппаратный крах при вызове mem_malloc держал настороже. Разрешилось добавлением определения MEM_ALIGNMENT, который раньше был обойдён вниманием.
По этой же причине стабильно заработал поддерживаемый сообществом HTTP-сервер, что и побудило отказаться от планов создания собственного.
Нерешённые вопросы
1. Ньюансы релицензирования стека lwip, который может иметь свои условия включения в состав другого ПО;
2. Доработка DNS-сервера для обработки «многовопросных» пакетов;
Вместо заключения
Благодарю читателя за терпение и надеюсь, что данная статья окажется для него полезной. Опубликованная в исходных кодах библиотека LRNDIS доступна для использования на правах MIT-лицензии. Считаю замечательным, если работа, на которую было уделено ощутимое время и запас сил, окажется полезной ещё кому-то. На худой конец, без использования открытых библиотек не получилось бы и этой.
В данный момент планируется поддержка библиотеки, поэтому за вопросами можно обращаться по адресу электронной почты fsenok@gmail.com.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Open Source проекты с каждым днём набирают всё большие обороты, появляются новые, активно развиваются популярные.
Такие проекты как Bootstrap, Angular.js, Elasticsearch, Symfony Framework, Swift и многие другие привлекают новых разработчиков, их сообщество растёт. Всё это даёт огромный рост проектам, а самим разработчикам интересно поучаствовать в разработке чего-то, чем пользуется весь мир.
Я, как и многие другие программисты, не устоял и также время от времени участвую в разработке Open Source проектов, в основном на PHP.
Но когда я начинал, я столкнулся с проблемой — я не знал, как правильно организовать процесс «контрибьютинга», с чего начать, как сделать так, чтобы мой Pull Request рассмотрели и т.д.
Всем начинающим «контрибьютерам», которые столкнулись с похожим проблемами, добро пожаловать под кат.
Сам процесс участия в Open-Source проекте рассмотрим на примерах различных PHP фреймоворков, возьмём Symfony, Yii2.
Первое, что необходимо сделать — это создать аккаунт на GitHub (если его ещё у Вас нет). Заполняйте его внимательно, так как Ваш GitHub профиль — это фактически Ваша визитная карточка в мире Open Source.
Далее следует ознакомиться с правилами участия в разработке для выбранного Вами проекта. Данные правила обычно находятся в файле
Обычно, есть несколько способов участия в разработке Open Source проекта, основные — это отправка сообщения о какой-то ошибке или желаемом улучшении (Submitting Issue) или непосредственное создание Pull Request с вашим исправлением или улучшением (Code Contributing).
Так же Вы можете поучаствовать в улучшении документации, ответах на вопросы, возникщих у других разработчков и многое другое.
Если Вы захотели уведомить разработчиков о какой-либо найденной ошибке или улучшении, Вам необходимо создать соответствующий GitHub Issue.
Но перед тем, как создавать его, проверьте, не существует ли уже такого же или похожего, созданного кем-либо другим.
Перед созданием также не забудьте ознакомиться с правилами отправки отчёта об ошибке для данного проекта. К примеру, вот правила для Yii Framework
Обычно, описание должно быть максимально чётким, понятным, желательно наличие примеров и описания как воспроизвести ошибку. Это сэкономит огромное время и разработчикам, и Вам, так как избавит Вас от ответа на уточнящие вопросы и т.д.
Если вы нашли GitHub Issue, которое хотели бы исправить или же создали свой собственный, то следующим Вашим шагом будет отправка соответствующего Pull Request.
Опять же, для начала не забудьте ознакомиться с правилами участия в разработке для выбранного Вами проекта.
Например, вот правила для Yii.
Далее я хотел бы описать наиболее часто встречаемый процесс работы с Git и GitHub при участии в Open Source проектах (Git Workflow).
Этот процесс может отличаться от проекта к проекту, да и в целом он присущ не только Open Source проектам, но и многим закрытым проектам на GitHub и BitBucket.
Шаг 1 — Подготовка рабочего окружения
Естественно, для разработки Вам надо подготовить Ваше рабочее окружение.
Многие Open Source проекты указывают, как именно необходимо его настроить, какие библиотеки, пакеты, инструменты, их версии и тд необходимы.
Для PHP-проектов обычно Вам понадобится приблизительно такой минимальный список
Git;
PHP; (Обычно версии от 5.3+)
MySQL;
Composer.
Кроме того, часто необходим PHPUnit. Обычно он идёт в составе самого проекта и лучше использовать именно его, так как в разных версиях PHPUnit тесты могут попросту не работать и то, что работает у вас с новейшей версии, может не работать на CI сервере проекта, где библиотека более старая.
Шаг 2 — Создаём копию (Fork) репозитория проекта
Заходим на страницу выбранного Вами проекта и нажимаем кнопку «Fork». Данная команда создаст Вашу собственную копию репозитория данного проекта.
Далее Вам необходимо склонировать вашу копию репозитория.
git clone http://ift.tt/1J8zFJZ
Далее Вам необходимо добавить ветку upstream для проекта, которая будет ссылаться на базовый репозиторий (вариант для Yii)
cd <Локальная-Папка-Проекта>
git remote add upstream http://ift.tt/1n2p0pM
Шаг 3 — Настроим Git
Далее, необходимо сделать небольшую настройку Вашего Git, для того, чтобы при отправке коммитов, отображалось ваше корректное имя.
Для это достаточно выполнить данные команды:
Далее, в 99% случаев для проекта Вам придётся выполнить загрузку библиотек через Composer
cd <Локальная-Папка-Проекта>
composer install
Шаг 5 — Тесты
Перед тем, как начать работу, настройте в своей любимой IDE или просто в консоли PHPUnit (реже Behat, PhpSpec и тд) для запуска и работы с тестами.
После настройки запустите тесты для проекта и проверьте что они корректно проходят.
Шаг 6 — Работаем с кодом
Начиная работать над вашим исправлением, изначально надо создать соответствующую Git ветку, основанную на актуальном коде из базового репозитория.
Выбирайте чётко и лаконично имя ветки, которое отражало бы суть изменений.
Считается хорошей практикой включать в названии ветки номер GitHub issue.
Теперь вы можете смело приступать к работе над кодом.
Работая, помните о следующих правилах:
Следуйте стандартам кодирования (обычно это PSR-стандарты);
Пишите юнит-тесты, чтобы доказать, что ошибка исправлена, или что новая функция на самом деле работает;
Старайтесь не нарушать обратную совместимость без крайней необходимости;
Используйте простые и логически цельные коммиты;
Пишите чёткие, ясные, полные сообщения при коммите изменений.
Шаг 7 — Отправляем Pull Request
Пока Вы работали над кодом, в основную ветку проекта могли быть внесены другие изменения. Поэтому перед отправкой ваших изменений Вам необходимо сделать rebase Вашей ветки.
Делается это так:
git checkout <ИМЯ-ВАШЕЙ-ВЕТКИ>
git fetch upstream
git rebase upstream/master
Теперь вы можете отправить Ваши изменения.
git push origin <ИМЯ-ВАШЕЙ-ВЕТКИ>
После этого заходим в Ваш репозиторий-клон проекта, в котором Вы участвуете и нажимаем кнопку «New Pull Request».
И видим следующую форму:
Слева необходимо выбрать ветку, в которую Вы хотите смержить изменения (обычно это master, ну а вообще это ветка, на которую вы делали rebase).
Справа — ветку с Вашими изменениями.
Далее Вы увидите сообщение от GitHub о том, возможно ли автоматически смержить изменения или нет.
В большинстве случаев, Вы увидите Able to merge.
Если же есть конфликты, Вам скорее всего придётся пересмотреть Ваши изменения.
Далее нажимаем кнопку — Create Pull Request.
При заполнение имени и описания вашего Pull Request считается хорошей практикой указывать номер Issue, для которого создан ваш Pull Request.
Обычно для многих крупных проектов настроен CI сервер, часто Travis-CI.
После создания Pull Request он будет прогонять тесты, возможно какие-то инструменты для метрик и так далее. Результы его работы вы увидите в Вашем Pull Request как показано ниже:
В случае, если тесты не будут пройдены или билд не будет собран, вы увидите красное сообщение об ошибке и по ссылку Details сможете увидите, что же именно не так. В большинстве случае Вам необходимо будет исправить ваш Pull Request, чтобы все проверки проходили успешно.
Шаг 8 — Перерабатываем Pull Request
Если с Вашим Pull Request всё хорошо, то в скором времени он будет смержен кем-то из команды.
Но часто бывает, что разработчики попросят Вас внести какие-то изменения.
Для этого просто возвращаемся к шагу 6 и после внесения изменений и коммита выполняем похожие команды:
Примечание: Лично я люблю отправлять Pull Request лишь с 1 коммитом. Для этого я делаю «squash» ненужных коммитов. Как это сделать можно прочитать здесь — http://ift.tt/1eN7JIW
Шаг 9 — Убираемся после себя
После того, как ваш Pull Request был принят или же отвергнут, Вам необходимо удалить ветку с Вашими изменениями.
Делается это просто
Пожалуй это всё, что касается базовых вещей участия в Open Source проектах.
Хотел бы добавить, чтобы Вы не ленились и участвовали в Open Source проектах, это огромный и интересный опыт, а также галочка в резюме ;)
Также, для PHP-разработчиков есть отличный гайд как контрибьютить в Symfony, он будет полезен не только при работе с Symfony http://ift.tt/1HQAmnN
Всем Спасибо!
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
MIPSfpga — это пакет, который содержит процессорное ядро в исходниках на Verilog, которое можно менять, добавлять новые инструкции, строить многопроцессорные системы, менять одновременно софтвер и хардвер, симулировать на симуляторе верилога, синтезировать для ПЛИС/FPGA и т.д. Его можно в целях эксперимента например запускать с частотой 1 такт в секунду и выводить наружу информацию о состоянии кэша, конвейера, и любых структур внутри процессора. При этом ядро MIPS microAptiv UP внутри MIPSfpga — это то же ядро которое например используется в платформе IoT Samsung Artik 1 и Microchip PIC32MZ, т.е. студенты получают возможность работать с тем же кодом, с которым работают инженеры в Samsung и Microchip.
MIPSfpga не предназначен для введения в предмет с абсолютного нуля. Для его плодотворного использования нужно чтобы студент или исследователь уже знал основы цифровой схемотехники, умел бы программировать на Си и на ассемблере, а также представлял бы концепции микроархитектуры — конвейера, конфликтов конвейера и т.д. Желательно, чтобы до работы с MIPSfpga студент уже бы построил собственный простой процессор с нуля и мог бы сравнивать свой простой процессор с процессором, используемым в промышленности и совместимым с развитой экосистемой разработки.
Сначала желательно прочитать базовую презентацию в MIPSfpga_Fundamentals/Slides/MIPSfpga_LectureSlides.pdf
Потом можно просмотреть «MIPSfpga/MIPSfpga Getting Started Guide.pdf» — на нем не нужно зацикливаться; это популярное описание, которое расжевывает слайды, но не заменяет ни в коей мере коммерческую дукументацию на ядро MIPS microAptiv UP, публичная часть которой находится в директории MIPSfpga/Documents, в том числе документация по внешним сигналам (MIPS32 microAptiv UP Processor Core Family Integrator’s Guide) и программированию (MIPS32 microAptiv UP Processor Core Family Software User’s Manual).
Документацию по архитектуре MIPS стоит скачать (с регистрацией) из:
Вскоре после выпуска, у MIPSfpga начали появляться разнообразные расширения и улучшения. Вместо исходного пакеты мы рекомендуем использовать одно из таких расширений, которое называется MIPSfpga+.
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Прошло уже много времени с выхода второй статьи (часть 1, часть 2), а тут как раз есть что рассказать, так как вышел первый релиз третьей версии системы.
Вкратце об изменениях
Третья версия понемногу двигается в направлении микроядерной архитектуры. Это значит что код ядра всё так же достаточно сильно связан (хотя немного меньше чем до этого), некоторые второстепенные фичи были попросту удалены и появилось больше точек соприкосновения, где разработчик может при необходимости вклиниться в работу системы если он того желает.
На стороне сервера был проведен масштабный рефакторинг нацеленный на простоту и качество кода, что за последние пол года вылилось в повышение оценки Scrutinizer с 5.4 или что-то около того до текущих 7.74/10, что уже совсем неплохо.
На стороне клиента произошла революция, Polymer 0.5.x был обновлен до Polymer 1.x и все компоненты были соответственно переписаны, ещё был полностью выпилен UI фреймворк и некоторые другие изменения.
Polymer
Пожалуй, стоит начать с Polymer. На Google I/O 2015 была анонсирована первая стабильная версия Polymer 1.0, которая весьма существенно, хоть и не радикально отличается от версии 0.5, используемой в CleverStyle CMS на тот момент.
К сожалению, первая версия была достаточно кривой с большим количеством неудобств, и даже версия 1.1 не сильно это исправила.
CleverStyle CMS 3 поставляется с Polymer 1.2 и рядом патчей поверх, которые исправляют многие неровности в работе библиотеки, а так же вносят некоторые удобства. Многие из ранних патчей уже приняты в кодовую базу Polymer, но не все.
Так же для более быстрой загрузки сборка Polymer поставляемая с системой являет собой минифиицированную JS версию вместо набора официальных неминифицированных HTML файлов.
Таким образом Polymer в составе системы является гораздо лучшей средой для разработки чем ванильная версия.
Патчи поверх Polymer протестированные и обратно совместимые, так что проблем при использовании собственных или сторонних компонентов не будет (на момент написания статьи я вхожу в топ-10 разработчиков Polymer по вкладу в кодовую базу, так что я знаю о чём говорю).
К примеру:
// Before
Polymer({
is : 'my-element',
properties : {
username : {
type : String,
value : 'Guest'
},
registered : {
type : Boolean,
value : false
}
}
});
// After
Polymer({
is : 'my-element',
properties : {
username : 'Guest',
registered : false
}
});
То есть имея значение по умолчанию нет никакой проблемы вывести тип свойства, но разработчики никак не примут соответствующий PR, хотя это у них P1.
Или пример касающийся стилей:
// Before
:host ::content div {}
// After
::content div {}
Мелочь, но приятно что этот костыль больше не нужен (это проблема в Polymer, по спецификации :host там не нужен), PR тоже ожидает своего часа.
Последнее что стоит упомянуть — так это то, что Polymer 1.x на момент написания статьи не поддерживает расширение пользовательских элементов, но хак с переопределением элементов всё же был портирован и позволяет разработчику полностью или частично переопределять внешний вид и устройство встроенных системных и любых других пользовательских элементов. Подробнее с примерами в документации.
TinyMCE и Shadow DOM
Полноценные WYSIWYG редакторы это большие и сложные приложения и ни одно из популярных решений не поддерживает работу внутри Shadow DOM по причине сложности реализации и поддержки (на момент написания статьи, хотя судя по инициативности разработчиков это ещё долгое время будет актуально).
Проведя несколько дней в дебрях мегабайтов JavaScript кода и пошаговом отладчике браузера мне удалось получить обратно совместимую версию TinyMCE, которая полноценно работает внутри теневого дерева.
На сколько мне известно — это первая в мире реализация полнофункционального WYSIWYG редактора с поддержкой Shadow DOM, а CleverStyle CMS первый продукт, где вы можете его использовать что называется из коробки.
Для того чтобы подключить редактор нужно установить плагин TinyMCE и обернуть <textarea> следующим образом:
<cs-editor>
<textarea></textarea>
</cs-editor>
Под капотом элемент-обертка применит Shadow DOM-совместимую версию TinyMCE к <textarea>, а так же подключит CSS стили к редактору в дополнение к используемым по умолчанию глобальным, чтобы элементы интерфейса корректно отображались даже внутри Shadow DOM.
А ещё элемент-обертка понимает когда он перемещается в DOM, фокусируется и так далее, обновляя соответствующим образом связь с текстовым полем.
Есть так же вариация с inline режимом, применяемым для редактируемого <div>:
Интересно, что при отсутствии плагина TinyMCE элемент-обертка просто не будет обновлен до веб-компонента и пользователь увидит обычное текстовое поле, такое вот прогрессивное улучшение:)
Так что теперь впервые в истории человечества можно использовать WYSIWYG редактор в любом месте документа на любом уровне вложенности теневого дерева.
Исторически система поставлялась с каким-то UI фреймворком. Давным давно это был jQuery UI, который впоследствии был заменен на UIkit.
Последний служил весьма неплохо до того момента как в системе начали использоваться веб-компоненты, после чего несколько критических недостатков UIkit послужили причиной его полного выпиливания.
Во-первых та же поддержка Shadow DOM. UIkit понятия не имеет (так же как и Bootstrap, Foundation и другие приятели) что такое теневое дерево. И ладно если бы это касалось только стилей — были проблемы с обработкой событий и прочими нюансами.
В течении многих месяцев система поставлялась с растущим количеством патчей поверх ванильной версии для обеспечения поддержки Shadow DOM, но разработчики не спешили принимать патчи, к сожалению.
Вторая существенная проблема — это избыточная верстка и отсутствие поддержки data-binding из Polymer. В результате подключение компонентов UIkit превращалось в месиво как на стороне разметки, так и в JavaScript, причиняя боль и страдания при каждой попытке использования.
Решение было нелегким. На поиски альтернативы ушло дня три, ещё пару дней на обдумывание реализации и в результате появился пока ещё подпроект CleverStyle Widgets (есть планы выделить в отдельный самостоятельный проект).
CleverStyle Widgets
Как следует из названия, это не фреймворк, хотя он и заменил на 99% UIkit.
Виджеты — это набор веб-компонентов.
Все веб-компоненты отлично работают с Shadow DOM по определению, так как используют Polymer и поддерживают его data-binding систему (в отличии от UIkit, Bootstrap, Foundation и других приятелей).
Они имеют радикально простой API для пользователя, чаще всего это один тэг, который делает всё что нужно — никаких пятиэтажных вложенностей безликих <div>.
Но что ещё более важно — элементы сами по себе не имеют визуального стиля — он определяется извне с помощью CSS mixin-ов (в отличии от фиксированного внешнего вида Paper Elements с Material Design и Strand, который вообще идет в едином визуальном исполнении). Таким образом вы можете сделать внешний вид таким, каким он нужен именно вам.
В набор виджетов входят кнопки, переключатели, всплывающие подсказки, модальные окна и подобные нужные вещи.
Несколько примеров использования:
<button is="cs-button" type="button" icon="home" primary>Primary button with home icon</button>
<label is="cs-label-switcher">
<input checked type="radio" value="0">
Zero
</label>
<label is="cs-label-switcher">
<input checked type="radio" value="1">
One
</label>
<nav is="cs-nav-pagination" page="3" pages="10"></nav>
<cs-notify success left>Hello</cs-notify>
<button is="cs-button" type="button">Button will open modal</button>
<section is="cs-section-modal">One Two Three</section>
Упор сделан на максимальное сходство с нативными элементами, максимальное использование встроенного функционала браузера.
Больше примеров и описание свойств каждого элемента в документации.
Фронтенд без стилей по умолчанию
Используя UI фреймворк вы получаете огромную кучу стилей примененных ко всему документу, что периодически вынуждает бороться с этими стилями, порой даже прибегая к использованию !important.
Что хорошего в CleverStyle CMS 3 так это то, что НИКАКИЕ СТИЛИ НЕ ПРИМЕНЕНЫ К ДОКУМЕНТУ ПО УМОЛЧАНИЮ!
На практике это значит что даже normalize.css по умолчанию не используется. Разработчик имеет полную свободу по настройке внешнего вида и при желании может воспользоваться встроенными shared styles. Это так же значит что вы можете без конфликтов портировать любой готовый HTML шаблон в качестве темы оформления, можете при желании воспользоваться тем же Bootstrap, UIkit или чем-то ещё без проблем с наложением стилей.
Ещё больше фронтенда
Система никогда не использовала шаблонизатор и никогда не будет. Для генерации разметки используется BananaHTML, которая тоже была обновлена с частичной потерей обратной совместимости и сейчас гораздо более удобная и прямолинейная чем раньше.
Тем не менее, сейчас количество кода на сервере генерирующего разметку стало существенно меньше (в ядре системы это всего несколько строчек). Взамен вся админка сейчас работает полностью на клиенте, включая навигацию между страницами и взаимодействует с сервером через API.
Это так же значит что разработчик может либо модифицировать интерфейс админки не меняя ядро, либо вообще написать альтернативную админку используя API если проект того требует. То же касается настроек пользователя.
Качество кода
Рефакторинг на сервер не только упростил понимание кода, но и в целом повысил его качество по ряду объективных метрик. При этом Scrutinizer имеет доступ к ещё большему количеству кода, так как API системы использует маршрутизацию основанную на контроллере, а Scrutinizer с ООП дружит лучше.
Прочие интересные изменения
На фронтенде был переработан объект cs.Event, теперь события основываются на Promise.
Это последняя стабильная ветка с поддержкой IE10 (и, возможно, IE11), поэтому полифилы для IE/Edge теперь вынесены в отдельную папку и подключаются для этих отставших браузеров, остальные браузеры не тратят на это трафик.
К минификации CSS и объединению CSS/JS/HTML добавилась минификация JS. Реализация весьма простая, как и минификация CSS, но очень быстраяя и весьма эффективная.
А CSS минификатор перестал встраивать картинки и прочие ресурсы размером больше 4 КиБ, вместо этого он просто корректирует относительные пути, на практике это означает гораздо более начальную быструю загрузку страницы.
Plupload модуль объявлен устаревшим, вместо него теперь появился модуль Uploader, который имеет независимую реализацию всего нужного для загрузки файлов (в том числе Drag'n'Drop, множественная загрузка файла), но при этом в неминифицированном виде имеет в 15 раз меньший размер JavaScript кода чем минифицированный Plupload.
Улучшены интерфейсы работы с многоязычностью как на клиенте, так и на сервере, добавлен ряд событий, на которые разработчик может подписаться, проведено множество оптимизаций, сторонние компоненты обновлены до актуальны версий и многое другое (полный список изменений).
Небольшой тест производительности
Имея достаточно много функциональности из коробки в ядре, CleverStyle CMS остается чрезвычайно быстрой системой.
Понятно, что подобные сравнения не имеют большой практической пользы, но тем не менее они показывают накладные расходы, создаваемые собственно ядром системы, выше этих результатов прыгнуть в общем случае не получится.
Забавы ради была взята последняя git версия CleverStyle CMS на момент написания статьи (3.146.4+build-1793) и абсолютно пустая Symfony Standard Edition 3.0.1.
Нужно заметить, что CleverStyle CMS не работает без БД, поскольку она заводит сессию на каждого посетителя в БД (в данном случае без поддержки cookie это значит что сессия создавалась при каждом запросе) + использовался файловый движок кэша. Symfony Standard Edition устанавливалась через Composer и к БД при запросах не подключалась.
Состояние обоих систем «из коробки», в CleverStyle CMS загружалась пустая главная страница, в Symfony загружалась стандартная страница с надписью «Welcome to Symfony 3.0.1».
nazar-pc@nazar-pc ~> ab -c256 -n10000 cscms.loc
This is ApacheBench, Version 2.3
Copyright 1996 Adam Twiss, Zeus Technology Ltd, www.zeustech.net
Licensed to The Apache Software Foundation, www.apache.org
Server Software: Apache/2.4.17
Server Hostname: cscms.loc
Server Port: 80
Document Path: /
Document Length: 2132 bytes
Concurrency Level: 256
Time taken for tests: 7.813 seconds
Complete requests: 10000
Failed requests: 8468
(Connect: 0, Receive: 0, Length: 8468, Exceptions: 0)
Total transferred: 25217819 bytes
HTML transferred: 21327819 bytes
Requests per second: 1279.86 [#/sec] (mean)
Time per request: 200.022 [ms] (mean)
Time per request: 0.781 [ms] (mean, across all concurrent requests)
Transfer rate: 3151.89 [Kbytes/sec] received
Connection Times (ms)
min mean[±sd] median max
Connect: 0 4 58.3 0 1003
Processing: 5 171 670.6 96 6888
Waiting: 4 171 670.7 96 6888
Total: 9 175 673.2 96 6892
Percentage of the requests served within a certain time (ms)
50% 96
66% 103
75% 108
80% 112
90% 126
95% 148
98% 221
99% 3507
100% 6892 (longest request)
Symfony Standard Edition
nazar-pc@nazar-pc ~> ab -c256 -n10000 symfony.loc/web
This is ApacheBench, Version 2.3
Copyright 1996 Adam Twiss, Zeus Technology Ltd, www.zeustech.net
Licensed to The Apache Software Foundation, www.apache.org
Server Software: Apache/2.4.17
Server Hostname: symfony.loc
Server Port: 80
Document Path: /web/
Document Length: 4580 bytes
Concurrency Level: 256
Time taken for tests: 8.290 seconds
Complete requests: 10000
Failed requests: 0
Total transferred: 48440000 bytes
HTML transferred: 45800000 bytes
Requests per second: 1206.22 [#/sec] (mean)
Time per request: 212.233 [ms] (mean)
Time per request: 0.829 [ms] (mean, across all concurrent requests)
Transfer rate: 5706.01 [Kbytes/sec] received
Connection Times (ms)
min mean[±sd] median max
Connect: 0 14 119.0 0 3003
Processing: 6 197 43.7 194 594
Waiting: 6 194 40.3 192 594
Total: 15 211 127.4 194 3226
Percentage of the requests served within a certain time (ms)
50% 194
66% 203
75% 210
80% 216
90% 242
95% 283
98% 387
99% 1182
100% 3226 (longest request)
Выводы каждый сделает для себя сам.
На этом всё, жду комментариев.
Желающие пообщаться чатике могут сделать это в Gitter.
Код на GitHub, документация там же в разделе wiki.
Запустить пощупать можно одной строчкой с помощью Docker:
docker run --rm -p 8888:8888 nazarpc/cleverstyle-cms
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Данная статья является продолжением поста Генераторы непрерывно распределенных случайных величин. В этой главе учитывается, что все теоремы из предыдущей статьи уже доказаны и генераторы, указанные в ней, уже написаны. Как и ранее, у нас имеется некий базовый генератор натуральных чисел от 0 до RAND_MAX:
unsigned long long BasicRandGenerator() {
unsigned long long randomVariable;
// some magic here
...
return randomVariable;
}
С дискретными величинами все интуитивно понятнее. Функция распределения дискретной случайной величины:
Несмотря на простоту распределений дискретных случайных величин, генерировать их подчас сложнее, нежели чем непрерывные. Начнем, как и в прошлый раз, с тривиального примера.
Распределение Бернулли
Пожалуй, самый быстрый из очевидных способов сгенерировать случайную величину с распределением Бернулли — это сделать подобным образом (все генераторы возвращают double лишь для единства интерфейса):
void setup(double p) {
unsigned long long boundary = (1 - p) * RAND_MAX; // we storage this value for large sampling
}
double Bernoulli(double) {
return BasicRandGenerator() > boundary;
}
Иногда можно сделать быстрее. «Иногда» означает «в случае, при котором параметр p является степенью 1/2». Дело в том, что если целое число, возвращаемое функцией BasicRandGenerator() является равномерно распределенной случайной величиной, то равномерно распределен и каждый его бит. А это значит, что в двоичном представлении число состоит из битов, распределенных по Бернулли. Так как в данных статьях функция базового генератора возвращает unsigned long long, то мы имеем 64 бита. Вот какой трюк можно провернуть для p = 1/2:
double Bernoulli(double) {
static const char maxDecimals = 64;
static char decimals = 1;
static unsigned long long X = 0;
if (decimals == 1)
{
/// refresh
decimals = maxDecimals;
X = BasicRandGenerator();
}
else
{
--decimals;
X >>= 1;
}
return X & 1;
}
Если же время работы функции BasicRandGenerator() недостаточно мало, а криптоустойчивостью и размером периода генератора можно пренебречь, то для таких случаев существует алгоритм, использующий лишь одну равномерно распределенную случайную величину для любого размера выборки из распределения Бернулли:
void setup(double p) {
q = 1.0 - p;
U = Uniform(0, 1);
}
double Bernoulli(double p) {
if (U > q)
{
U -= q;
U /= p;
return 1.0;
}
U /= q;
return 0.0;
}
Почему этот алгоритм работает?
Равномерное распределение
Уверен, что любой из вас вспомнит, что его первый генератор случайного целого числа от a до b выглядел похожим на это:
double UniformDiscrete(int a, int b) {
return a + rand() % (b - a + 1);
}
Что ж, и это вполне правильное решение. С единственным и не всегда верным предположением — у вас хороший базовый генератор. Если же он дефективный как старый С-шный rand(), то вы будете получать четное число за нечетным каждый раз. Если вы не доверяете своему генератору, то лучше пишите так:
double UniformDiscrete(int a, int b) {
return a + round(BasicRandGenerator() * (b - a) / RAND_MAX);
}
Еще следует заметить, что распределение не будет совсем равномерным, если RAND_MAX не делится длину интервала b — a + 1 нацело. Однако, разница будет не столь значима, если эта длина достаточно мала.
Геометрическое распределение
Случайная величина с геометрическим распределением с параметром p — это случайная величина с экспоненциальным распределением с параметром -ln(1 — p), округленная вниз до ближайшего целого.
Доказательство
Пускай W — случайная величина, распределенная экспоненциально с параметром -ln(1 — p). Тогда:
Можно ли сделать быстрее? Иногда. Посмотрим на функцию распределения:
и воспользуемся обыкновенным методом инверсии: генерируем стандартную равномерно распределенную случайную величину U и возвращаем минимальное значение k, для которого эта сумма больше U:
double GeometricExponential(double p) {
int k = 0;
double sum = p, prod = p, q = 1 - p;
double U = Uniform(0, 1);
while (U < sum) {
prod *= q;
sum += prod;
++k;
}
return k;
}
Такой последовательный поиск довольно эффективен, учитывая, что значения случайной величины с геометрическим распределением сконцентрированы возле нуля. Алгоритм, однако, быстро теряет свою скорость при слишком маленьких значениях p, и в таком случае лучше все же воспользоваться экспоненциальным генератором.
Есть секрет. Значения p, (1-p) * p, (1-p)^2 * p,… можно посчитать заранее и запомнить. Вопрос в том, где остановиться. И тут на сцену выходит свойство геометрического распределения, которое оно унаследовало от экспоненциального — отсутствие памяти:
Благодаря такому свойству, можно запомнить лишь несколько первых значений (1-p)^i * p и затем воспользоваться рекурсией:
// works nice for p > 0.2 and tableSize = 16
void setupTable(double p) {
table[0] = p;
double prod = p, q = 1 - p;
for (int i = 1; i < tableSize; ++i)
{
prod *= q;
table[i] = table[i - 1] + prod;
}
}
double GeometricTable(double p) {
double U = Uniform(0, 1);
/// handle tail by recursion
if (U > table[tableSize - 1])
return tableSize + GeometricTable(p);
/// handle the main body
int x = 0;
while (U > table[x])
++x;
return x;
}
Биномиальное распределение
По определению случайная величина с биномиальным распределением — это сумма n случайных величин с распределением Бернулли:
double BinomialBernoulli(double p, int n) {
double sum = 0;
for (int i = 0; i != n; ++i)
sum += Bernoulli(p);
return sum;
}
Однако, есть линейная зависимость от n, которую нужно обойти. Можно воспользоваться теоремой: если Y_1, Y_2,… — случайные величины с геометрическим распределением с параметром p и X — наименьшее целое, такое что:
то X имеет биномиальное распределение.
Доказательство
По определению, случайная величина с геометрическим распределением Y — это количество опытов Бернулли до первого успеха. Есть альтернативное определение: Z = Y + 1 — количество опытов Бернулли до первого успеха включительно. Значит, сумма независимых Z_i — количество опытов Бернулли до X + 1 успеха включительно. И эта сумма больше n тогда и только тогда, когда среди первых n испытаний не более чем X успешных. Соответственно:
q.e.d.
Время работы следующего кода растет только с увеличением величины n * p.
double BinomialGeometric(double p, int n) {
double X = -1, sum = 0;
do {
sum += Geometric(p) + 1.0;
++X;
} while (sum <= n);
return X;
}
И все же, временная сложность растет.
У биномиального распределения есть одна особенность. При росте n оно стремится к нормальному распределению или же, если p ~ 1/n, то к распределению Пуассона. Имея генераторы для этих распределений, можно ими заменить генератор для биномиального в подобных случаях. Но что, если этого недостаточно? В книге Luc Devroye «Non-Uniform Random Variate Generation» есть пример алгоритма, работающего одинаково быстро для любых больших значений n * p. Идея алгоритма состоит в выборке с отклонением, используя нормальное и экспоненциальное распределения. К сожалению, рассказ о работе этого алгоритма будет слишком большим для данной статьи, но в указанной книге он исчерпывающе описан.
Распределение Пуассона
Если W_i — случайная величина со стандартным экспоненциальным распределением с плотностью lambda, то:
Доказательство
Пускай f_k(y) — плотность стандартного распределения Эрланга (суммы k стандартных экспоненциально распределенных случайных величин):
тогда
и вероятность получить k:
совпадает с распределением Пуассона. q.e.d.
Используя это свойство, можно написать генератор через сумму экспоненциально распределенных величин с плотностью rate:
double PoissonExponential(double rate) {
int k = -1;
double s = 0;
do {
s += Exponential(1);
++k;
} while (s < rate);
return k;
}
На этом же свойстве основан популярный алгоритм Кнута. Вместо суммы экспоненциальных величин, каждую из которых можно получить методом инверсии через -ln(U), используется произведение равномерных случайных величин:
и тогда:
Запомнив заранее значение exp(-rate), последовательно перемножаем U_i, пока произведение его не превысит.
Можно же использовать генерацию только лишь одной случайной величины и метод инверсии:
Поиск k, удовлетворяющего такому условию лучше начинать с наиболее вероятного значения, то есть с floor(rate). Сравниваем U с вероятностью, что X
void setup(double rate)
floorLambda = floor(rate);
FFloorLambda = F(floorLamda); // P(X < floorLambda)
PFloorLambda = P(floorLambda); // P(X = floorLambda)
}
double PoissonInversion(double) {
double U = Uniform(0,1);
int k = floorLambda;
double s = FFloorLambda, p = PFloorLambda;
if (s < U) {
do {
++k;
p *= lambda / k;
s += p;
} while (s < U);
}
else {
s -= p;
while (s > U) {
p /= lambda / k;
--k;
s -= p;
}
}
return k;
}
Проблема всех трех генераторов в одном — их сложность растет вместе с параметром плотности. Но есть спасение — при больших значениях плотности распределение Пуассона стремится к нормальному распределению. Можно также использовать непростой алгоритм из вышеуказанной книги «Non-Uniform Random Variate Generation», ну, или же, попросту аппроксимировать, пренебрегая точностью во имя скорости (смотря какая стоит задача).
Отрицательное биномиальное распределение
Отрицательное биномиальное распределение еще именуется распределением Паскаля (если r целое) и распределением Поля (если r может быть вещественным). Используя характеристическую функцию, легко доказать, что распределение Паскаля — это сумма r геометрически распределенных величин с параметром 1 — p:
double Pascal(double p, int r) {
double x = 0;
for (int i = 0; i != r; ++i)
x += Geometric(1 - p);
return x;
}
Проблема такого алгоритма налицо — линейная зависимость от r. Нам нужно что-то такое, что будет работать одинаково хорошо при любом параметре. И в этом нам поможет отличное свойство. Если случайная величина X имеет распределение Пуассона:
где плотность случайна и имеет гамма-распределение:
то X имеет отрицательное биномиальное распределение. Поэтому, оно иногда называется гамма-распределением Пуассона.
Доказательство
Теперь, мы можем быстро написать генератор случайной величины с распределением Паскаля для больших значений параметра r.
double Pascal(double p, int r) {
return Poisson(Gamma(r, p / (1 - p)));
}
Гипергеометрическое распределение
Представьте, что в урне находится N шаров и K из них белые. Вы вытаскиваете n шаров. Количество белых среди них будет иметь гипергеометрическое распределение. В общем случае лучше брать алгоритм, использующий это определение:
double HyperGeometric(int N, int n, int K) {
int sum = 0;
double realK = static_cast<double>(K);
double p = realK / N;
for (int i = 1; i <= n; ++i)
{
if (Bernoulli(p) && ++sum == K)
return sum;
p = (realK - sum) / (N - i);
}
return sum;
}
Или же можно воспользоваться выборкой с отклонением через биномиальное распределение с параметрами:
и константой М:
Алгоритм с биномиальным распределением хорошо работает в экстремальных случаях при больших n и еще больших N (таких, что n
Логарифмическое распределение
Для данного распределения существует полезная теорема. Если U и V — равномерно распределенные случайные величины от 0 до 1, то величина
будет иметь логарифмическое распределение.
Доказательство
Вспомнив генераторы для экспоненциального и геометрического распределений, несложно увидеть, что X, заданный формулой выше, удовлетворяет следующему распределению:
Докажем, что X имеет логарифмическое распределение:
q.e.d.
Для ускорения алгоритма можно воспользоваться двумя уловками. Первая: если V > p, то X = 1, т.к. p >= 1-(1-p)^U. Вторая: пускай q = 1-(1-p)^U, тогда если V > q, то X = 1, если V > q^2, то X = 2 и т.д. Таким образом, можно возвращать наиболее вероятные значения 1 и 2 без частых подсчетов логарифмов.
void setup(double p) {
logQInv = 1.0 / log(1.0 - p);
}
double Logarithmic(double p) {
double V = Uniform(0, 1);
if (V >= p)
return 1.0;
double U = Uniform(0, 1);
double y = 1.0 - exp(U / logQInv);
if (V > y)
return 1.0;
if (V <= y * y)
return floor(1.0 + log(V) / log(y));
return 2.0;
}
Зета распределение
В знаменателе — зета-функция Римана:
Для зета распределения существует алгоритм, позволяющий не вычислять римановскую зета-функцию. Нужно лишь уметь генерировать распределение Парето. Доказательство могу приложить по просьбе читателей.
void setup(double s) {
double sm1 = s - 1.0;
b = 1 - pow(2.0, -sm1);
}
double Zeta(double) {
/// rejection sampling from rounded down Pareto distribution
int iter = 0;
do {
double X = floor(Pareto(sm1, 1.0));
double T = pow(1.0 + 1.0 / X, sm1);
double V = Uniform(0, 1);
if (V * X * (T - 1) <= T * b)
return X;
} while (++iter < 1e9);
return NAN; /// doesn't work
}
Напоследок маленькие алгоритмы для прочих сложных распределений:
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
