GCJ(Google Code Jam) - контест по спортивному программированию, который проводит всем известная компания Google. Контест не командный, международный, проводится в онлайн. В этому году участвовал в первый раз, основные результаты таковы: остановился на втором раунде, в третий не прошёл.
Впечатления
Сумбурные. Участие в ICFPC и в Sapka рождает совсем другие эмоции. GCJ более напряженный, задачи значительно меньше по объему, но труднее, временные рамки куда жестче. Однако задачи GCJ отличаются и от тех, что встречаются на ACMовских олимпиадах. Большинство задач действительно имеют очень короткие и очень красивые решения, каждую из них действительно можно решить за отведенное время, если уловить какую-то важную мысль.
Выводы
Неожиданно для себя обнаружил доказательство тезиса "Разные ЯП - для разных задач". Решал задачи на Python(основной язык), Haskell и С++ - действительно, иногда тот или иной язык куда лучше подходил для решения определенной задачи
Фан можно получать и от простых задачек, не обязательно рулить спутниками или писать AI для bombermanа. Зря я почти забросил теорию - теперь сыплюсь на стандартных алгоритмах и мне очень стыдно
Нужно обязательно участвовать в следующих GCJ. Он совсем не напрягает и занимает куда меньше времени, чем многодневные командные состязания
Интересная ссылкa
Недавно мне подбросили ссылку на еще один контест - Hugi Size Coding Competition Series(hugi-compo), который кардинально отличается от всех, в которых я доселе участвовал. Именно этим он и привлекателен, хоть я и не обладаю достаточной квалификацией для удачных выступлений(контест посвящен ассемблерной оптимизации). Возможно, кого-нибудь заинтересует такое нестандартное соревнование. Спасибо за внимание!
Я всегда защищаю С++, когда приверженцы других языков ругают его за невыразительный синтаксис, чрезмерную сложность или раздутость, потому что, по-моему мнению, на С++ можно писать красиво, и особенно в этом помогают различные высокоуровневые конструкции из стандартной библиотеки. В одном из споров в c_plus_plus@c.j.r речь зашла о том, какой же из языков лучше - простой С или всё же С++? В качестве одного из аргументов я предложил провести эксперимент - сколько времени понадобится для решения простой задачи: из stdin считываются строки текста, и после этого в обратном порядке записываются в stdout, т.е., первая строка в stdin становится последней в stdout. Длина строк не ограничена, поэтому для решения ее на С понадобится выделять и перевыделять память, от этого код на С разбухнет, что станет наглядной демонстрацией превосходства высокоуровневых конструкций С++. Более того, я предположил, что код на С++ может быть даже производительней кода на С, написанного без дополнительного профилирования - ведь контейнеры С++ выделяют память так, чтобы reallocate происходил реже. Пример кода на С++, написан за пару минут для демонстрации:
int main() { std::vector<std::string> v; while(std::cin) { std::string s; std::getline(std::cin,s); v.push_back(s); } for (std::vector<std::string>::reverse_iterator it = v.rbegin();it!=v.rend();++it) { std::cout<<*it<<"\n"; } }
Как видите, код далеко не оптимален, однако мне хотелось показать, что даже такое решение лучше, чем код на С. Тут же захотелось проверить, а как другие языки справятся с этой задачей. Например,однострочник на Ruby:
$stdin.readlines.reverse.join.display
Когда я протестировал его на небольших файлах, С++ решение оказалось быстрее решения на Ruby в десятки раз, что меня нисколько не удивило. Однако для чистоты эксперимента я решил увеличить размер файла. Я сгенерировал файл в 100 строк общим размером ~600mb(исходник на Python):
Python 2.6.2 real 0m4.855s user 0m0.913s sys 0m1.233s
Т.е., еще быстрее, чем ruby (что уже не удивительно ;) ). Просмотрев код на С++, я добавил простейшую оптимизацию, которую изначально добавлять не хотел, чтобы код совсем не был похож на С. Я добавил хранение в векторе указателей, а не строк, что должно было убрать ненужное копирование:
int main() { std::vector<std::string*> v; while(std::cin) { std::string * s =new std::string(); std::getline(std::cin,*s); v.push_back(s); } for (std::vector<std::string*>::reverse_iterator it = v.rbegin();it!=v.rend();++it) { std::cout<<*(*it)<<"\n"; delete*it; } }
Но результат всё так же не вдохновляет:
real 0m46.444s user 0m43.462s sys 0m1.379s
Назначив ответственным за тормоза std::string, я попытался переписать всё на QString из Qt, которые, по слухам, умеют copy-on-write и вообще быстрые. Наивный код:
int main() { QList<QString> v; QTextStream st (stdin); QTextStream sto (stdout); while(!st.atEnd()) { v.push_back(st.readLine()); } QListIterator<QString> it(v); it.toBack (); while (it.hasPrevious ()) sto<<it.previous()<<"\n"; }
Однако это решение пожрало все 2 гигабайта моей оперативной памяти и я его остановил, попросив Qt-шников с c_plus_plus@c.j.r помочь с оптимизацией. После нескольких минут получился вот такой код, который использовал уже 1.4 гигабайта оперативки:
int main () { QList<QByteArray> v; QTextStream st (stdin); QTextStream sto (stdout); int line =0; while (!st.atEnd ()) { std::cerr <<"Reading line... "<< line++<< std::endl; v.push_back (qCompress (st.readLine ().toUtf8 (), 9)); } QListIterator<QByteArray> it (v); it.toBack (); while (it.hasPrevious ()) { std::cerr <<"Writing line... "<< std::endl; sto << qUncompress (it.previous ()) <<"\n"; sto.flush (); } }
Однако он работал еще медленнее, чем на стандартных строках - более двух минут. Для чистоты эксперимента я также написал вариант на Python, который не использовал стандартные join и reversed, а был более похож на код на С++:
importsys s = sys.stdin.readlines() for x inxrange(len(s)-1,-1,-1): sys.stdout.write(s[x]+'\n')
Его результаты:
real 0m2.198s user 0m0.884s sys 0m1.190s
Выводы
Если не учитывать опыты с Qt(всё равно ведь хороших результатов добиться не удалось), ни в одном из языков не было использовано каких-либо особых оптимизаций, напротив, были использованы те конструкции высокого уровня, которые предлагает сам язык. И удивительно, что программы на Python и Ruby смогли с большим отрывом обогнать аналогичную программу на С++. Я сам еще не знаю причину этого, и я был бы очень рад, если бы кто-то смог прогнать аналогичные тесты у себя на машине. Однако вне зависимости от причины, такой результат явственно говорит одно - нельзя безоговорочно верить в то, что С++ быстрее интерпретируемых языков, особенно если простейшие высокоуровневые конструкции в них, такие как строки, работают лучше.
P.S.
Я не старался создать идеальные условия для тестирования и не прогонял тесты сотни раз, чтобы получить идеальный результат. Достаточно всего-лишь заметить, что в этом синтетическом тесте Python был в 2-5 раз быстрее Ruby, а Ruby была в 4-5 раз быстрее С++. Спасибо за внимание!
int main() { std::ifstream fin("/dev/stdin"); std::vector<std::string*> v; while(fin) { std::string * s =new std::string(); std::getline(fin,*s); v.push_back(s); } for (std::vector<std::string*>::reverse_iterator it = v.rbegin();it!=v.rend();++it) { std::cout<<*(*it)<<"\n"; delete*it; } }
real 0m1.783s user 0m0.656s sys 0m1.070s
Т.е., тормозил std::cin. Естественно, это не оправдание, поэтому реабилитация только частичная. Вывод: tools don't kill software. people kill software.
Лучше поздно, чем никогда - предлагаю вам обещанную третью часть с описанием того, что есть LaTeX-beamer и как его можно использовать при написании бакалаврской работы. beamer - класс LaTeX, который позволяет быстро создавать красивые слайды. Если вы не знаете, что это такое или ни разу не пробовали - попробуйте, и вам больше никогда не захочется запускать громоздкие системы WISIWYG для создания слайдов. Основные достоинства beamer, на которые хотелось бы обратить внимание:
Полное разделение оформления и содержания. Сначала пишите текст, а оформление можно сменить в любой момент
Очевидный плюс, но забывать о нём нельзя: можно использовать все возможности LaTeX
Красивые и удобные темы оформления "из коробки"
Широкие возможности в настройке и доводке
Пример применения
Эта статья не задумывалась как учебное пособие по beamer, ее цель - дать представление и заинтересовать. Поэтому сразу перейдём к скриншотам и некоторым советам. Титульная страница, которую любезно сгенерирует вам beamer после заполнения некоторых полей: Один из слайдов: Как видите, слайды выглядят весьма привлекательно. К тому же, представьте, что каждый слайд - это всего пара строчек текста. А теперь, как я и обещал, несколько советов подкрепленные кодом:
Не пытайтесь изменить шрифт, чтобы вместить на слайд как можно больше информации. Выполненные в PowerPoint с 12pt шрифтом презентации навевают тоску и абсолютно нечитаемы с расстояния в 5-10 метров. Если уж очень нужно разместить на слайде побольше, а количества строк не хватает - используйте двухколоночную вёрстку. Тогда даже большое количество формул может поместиться на один слайд: Для верстки в две колонки используйте пакет multicol(на примере вставки изображений в две колонки):
Создатели тем оформления 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 тоже можно! Пример:
Этот код отводит отдельный слайд под видео. Стоит отметить, что видео можно будет проиграть только в Adobe Reader (я не знаю свободных альтернатив, которые бы поддерживали видео). Также обратите внимание, что я использую внешний плеер. Использование внешнего плеера гарантирует максимальную кросс-платформенность вашего PDF документа
Выводы
Используйте LaTeX, используйте beamer. Забудьте о медленных, неудобных офисных пакетах, полных недостатков и ошибок.
P.S.
Здесь вы можете найти исходники презентации (без изображений и видео)
Продолжая добрую традицию подробно описывать контесты, начатую с 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 часа контеста все участники прохлаждались :)
Слишком много версий заданий. Последние я даже не читал - надоело
Математика - это круто, и я не жалею, что участвовал в контесте, но всё же хотелось увидеть 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 chase
Chasing maneuver по Orbital Mechanics. Работал не очень, использован не был
Не так давно стараниями 42cc была выпущена версия 0.1 бэкенда к CouchDB для Django ORM. Доступ к нему можно получитьна github, также есть трак. Так как я принимал в этом проекте весьма деятельное участие, то мне бы хотелось рассказать про него поподробнее. Я не буду останавливаться на том, нужна или не нужна CouchDB. Вы можете прочитать об этом здесь или в google. Мне бы хотелось отметить один из недостатков CouchDB - он непривычен для людей, привыкших к реляционным базам данных, а следовательно, может показаться неудобным. Это и стало одной из причин разработки django-couchdb. Основная цель разработки - позволить описывать взаимодействие приложений на Django с CouchDB на знакомом "языке" - на языке Django ORM. Для поверхностного использования не понадобится даже знания о том, что такое CouchDB - достаточно прописать backend в DATABASE_ENGINE и использовать его. Простейшие примеры того, что умеет django-couchdb(в виде теста):
class Boo(models.Model): title = models.CharField(max_length=20) slug = models.SlugField() class Meta: unique_together = ('title', 'slug')
class Foo(models.Model): boo = models.ForeignKey(Boo) boo2 = models.ForeignKey(Boo, related_name="foo2_set")
А именно: работает генерация "схемы" из моделей, insert, update, delete, select, joins(не все). Не работает - ManyToManyField, aggregates. Поэтому django.contrib(например, admin) работает, но не полностью.
Перспективы развития
Дальнейшее развитие будет вестись в нескольких направлениях:
Исправление недостатков, поддержка других возможностей ORM
Развитие backend для использования сильных сторон CouchDB
Увеличение производительности
Выводы
Получился очень удобный инструмент, скрывающий особенности реализации (JS, HTTP запросы). Спасибо за внимание, ожидайте новые версии и новые возможности :)
В предыдущей статье было дано краткое видеоописание программного продукта, который появился в результате написания бакалаврской работы. Во второй части хотелось бы рассказать про вёрстку диплома в LaTeX - ведь именно она заняла большую часть времени, которое я потратил на диплом(в несколько раз больше, чем было затрачено на программу :( ). Для нетерпеливых сразу дам ссылку на конечный вариант (в формате PDF) - скачать(~800kb). Я уже как-то упоминал про LaTeX. С момента публикации той заметки, я занимался написанием и версткой диплома с использованием этого замечательного инструментария. Я не буду давать подробные описания, но хотелось бы отметить основные пункты. Cкачать исходные тексты можно здесь(~2mb).
Сборка
Для сборки я использовал scons. Рекомендую. Достаточно написать простейший Sconstruct файл:
После этого полная сборка выполняется командой scons или scons pdf.
Класс
Для написания диплома был использован видоизменённый rusthesis класс - я назвал его uadiplom. Многие изменения, связанные с требованиями моего ВУЗа были учтены в нём, однако многое было сделано отдельно - с использованием дополнительных пакетов.
Списки TODO
При написании диплома я пользовался замечательным пакетом todonotes, который и вам рекомендую попробовать. Для того, чтобы его использовать, понадобится:
\usepackage[paperwidth=210mm,paperheight=297mm,left=25mm,right=35mm,top=2cm,bottom=2cm]{geometry} % нужно оставить поле справа \usepackage[colorinlistoftodos, shadow, textwidth=3cm, textsize=tiny]{todonotes} % и установить размер пометок \usepackage{hyperref} % для ссылок \hypersetup{colorlinks=true, linkcolor=blue, citecolor=blue, filecolor=blue, urlcolor=blue}
Эти команды можно использовать прямо в тексте. Чтобы сгенерировать список TODO, достаточно вставить команду \listoftodos. Предлагаемые todonotes выглядят красиво и очень удобны.
Настройки заголовков
Одной из норм, которые приняты в моем ВУЗе, являются странноватые подписи к таблицам. А именно - подпись идёт сверху, в две строки, первая из которых - "Таблица ##" курсивом справа, а вторая - название таблицы жирным по центру. Для того, чтобы добиться этого, был использован пакет caption:
Был использован bibtex. Стиль - модифицированный gost780u (который я назвал uabib). Единственная модификация, которая понадобилась - изменение подхода к аббревиатурам.
Оформление рисунков
Для вставки рисунков были добавлены простенькие шорткаты:
Он принял такой вид, чтобы правильно обрабатывать разрывы страниц (с надписью "Продолжение таблицы ##" в правом верхнем углу). Назначение параметров можно понять по представленному коду.
Выводы
LaTeX можно и нужно использовать при написании текстов со сложной версткой. Он очень удобен и обладает неоспоримыми преимуществами, среди которых одним из важнейших является возможность каскадных изменений. Основные неудобства связаны с нежеланием ВУЗов переходить на использование LaTeX. Например, в моем случае пример титулки был выдан в виде .DOC файла(поэтому официальную титулку я делал в OpenOffice, в предложенном архиве - заглушка), а пример рамок для плакатов - вообще в формате Visio. Что уж сетовать на неточность требований и неквалифицированность нормоконтролёра. Также одним из недостатков LaTeX является его сложность в некоторых вещах по отношению к WYSIWIG редакторам(к примеру, вспомните таблицы). Этот недостаток уравновешивается тем, что квалифицированную помощь всегда можно найти, например, в комнате #latex на freenode. Спасибо за внимание! В следующей части я расскажу про использование beamer для создания презентаций.
Finally, my bachelor thesis has come to an end! And now I am going to publish the most interesting stuff I've done. Let me introduce you CamTrack, a simple OpenCV based tool that can be used to control your desktop using webcam. There is nothing breaking new in there (it is only a bachelor thesis and in Ukraine it is not something difficult). But I think, it can be a strong open source competitor to the CamSpace software.
You can find the source code on bitbucket. Or use direct link to download latest version. Don't hesitate to ask if you have any problems with installation.
If you're interested in this software or if you want to take part in it - please contact me.
Announcement for russian readers: I am also going to publish my thesis papers and give some suggestions about writing thesis using LaTeX. Stay tuned.
Предыдущий пост вызвал множество споров в pythonua@c.j.r на тему сложности синтаксиса С++ и сложности синтаксиса лямбд в частности. Действительно, в С++ 0x лямбды - это не one-line expressions, а полноценные анонимные функции. Именно поэтому синтаксис и так сложен. Например, возьмём Python и его лямбды. Так как синтаксис Python изначально минималистичен, то и лямбды в нём выглядят аккуратно и понятно. Однако, с другой стороны такая минималистичность может сыграть и злую шутку. Вот пример - не так давно поднимался вопрос о замыканиях в Python. Речь в этой статье шла о таком небольшом сниппете:
l =[] for i inrange(2): for j inrange(2): l.append(lambda: i + j)
При такой реализации замыкания не происходит - в l мы получим абсолютно одинаковые функции. Основной вывод вышеприведенной статьи - правильная реализация замыканий в Python - это:
def lsum(n, m): returnlambda: n + m
l =[] for i inrange(2): for j inrange(2): l.append(lsum(i, j))
Но что мы видим в этом коде? Вместо удобного inline использования - отдельная функция, которая отвлекает внимание и всё портит. Теперь вернёмся к С++ и посмотрим как в игру вступает один из синтаксических наворотов - capture list:
С++ 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.
intmain() { 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){returnstd::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<>{ staticconstint value =0; };
template<unsigned x,unsigned... Args> struct mysum<x, Args...>{ staticconstint value = x + mysum<Args...>::value; };
Что такое tddspry? Это небольшой набор утилит для тестирования django-приложений с помощью nosetests. Если по какой-то причине Вы не можете воспользоваться Django Test-execution Framework или джанговские тесты просто Вас раздражают, то обязательно обратите внимание на этот небольшой проект. На данный момент в состав tddspry включены хэлперы для написания тестов, а также моки для БД и twill. В дальнейшем возможно включение поддержки Windmill, etc. Проект открыт для предложений. :) Пример использования:
class TestUI(TwillMock, DbMock): def setup(self): super(TestUI,self).setup() login_to_admin(username='admin', password='admin')
Возможно, многие из читателей уже слышали о таком сервисе, как ItQuest.ru. А если не слышали - обязательно обратите на него внимание. Ресурс идейно схож с StackOverflow - большая база вопросов и ответов на IT тематику. Так что если у Вас есть вопрос, ответ на который не знает даже Google, попробуйте задать его здесь. P.S. Сайт написан на Django. Еще один повод присмотреться.
Не так давно закончился контест 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 - отличная платформа для визуализации чего-либо
Многие пользователи ПК пользуются всего двумя раскладками клавиатуры - для родного и для английского языка. Если Вы привыкли к использованию двух раскладок, то переход на использование трёх или более раскладок может быть очень болезненным: Вы будете случайно попадать не на ту раскладку, писать белиберду и страшно ругаться. Для того, чтобы облегчить себе жизнь с тремя и более раскладками(у меня английская, русская и украинская), я настроил такую схему переключения раскладок: левый Shift + левый Ctrl переключает между первой и второй раскладкой, а правый Shift + правый Ctrl переключает циклически все раскладки. Так как обычно я переключал раскладку левой рукой, то привычная комбинация введением новых раскладок нарушена не была, при этом сохранилась возможность перейти на любую добавленную раскладку. Основным источником информации для меня стал вот этот сайт. Ниже руководство для нетерпеливых :) Итак, первым делом скажу, что я не захотел полностью следовать советам с указанного выше сайта, так как предложенный там способ задания конфигурационных файлов предполагал редактирование xorg.conf, а также добавление собственных конфигурационных файлов в папки настроек Xorg. Таким образом, я пошел по пути наименьшего сопротивления и моё решение - "fast and dirty". В данном руководстве я предполагаю, что переключение раскладок по Shift + Ctrl уже настроено, все раскладки уже добавлены. Начнём с того, что получим текущую настройки XKB:
xkbcomp :0
, где :0 - id вашего X Display (скорее всего он у вас :0). Эта команда создаст файлик server-N.xkb , где N - указанный Вами id. Откройте этот файлик и найдите там описание символов ISO_Next_Group, ISO_Prev_Group, ISO_First_Group и ISO_Last_Group. У меня описания выглядят примерно так:
ISO_Next_Group, ISO_Prev_Group, ISO_First_Group и ISO_Last_Group - это специальные символы, которые как раз и отвечают за переключение раскладок. В варианте указанном выше ISO_Next_Group переключает на следующую раскладку, ISO_Prev_Group - на предыдущую, ISO_First_Group - на первую, а ISO_Last_Group - на вторую. Осталось переназначить клавиши, чтобы они указывали на другие символы. Дифф для трёх раскладок (для четырёх и более - добавятся новые группы):
Т.е, заменим для комбинации клавиши LFSH + LCTL символ ISO_Prev_Group на ISO_First_Group и ISO_Last_Group в зависимости от раскладки. После того, как Вы отредактировали файл, осталось залить настройки. Делается это так:
xkbcomp file.xkb :0
, где file.xkb - ваш сохранённый файл, а :0 - display id. Хочу отметить, что при перезагрузке иксов все ваши настройки сбросятся. Т.е., для того, чтобы настройки загружались при старте, их надо добавить в автозагрузку. Минус такого подхода в том, что если обновить X Server, то настройки могут стать несовместимыми и иксы могут зависать. Поэтому я просто добавил шорткат для применения настроек и запускаю его тогда, когда мне нужно. Еще один важный момент: xkbcomp перезаписывает все настройки. Т.о., если Вы переназначите какие-нибудь клавиши через xmodmap, то Вам нужно будет заново создавать файл настроек, иначе при применении настроек сделанные через xmodmap переназначения пропадут. Удачи с настройкой!
Лично я считаю 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, асинхронные вызовы функции, лямбда функции, а также многое-многое другое. Многое из этого не реализовано(например, циклы), но часть функциональности уже существует и работает, как можно увидеть из примера.
Выводы
Reia - многообещающий ЯП, которому, однако, не хватает разработчиков. Возможно, если реализации будет уделяться больше времени, то этот ЯП станет мостиком, по которому толпы приверженцев императивного подхода ринутся в страну Erlang
Как по мне, синтаксис Reia перегружен. Этот вывод только подкрепляет моё убеждение, что Erlang - отлично спроектирован и очень элегантен
Не далее как 24-го февраля сего года увидела свет новая версия одной незаменимой вещи для разработки под Google AppEngine, а именно app-engine-patch. Кажется, ничего особенного на этом скриншоте нет - всего лишь Django admin интерфейс. Однако, я не зря запостил этот скриншот - это админка Django запущенная под app-engine-patch! Теперь и под GAE можно получить эту "killer" feature Django. Об остальных нововведениях можно прочитать здесь. Меня особенно радует, что портировано django.contrib.sites, однако пока я не могу заставить django.contrib.sitemaps работать.
P.S. Еще два поинта, на которые я хотел бы указать. Во-первых, планы на будущее - "Native Django support (including Model class)."(с). Во-вторых, появилась некая тулза, которая пытается проверять импорты на правильность(кто сталкивался со страшными ошибками при случайных рекурсивных импортах - поймёт, насколько это хорошо :) )
Posts
