Дмитрий Нестерук

Блог о программировании — C#, F#, C++, архитектура, и многое другое

Как выглядит разработка для Blackberry 10

с 21 комментариями

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

Языки и Технологии

Вот у Android все понятно: программы пишутся на Java. Для iOS тоже все более менее понятно: нужно использовать Objective-C, хотя Xamarin предлагает разрабатывать эти приложения в Visual Studio на C# (я это делаю, т.к. хочется использовать R#, и отладка из Студии реально работает, но это дорогая опция). На нишевых платформах все очень неоднородно — под Windows Phone можно писать на C#, C++ или WinJS (это адское месиво из HTML, CSS и JS) а на WinJS для WP8 вроде как нельзя писать. На Blackberry, правда, все еще хуже. Варианты примерно такие:

  • Использовать Java, но это только для «старых» версий, т.е. не для современной BB10. Отпадает сразу.

  • Портирование приложений Android. Ход хороший, конечно, но уверен что реализовано не без косяков. К тому же, не катит для тех, у кого приложений нет вообще.

  • Адаптация приложений Adobe AIR. Та же ситуация что и с Андроидом, плюс я не знаю кто нынче вообще кроме Adobe использует AIR. Последнее приложение которое я видел на AIR был «тяжелый» TweetDeck, но потом он магически материализовал себя как приложение Google Chrome и потребность в Standalone версии отпала вообще.

  • С++. Аааааа! Для написания «современных» BB10 приложений нужно использовать С++!

Я ничего не имею против плюсов, но видев тот адъ который творился с использованием плюсов для Symbian (привет двухэтапное создание объектов), энтузиазма у меня особого не наблюдалось. Тем не менее, решил скачать SDK.

Создание проекта

Всегда интересно, что же предлагает IDE на момент создания проекта. Ведь для мобильных устройств нужно настроить как минимум deployment targets, а это та еще задача, пусть у BB10 еще и нет той фрагментации что у Андроида. Итак, поехали.

Cascades – это то как называется новый интерфейс BB10. Следующий этап – выбор шаблона проекта, при условии что мы решили делать UI а не игру на OpenGL:

Далее все интересней – после генерации проекта (был еще один скрин для названия, я его не стал приводить), появляется мегаокно настроек. Первое, что эта штука делает – это находит ваши девайся или симуляторы:

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

А вот это очень правильно хотя… если учесть как у них там дела… хотя нет, дела у них не так плохо:

Ну да ладно, я зарегился и BBRY (это их новый тикер, раньше был RIMM) уведомил меня о том что ждать часа этак 2.

Интересно, зачем 2 часа на то чтобы выдать ключи? Вероятно там, на том конце, кто-то пробивает мое имя в Гугле чтобы узнать, являюсь ли я of good character. Между прочим, character checks все еще существуют в реале, например для того чтобы получить британский паспорт или права, за вас должен поручиться резидент. Но в данном случае это как-то особенно странно. Дайте мне мои ключи!!!

QNX Momentix IDE

Blackberry поставляется со своей собственной IDE для разработки под названием Momentix IDE. Это только звучит красиво. На самом деле – это Eclipse со всеми вытекающими. Какими? Ну во-первых, система не понимает свой собственный синтаксис:

Автодополнение мало того что выглядит неаппетитно, да еще и тормозит впридачу.

Редактирование UI происходит на языке QML который, не являясь XML-образным, вообще непонятно как редактировать. То есть выглядит это например так:

Автодополнения тут нет вообще (а мы еще ругаемся на XAML), но зато ошибку он подсвечивает. Конечно, этот же QML можно редактировать и в визуальном редакторе:

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

Эмулятор

Признаюсь: я все еще зол на то что Microsoft заставляет пользователей устанавливать Windows 8 только для того чтобы воспользоваться ролью Hyper-V (которая, пакость, еще требует обновленных процов, Core 4 Quad якобы не катит, нужен core i7) под которой запускать эмулятор. Слава Рогам что с Blackberry все проще – вам просто дается VM под VMWare, и все.

Первое что замечаешь — это варианты запуска OS для разных устройств. То что все это в одной виртуалке – это удобно, не люблю когда плодят сущности. Что не очень радует так это наличие Safe Mode, что как бы намекает что «что-то может пойти не так». (И действительно, на практике у меня система после перезапуска просто показала черное окно без каких-либо намеков на активность.)

Должен признаться — QNX Neutrino, подпиленный под Blackberry, выглядит неплохо:

Конечно, UI этот не для фэнбоев Apple а скорее для людей которые просто хотят to get shit done, поэтому собственно мне Q10 и нравится (цена не нравится совсем, правда).

Ну да ладно, вся суть в том, что имея приложение в Momentix IDE, можно нехитрой манипуляцией запустить его в эмуляторе. К сожалению, при первом запуске я получил лишь:

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

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

Пишем Код

У меня обычно первое желание в «плюсовом» проекте – подключить STL и Boost. Но перед этим хочется показать как вообще все происходит. Например, вот как можно создать новый класс:

Добавил #include <vector>, скомпилировал, вроде съело. Это значит что STL, как минимум, работает. Добавляю метод и тут оказывается что IDE добавляет в автодополнение все что вообще только можно:

Это же как сильно нужно ненавидеть разработчиков чтобы в список дополнения залить вообще все, что только можно найти на верхнем уровне. Самое интересное что что моей функции из заголовочного файла в списке вообще нет, что бред и сумасшествие. Да, что там, для member fields автодополнения тоже нет, есть разве что для this-> но дальше него дело не идет.

Решил сделать кнопку. Внезапно в начале ввода атрибута появился комплишн, уже что-то

Смарт-комплишна на этот enum (если это можно так назвать) конечно не было, увы. Кстати, точно так же как и в Visual Studio/XAML, тут есть визуальный редактор свойств, который наверняка может быть полезен:

Для обработки события кнопки можно писать код прямо в QML, что выглядит неидиоматично. Даже XAML не опускается до такого уровня:

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

Ну неужели так сложно помочь пользователю синхронизовать все это дело? Почему я должен беспокоиться о том, что последние скачанные пакеты не стыкуются? Еще примечательно что, в отличии от Visual Studio (да и большинства вменяемых IDE), Momentix IDE не восстанавливает window layout из дебажного в обычный после того как вы закрыли отладку. Как холодной рыбой по лицу, чесслово.

Еще интересно то, что дебаггер у меня не сработал где просили но зато сработал где не просили, а именно почему-то воткнулся в main() хотя моего брейкпоинта там не стояло.

Да, и что касается Boost, то нашел на просторах интернета проект, который как раз портирует Boost для Blackberry, так что если что, можно воспользоваться.

Заключение

Понятное дело что для того чтобы понять как все действительно хорошо нужно попользоваться системой месяц-другой. Мое субъективно ощущение что все могло бы быть намного хуже, и что надо благодарить Рога за то, что у Blackberry получилось хоть что-то. По крайней мере, Cascades — неплохая система, и я думаю что Q10 – неплохой девайс.

Другое дело что API сделанный на С++/QML полностью неинтуитивен. Например, вот как выглядит код создания UI из QML. Попробуйте догадаться что тут что.

Так что против BBRY тут два фактора: неудобный язык (все же Java или C# поудобнее будут), а также неудобная IDE. Много ли разработчиков захотят писать под эту платформу? Пока что относительно пустой магазин Blackberry World — плохо для экосистемы, но что если ее забросают недопроектами в стиле тех «соревнований» которые устраивает Microsoft? Этого-то точно не хотелось бы. Лучше мало, но качественно, чем 99% мусора.

У меня пока всё. Comments welcome.

Написано Dmitri

5 Май 2013 в 11:47

Опубликовано в IDE

Отмечено как , , , , ,

Генерация псевдослучайных чисел

оставьте комментарий »

Должен признаться, что меня никогда толком не волновли механизмы генерации случайных чисел. Ну есть себе rand() или Random, и пускай живет. Но в последнее время, особенно когда внезапно захотелось генерировать числа с нормальным распределением, пришлось немного вникнуть в тему. Поэтому этот пост – про случайные числа.

Равномерное Распределение

Когда вы вызываете какой-нибудь rand() – вы получаете псевдослучайное число с равномерным распределением. Давайте рассмотрим, почему псевдо, и почему с равномерным.

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

Кому-то может показаться, что псевдослучайно – значит плохо. Это вовсе не так. Например, если у вас есть генератор случайных картинок, вы можете сгенерировать много картинок с небольшим разрешением, а потом воссоздать понравившуюся вам картинку с большим разрешением. Главное запомнить seed value каждой картинки что, собственно, не сложно.

Теперь насчет равномерности распределения. Вообще, идея достаточно простая – когда вы генерируете число от 0 до 1, идея в том что вероятность любого числа – одинакова. Иначе говоря, если \theta_1 < \theta_2, то случайная величина Y имеет непрерывное равномерное вероятностное распределение на интервале (\theta_1, \theta_2) если фунция плотности Y выглядит вот так:

\displaystyle f(x)=\frac{1}{\theta_{1}-\theta_{2}}, \theta_{1} \leq y \leq \theta_{2}

Вообщем-то, самая примитивная реализация этой функции это нечто вроде x_n = ax_{n-1}+b \ (\mathrm{mod} \ m), но на практике используются чуть более сложные варианты которые дают более «качественные» случайные числа. И кому-то из вас наверное хочется закричать что «это все булшит» и «какая разница?», но когда вы делаете, например, Монте-Карло симуляции в которых случайных чисел нужно реально много, важно иметь хорошие случайные числа чтобы ваша модель ближе отражала полный хаос который творится во вселенной. (Правильное слово энтропия, кстати.)

Есть целый ряд статистических тестов для проверки качества случайных чисел. Мой подход к этому вопросу – брать лучшее, что можно получить в тех или иных случаях, например рутину ran4 из Numeical Recipes in C. Хотя, по правде сказать, даже дефолтная реализация случайных чисел в .NET – сделана «по Кнуту», и является вполне юзабельной.

Что еще сказать про равномерно распределенные случайные числа? Ну, то что среднее значение – это среднее всего диапазона, т.е.

\displaystyle E[Y]=\frac{\theta_1+\theta_2}{2}

А дисперсия равна

\displaystyle V[Y]=\frac{(\theta_2-\theta_1)^2}{12}

Последний результат особенно интересен. Попробуйте угадать, что будет если сложить 12 случайных чисел и отнять 6!

Нормальное Распределение

Нормальное распределение само по себе выглядит чуть иначе и имеет функцию плотности

\displaystyle f(y)=\frac{1}{\sigma\sqrt{2\pi}}\exp(\frac{-(y-\mu)^2}{2\sigma^2})

Соответственно, это распределение параметризовано средним и дисперсией, т.е. E[Y]=\mu и V[Y]=\sigma^2.

Грубым, но действительно работающим приближением к получению случайного нормально распределенного значения является подход, в котором мы берем, скажем, 12 случайных равномерно распределенных значений и вычитаем 6. Почему? Это возможно благодаря центральной предельной теореме, котороая говорит нам, что сумма большого количества независимых случайных величин (мы это называем i.i.d. – independent and identically distributed) имеет распределение, близкое к нормальному. Соответственно, количество случайных чисел (12) выбрано не случайно, а так чтобы «погасить» дисперсию.

Случай выше подходит разве что для простых вычислений в Excel, где нет встроенной функции RAND() с нормальным распределением. Если же говорить о программировании, то тут скорее полезно преобразование Бокса-Мюллера. Идея в том, что мы берем два случайных числа v_1 и v_2 и проверяем что они находятся в единичном круге (т.е. v_1^2+v_2^2<1). Если они подходят, то берем и возвращаем одно из этих двух чисел, наприемер v_1, но не само по себе а как

\displaystyle r = v_1^2+v_2^2 \\ f = \sqrt{-2 \frac{\log{r}}{r}} \\ \mathrm{return} \ v_1 \times f

Доказательство этого механизма достаточно сложное, так что я его пожалуй оставлю – всегда можно почитать Википедию или Numerical Recipes. Мораль в том, что этот метод позволяет генерить большое кол-во нормально распределенных величин с определенным средним и дисперсией.

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

Написано Dmitri

16 Апрель 2013 в 22:47

Опубликовано в Mathematics

Отмечено как

База данных для технических сообществ

с одним комментарием

Буду краток. Я устал от фейловых мертвопроектов вроде Ineta.ru и хочу тупо иметь базу данных лидеров сообществ, академических учреждений и евангелистов которые готовы посетить те или иные мероприятия. Хочется предоставить user-группам некий kiosk сервис, на котором они могу связываться с другими группами, евангелистами, и т.п. Этакая большая база e-mail’ов и скайп-контактов. Чтобы все видели кто где есть.

Логично, так?

Так вот, я планирую развернуть приватную версию Dynamics CRM которая поможет нам справиться с этой, по сути дела, тривиальной проблемой. А именно:

  • Иметь список всех людей, которые участвуют в технических мероприятиях как организаторы или спикеры. Таких людей очень мало, если брать Microsoft stack, то это MVP плюс еще немного народу. В других стэках тоже людей не так много.

  • Иметь список всех юзергрупп. Волнуют не столько мероприятия которые проходят (это будет и на Ineta и на отдельных сайтах) а скорее географический разброс и понимание того кто где и с кем можно пообщаться.

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

Вся эта тема – полностью приватная, в паблик ничего не выходит. Доступ даю я, напрямую, никакой авторегистрации и прочих благ.

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

Язык английский – опять же, никто напрягаться не планирует, мир глобализован, все такое.

Вот как-то так. Если это вам это нужно для деятельности, пишите мне напрямую (skype: dmitri.nesteruk). Если нет – сорри что съел минуту вашего времени.

Написано Dmitri

29 Март 2013 в 20:18

Опубликовано в Technology

Анонс весенних мероприятий

с 19 комментариями

Несмотря на мои отчаянные попытки жить за пределами России, у меня на сегодняшний день запланированы как минимум 4 мероприятия, на которых я планирую делать доклады по ReSharper а также другим интересным технологиям. Вот предварительный список мест, где я планирую появиться:

  • HTML5 Camp, Москва, 15 Марта — буду делать доклад на тему того как ReSharper ускоряет разработку веб-приложений. Как всегда, не обойдется без обильной кодогенерации а также использования Zen Coding (или даже Emmet, если получится адаптировать к ITextControl).

  • Хельсинки, 3 Апреля — буду делать два доклада, один по ReSharper, другой по использованию F#.

  • Ижевск+Казань, 6-9 Апреля — в Ижевске я расскажу про то, как использовать ReSharper при разработке приложений для Windows Phone 8. Для казани программа еще не определена, но планируется несколько докладов, так что помимо ReSharper/dotX тулов я также возможно расскажу про такие вещи как построить типографический редактор на MPS или простую систему финансовой отчетности на основе YouTrack Workflow Editor (я не шучу!).

  • Рига, 18 Апреля — доклад по Fast Code Craft на встрече DevClub.lv, Рига, Латвия.

  • Санкт-Петербург, 25 Апреля — доклад по YouTrack Workflows на встрече Петербургского ДевКлуба. Встреча пройдет в технопарке Ингрия.

  • Microsoft DevCon, подмосковье, 29-30 Мая — тут планируется много всего. Во-первых, будет стэнд, это значит что у вас будет два дня на то чтобы позадавать каверзные вопросы про ReSharper и другие продукты. Во-вторых, будет короткий, 30-минутный доклад под названием «Что нового в ReSharper 8». Ну и наконец мы планируем круглый стол, чтобы пообщаться на тему наших продуктов и всего такого.

Официальные анонсы разных мероприятий будут появляться по мере их готовности. Мероприятия в России мы будем проводить вместе с Филиппом Торчинским (@philipto) — новым евангелистом JetBrains по России.

Написано Dmitri

3 Март 2013 в 21:27

Опубликовано в Events

Отмечено как ,

Итоги 2012 года

с 25 комментариями

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

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

ПО, которое удалось зарелизить:

  • ActiveMesa X2C – программа, которая из Excel генерирует код. Удивило то, насколько просто интегрироваться с Microsoft Office и в принципе результат порадовал. Единственное что у Офиса все очень мутно в плане маркетплейса, а без правильного маркетинга, как вы понимаете, продукты долго не живут.

  • Мнемоники для ReSharper, IDEA и (в будущем) прочих платформ – это то что уже давно хотелось иметь, но увы остались проблемы перворманса которые тоже нужно как-то решать – я даже из-за этого слегка сократил feature set генерируемых файлов.

  • Основной объем зарелиженного ПО в этом году – скринкасты, блог-посты и внутренние проекты.

Языки и их использование:

  • C# и F# остаются основными языками. F# продолжает очень хорошо показывать себя для вычислений.

  • С++ тоже мною использовался, но я как-то поуспокоился относительно стека Intel – особенно если учесть что они не смогли засимшипить с VS2012. Это вечная их проблема, и мне уже порядком поднадоело. К тому же, в компиляторе от Microsoft появилась технология С++ AMP, которая склоняет весы к «дефолтному» компилятору.

  • Другие языки практически не использовались. Более того, как-то энтузиазма в этом плане поубавилось. Например TypeScript уже не воспринимается как что-то «ого-го».

Новое ПО:

  • В этом году я основательно познакомился с Mathematica и MATLAB. Это системы компьютерной алгебры которые присутствуют у меня в академической подписке (я все еще являюсь исследователем в моем университете, года так с 2006го). У них разные сильные и слабые стороны так что я использую обе.

  • Я начал использовать MarkdownPad для редактирования Markdown как в GitHub’овских README.md так и везде где нужно.

  • Я встроил MathJax в TypograFix, и хотя качество отрисовки формул на не-Retina дисплеях продолжает разочаровывать (ну когда, когда десктопные мониторы наконец догонят?) я уже успел воспользоваться возможностями, как на этом блоге так и на других.

Вообще глобально новая вещь:

  • В этом году я более менее систематично начал изучать quant finance. Отсюда собственно и CAS’ы, а также сопутствующие книги по математике, статистике и прочим заумным дисциплинам. Очень непривычно из самой открытой области (IT) заглянуть в закрытую, проприетарную, где все любят только деньги и никто не любит новичков.

  • В плане сообществ начал посещать Wilmott.com, Quant Finance @ StackExchange, ну и всякие Российские сайты иногда. Приятно быть в среде где ты очень мало понимаешь – это наверное как быть начинающим программистом, когда тебе все кажется какой-то магией. Единственная разница, как я понял, что программистом может быть вообще кто угодно, а на quant finance у большинства людей кишка тонка – нужно намного больше инвестиций – как временных так и денежных.

  • Я чуть было не пошел учиться на MFE (admission получил, что радует, значит не совсем идиот), но в последний момент решил что лучше практиковать чем сидеть и 2 года учиться. Был бы я лет на 10 помоложе, может и пошел бы.

Технологии которые удивили или порадовали:

  • iPad с Retina Display – и тут можно наверное без пояснений, не так ли? По сравнению со всем мусором что делается на платформе РС, новый iPad – единственное что стоит своих денег. (Я продолжаю плеваться в сторону производителей PC-ноутбуков, не говоря о планшетах. Горите все в аду.)

  • Audiolab M-DAC очень сильно порадовал качеством звука. Как сказал мне продавец в магазине, эти штуки расходятся как горячие пирожки. Не удивительно.

  • MindTouch – его бесплатная версия Core – оказалась прекрасной заменой SharePoint… впрочем, чем больше я думаю про SharePoint, тем более очевидна его несостоятельность. В то же время, Microsoft всех и каждого пытается перевести на порталы на SharePoint… на портале MVP меня уже заблокировали т.к. я проигнорировал их требования менять пароль.

Я больше не хочу делать каких-то предсказаний или прогнозов относительно будущего технологий. Понятное дело что Microsoft будет давить свою новую линию, ну и другие производители тоже. Все будут беситься от новых мобильничков, планшетиков и прочей дребедени. Чем бы дитя не тешилось, лишь бы не плакало.

У меня все. С наступающим!

Написано Dmitri

9 Декабрь 2012 в 19:51

Опубликовано в Life, Technology

Оптимизация математических выражений

оставьте комментарий »

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

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

Умножение

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

Например, если изначально у нас есть формула

\displaystyle y=ax^2+bx+c

То в целях повышения производительности, мы можем переписать эту формулу как

\displaystyle y=x(ax+b)+c

В первой формуле – 3 умножения и 2 сложения. Во втором – 2 умножения и 2 сложения. Так или иначе мы сэкономили стоимость одного умножения, т.е. срезали как минимум 20% стоимости этого вычисления.

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

  • a^2-b^2=(a+b)(a-b) имеет смысл при условии что умножение дороже сложения.

  • x^2+10x+16=(x+8)(x+2) содержит одно умножение вместо 3-х (!) но подразумевает решение уравнения. Такую оптимизацию очень сложно обобщить, и в общем случае она подразумевает решение практически бесконечного количества уравнений.

Возведение в степень

Функции возведения в степень обычно заточены под нецелые степени, т.е. степень это значение типа float или double и соответственно для вычисления используются ряды Тейлора. Это значит что цена вычисления x^2 в десятки (!) раз больше чем цена x \cdot x.

В долгосрочной перспективе, любое вычисление x^n где n \ge 2, n \in \mathbb{Z} подразумевает \left\lceil \log_{2}n\right\rceil умножений. В принципе, некоторые языки (например С++) имеют перегрузки метода возведения в степень, где параметр степени – целое число (т.е. int). В этом случае никаких дополнительных усилий не требуется. Если же такой функции не существует (например, в .NET), то есть два варианта:

  • Для n=2,3 имеет смысл просто заменить возведение в степень на умножение, т.к. это эффективней и понятнее чем использование сторонней функции.

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

Конечно, существует и просто неэффективное использование функции возведения в степень: например, не имеет смысла считать x^{0.5} когда вместо этого можно намного быстрее посчитать \sqrt{x}. Ну и не будем забывать про совсем уж специализированные оптимизации расчета функций, например всем известный механизм расчета 1/\sqrt{x} Джона Кармака.

Деление

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

\displaystyle \frac{a}{x}+\frac{b}{x}=\frac{a+b}{x}

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

\displaystyle \frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}

Два деления вместо одного имеют смысл, особенно когда деление в 6 раз медленнее умножения.

Введение временных переменных

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

\displaystyle ax^6+bx^3=x^3(ax^3+b)

мы продолжаем считать x^3 дважды, что влечет за собой 4 умножения вместо 2-х. Гораздо проще внедрить временную переменную y=x^3 и потом просто посчитать y(ay+b).

Заключение

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

Ну и не забывайте, что компилятор тоже не дремлет, и некоторые вещи все же оптимизирует, например:

\displaystyle x/4=x\gg 2

Так что оптимизируйте с удовольствием, или используйте программы, которые оптимизируют за вас. ■

Написано Dmitri

4 Декабрь 2012 в 21:42

Опубликовано в Mathematics

Кодогенерация на практике

с 7 комментариями

Должен признаться, что меня в разработке ПО беспокоит в основном одна, весьма глобальная, вещь – а именно вопрос того, что же является следующим этапом эволюции этого процесса. Ведь я просто уверен что мы не остановимся на текущих языках и подходах, даже не смотря на общее состояние застоя. Интересуют меня, понятное дело, не столько бизнес-процессы разработки (практика показывает, что “тяжелые” процессы обычно инверсно коррелируют с профессиональными навыками и производительностью вообще) сколько инструментарий и сами подходы, с помощью которых ПО разрабатывается.

У меня например на практике очень хорошо “срослось” с кодогенерацией. Настолько хорошо, что думаю стоило бы рассказать эту историю.

Как все начиналось

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

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

Вместо этого, я решил сделать по-другому, и написал custom tool для Visual Studio (тогда еще 2005 версии), который просто-напросто применял к файлам XML трансформации XSLT (используя возможности .NET которые, в плане XML, весьма убоги) и добавлял сгенерированные файлы в проект.

Эта тула, которую я даже попробовал распространить между другими участниками проекта, использовалась мной (а в последствии, когда я “ушел в менеджмент”, моим коллегой) для описания пользовательского интерфейса в формате XML (ну почти как XAML, не правда ли?) и последующей генерации C# файлов (в т.ч. метода InitializeComponent()) для создания собственно интерфейса.

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

  • Сущности
  • Хранимые процедуры для базы данных
  • Пользовательский интерфейс (WPF)

Примерно в то же время я модифицировал свой custom tool для того, чтобы он создавал несколько файлов одновременно и использовал вместо .NET’ного движка Altova XML и язык XQuery соответственно. Язык этот был выбран потому, что в то время Microsoft оправдывали отсутсвие поддержки XSLT 2.0 в .NET идеей о том что “XQuery все равно лучше” и что будем поддерживать его. Сейчас 2012 год, а воз и ныне там.

Проблемы восприятия

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

Впрочем, лично меня это не смутило и с тех времен я постоянно генерю код то тут то там. Например, реализация мнемоников для ReSharper (и не только – они рано или поздно у меня будут для всей линейки IDEA) – это чистой воды кодогенерация, которая просто создает в XML 600+ шаблонов, которые разворачиваются в различные программные конструкты.

Со временем у меня появилось немного измененное восприятие кодогенерации: вместо того чтобы просто генерировать ORMы для баз данных (привет LLBLGen!), я понял что кодогенерация может быть использована для доменных трансформаций, то есть для генерации готового к компилированию кода из какого-то другого представления – представления, которое является “родным” для той или иной предметной области.

Проект MathSharp: генерация кода из математической нотации

Когда я все еще работал на своей “первой” работе (де факто она была никаким образом не первой, но…), одна из задач разработчиков заключалась в том, чтобы брать формулы из 200-страничного документа и конвертировать их в код. Не очень-то сложная работа, если честно, но трудоемкая и, подозреваю, весьма нудная.

Посудите сами: есть у вас например формула вроде

image

а вам нужно конвертировать ее в код вроде

p = rho*R*T + (B_0*R*T-A_0-((C_0) / (T*T))+((E_0) / (Math.Pow(T, 4))))*rho*rho +
    (b*R*T-a-((d) / (T)))*Math.Pow(rho, 3) +
    alpha*(a+((d) / (t)))*Math.Pow(rho, 6) +
    ((c*Math.Pow(rho, 3)) / (T*T))*(1+gamma*rho*rho)*Math.Exp(-gamma*rho*rho);

А теперь представьте что у вас есть сотни формул…

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

  1. Берем формулу в Word и копируем ее в формате MathML. Это такой XML-образный формат как раз для формул.
  2. Парсим MathML и создаем в F# дерево как набор алгебраических типов. F# используем потому что pattern matching+algebraic data types намного легче анализировать.
  3. По созданному дереву генерим код.

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

После внезапного успеха MathSharp (программа писалась где-то неделю), я начал думать что возможно я “ближе к истине” и что подход доменных трансформаций – это как раз то, что доктор прописал от скуки и рутины в разработке. И я начал думать: а какие еще есть нотации, которые люди используют часто, и которые тоже было бы полезно автоматически переводить в код? Так родился еще один проект.

Проект X2C: генерация кода из таблиц Excel

Excel – это двигатель прогресса. Когда кому-то нужно что-то подсчитать, то они вряд ли сразу открывают Matlab или Mathematica: если вычисления простые, то их можно вписать в Excel’евскую табличку и сразу получить как расчеты так и красивое форматирование.

Генерация кода из Excel – задачка посложнее. Ведь сначала нужно понять что генерировать, и для этого я ввел концепцию мэппингов. С помощью них клетки в таблице могут “мэпиться” на переменную, функцию, сущность (т.е. класс), вектор или матрицу. Соответственно все формулы которые используются в Excel нужно поддерживать в том или ином языке программирования. На текущий момент, я использую:

  • C++ и библиотеку Boost.Math
  • C# и (коммерческую) библиотеку NMath

Сам проект называется X2C и реализован в виде плагина для Excel (спасибо Студии и ее интуитивности при разработке VSTO решений) который предоставляет Ribbon UI для разметки клеток и кодогенерации. Этот проект тоже писался быстро т.к. большинство сложных компонентов (например, парсер для формул) взяты со стороны (спасибо компаниям за MVP лицензии!). Мне лишь осталась только задача кодогенерации которая, в данном случае, весьма непростая но по крайней мере понятная. Кстати, если интересно как выглядит вся “кухня”, у меня есть скринкаст который как раз все это иллюстрирует.

Как и с формулами, я провалидировал модель разработки математических алгоритмов в Excel на реальных проектах (в основном в финансовой области), и удостоверился что этот подход действительно стоит усилий. Но меня продолжала и продолжает одолевать мысль, что за всем этим стоит что-то еще более существенное. Далее идут некоторые мои “наборски” на тему того, куда же все идет.

Генерация пользовательского интерфейса из Excel

Давайте начистоту: визуальный дизайнер того же WPF – ни ахти насколько полезный. Я даже не помню как он выглядит т.к. никогда им толком не пользовался. Мораль в том, что большинству разработчиков проще писать руками XAML и потом только эпизодически смотреть на то, получился ли нужный UI или нет.

Задумался я об этом, и тут меня осенило. Ведь если взять скажем Metro-style UI (да-да, я буду использовать слово Metro, мне так удобней), то это фактически большой набор прямоугольников. А знаете что еще набор прямоугольников? Правильно – таблицы в Excel.

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

  • Реализация UI упрощается до уровня Excel. Понятное дело что это устроит не всех, но большинство LoB приложений – это как раз лейблы, текст-боксы и кнопки.
  • Можно автоматически привязать данные и UI, без лишних телодвижений.

Вывод тут один: Excel можно использовать для разработки приложений, в которых используются в основном вычисления и простые контролы. При этом data binding а также проблемы отсутствующих значений (data binding контролов на поля типа Nullable<T> и сопутствующая головная боль) также разрулены на уровне генератора.

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

CPS и формализация Control Flow

Continutation Passing Style (CPS) – это тривиальная, как в танке, практика в которой сложный алгоритм бъется на несколько частей которые вызываются последовательно, и каждая часть возвращает результат вызова следующей. То есть алгоритм из 3-х частей это функция A() которая возвращает результат вызова B(), и так далее. При этом предпочтительно не иметь общего состояния для A() и B(), а вместо этого передавать в функцию только нужные на момент вызова состояния.

Не все конечно любят CPS, но я его успешно использую в тех случаях, когда алгоритм по своему размеру переходит все допустимые рамки. Я также пользуюсь очень “красочными” названиями для составных методов, а также стараюсь применять separation of concerns, так что каждый метод выполняет одну, понятную задачу.

Почему я завел разговор про CPS? Потому что, фактически, поток выполнения программы в этому случае является, по сути… отдельной, маленькой но предметной таки областью. И формальное опередение этой области – “конечный автомат”. Соответственно, вместо того чтобы просто включать механизм создания конечных автоматов в программу как код (пойди разберись как там API Stateless работает), в очередной раз можно прибегнуть к подходу с отдельным редактором. Который может выглядеть например вот так:

image

Пример выше содержит 5 методов, один из которых даже вызывается асинхронно. На практике же, алгоритм описаный в подобном стиле может содержать любое количество методов, но при этом оставаться понятным на концептуальном уровне. Сгенерированный же код уже может быть сполне себе непонятным – например в этой статье я генерирую код на основе механизма Pulse & Wait а это, согласитесь, не самая интуитивная конструкция в .NET-е.

Что следующее?

Вообще все эти разработки наводят на мысли что возможно я копаю в правильном направлении, но не копаю достаточно глубоко. Например, я прекрасно могу в математической нотации выразить подсчет Sharpe ratio но когда дело касается, например, формулы Блэка-Шоулза, то внезапно оказывается что для подсчета кумулятивного нормального распределения N(x), не существует аналитического решения а вместо этого существует формула для приблизительных расчетов. И соответственно парадигма автоматической конверсии рассыпается как карточный домик.

Думаю что основной задачей на данный момент должно стать создание “этически правильного” workflow редактора – некого аналога Workflow Foundation который вместо того чтобы пытаться убить сто зайцев сразу решал бы хотя бы основные задачи, такие как например создание из модели конечного автомата набора заглушек. Мне кажется что это не так сложно, другое дело что в отличии от прямолинейных конверсий, непонятно что добавлять а что нет.

У меня на сегодня все; сорри что стал постить так редко, но на то были причины – например, весь Октябрь я проездил по России с докладами про ReSharper. В плане докладов кстати планы тоже изменились – из за вышеперечесленных программ, меня теперь все повсюду зовут, так что плюсы в карму и плюшки в казну. До новых встреч!

Написано Dmitri

4 Ноябрь 2012 в 0:57

Опубликовано в code generation

Отмечено как , ,

« Предыдущие записи
Follow

Get every new post delivered to your Inbox.

Join 83 other followers