*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

среда, 24 июня 2009 г.

Lego NXT remote control via bluetooth

Продолжаю постепенно выкладывать на Google Code свои проекты.

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

Назвал незамысловато — nxtbtrc.

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

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

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

Albert Huang, Larry Rudolph
Bluetooth Essentials for Programmers



Обновление: Небольшое видео, демонстрирующее все в работе:




Посты по теме:

вторник, 23 июня 2009 г.

The Myth of the Genius Programmer

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



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

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

Есть у меня мысль заправить это видео на наш очередной пятничный образовательный просмотр.

четверг, 18 июня 2009 г.

Как реализована сортировка в STL

Все началось с того, что я почему-то написал свою реализацию классического алгоритма быстрой сортировки QuickSort. И все бы хорошо, но я, конечно, решил померяться достоинством с STL'ой реализацией. Результат был очевиден, и я даже не хочу приводить цифры.

Вобщем, я открыл файл algorithm из STL'я в Visual Studio 2008 и часок покопался в нем. Вот результаты моих "исследований".

Начнем с нестабильной сортировки std::sort().
  • основа: алгоритм быстрой сортировки QuickSort (почти как у меня)
  • выбор опорного элемента — центральный по индексу элемент в сортируемом фрагменте
  • после каждого выбора опорного элемента:
    • начальный, опорный и последний элементы сортируются между собой (их всего три, так что тут это делается тремя последовательными if'ами)
    • если длина сортируемого фрагмента менее более 40, то отрезок делится 8 частeй (длина каждой части S = 1/8*N) и для троиц элементов (1, S, 2*S), (N/2 - S, N/2, N/2 + S) и (N - 2*S, N - S, N) делается такая же минисортировка, как и на предыдущем шаге (где число элементов было меньше 40)
    • далее происходит обычная для QuickSort процедура деления фрагмента на две части с использованием опорного элемента (цикл по перебрасыванию элементов, меньших опорного направо, а больших — налево)
  • затем вся процедура рекурсивно повторяется для левой и правой частей
Количество рекурсивных операций не идет до победного конца, как в чистом QuickSort. Если количество итераций (процедур разделения массива) превысило 1.5*log2(N), где N длина всего массива, то рекурсивные операции прекращаются. Если количество оставшихся недосортированных элементов меньше 32-х, то фрагмент досортируется методом вставки InsertionSort (этот метод имеет общую сложность O(N2) и для больших массивов не используется, но на малых длинах он быстрее всех из-за простоты). Если же остается более 32-х элементов, то досортировка происходит пирамидальным методом HeapSort в чистом его виде.

Видимо все эти ухищрения для уменьшения накладных расходов QuickSort на малых массивах.

Вот такая вот далеко непрямолинейная реализация.

Далее.

Стабильная сортировка std::stable_sort() реализована алгоримом слияния MergeSort. Особых ухищрений по сравнению с чистным алгоритмом я не нашел. Разве что малые фрагменты (короче 32-х элементов) досортировываются методом вставки InsertionSort, как и в случае с QuickSort.

Частичая сортировка std::partial_sort() реализована в чистом виде пирамидальным методом HeapSort.

Вывод:
Читать исходники очень интересно. Особенно хорошие исходники.

пятница, 12 июня 2009 г.

Скрипты на Lua в С++

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

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

Моя идея была в создании чисто плюсого интерфейса для Lua с максимально простой интеграцией в рабочий проект.

То, что пока вышло называется luascript.

Для включения в свой проект надо скопировать библиотеку в подкаталог luascript/ и добавить в проект два файла: luascript/luascript.cpp и luascript/lua/lua-files.c.

После этого можно писать вот такие куски кода:
lua script;
script.set_variable<lua::string_arg_t>("a", "test");
script.exec("b = a .. '123';");
std::cout << script.get_variable<lua::string_arg_t>("b").value());
Данный простой скрипт принимает строку через переменню a, добавляет к ней "123" и записывает результат в переменную b, которая потом подхватывается из С++.

Если надо добавить свою функцию, например, для проверки существования файла, можно написать так:
class file_exists_func_t {
public:
// Регистрируем аргументы функции. В данном случае один аргумент типа "строка".
static const lua::args_t* in_args() {
lua::args_t* args = new lua::args_t();
args->add(new lua::string_arg_t());
return args;
}

// Регистрируем выходные параметры. В данном случае это просто bool.
// Фукнция в Lua может возвращать не только одно значение, а несколько,
// поэтому можно задать список типов выходных параметров.
static const lua::args_t* out_args() {
lua::args_t* args = new lua::args_t();
args->add(new lua::bool_arg_t());
return args;
}

// Задаем namespace и, собственно, имя фукнции.
// Получается "fs.file_exits()".
static const std::string ns() { return "fs"; }
static const std::string name() { return "file_exists"; }

// Данный метод вычисляет значение функции.
// Сначала надо разобрать входные параметры, вычислить функцию и
// положить результы с массив выходных значений. Правильность
// работы с типами аргументов, выходных данных и индексов в массивах,
// их описывающих, лежит на плечах автора функции.
static void calc(const lua::args_t& in, lua::args_t& out) {
std::string filename = dynamic_cast<lua::string_arg_t&>(*in[0]).value();
std::ifstream is(filename.c_str());
dynamic_cast<lua::bool_arg_t&>(*out[0]).value() = is.good();
}
};
...
try {
// Создаем исполнителя скрипта.
lua script;
// Регистрируем нашу функцию "fs.file_exists()".
script.register_function< file_exists_func_t >();
// Устанавливаем переменную "fname" в "readme.txt".
script.set_variable<lua::string_arg_t>("fname", "readme.txt");
// Вызываем скрипт.
script.exec("exists = fs.file_exists(fname);");
// Получаем результат через переменную "exists".
bool exists = script.get_variable<lua::bool_arg_t>("exists").value();
} catch (lua::exception& e) {
std::cerr << "error: " << e.error() << ", line " << e.line();
}
Что пока не поддерживается, так это параметры типа таблица (хеш) для передачи их в функцию и получения их в качестве результата.

В каталоге lib лежат несколько мини примеров на Lua. Например, вот так можно вызвать внешнюю функцию для base64 кодирования или декодирования:
lua script;
script.exec("package.path = package.path .. ';./lib/?.lua'");
script.exec("require('base64'); a = base64.encode('test');");
// Данный пример напечатает "dGVzdA==".
std::cout << script.get_variable<lua::string_arg_t>("a").value();
Исходники доступны для просмотра в онлайне, или через Mercurial.

Сборка.

Пока я проверял только в Студии 2008. Тестовый проект включает в себя библиотеку, lua 5.1.4, Google Test 1.3.0 и несколько тестов, чтобы почувствовать вкус библиотеки. Все в одном флаконе.

Те, у кого есть SCons, могут собрать, набрав scons -Q. У кого нет, могут запустить скрипт compile-vs2008.cmd. Собранный runner для тестов luascript_unittest_vs2008.exe должен работать без ошибок. Посмотрев сами тесты в файле luascript_unittest.cpp можно в целом понять, как работать с библиотекой. Документация, конечно, будет, но пока так.

Общие замечания.

Забавно, в этих исходниках я попытался в качестве эксперимента максимально работать по стандарту кодирования Google. Из основного, что затронуло лично меня, это:
  • Отступ в 2 пробела (естественно, никаких табов). Для слов "public", "protected", "private" отступ в один пробел.
  • Максимальная экономия вертикального места (по возможности не лепить лишних пустых строк).
  • Открывающая скобка "{" практически всегда на той же строке (для классов, функций, циклов, условий и т.д.). Я раньше так не делал для классов и функций.
  • Никаких cast'ов в стиле С, даже для элементарных типов. Только приведения в стиле С++. Мне это очень нравится.
  • Забота о длинных строках. Как только можно избегать строк длинее 80 символов.
  • В именах закрытых членов класса использовать не "__" в качестве префикса, а "_" в качестве суффикса.
Это был снова эксперимент на Google Code и в opensource'e в целом. Если честно, то выкладывание исходников на публику страшно оздоравливает код, причем по всем статьям.

Данный проект не такой сухой как ранее выложенный SerialCom. Я с ним более менее активно работаю, так что должны быть точно улучшения. На работе, например, я его примастырил для гибко сконфирурированного фильтрования при журналировании. Есть, конечно, проблемы с производительностью (интерпретатор, все-таки, хоть и с виртуальной машиной), но есть пути улучшения.


Посты и ссылки по теме:

воскресенье, 7 июня 2009 г.

Хостинг на Google Code: SerialCom

В качестве эксперимента перенес один из своих старых проектов на Google Code. Очень хотелось пощупать хостинг Mercurial.

SerialCom — программа для ковыряния в потоковых протоколах. Умеет работать с компортом, быть TCP/IP клиентом или сервером. Умеет удобно отображать и посылать шестнадцатеричные дампы. В довершение — проста как валенок.

Вобщем, когда-то мне нужна программа для удобной отладки устройства на PIC'е, с которым надо было работать по RS232. Ничего готового, подходящего мне по всем параметрам, я тогда не нашел, поэтому написал свою. Благо борландовые продукты располагают к пятиминутным двухкликовым проектам. Через некоторое время добавил работу с TCP/IP. Отлично подходит для возни с протоколами.

Проект очень прост. Кругом VCL и удобная компонента для работы с портом. Но это и обратная сторона медали — компилируется только в C++ Builder'е, причем из-за гениальной архитектуры компонент в VCL для сборки без допиливания нужен билдер именно версии 6.0. Использование более поздних сред потребует танцев по установки обновленной версии компортовой компоненты.

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

Что понравилось.

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

Удобно, что сходу в довесок к хостингу получаешь возможность создать группу для обсуждений по проекту, привязку к единой статистике посещаемости сайта Google Analytics (просто надо UA указать), механизм code review и баг трекер впридачу. Хорошо не то, что все эти, в целом, обычные примочки есть, а хорошо, что они все связаны и даются одним кликом.

Что не понравилось.

Пришлось изменить оригинальное имя с SmartCom на SerialCom, так как первое уже занято. Но это так, ерунда.

Лично мне пока все нравится. Будем искать проблемы, а то без них как-то пресно.

суббота, 6 июня 2009 г.

Архитектура Mercurial на Google Code

После Google I/O Mercurial стал доступен на Google Code в публичном доступе наравне с Subversion.

Весьма занимательное видео, рассказывающее некоторые подробности о внедрении Mercurial на Google Code. Почему именно Mercurial, а не Git или Bazaar, какие особенности именно у Mercurial, отличающие от конкурентов (я, например, не знал, в Mercurial хеш-идентификатор каждого коммита задействует не только метаданные, но и само содержимое файлов, что конкретно ограничивает возможности "переписывания" истории, хотя с точки зрения гугловцев это преимущество, нежели недостаток), и, собственно, как все это легло в инфраструктуру Google.




Посты по теме:

понедельник, 1 июня 2009 г.

Обучение программированию на Лиспе

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

Например, в школе, когда юный мозг так податлив и нежен, ничто так не уродует его как Бейсик, Рапира, Фокал, Лого или что-то там еще есть из разряда "простых языков для начинающих". Лисп же совершенно без навязывания угловатых конструций типа циклов, условий, да вообще "программных строк" так таковых помогает сходу въехать в краеугольные темы типа рекурсии, списков, деревьев и т.д., которые так тяжело даются пониманию потом, когда в голове уже сидят классы, процедуры, функции с циклами впридачу. В Лиспе же можно без нудного прогружения в замыслование механизмы языке сходу переходить к делу - к структурам данных и алгоритмам. И получается, что их изучение идет параллельно с изучением языка программирования, а не с огромным запозданием. А это очень полезно для формирования правильного программерского мышления.

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