Showing posts with label статьи. Show all posts
Showing posts with label статьи. Show all posts

Tuesday, July 7, 2009

Bachelor Thesis in Computer Science. Part 3. Слайды в LaTeX-beamer

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

  • Полное разделение оформления и содержания. Сначала пишите текст, а оформление можно сменить в любой момент
  • Очевидный плюс, но забывать о нём нельзя: можно использовать все возможности LaTeX
  • Красивые и удобные темы оформления "из коробки"
  • Широкие возможности в настройке и доводке

Пример применения

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

Как видите, слайды выглядят весьма привлекательно. К тому же, представьте, что каждый слайд - это всего пара строчек текста. А теперь, как я и обещал, несколько советов подкрепленные кодом:
  • Не пытайтесь изменить шрифт, чтобы вместить на слайд как можно больше информации. Выполненные в PowerPoint с 12pt шрифтом презентации навевают тоску и абсолютно нечитаемы с расстояния в 5-10 метров. Если уж очень нужно разместить на слайде побольше, а количества строк не хватает - используйте двухколоночную вёрстку. Тогда даже большое количество формул может поместиться на один слайд:
    Для верстки в две колонки используйте пакет multicol(на примере вставки изображений в две колонки):
    \usepackage{multicol}
    %%....
    \begin{multicols}{2}
    \begin{figure}[!ht]
    \begin{center}
    \includegraphics[width=\columnwidth]{../img/positioning_slides1}
    \end{center}
    \end{figure}

    \begin{figure}[!ht]
    \begin{center}
    \includegraphics[width=\columnwidth]{../img/positioning_slides2}
    \end{center}
    \end{figure}
    \end{multicols}
  • Создатели тем оформления beamer не подумали, что название может быть длинным и сократить его будет нельзя. Поэтому во многих темах длинные названия не влазят на слайд. Однако это можно исправить - например, использование подправленной темы оформления, которую вы видели на скриншотах:
    \usetheme{Antibes}
    \useinnertheme{rounded}
    \setbeamertemplate{headline}
    {%
    \begin{beamercolorbox}[wd=\paperwidth,ht=6.5ex,dp=1.125ex,%
    leftskip=.3cm,rightskip=.3cm plus1fil]{title in head/foot}
    \usebeamerfont{title in head/foot}\parbox[b]{0.95\paperwidth}{\@title}
    \end{beamercolorbox}
    \begin{beamercolorbox}[wd=\paperwidth,ht=2.5ex,dp=1.125ex,%
    leftskip=.3cm,rightskip=.3cm plus1fil]{section in head/foot}
    \usebeamerfont{section in head/foot}%
    \ifthenelse{\value{page}>1}{\hskip2pt\raise1.9pt\hbox{\vrule width0.4pt height1.875ex\vrule width 5pt height0.4pt}}{}
    \hskip1pt%
    \insertsectionhead
    \end{beamercolorbox}
    \begin{beamercolorbox}[wd=\paperwidth,colsep=1.5pt]{lower separation line head}
    \end{beamercolorbox}
    }


    \setbeamertemplate{footline}
    {%
    \leavevmode%
    \hbox{\begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm plus1fill,rightskip=.3cm]{author in head/foot}%
    \usebeamerfont{author in head/foot}\insertshortauthor
    \end{beamercolorbox}%
    \begin{beamercolorbox}[wd=.5\paperwidth,ht=2.5ex,dp=1.125ex,leftskip=.3cm,rightskip=.3cm plus1fil]{title in head/foot}%
    \usebeamerfont{title in head/foot}Слайд \insertframenumber
    \end{beamercolorbox}}%
    \vskip0pt%
    }
    Этот небольшой сниппет может стать отправной точкой для написания собственных тем оформления - в нём совсем несложно разобраться по названиям команд
  • Скриптованные презентации никому не нужны. Я имею в виду моргающие анимированные слайды со сложной системой переходов, которые можно создать в Microsoft Office или OpenOffice. Для улучшения восприятия достаточно простейших эффектов, которых можно легко добиться в beamer. Единственной полезной вещи, которой может не хватать в beamer по сравнению с PowerPoint и Impress - воспроизведение видео. Однако встроить видео в PDF тоже можно! Пример:
    \usepackage{movie15}
    %%...
    \frame
    {
    \includemovie[externalviewer]{}{}{../vid/mouse_emulation.avi}
    }
    Этот код отводит отдельный слайд под видео. Стоит отметить, что видео можно будет проиграть только в Adobe Reader (я не знаю свободных альтернатив, которые бы поддерживали видео). Также обратите внимание, что я использую внешний плеер. Использование внешнего плеера гарантирует максимальную кросс-платформенность вашего PDF документа

Выводы

Используйте LaTeX, используйте beamer. Забудьте о медленных, неудобных офисных пакетах, полных недостатков и ошибок.

P.S.

Здесь вы можете найти исходники презентации (без изображений и видео)

Tuesday, June 30, 2009

ICFP contest 2009

Продолжая добрую традицию подробно описывать контесты, начатую с Sapka contest, предлагаю вашему вниманию отчёт о ICFPC 09

Введение

ICFP Contest - командный контест, который проводится один раз в году. Количество участников в команде не ограничено. Задание одно, на весь контест отводится 72 часа(3 суток). Контест делится на lightning round(оцениваются решения, полученные в первые 24 часа) и main round(оцениваются все отосланные решения).

Команда

Страницу команды Concrete mixers можно найти здесь. Т.е., 4 человека, но после lightning A2K отошел от дел. С одним из оставшихся участников - xa4a - я уже участвовал в Sapka, и мы там даже взяли призовое место на Lightning. Со вторым из оставшихся - Murkt - до этого работать вместе не приходилось, но мы вроде неплохо сработались.

Инструменты

Основной язык - Python. В качестве системы контроля версий использовали Mercurial, в качестве хостинга - bitbucket. Для визуализации был использован pygame(также были попытки использовать Qt, но в итоге остался вариант с pygame). Для общения использовали конференцию в jabber.

Задание

Оригинальное задание (последнюю версию) можно скачать здесь. Кратко - нужно было писать управляющие программы для спутника для выполнения разных задач. Поведение спутника и окружающей его вселенной эмулировалось в бинарниках, которые предоставляли организаторы. Бинарники можно было запустить на виртуальной машине, спецификации которой были также предоставлены. Список маневров, которые нужно было выполнять со спутником:
  • Перевод спутника с одной круговой орбиты на другую
  • Рандеву с другим спутником, двигающимся по круговой орбите
  • Аналогичное рандеву, но начальная орбита и конечная могут быть эллиптическими
  • Упрощенное рандеву с 11-ю спутниками на произвольных орбитах. Также здесь присутствует Луна и заправочная станция
Таким образом, большая часть задания связана с орбитальными маневрами - сплошная математика и физика.

Ночь первая (26.06-27.06)

Получили задание, прочитали, пообсуждали, устранили непонимания, распределили задания. Где-то через два часа у нас наконец появился парсер бинарников, еще через час было две VM, из которых мы выбрали лучшую. Еще через два часа я сделал первый тестовый солвер с визуализатором, а к этому моменту xa4a уже залил нужные формулы для hohmann transfer, A2K доделывал логгер, который был нужен для формирования сабмишенов.
Т.о., через 5 часов после начала я приступил к прикручиванию формул к солверу, однако это оказалось не так просто. Murkt с чувством выполненного долга(написанная им VM работала, хоть и медленно) пошел спать, а мы с xa4a и A2K еще часа два пытались починить логгер и формулы, A2K писал визуализатор на Qt. Результат первой ночи - готова VM, визуализатор, основная инфраструктура, однако очков всё еще 0

День первый (27.06)

С утра Murkt и xa4a подхимичили формулы и у нас в нашем симуляторе появились первые очки. Однако при попытке сабмита тут же стало понятно, что написанный ночью логгер ошибочен и я взялся его переделывать. В 14:20 был "EPIC WIN!!!!!"(с)Murkt - первые очки, полученные после исправления логгера. Задачи 1001-1004 в этот момент времени перешли в статус решенных. И пока xa4a и Murkt продолжали изыскания с задачами 2001-2004, я в течение часа многократно ускорил VM путем генерации и последующей интерпретации кода на Python. Также скриншот, сохранившийся с этого временного участка:
В дальнейшем мы все вместе пытались побороть задачи 2001-2004. Напомню, в этих задачах нужно было не просто перелететь на другую орбиту, как в 1001-1004, а и попасть еще и в ту же точку этой орбиты, что и другой спутник. Для того, чтобы этого добиться, мы ввели понятие hohmann delay - время ожидания, нужное, чтобы после него при hohmann transfer попасть в нужную точку. В 18:40 Murkt получил первые очки этим методом. Однако метод оказался совсем не стабильным - решение он давал, но давал и большие погрешности. Поэтому оставшееся до окончания lightning время мы работали в двух направлениях - устранение погрешности и 3001-3004. Ничего существенно добиться мы не успели и lightning закончили с результатом где-то 945 баллов. В top lightning'a мы,естественно не попали, и место в lightning на данном этапе узнать невозможно, хотя и очень интересно.
Ниже - визуализатор, который писал A2K, но который так и не был использован:

Ночь вторая (27.06-28.06)

Появилась Луна и задачи 4001-4004. Часа через четыре усилиями Murkt и xa4a были существенно проапгрейджены решения наших 8 задач и получено 1127.44746 очков. Приблизительно этого хотелось добиться в lightning, но не успели, а жаль. Также xa4a очень красиво переделал солверы (стало чем-то похоже на twisted). С 3х до 6 утра я сделал алгоритм подгазовки через phasing - он работал идеально и позволял проходить 2001-2004 даже без hohmann delay.

День второй (28.06)

Murkt почистил код, а мы с xa4a пытались найти параметры эллиптических орбит и у нас никак не получалось вывести формулу, которая бы работала для всех задач 3001-3004. В поисках решения были привлечены ЧМ и придумано несколько странных методов определения. Однако это ни к чему не привело, а уравнение орбиты было выведено xa4a чуть позже, когда я отсутствовал.

Ночь третья (28.06-29.06)

Murkt сделал naive chase - подгазовку, которая плевала на всю астрофизику и просто заставляла суптник лететь к цели, сжигая при этом топливо(занятный пример представлен ниже).
Этот naive chase отлично работал на небольших расстояниях. Совместив его с hohmann elliptic transfer, который к этому моменту я докрутил до состояния бета, у нас получилось решить все задачи из 3001-3004. Также я пытался сделать phasing для эллиптических орбит, однако из-за каких-то погрешностей точность phasingа оказалась меньше, чем нужно. Тем не менее, применение одной итерации phasing, а потом naive chase привело к увеличению очков.

День третий (29.06)

Весь день был проведен в попытках улучшить переходы по эллиптическим орбитам для 3001-3004, чтобы затем использовать в 4001-4004. Я попытался еще ускорить виртуальную машину посредством psyco (работало отлично, но только на 32-битных системах) и cython(работало везде, но компиляция была слишком долгой, кеширование скомпилированного нужно было делать, а профит был меньше, чем с psyco, т.о. в итоге от него отказались). В 13:04 был эпический "OMFG", когда мы заметили, что в Orbital Mechanics (описание ее смотрите ниже) есть матлабовский код, в котором есть готовые нужные нам формулы и алгоритмы - только копируй, исправляй и пользуйся. По этому коду xa4a переделал определение параметров орбиты, а я пытался сделать smart chase - через уравнение Ламберта. Однако, по-моему мнению, это было лишним - код нормально работать отказывался, а определение параметров орбиты вообще стало работать хуже, чем было. Smart chase также работал хуже, чем naive chase. Я попытался вывести hohmann elliptic delay - аналог hohmann delay но для произвольных эллиптических орбит, однако и этот алгоритм нам не очень пригодился. В этот момент - оставалось часа 3 до конца контеста - мы решили, что нужно хотя бы какие-нибудь Score получить на задачах 4001-4004. Murkt сделал простой солвер, который работал также, как 3001-3004(hohmann elliptic transfer+naive chase), однако ему не хватало топлива. Остальные три часа мы пытались подстроить naive chase, так чтобы он экономил топливо. Итог - пойманы три спутника в 4001(третий спутник был пойман мной за 7 минут до окончания, скриншот смотрите ниже) и два спутника в 4002.
Итог контеста - Weighted Total Score 2852.2285 (14 problems solved), 21 место, если последние 4 часа контеста все участники прохлаждались :)

О разном

  • Репозиторий с исходниками можно найти здесь
  • Orbital mechanics - кодовое название книги Howard Curtis "Orbital mechanics for engineering students" - для нас она стала Библией астрофизики
  • Отчёт от Murkt
  • Отчёт от xa4a

Организаторам

  • Слишком много версий заданий. Последние я даже не читал - надоело
  • Математика - это круто, и я не жалею, что участвовал в контесте, но всё же хотелось увидеть programming contest

Выводы

Как ни странно, текущий раздел не последний в этом отчёте. Тех, кто интересуется математикой, могут также прочитать и следующий раздел. Здесь же хотелось отметить, что фана от ICFPC 09 было всё же меньше, чем от Sapka (возможно потому, что Sapka была первым моим подобным контестом), однако море удовольствия от решения математических задачек я всё же получил. Будем надеяться, что в следующем году я тоже смогу поучаствовать.

О математике

За время контеста я получил(вывел сам, подсмотрел в Orbital Mechanics) множество формул. Здесь небольшой список, что было проделано(список не включает достижения остальных участников соревнования):









Кодовое имяОписание
hohmann delayПозволял найти время, которое нужно подождать на текущей орбите, чтобы при hohmann transfer на целевую орбиту попасть в нужную точку. Я выводил из равенства конечных углов, где конечные углы - функции времени. Этот hohmann delay не был использован в решении
phasingБыл подсмотрен в Orbital Mechanics и немного подправлен, чтобы была возможность совершать подстройку из любой точки орбиты, а не только из перигея. Вывод можно посмотреть в Orbital Mechanics
orbital equation v.1Позволял находить уравнение орбиты по двум точкам. Был выведен из системы двух уравнений орбиты в разных точках. Работал идеально на орбитах, apse line которых совпадала с осью абсцисс
orbital equation v.2К v.1 был добавлен еще один параметр - угол поворота орбиты. Параметры должны были находиться теперь уже по трём точкам. Решение искалось численно, потому что косинусы. Довести до ума так и не получилось, возможно, в моих предположениях была какая-то ошибка
orbital equation v.3Было использовано уравнение орбиты в векторах. Также должно было определять по трём точкам и находить угловой момент и вектор эксцентриситета. Не был доведен до ума, потому что см. ниже
orbital equation v.4Был подсмотрен в википедии в статье про кеплеровские орбиты. Вероятно, я где-то ошибся, но и эта формула выдавала неправильные результаты, хотя по этой же статье xa4a смог сделать рабочую версию
hohmann elliptic transferПочти то же самое, что и hohmann transfer, только без упрощений, возможных для круговых орбит. Вывод можно посмотреть в Orbital Mechanics. Было использовано для 3001-3004
elliptic phasingТо же самое, что и phasing, но для эллиптических орбит. Работало хуже, чем phasing, но работало для некоторых задач из 3001-3004. Вывод можно посмотреть в Orbital Mechanics
Smart chaseChasing maneuver по Orbital Mechanics. Работал не очень, использован не был

Wednesday, May 13, 2009

C++ 0x уже сегодня?

Вступление

С++ 0x - кодовое имя грядущего стандарта С++, который несет в себе огромное количество изменений. Если и до этого язык С++ был одним из самых нагруженных и сложных, то с приходом нового стандарта он может вообще быть погребен под собственной массой. Но случится ли это? Ответу на этот вопрос и посвящен данный пост.

Основная часть

На BoostCon было точно подмечено, что "С++ 0x" нужно читать как "C++ 0A","C++0B", etc, однако многое можно попробовать уже сейчас.
Для этого я собрал gcc из cxx0x-lambdas-branch, который, по-моему, сейчас максимально близок к C++0x (бранч периодически мержится с основной веткой, но в этом бранче полностью отстутствуют Concepts). О том, как собирать - смотрите ссылки ниже.
Итак, имеем:
$ bin/gcc --version
gcc (GCC) 4.5.0 20090421 (experimental)
Copyright (C) 2009 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
Попробуем что-нибудь написать:
#include <iostream>
#include <vector>
#include <algorithm>


int main()
{
std::vector<int> v = {1,2,3,4,5};
std::vector<std::pair<int,int>> v2;
std::transform(v.begin(),
v.end(),
std::back_inserter(v2),
[](int x){return std::pair<int,int>(x, x*x);});
for_each(v2.begin(),v2.end(),[](std::pair<int,int> x){std::cout<<"("<<x.first<<","<<x.second<<")";});
int s = 0;
for_each(v.begin(),v.end(),[&s](int x){s+=x;});
std::cout<<"\nResult:"<<s<<"\n";
// static_assert(false, "Dummy assertion!");
auto is_42 = [](int x) {return x == 42;};
auto answer = 42;
if (is_42(answer))
{
std::cout<<"Yes, it is!\n";
}
decltype(answer + 42) new_answer = 43;//?
std::cout<<"New Answer:"<<new_answer<<"\n";
}
Впечатляет? Присмотритесь внимательней, в этом примере: initializer lists(список инициализации для v), right angle brackets (две правые угловые скобки в определении v2), lambda(с захватом переменных и без), static_assert (закомментирован), auto (для простых случаев и для лямбда-выражений), decltype(для определения типов). Меня очень впечатлило. Несмотря на то, что в язык добавлены новые элементы, язык стал только выразительней, а никак не сложнее.
Таким образом, С++ вбирает в себя всё новые и новые идеи. Несложно заметить, что С++ 0x - огромный шаг поближе к Haskell. Кто считает, что это чепуха - присмотритесь к Variadic Templates:
template<unsigned... Args> struct mysum;
template<>
struct mysum<> {
static const int value = 0;
};

template<unsigned x, unsigned... Args>
struct mysum<x, Args...> {
static const int value = x + mysum<Args...>::value;
};

int main()
{
static_assert(mysum<10,20,11,1>::value==42, "Wow!");
}
Variadic Templates уже доступны, однако работают не полностью.

Выводы

С++ 0x - попытка скачкообразно осовременить С++. И, как мне кажется, эта попытка вполне может оказаться удачной.

Ссылки

Спасибо за внимание!

Monday, March 23, 2009

Sapka contest

Не так давно закончился контест Sapka, который проходил с 13-го по 20-е марта 2009 года. Я принимал в этом контесте участие и не могу не поделиться впечатлениями, ведь их было очень-очень-очень много.

Введение

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

Команда

Sapka и ICFPC - командные соревнования. Естественно, участвовать можно и одному, но для одного человека объем работы очень велик, да и вместе веселее. Поэтому очень важным является выбор команды, настройка средств коммуникации, распределение ролей и т.д.
Я до самого конца не был уверен, буду ли я участвовать в Sapka, поэтому команду я нашел лишь за день до соревнований, да и за день мы никак не готовились к участию. Как ни странно, но ничего страшного из-за этого не случилось, были и покрупней просчёты :) Итак, команда под названием "a" изначально состояла из трёх человек - Вашего покорного слуги, xa4a и A2K. Но у последнего участника под конец соревнования были завалы с учебой, поэтому написанием самого решения занимались всего два человека.

Начало соревнования

Оригинальное задание можно прочитать на сайте Sapka. Фан начинается уже здесь. Если кратко - то нам даётся некий сервер некой игры, в которую надо стучаться по телнету. Нужно написать клиента для этой игры. Всё! Никакого точного ТЗ, только упоминание о том, что сначала сервер нужно сконфигурировать. И вот с таким багажом знаний все участники и вступают в игру.
Лично для себя я всё время участия могу поделить на 3 этапа:

Этап 1. Хак сервера :)

То, что сервер написан на Java, и то, что защита там игрушечная, впоследствии позволило многим командам получить все нужные для конфигурации данные в течение первых 1-2х часов соревнования. Это также вызвало бурные дискуссии и недовольство тех, кто не смог сервер хакнуть. В гугл-группе даже жаловались, что из-за того, что в команде не было ни одного джависта, у них не получилось похачить сервер и поэтому они не смогли "заняться собственно программированием"(с). Для тех, кто все еще считает, что для взлома сервера обязательно нужны знания Java - следующий абзац.
Обладая минимальными знаниями Java и обладая к Java большой нелюбовью, я пересилил себя и приступил к "взлому" сервера. Вся процедура взлома заключалась вот в чём: разархивировать jar; увидеть, что там есть какой-то loader; натравить на него jad (найден в google по словам Java Decompiler); открыть Eclipse; запихать туда расшифрованный код; пройтись по коду и найти место, где происходит дешифрация; добавить запись в файл прямо там(код записи в файл был также найден в google ;));скомпилировать и использовать получившийся код для дешифрации файлов; после этого натравливать jad на дешифрованные файлы. Чтобы долго не лазить по обфусцированному коду, я взял и банально расшифровал самые большие файлы, которые были в архиве. И тут же налетел на нужные файлы - на описания логики игр. Чуть погодя(почему погодя - смотрите ниже) был написан и генератор конфигурационных токенов(простым копированием существующего кода). Вы всё еще считаете, что для взлома сервера нужно было знание Java? ;)
На самом деле, я занимался исследованием сервера намного дольше, чем это могло показаться. Во-первых, я вначале пытался достать конфигурационные токены прямо из памяти, но успеха не добился. Во-вторых, команда активно ковыряла квестовую часть Сапки, и я также принимал в этом участие.

Этап 2. Квест

Все конфигурационные токены можно было достать, пройдя текстовый квест, общаясь по telnet с сервером. Это было очень увлекательно, поэтому даже когда я уже достаточно продвинулся в процессе взлома, мы всё равно продолжали решать задачки. Так были найдены практически все токены, кроме DNA (сгенерировать токен оказалось намного проще, чем решить эту задачу). Также были подсмотрены в коде сервера секретные пароли, так что токены, которые они дают, также были получены путём хака.
В общем, описать квестовую часть практически невозможно - это было незабываемо! :) Внутри был Брейнфак, Forth-подобный язык, "шашки"(за них отдельное спасибо, я был просто поражен, когда обыграл его) + несколько задачек на преобразование текста. Я постарался не выдавать никаких секретов в описании, поэтому если вы не видели квеста - it's worth to try it out! Даже несмотря на то, что игра завершена, удовольствие вам гарантировано.

Этап 3. Программирование бота

После прохождения квеста стало ясно, что нам нужно написать клиент к bomberman-like игре. В качестве основного инструмента был выбран язык Python. Краткое описание процесса:
xa4a - написание парсера для сообщений от сервера
xa4a - создание визуализатора (на pygame)
tilarids(/me) - улучшение визуализатора
xa4a - создание keyboard controller
xa4a - рефакторинг, фикс багов, random AI
tilarids(/me) - добавлено избегание опасных мест
tilarids(/me) - добавление уничтожителя стен

Здесь небольшая врезка - кончился lightning раунд. На lightning раунд был отправлен бот, который не ставил бомб, а только убегал от опасностей. Причина - за убийство себя давали -1000 очков, а бот был страшен в своей наглости и часто себя убивал.
Дальнейшая разработка заключалась практически в улучшении, рефакторингом и пофиксах существующих алгоритмов.
xa4a - большой рефакторинг, добавлен нормальный механизм переключения состояний
tilarids(/me) - добавлен учёт времени взрыва бомб, простейшее начисление очков(в соответствии с идеей A2K), пофикс багов
xa4a - добавление охоты за бонусами, пофикс багов, рефакторинг бомб
tilarids(/me) - добавление охоты за противником
xa4a - завершение рефакторинга бомб, добавление учета подрыва бомбами друг друга, пофикс багов
tilarids(/me) - пофикс багов, пофикс учета коллапса мира, сабмит

На этом уже подошел к концу сам контест. Мы засабмитили бота, который умеет всё, что нужно для победы, но, к сожалению, он всё же не бессмертен и частенько умирает.
Краткое описание алгоритмов. Бот - простейший автомат, с такими состояниями как "беги", "ищи, куда поставить", "ставь", "охоться за бонусами", etc. Переход из одного состояния в другое был жестко зашит - никакой сложно логики выбора состояния не было - она была просто лишней. Для нахождения путей был применен волновой алгоритм, который учитывал опасности на пути. Для нахождения места, куда ставить, также использовался волновой алгоритм, на котором помечались цели с указанием очков за эти цели. После того, как алгоритм отрабатывал, выбиралась цель с набольшим количеством очков, такая, что если рядом с целью поставить бомбу, то мы сможем оттуда убежать(для проверки, можем ли мы убежать, также использовался волновой алгоритм). В случае, когда бомбу поставить не было возможности, включалась охота за бонусами.
Для тех, кто хочет посмотреть, как это выглядело:

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

Благодарности

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

Организаторам

  • Всё же сервер надо защищать лучше. Чтобы взлом сервера был отдельной трудной задачей, а не заменял прохождение квеста. Например, можно было бы некоторые задания составить так, чтобы понадобилось их решать программно в момент запуска клиента
  • Побольше бы заданий наподобие fifth. Задачки на преобразование текста были занятные, но по количеству фана намного менее содержательные
  • Я буду очень рад поучаствовать в Sapka 2010 ;)

Себе на заметку

  • Если желаешь выиграть, нужно пользоваться даже относительно нечестными методами. Если бы мы не тратили время на квест, когда уже были почти все токены, на лайтнинг можно было бы успеть отправить уже активного бота
  • Количество участников в подобных соревнованиях - не главное. Но хорошо, если есть участники, которые могут потратить время на поиск и исправление багов
  • Возможно, стоило попробовать переписать всё вообще без состояний, чтобы получить простого, как пробка, но зато бессмертного/безбажного бота. Но после драки кулаками не машут :)
  • Pygame - отличная платформа для визуализации чего-либо

Monday, March 2, 2009

Reia - скриптовый язык для виртуальной машины Erlang`а

Лично я считаю Erlang одним из самых простых яызков программирования, а среди знакомых мне функциональных языков - самым простым. К тому же на Erlang благодаря его направленности на создание конкурентных приложений написано уже множество проектов, таких как Yaws, CouchDB, ejabberd, которые являются для него наилучшей рекламой.
Таким образом, Erlang - функциональный язык с простым и понятным синтаксисом, который нашёл свою нишу, и если вы интересуетесь созданием масштабируемых конкурентных систем - вам стоит выучить его. Однако из-за того, что Erlang - функциональный, его синтаксис и стиль понятен не всем - он слишком отличается от императивных языков(таких как С и подобные) и даже от Ruby/Python, которые включают в себя частицы функционального подхода.
Если Вы столкнулись с такой проблемой - обратите внимание на Reia - скриптовый Ruby/Python like язык для виртуальной машины BEAM(эта виртуальная машина используется также и в Erlang). Язык Reia совместим с Erlang и может использоваться для создания конкурентых приложений, однако используя при этом скриптовый синтаксис. Вот простейший пример:

module Foo
def bar
receive
when msg
["Received ",msg].join().puts()
bar()
pid = Process.spawn(fun {Foo.bar()})
pid ! "Hello"
pid ! "World"
Результат:
Received Hello
Received World
В язык заложено очень много возможностей(как по мне - слишком много :) ): отсылка сообщений процессам и объектам, встроенные регулярные выражения, pattern matching, асинхронные вызовы функции, лямбда функции, а также многое-многое другое. Многое из этого не реализовано(например, циклы), но часть функциональности уже существует и работает, как можно увидеть из примера.

Выводы

  1. Reia - многообещающий ЯП, которому, однако, не хватает разработчиков. Возможно, если реализации будет уделяться больше времени, то этот ЯП станет мостиком, по которому толпы приверженцев императивного подхода ринутся в страну Erlang
  2. Как по мне, синтаксис Reia перегружен. Этот вывод только подкрепляет моё убеждение, что Erlang - отлично спроектирован и очень элегантен

Tuesday, February 10, 2009

Знакомьтесь: Geany!

Введение

Я уже писал, что мне очень нравится редактор SciTE и поэтому я его постоянно использую, например, при программировании на Python. Однако в GTK версии есть несколько недостатков:
  • Открытие большого числа вкладок невозможно - не работает прокрутка и multiline
  • Глюки с юникодом - если написать \что-то при редактировании TeX документа, получим несуразные символы. Эти же несуразные неудаляемые символы также иногда появляются в строке поиска
  • Нет нормальной интеграции с shell. В итоге для простейшей проверки конструкции в ipython приходится переключаться на терминал
Естественно, можно было бы подправить это в самом SciTE, но зачем, если всё уже сделано? Представляю вам Geany - простейший редактор с замашками IDE(которые, в принципе, не мешают :) ) основанный на том же движке, что и SciTE - на Scintilla.

На этом скриншоте он уже немного подконфигурирован для моего удобства. Возможности Geany:
  • Подсветка, фолдинг - аналогично SciTE
  • Нормальные табы
  • Поддержка VTE
  • Symbol explorer
  • Плагины(в числе встроенных FileBrowser, SplitWindow и т.д.)
  • Автодополнение по символам(неплохое, но для Python хотелось бы лучше. Geany - Open Source, так что возможно это желание будет реализовано)
  • Автозакрытие тегов
  • Сессии
Более подробно хотелось бы остановится на поддержке VTE. Благодаря ей в Geany есть полноценный терминал! Насколько это удобно можно понять, прочитав следующий раздел.

Конфигурирование

В этом разделе я хочу дать описание моего рабочего окружения в Geany. Оно не блещет уникальностью, но весьма удобно. Конечный внешний вид - на скриншоте выше. По пунктам:
  1. Ставим. Я просто выполнил "emerge -av geany". Думаю, в остальных Linux дистрибутивах его можно поставить сходным же образом. Для Windows пользователей - есть инсталляторы
  2. Убираем Sidebar, дабы сэкономить площадь
  3. Задаем комбинации клавиш для удобного перемещения по табам
  4. Настраиваем терминал - самая интересная часть. Я выбрал себе темную темку и запустил внутри screen - в итоге я могу переключаться между логами сервера, ipython и дополнительными консолями. Для меня терминал в Geany - самый важный инструмент. В нём я работаю с git и hg, в нём я отлаживаю приложение, в нём же я и лажу по файлам("geany file_name" открывает файл в новой вкладке). Таким образом, терминал мне заменяет File Browser, Debugger и VCS Inegration
  5. Настраиваем шрифт, остальные комбинации клавиш и интерфейс по вкусу
У меня в screen не заработала клавиша Backspace, пришлось биндить. Ниже - кусок конфигурационного файла screen (.screenrc), который делает screen юзабльным:
bindkey -d ^@ stuff ^? # пофикс backspace
hardstatus on
hardstatus alwayslastline
hardstatus string "%{Gk}| %-w%{+u}%n %t%{-}%+w |%=(%l) %d/%m %c"
До сих пор нормально не работает скролл на мышке, прокрутка вверх генерит "^[[A". Если у кого-то есть уже решение - поделитесь :) Если разберусь сам - проапдейчу.

Выводы

Geany - отличный редактор, полностью покрывающий мои запросы. На данный момент я использую его для Python разработки и редактирования TeX файлов. Для С++ же я предпочитаю IDE Anjuta, хоть Geany можно использовать и здесь.

Monday, January 12, 2009

C++: Как поймать опасные исключения

Существует множество мнений по поводу механизма исключений: некоторые называют исключения "скрытым goto", другие же считают исключения отличным механизмом и предлагают его использовать везде и всегда. Единственное, с чем согласны все - исключения нужно использовать с особой осторожностью. Ведь даже с виду совсем безобидный код может привести к тому, что ваше приложение упадёт в самый неподходящий момент.
С++, как многим известно, предоставляет некий механизм спецификации исключений - exceptions spectifications(п.15.4), простейший пример которого представлен ниже:

void foo() throw(Exception1, Exception2)
{
//...
}
В этом небольшом примере функцию foo описывают как функцию, которая может бросить исключения Exception1 и Exception2. Однако, как пишут в Boost Requirements and Guidelines:
The biggest problem with exception-specifications is that programmers use them as though they have the effect the programmer would like, instead of the effect they actually have.
или
Основная проблема со спецификацией исключений в том, что программисты используют их, как будто они работают так, как этого хочет программист, а не так, как они действуют на самом деле
Действительно, попробуйте в функции foo бросить исключение Exception3 и скомпилировать при помощи GCC(другие компиляторы я не использую, но думаю, что они действуют также). Ничего не произошло? И у меня то же самое :)
Т.е., спецификация исключений - вещь относительно бесполезная, а иногда и вредная(некоторые компиляторы не инлайнят функции с exception specifications). Существует много тредов-обсуждений в листе рассылки GCC по поводу возможности вывода предупреждений о несоответствующем спецификации использовании исключений(вот это сообщение - самое полезное, по-моему). В конце концов, подобные запросы отклоняются, ибо "невозможно реализовать из-за сложности межпроцедурного анализа. GCC не предназначен для такого".
Однако, это не остановило проект EDoc++, о котором и хотелось бы рассказать подробней. Он использует пропатченный GCC для анализа кода на ошибки при использовании исключений. Например, у нас есть код:
#include <iostream>
class C1{};
class C2{};

void foo() throw (C1)
{
throw C2();
};

class C
{
public:
~C()
{
foo();
}
};

int main()
{
C c;
}

В этом примере есть несколько ошибок, связанных с исключениями:
  • Не соблюдается спецификация в функции foo
  • Бросается исключение из деструктора
  • Исключение выходит за функцию main, что приводит к аварийному завершению программы
Попробуем проанализировать наш код с использованием EDoc++. Сначала EDoc++ надо собрать, потом проинициализировать окружение. В итоге мы получаем bash-оболочку с приглашением "EDOC ->". Я сохранил вышеприведенный С++ файл в ~/dev/sandbox/t.cpp. Компилируем(все дополнительные опции смотрите в документации к EDoc++):
EDOC -> g++ -fedoc-source -c ~/dev/sandbox/t.cpp -o ~/dev/sandbox/t.o
EDoc++ создает дополнительный файлик, который при опции -fedoc-source попадает в ~/dev/sandbox/t.cpp.edc. Показываем полученные результаты:
EDOC -> edoc --show-all --format simple ~/dev/sandbox/t.cpp.edc 
F: _GLOBAL__D__Z3foov()

F: _GLOBAL__I__Z3foov()

F: foo()

F: __static_initialization_and_destruction_0(int, int)

F: C::~C()

F: main()

ERROR(ECRASH_SPEC): Exception may propogate through restrictive specifier :The function: foo() can throw an exception of type: C2 that is not allowed by its specifier list: throws(C1)
Кажется, лучше сообщение об ошибке и не укажешь. Исправим ошибку - будем делать throw C1; вместо throw C2;. Перекомпилируем и посмотрим:
EDOC -> edoc --show-all --format simple ~/dev/sandbox/t.cpp.edc 
[...skip...]
ERROR(EMAIN_EXC): An exception may propogate out the main function. :The exception: C1 may propagate out the main function which may cause a program abort.

WARNING(WDESTR_EXC): An exception may propogate through a destructor. :Destructor: C::~C(), Exception: C1
Ага! Мы чуть-чуть не упустили исключение за пределы деструктора. Это ужасно. Уберём наконец throw С1; из foo для того чтобы проверить, как EDoc++ отреагирует на спецификацию без реального выбрасывания исключений:
EDOC -> edoc --show-all --format simple ~/dev/sandbox/t.cpp.edc
[...skip...]
Молчит. Т.е., он не принимает во внимание спецификации, если эти спецификации врут, что, в принципе, правильно.
EDoc++ обладает еще множеством достоинств: он поддерживает множество форматов вывода, множество способов хранения .edc информации, судя по отличной документации он правильно работает с указателями на функции, которые бросают исключения, и умеет находить ошибки даже в тех случаях, когда они делятся между несколькими модулями компиляции. В общем, отличный инструмент, спасибо создателям :)

Monday, December 22, 2008

Почему программисты должны писать документы в LaTeX

Хочу сразу написать, что в этом небольшом посте мне бы не хотелось рассказывать о преимуществах LaTeX в том виде, как это принято. Вы не найдете здесь похвал в адрес удобства использования, удобства редактирования, изменения оформления, набора формул, составления содержаний и списков литературы - всё это присуще LaTeX, но и упоминалось уже неприличное количество раз. Я бы хотел рассказать о тех забавных преимуществах, которые лично мне в LaTeX показались важными.
В процессе обучения в НАУ им. Н.Е. Жуковского "ХАИ" я дошел до момента, когда нужно писать бакалаврскую работу. Ничего особенного в этом нет, тема была выбрана, "исследования" проведены, программа уже написана. Осталось только написать пояснительную записку.
А это с незапамятных времен было для меня самым сложным. Еще участвуя в МАН, при написании курсовых работ и т.п. я заметил за собой жгучее нежелание писать текст. Это было скучно и неинтересно, не то что создавать программную реализацию.
Но недавно я открыл для себя LaTeX и все переменилось! Теперь я с удовольствием набираю текст, вставляю команды, "компилирую", правлю опечатки и пишу дальше. У меня даже появились "баги"(вызванные, вероятно, моим собственным недопониманием команд), которые я, ругаясь, фикшу. Написание скучного текста превратилось в увлекательнейший труд - вот вам причина, по которой программисту стоить писать документы в LaTeX!
Побочная причина - возможность хранения истории изменений в репозитории. Ведь когда пишешь документ, так и хочется закоммитить, чтобы увековечить свои изменения, а .tex файлы для этого подходят как нельзя лучше.


Напоследок хотелось бы дать несколько интересных ссылок
Также в качестве бесплатной рекламы - эти люди занимаются составлением руководств по верстке дипломов в LaTeX, честь им и хвала.Я собираюсь выложить в общий доступ мои наработки(классы, стили) как только пояснительная записка будет написана. Надеюсь, это окажется полезным для тех, чьи alma mater предъявляют схожие к моему требования.

Friday, November 21, 2008

О разделении труда, написании кейсов и их реализации

Прошедшая вчера встреча IT Talk натолкнула меня на интересные воспоминания. Я вспомнил предисловие к роману Джека Лондона "Сердца трёх". А точнее, заметил, что Лондон описывает в нем не только свою работу, но и современные реалии IT.
Предисловие к предисловию. Обычно процесс разработки состоит в преобразовании начальной идеи в кейсы-требования, которые потом преобразуются в код. Т.о., есть два вида работ - написание кейсов и написание кода. В последнее время существует множество мнений на тему, нужно ли написание кейсов:

  • кейсы писать не надо. Нужно, чтобы кодописатели хорошо представляли идею, тогда они сразу преобразуют ее в код
  • кейсы писать надо, они играют основную роль и для тестирования и для разработки
  • надо писать множество детальных кейсов, отдельно для тестирования, отдельно для разработки
  • кейсы писать нужно для коммуникации с заказчиком
  • и т.д., и т.п.
Мнения о том, кто должен выполнять эти работы:
  • Technical writers
  • QA, им потом это тестировать
  • Бизнес аналитик, так как его прямая обязанность - разбираться в начальной идее
  • Разработчики, так как они могут представить программный продукт
  • Отдельный случай - когда в команде нет особого разделения на роли и идеей проникнут каждый - тогда кейсы могут писать все.
Джек Лондон "Сердца Трёх", отрывки из предисловия с комментариями:
..Разделение труда - прежде всего. И вот, связавшись с могущественными газетными объединениями или с отдельными лицами, как это имело место в данном случае, - я имею в виду "Сердца трех", - они заказывают высококвалифицированным сценаристам (даже ради спасения собственной жизни не сумевшим бы написать роман) сценарий, который романисты (даже ради спасения собственной жизни не сумевшие бы написать сценарий) превращают затем в роман...
Комментарий 1. Встречаются люди, которые могут писать только сценарии или только романы. Не нужно заставлять их выполнять оба вида работ.
...Итак, мы работали параллельно, каждый над своим куском. Когда я писал какую-то главу, я, естественно, не мог принимать в расчет того, что происходит в следующей или через двенадцать глав, так как я этого не знал. Не знал этого и м-р Годдард. Отсюда неизбежные последствия: нельзя сказать, чтобы повествование в "Сердцах трех" отличалось особой последовательностью, хотя, оно, безусловно, не лишено логики...
Комментарий 2. И сценарист и романист работают в условиях, когда неизвестно, что будет дальше. Это нормально.
...Представьте себе мое изумление, когда я, будучи на Гавайях, вдруг получаю от м-ра Годдарда по почте из Нью-Йорка сценарий четырнадцатогоэпизода (я же в то время только еще трудился над литературной обработкой десятого эпизода) и вижу, что мой герой женат совсем не на той женщине! И в нашем распоряжении всего только один эпизод, когда можно избавиться от нее и связать моего героя узами законного брака с единственной женщиной, на которой он может и должен жениться. Как это сделано - прошу посмотреть в последней главе или пятнадцатом эпизоде. Можете не сомневаться, что м-р Годдард надоумил меня, как это сделать.
Комментарий 3. Сценарий обычно опережает роман по количеству эпизодов. Задача сценариста - стараться не допускать того, чтобы новые эпизоды влияли на старые.
Комментарий 4. К сценарию нужно относится со всей серьезностью. Если вдруг нужно что-то добавить в сценарий - нужно пытаться сделать это с минимальными изменениями в уже написанном, тогда роман тоже нужно будет минимально переписывать. Т.е., написание кейсов очень сходно с написанием кода. Вместо привычного "unit тесты -> код -> рефакторинг" при написании сценария нужно придерживаться сходного "проверка требования на удовлетворение какой-то части идеи -> написание требования -> рефакторинг"
...Дело в том, что м-р Годдард - мастер по части развития действия и гений по части быстроты. Развитие действия нимало не волнует его. "Изобразить", - спокойно указывает он в авторской ремарке киноактеру. Очевидно,актер "изображает", ибо м-р Годдард тут же начинает нагромождать однодействие на другое. "Изобразить горе!" - приказывает он, или "печаль",или "гнев", или "искреннее сочувствие", или "желание убить", или "стремление покончить жизнь самоубийством". Вот и все. Так и должно быть - иначе, когда же он завершил бы работу и написал свои тысячу триста сцен?
Но можете себе представить, каково пришлось мне, несчастному, который не мог ограничиться волшебным словом "изобразить", а должен был описать - и притом весьма подробно - все те настроения и положения, которые одним росчерком пера наметил м-р Годдард! Черт побери! Диккенсу не казалось чрезмерным излишеством потратить тысячу слов на описание и возможно более тонкую обрисовку горестных переживаний того или иного из своих героев. А вот м-р Годдард говорит: "Изобразить", - и рабы киноаппарата делают все, что нужно...
Комментарий 5. Сценарист не должен вдаваться в подробности. "Изображать" умеет романист, не надо отбирать у него хлеб.
Если в основе этой авантюры, именуемой "Сердца трех", лежит сотрудничество, я восхищен идеей сотрудничества. Но только - увы! - боюсь, что такого коллегу, как м-р Годдард, можно встретить не чаще, чем одного на миллион. Мы ни разу не перебросились даже словом, у нас не было ни одного спора, ни единой дискуссии. Но в таком случае я, должно быть, и сам - не коллега, а мечта! Разве я не позволил ему - без единого намека на жалобу или возражение - "изображать" все, что ему заблагорассудится, на протяжении 15 эпизодов сценария, 1300 сцен и 31000 футов пленки, а затем 111000 слов, составивших роман? И все-таки теперь, когда я кончил сей труд, я очень был бы рад, если бы не начинал его, - по одной простой причине: мне хотелось бы самому прочесть книгу и посмотреть, как она читается. А меня это очень интересует. Очень.
Комментарий 6. Сотрудничество подразумевает под собой профессионализм обеих сторон. Все вышеприведенные комментарии не рассматривают случаи, когда какая-то из сторон - непрофессиональна. Как по мне, глупо пытаться собрать хор из не имеющих слуха людей.
Комментарий 7. Сценарист и романист должны быть удовлетворены результатом. Именно не работой, а результатом.

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

Thursday, August 28, 2008

IPv6 не будет

Слегка адаптированная мной заметка по мотивам http://www.extremetech.com/article2/0,2845,2328258,00.asp:

Arbor Networks измерили объем IPv6 траффика, проходящего через 2400 бэкбонов и роутеров у 87 провайдеров Интернет по всему миру. Учет велся с Июня 2007 по Июль 2008 года. Полученные данные были использованы для исследования, которое компания считает наиболее всеохватывающим исследованием ситуации с IPv6 на сегодняшнее время. В целом Arbor отследил 15 экзабайт траффика - при этом все человеческое знание занимает 4 экзабайта, как заявляют представители компании.

Это исследование показало, насколько плачевна ситуация в стане IPv6. Если верить полученным данным, объем междоменного IPv6 траффика составил всего 0.0026% от объема IPv4 траффика. Были замечены два пика активности между 4 ноября и Рождеством 2007 года, на пике процентное соотношение поднялось до 0.012%. При этом, процент соответствия IPv6 и IPv4 траффика оставался неизменным за все время исследования.

Я уже писал о том, что такое IPv6 и насколько переход на него с устаревшего IPv4 важен. В действительности, если не будет существенных сдвигов в ближайшее время, то по некоторым оценкам уже к 2011 году IPv4 адреса закончатся и развитие сети Интернет остановится. Переход же на IPv6 даст возможность использовать 340 миллиардов миллиардов миллиардов миллиардов адресов, чего должно хватить на ближайшее будущее :)

"Я не думаю, что переход уже начался", - говорит Scott Iekel-Johnson, основной автор исследования и главный специалист по программному обеспечению в компании Arbor, -"Не похоже, что хотя бы в какой-нибудь значительной части из охваченных исследованием регионов были существенные сдвиги"
Как это ни дико, по заявлениям исследователей, один из пиков совпал с собранием рабочей группы проектирования Интернет (IETF) - одной из групп, которая яростно толкает индустрию к использованию IPv6 адресования. Во время собрания, как говорят представители Arbor, участников попросили выключить IPv4 функциональность на своих компьютерах и роутерах и проверить, какие сайты будут доступны. Чтобы протестировать инфраструктуру, они смотрят онлайн-видео, качают файлы больших объемов. Предполагается, что это и вызвало учтенный пик.

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

Исследователи видят два способа разрешения проблемы. Первый - поддержка идеи компаниями и государственными органами. Второй - проникновение идеи глубоко в массы. Iekel-Johnson делает ставку на первый вариант. Он приводит пример: "Если Comcast(ISP - прим. моё) скажет своим клиентам: 'Окей, вам нужно использовать IPv6, потому что у нас кончаются адреса, а мы хотим добавлять новых пользователей' - это приведет к существенным продвижениям".
Со своей стороны хочется добавить, что это исследование раскрыло мне глаза на то, насколько все плохо с IPv6. Возможно, понимание того, что мы еще в самом начале пути, подстегнет крупные компании, представителей государства и простых пользователей и продвижение пойдет быстрее.
Чтобы избежать обвинения в искажении фактов при адаптации я предлагаю поучаствовать в полном переводе статьи - сам я не смогу довести ее до читабельного вида без существенных правок. Поучаствовать и почитать текущий вариант перевода можно здесь

Friday, August 22, 2008

Использование Boost Python

“...one of the most highly regarded and expertly designed C++ library projects in the world.”
— Herb Sutter and Andrei Alexandrescu, C++ Coding Standards
Действительно, библиотека Boost - это живой пример того, насколько С++ может быть крут. И Boost.Python - не исключение.
Итак, Boost.Python - это библиотека, которая позволяет писать на С++ модули-расширения для Python, а также использовать возможности Python из С++. Зачем это может быть нужно? Например,
  • Переписывание bottlenecks на С/C++
  • Сокрытие части реализации в компилируемом модуле(весьма важно для распространениея коммерческих приложений)
  • Использование существующих библиотек(как на С/С++, так и на Python)
Конечно, можно использовать для решения этих задач Python C API, но, с одной стороны, С++ куда удобней для всего цикла разработки, а с другой - Boost.Python делает разработку на С++ настолько простой, что отказаться от нее невозможно.
Этим постом я не хочу повторять документацию по Boost.Python. Я ставлю целью скорее показать мощность Boost.Python и то, как он преобразует все вокруг :) И так как код - лучшая демонстрация, то я буду использовать фрагменты кода с пояснениями.
Итак, простейший модуль-расширение на С++:
#include <boost/python.hpp>
using namespace boost::python;
struct World
{
World(std::string msg_): msg(msg_) {}
std::string greet()
{
return msg;
}
std::string msg;
};
BOOST_PYTHON_MODULE(имя_модуля)
{
class_<World>("World", init<std::string>())
.def("greet", &World::greet)
;
}
Этот пример должен быть знаком тем, кто заглядывал в документацию. В нем ничего сложного нет - наш модуль включает в себя класс с конструктором и одной функцией. Предлагаю его взять в качестве основы и добавлять в него фрагменты ниже. Но сначала - как собирать этот пример. Предлагаю сохранить этот файл как имя_файла.cpp, после этого сборка может производиться при помощи gcc так:
gcc -shared -Wl,-soname,имя_модуля.so -o имя_модуля.so имя_файла.cpp -I /usr/include/python2.5/ -lboost_python
Обратите внимание, что имя_модуля должно совпадать с именем, указанным в файле. Также я использую python2.5. Тем, кто использует другую версию, нужно также поменять номер версии в пути для include.
Естественно, модуль не обязан состоять из одного файла, однако для сборки больших проектов рекомендую использовать distutils. Документация по нему достаточно подробная, чтобы собрать любой модуль. Самое главное - не забыть в описание Extension включить libraries=['boost_python'], а также указать то же имя Extension, что и внутри файлов используется.
После того, как простейший модуль собран и опробован,
In [1]: from имя_модуля import World
In [2]: w = World("Hello!")
In [3]: w.greet()
Out[3]: 'Hello!'
, можно приступать к самому интересному - к полезным обрывкам кода:
/*добавим две функции к World, "экспорт" их описывать не буду, можно по аналогии*/
void set(std::string msg) { this->msg = msg; }
void anotherWorldSet(World * world, std::string msg)
{
world->set(msg);
}
Проверяем:
In [1]: from hello_ext import World
In [2]: w1 = World("w1")
In [3]: w2 = World("w2")
In [4]: w1.anotherWorldSet(w2,"w2_new")
In [5]: w2.greet()
Out[5]: 'w2_new'
Т.е., Boost.Python прекрасно понимает, когда вы хотите получить объект по значению, а когда по ссылке. Более того, можно использовать и ссылки (void anotherWorldSet(World& world, std::string msg);) - разницы нет. Дальше перейдем к самому интересному - к boost::python::object. Это класс, который эмулирует работу Python объекта. Вот так, например:
void anotherObjectSet(object obj, std::string msg)
{
obj.attr("set")(msg);
}
И это работает, также как и предыдущий вариант. Обратите внимание на метод attr(). Его можно использовать как для вызова методов(см. выше), так и для получения значений:
std::string get_version()
{
/*Так импортятся Python модули. В качестве имени можно использовать и разделенные точкой названия*/
object sys = import("sys");
return extract<std::string>(sys.attr("version"));/*так преобразуются Python объекты в С++ объекты*/
}
std::string get_some(object myObj,std::string str)/*еще один пример*/
{
return extract<std::string>(myObj.attr(str.c_str()));
}
Раз уж зашла речь о Python объектах, то стоит рассказать о Python str и dict объектах:
dict foo_dict()
{
dict result;
result["1"]="2";
result["2"]="3";
return result;
}
object foo_string()
{
char buf[12]={0};
sprintf(buf,"%08XHELP",4242);
str s(buf,12);/*12 - длина строки*/
std::vector m;
m.push_back('1');m.push_back('2');m.push_back('3');m.push_back('4');
s += str(&m[0],m.size());
s += str("super test 2",12);
return s;
}
Т.е., работать с dict и str - одно удовольствие. Идем дальше, одна из пречудеснейших возможностей:
object get_func()
{
return make_function(&World::func);/*make_function - это чистая магия :)*/
}
std::string func()
{
return "I am func!";
}
Использование предыдущих фрагментов я не демонстрировал из Python, так как они очень просты. Представленный выше фрагмент ничуть не сложнее, но я все же покажу, как его использовать:
In [1]: from hello_ext import World
In [2]: w = World("Hello")
In [3]: f = w.get_func()
In [4]: f(w)
Out[4]: 'I am func!'
Обратите внимание на вызов f(w), здесь w - это self.
В общем, основные моменты я осветил. Многое еще можно найти в документации, во многом можно положиться на Boost.Python - он работает именно так, как вы от него ожидаете(например, C++ исключения транслируются в Python и т.д.).
Отдельно хочется упомянуть о нескольких важных вещах, которые могут привести к ошибкам:
  • В документации прекрасно описано наследование в Python от С++ классов. Однако, если вы переопределяете конструктор - обязательно вызывайте конструктор базового класса, даже если в базовом С++ классе он тривиален. Пренебрежение этим может вызвать непонятные ошибки
  • Если вы передаете Python объект по ссылке в С++ модуль, а потом сохраняете его там для дальнейшего использования - помните, что ссылка может стать невалидной - Python GC может и удалить его, если ссылка останется лишь в С++ части
Возможно, я буду обновлять этот список интересных моментов.
Ну, и на десерт. Если вы используете совместно С++ и Python модули (например, С++ модули используются для сокрытия функционала) и если вы используете логгирование, то скорее всего, вам захочется, чтобы логгирование всех модулей велось однотипно. Очень удобно было бы для этого использовать стандартный Python модуль logging. Чтобы было легче использовать этот модуль из С++, я написал небольшой класс:
/*----------------------------------------*/
/*logging.hpp*/
/*----------------------------------------*/
#pragma once
#include <boost/python.hpp>
#include <map>
#include <string>

class Logging
{
public:
static boost::python::object getLogger(const std::string& name);
static boost::python::object debug(const std::string& name);
static boost::python::object info(const std::string& name);
static boost::python::object warning(const std::string& name);
static boost::python::object error(const std::string& name);
static boost::python::object critical(const std::string& name);
static boost::python::object log(const std::string& name);

private:
typedef std::map<std::string,boost::python::object> LoggersMap;
static LoggersMap m_LoggersMap;
};
/*----------------------------------------*/
/*logging.cpp*/
/*----------------------------------------*/
#include "logging.hpp"

Logging::LoggersMap Logging::m_LoggersMap;

boost::python::object Logging::getLogger(const std::string& name)
{
static boost::python::object logging = boost::python::import("logging");
static boost::python::object settings = boost::python::import("conf.settings");/*Допустим, здесь хранятся настройки, в том числе и настройки логгирования*/

LoggersMap::iterator it = m_LoggersMap.find(name);
if(it != m_LoggersMap.end())
{
return (*it).second;
}
else
{
boost::python::object logger = logging.attr("getLogger")(name);
boost::python::object level = settings.attr("LOG_MODULES")[name];/*LOG_MODULES - dict, который ставит имя в соответствие с logging level*/
logger.attr("setLevel")(level);
m_LoggersMap[name] = logger;
return logger;
}
}

boost::python::object Logging::debug(const std::string& name)
{
return getLogger(name).attr("debug");
}

boost::python::object Logging::info(const std::string& name)
{
return getLogger(name).attr("info");
}

boost::python::object Logging::warning(const std::string& name)
{
return getLogger(name).attr("warning");
}

boost::python::object Logging::error(const std::string& name)
{
return getLogger(name).attr("error");
}

boost::python::object Logging::critical(const std::string& name)
{
return getLogger(name).attr("critical");
}

boost::python::object Logging::log(const std::string& name)
{
return getLogger(name).attr("log");
}
Использовать этот код очень просто:
Logging::getLogger("SomeLogger").attr("debug")("1.Logging stuff %s %s\n","1","2");
Logging::info("SomeLogger")("2.Logging stuff %s %s\n","1","2");
Logging::debug("SomeLogger2")("3.Logging stuff %s %s\n","1","2");
Logging::warning("SomeLogger")("4.Logging stuff %s %s\n","1","2");
Logging::error("SomeLogger2")("5.Logging stuff %s %s\n","1","2");
Logging::critical("SomeLogger2")("6.Logging stuff %s %s\n","1","2");

Спасибо за внимание! Буду рад любым исправлениям, корректировкам и дополнениям.

Tuesday, July 29, 2008

Совместное редактирование исходных текстов

Многие знают про технику парного программирования: это когда два программиста работают за одним компьютером, причем один набирает текст, а второй следит за ошибками и поправляет, периодически они меняются. Основной плюс данного подхода - в общении между членами команды (перечислять все преимущества не буду, читайте тут). С другой стороны, при таком подходе частенько хочется отобрать клавиатуру и написать быстренько самому, чем словами объяснять коллеге, что вы хотите.
Решений этой проблемы несколько. Некоторые стараются привнести идею парного программирования в обычную командную разработку, настаивая на регулярных мини-миттингах и "небольших" коммитах. Нельзя сказать, что этот способ плох, но все же он предполагает разделение задач между участниками команды.
В этой статье я хочу описать опыт использования инструмента для совместного редактирования кода Gobby - как по мне, это практически идеальное решение для парного программирования. Возможно, для кого-то из читателей это будет в новинку.
Итак, что такое Gobby - это бесплатный инструмент для совместного редактирования текста, который позволяет работать с несколькими документами одновременно, в котором есть чат и который работает во всех основных операционных системах (Linux, MacOS X, Windows, *nix). В действительности, Gobby - это просто редактор, который поддерживает технику парного(и более) программирования - только теперь вместо одной клавиатуры на всех у каждого программиста есть своя собственная.
Собственно об опыте использования: это невероятно! :) По пунктам:

  1. Еесли твой коллега находится далеко, то не нужно постоянно переключаться из окна IM мессенджера в окно редактора - все видно тут же.
  2. Смотреть, как появляется из ниоткуда исходный текст - это невероятно интересно!
  3. Очень удобно, что можно одновременно проверять работоспособность кода на разных машинах.
  4. Программистов может быть и не два, а больше, при этом так как вклад каждого отображается цветом, не запутаешься (в отличие от систем контроля версий, в которых выяснить, чья же это строчка кода, бывает трудно)
  5. Довольно удобный редактор с подсветкой синтаксиса без лишней функциональности
Из небольших неудобств - пока не нашел, можно ли поставить отображение курсора коллеги. Также стоит с небольшой грустью отметить, что под Windows есть некоторые проблемы с инсталляцией. Возможно, это единичный случай, но все же. Под Gentoo и Ubuntu все работает прекрасно, но так как множество разработчиков все же работает в Windows (по желанию или против оного :) ), то это может стать проблемой.
Скриншоты можно посмотреть здесь: http://gobby.0x539.de/trac/wiki/Screenshots
Чего не хватает: думаю, весьма полезен был бы централизованный сервер, на котором можно было бы любым желающим создавать сессии.
Аналоги: я не задавался целью найти что-нибудь аналогичное Gobby. Насколько мне известно, Eclipse поддерживает совместную работу. За любые указания на другие аналоги буду благодарен.

Wednesday, March 26, 2008

Собственные фильтры в админке django (Custom FilterSpecs)

Обновление от 04.05.2012. Данная статья была написана довольно давно, но до сих пор вызывает некоторый интерес. Спешу сообщить, что с 23-го марта 2012 года с релизом Django 1.4 начинать поиск информации про custom фильтры стоит с официальной документации

Админка django - одна из самых убойных фичей этого фреймворка, как признаются и сами авторы. Она позволяет автоматически подключить к вашему сайту функционал по добавлению, редактированию и изменению как встроенных, так и пользователских моделей. Конечно, если логика добавления и изменения информации слишком сложна, то эта админка не подходит, однако, это не означает, что ее не нужно использовать - она вполне может быть дополнением к существующему функционалу. Представьте, что создавая сайт-блог вы добавили функциональность, которая позволяет быстро создавать и редактировать записи. Но это не мешает вам использовать джанговскую админку, когда вам нужно изменить какие-то параметры записи, которые нельзя изменить иначе(подробней об админке можно прочитать в 6ой главе Djangobook)

Существуют также случаи, когда админка Django предоставляет практически весь функционал, который нужен на сайте. Например, если вам нужно приложение для внутреннего использования, которое показывает сохранённую в базе информацию по каким-нибудь событиям(пример из повседневной жизни :) ), то лучше встроенной админки не найдёшь - можно легко настроить, какие поля показывать, по каким полям вести поиск, по каким фильтровать - и всё это - лишь пара строчек кода!
Фильтры в админке - более чем удобная вещь. Например, если у вас есть поля, которые могут принимать значения из фиксированного набора(успех/не успех, номер ошибки, и т.д.), то фильтры позволяют быстро отфильтровать, например, все "успешные" записи, или все записи с упоминанием ошибки 302. Однако, может случиться, что стандартных наборов фильтров вам не хватит, и вы пожелаете добавить свой собственный.

Я постараюсь показать весь процесс добавления нового фильтра на весьма полезном примере - на фильтре, который позволит фильтровать записи по заданному промежутку времени. Например, если у вас есть поле "Время создания", то можно будет отфильтровать все записи, которые были созданы в промежутке между 25 марта 2008 года 00:00 и 26 марта 2008 года 15:00. Итак, начнём.

Все фильтры, которые есть в админке, расположены в django.contrib.admin.filterspecs, все фильтры являются наследниками FilterSpec, у которого есть два особо интересных метода - create и register. Новый фильтр нужно будет зарегистрировать, вызвав функцию FilterSpec.register(test,factory), где test - это функция, принимающая объект ..Field (фильтры создаются автоматически через интроспекцию существующих полей модели) и возвращающая True, если данный фильтр применим для данного поля, а factory - это обычно класс фильтра. Функция register() просто сохраняет эту пару во внутренний список. Функция create() вызывается, когда для какого-нибудь поля нужно создать фильтр - данная функция просматривает список, запускает test функции, и когда находит подходящий фильтр - использует factory для создания объекта и возвращает его. После объявления класса FilterSpec идут сами фильтры, которые сразу же и регистрируются.
Здесь следует важное замечание: фильтры добавляются в список append'ом, поэтому последний добавленный фильтр и будет при create вызван последним. А так как в уже рассмотренном файлике последним добавляется фильтр, который умеет фильтровать любые поля, что означает, что если мы зарегистрируем новый фильтр, то до него при create просто никогда не дойдёт очередь. Такое поведение мне не очень понятно(я привык, что последние добавленные обработчики обрабатываются первыми:) ), к тому же оно сводит на нет прямолинейные попытки добавить свой собственный фильтр.

Однако есть как минимум два способа обойти это недоразумение:
- Тикет #5883 содержит патч, который меняет порядок добавления. Он очень простой и вполне разумный. Я надеюсь, что когда-нибудь он войдёт в основную ветку :)
- Вместо register() можно вставлять нужную запись напрямую в список: FilterSpec.filter_specs.insert(-1, (test, factory))
Что использовать - ваш выбор. Я для себя выбрал путь патча, ибо хоть второй и не требует изменения кода django, однако он противоречит дзену :)

Разобравшись в том, как регистрировать фильтр, перейдём к тому, как он функционирует. Все фильтры рендерятся через шаблон filters.html (django/contrib/admin/templates/admin/filters.html). Для того, чтобы фильтр нормально отобразился, он должен уметь возвращать список опций выбора(choices), которые и будут отображены автоматически. Естественно, это не подходит для нашей цели(как вы помните, мы пытаемся сделать фильтрование по промежутку времени, для задания этого промежутка нам понадобится два текстовых поля), поэтому мы поменяем поведение шаблона(как подменить шаблон админки на свой можно прочитать всё в той же 6ой главе Djangobook). Текст шаблона filters.html ниже:

{% load admin_list %}
{% load i18n %}
{% load filter_tags %}
{% if cl.has_filters %}<div id="changelist-filter">
<h2>{% trans 'Filter' %} </h2>
{% for spec in cl.filter_specs %}
{% if spec.is_datetime_interval_filter %}
{% datetime_interval_filter cl spec %}
{% else%}
{% filter cl spec %}
{% endif %}
{% endfor %}</div>{% endif %}
Хочется обратить внимания на отличия от стандартного файла - подгружаются filter_tags - именно в нём у нас будет находиться inclusion tag datetime_interval_filter, который будет использоваться для всех фильтров, для которых is_datetime_interval_filter есть True(т.е., для нашего фильтра). Теперь посмотрим на новый тэг:
from django import template
register = template.Library()

@register.inclusion_tag('datetime_interval_filter.html')
def datetime_interval_filter(cl, spec):
return spec.get_output_dict(cl)
Ничего интересного в нём нет - он просто возвращает нужный для рендеринга контекст, оставляя процесс генерации его нашему объекту-наследнику FilterSpec(схожим образом действует и стандартный тэг filter). Как видно, он использует темплейт datetime_interval_filter.html - его текст ниже:
<script language='javascript'>
function set_new_location_{{field_name}}()
{
var lte = document.getElementById("{{field_name}}_lte_edit").value;
var gte = document.getElementById("{{field_name}}_gte_edit").value;
document.location.href = '{{query_str}}&{{field_name}}__gte='+gte+'&{{field_name}}__lte='+lte;
}
</script>
<h3>By {{field_title|escape}}:</h3>
<ul>
<li><input id="{{field_name}}_gte_edit" value="{{gte_old_value}}" /></li>
<li><input id="{{field_name}}_lte_edit" value="{{lte_old_value}}" /></li>
<li><a onClick='javascript:set_new_location_{{field_name}}();' style="cursor:pointer;">Filter</a></li>
</ul>
Что есть в темплейте - для каждого нашего фильтра создаётся небольшой скрипт, который займётся обработкой переходов на новую страницу с отфильтрованными данными. Также выводятся два текстовых поля и ссылка для перехода. Для того, чтобы корректно отрендерить этот темплейт, нужно передать:

field_name - имя поля, по которому будем фильтровать.
query_str - строка запроса, которая может содержать и другие значения фильтров.
field_title - название поля.
gte_old_value/lte_old_value - сохранённые значения текстовых полей. Выводятся в те же поля после применения фильтра, что очень удобно для редактирования.

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

Ну, и наконец, сам объект-фильтр:
from django.contrib.admin.filterspecs import FilterSpec
from django.utils.encoding import iri_to_uri

class DateFieldIntervalFilterSpec(FilterSpec):
def __init__(self, f, request, params, model):
super(DateFieldIntervalFilterSpec, self).__init__(f, request, params, model)

is_datetime_interval_filter = True

def get_output_dict(self,cl):
p = cl.params.copy()
return {
'field_name': self.field.name,
'query_str': iri_to_uri(cl.get_query_string(remove=["%s__lte"%self.field.name,"%s__gte"%self.field.name])),
'gte_old_value': p.get('%s__gte'%self.field.name,''),
'lte_old_value': p.get('%s__lte'%self.field.name,''),
'field_title':self.field.verbose_name
}
Небольшие пояснения по коду - как я уже говорил выше - мы наследуемся от FilterSpec. Конструктор не представляет никакого интереса. Флажок is_datetime_interval_filter мы уже упоминали - когда рассматривали темплейт filters.html. Единственная функция, которая требует рассмотрения - это get_output_dict(), которая возвращает словарь, используемый для рендеринга конечного html кода. field_name и field_title не представляют особого интереса - мы просто возвращаем имена поля, для которого работает фильтр. query_str мы получаем из объекта ChangeList - это основной объект, который содержит все фильтры, а также предоставляет доступ к нужным этим фильтрам параметрам(найти его можно в django.contrib.admin.views.main). В качестве параметров функции мы передаём список remove - в нём находятся те значения, которые возвращать не нужно, даже если они указаны. Это позволит нам избежать повторений вида &time__lte=smth1&time__lte=smth2. gte_old_value/lte_old_value мы получаем также из ChangeList - из текущих параметров.

После этого осталось зарегистрировать новый шаблон(для тестирования это можно сделать даже в Urlconf, хотя это и может вызвать некоторые проблемы при автоматической перезагрузке девелопмент сервера):
FilterSpec.register(lambda f: isinstance(f, models.DateField),DateFieldIntervalFilterSpec)
Хочу заметить, что я подменяю все DateTimeField(мне откровенно не нравится стандартный фильтр для DateTime), в то время, как можно добавить проверку на наличие у поля дополнительного атрибута, который добавлять только тем полям в модели, для которых нужен такой фильтр.

Ну, и конечно, хотелось бы посмотреть на результат. Вот скриншшот:На скриншоте - сохраненные Cdr events от Asterisk. Если как-нибудь будет время - я постараюсь осветить тот небольшой код, который позволяет сохранять евенты от Астериска в базе - это потрясающая иллюстрация возможностей Python, Django и Twisted.

Буду рад любым фидбекам и исправлениям. :)