Продолжаю постепенно выкладывать на Google Code свои проекты.
На этот раз это эксперимент годовалой давности удаленное управление для Lego NXT через апплет, работающий на сотовом телефоне.
Назвал незамысловато nxtbtrc.
Все просто запускается на телефоне апплет, он спаривается с NXT и потом может посылать на него команды. В целом ничего сложного, просто было интересно разобраться как работать с синим зубом в апплетах.
Врядли я там чего еще буду модифицировать, но может кому и пригодится.
Даже книжку, помню, для этого специально купил. Хорошая, кстати, книжка. Все доступно и понятно о bluetooth с точки зрения программиста. Рассмотрены несколько стеков разных производителей, их сравнение и использование на разных языках и платформах.
Albert Huang, Larry Rudolph
Bluetooth Essentials for Programmers
Обновление: Небольшое видео, демонстрирующее все в работе:
Посты по теме:
среда, 24 июня 2009 г.
вторник, 23 июня 2009 г.
The Myth of the Genius Programmer
Лично разделяю каждое слово в данном видео. Удивительно как то, что пытаешься донести до людей сам каждый день, собрано в одном видео.
Кстати, вопросы в конце тоже весьма и весьма полезны для обдумывания.
Лично для себя вынес, что code review в большинстве случаев гораздо эффективнее парного программирования.
Есть у меня мысль заправить это видео на наш очередной пятничный образовательный просмотр.
Кстати, вопросы в конце тоже весьма и весьма полезны для обдумывания.
Лично для себя вынес, что code review в большинстве случаев гораздо эффективнее парного программирования.
Есть у меня мысль заправить это видео на наш очередной пятничный образовательный просмотр.
Ярлыки:
google
четверг, 18 июня 2009 г.
Как реализована сортировка в STL
Все началось с того, что я почему-то написал свою реализацию классического алгоритма быстрой сортировки QuickSort. И все бы хорошо, но я, конечно, решил померяться достоинством с STL'ой реализацией. Результат был очевиден, и я даже не хочу приводить цифры.
Вобщем, я открыл файл
Начнем с нестабильной сортировки
Видимо все эти ухищрения для уменьшения накладных расходов QuickSort на малых массивах.
Вот такая вот далеко непрямолинейная реализация.
Далее.
Стабильная сортировка
Частичая сортировка
Вывод:
Читать исходники очень интересно. Особенно хорошие исходники.
Вобщем, я открыл файл
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 процедура деления фрагмента на две части с использованием опорного элемента (цикл по перебрасыванию элементов, меньших опорного направо, а больших налево)
- начальный, опорный и последний элементы сортируются между собой (их всего три, так что тут это делается тремя последовательными
- затем вся процедура рекурсивно повторяется для левой и правой частей
1.5*log2(N)
, где N длина всего массива, то рекурсивные операции прекращаются. Если количество оставшихся недосортированных элементов меньше 32-х, то фрагмент досортируется методом вставки InsertionSort (этот метод имеет общую сложность O(N2) и для больших массивов не используется, но на малых длинах он быстрее всех из-за простоты). Если же остается более 32-х элементов, то досортировка происходит пирамидальным методом HeapSort в чистом его виде.Видимо все эти ухищрения для уменьшения накладных расходов QuickSort на малых массивах.
Вот такая вот далеко непрямолинейная реализация.
Далее.
Стабильная сортировка
std::stable_sort()
реализована алгоримом слияния MergeSort. Особых ухищрений по сравнению с чистным алгоритмом я не нашел. Разве что малые фрагменты (короче 32-х элементов) досортировываются методом вставки InsertionSort, как и в случае с QuickSort.Частичая сортировка
std::partial_sort()
реализована в чистом виде пирамидальным методом HeapSort.Вывод:
Читать исходники очень интересно. Особенно хорошие исходники.
Ярлыки:
сортировка,
эксперименты,
c++,
stl
пятница, 12 июня 2009 г.
Скрипты на Lua в С++
Lua отличный язык для встраеваемых сценариев. Продуманная структура языка, полный арсенал для процедурного и модульного программирования, а-ля функциональные возможности в виде функций-объектов и замыканий, работа со списками, кооперативная многопотоковость, зачатки объектно-ориентированности в достаточной мере для языка подобного рода, и вообще приятный синтаксис. Написан на стандартном С, поэтому отлично компилируется на разных платформах.
Есть великое множество оберток Lua для С++, но я не нашел ни одной, где не надо вообще вызывать С-шные функции Lua вручную из основной программы. Также для создания новых функций на С++, которые можно будет вызывать из Lua, должен быть только С++'ый подход.
Моя идея была в создании чисто плюсого интерфейса для Lua с максимально простой интеграцией в рабочий проект.
То, что пока вышло называется luascript.
Для включения в свой проект надо скопировать библиотеку в подкаталог
После этого можно писать вот такие куски кода:
Если надо добавить свою функцию, например, для проверки существования файла, можно написать так:
В каталоге
Сборка.
Пока я проверял только в Студии 2008. Тестовый проект включает в себя библиотеку, lua 5.1.4, Google Test 1.3.0 и несколько тестов, чтобы почувствовать вкус библиотеки. Все в одном флаконе.
Те, у кого есть SCons, могут собрать, набрав
Общие замечания.
Забавно, в этих исходниках я попытался в качестве эксперимента максимально работать по стандарту кодирования Google. Из основного, что затронуло лично меня, это:
Данный проект не такой сухой как ранее выложенный SerialCom. Я с ним более менее активно работаю, так что должны быть точно улучшения. На работе, например, я его примастырил для гибко сконфирурированного фильтрования при журналировании. Есть, конечно, проблемы с производительностью (интерпретатор, все-таки, хоть и с виртуальной машиной), но есть пути улучшения.
Посты и ссылки по теме:
Есть великое множество оберток 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 символов.
- В именах закрытых членов класса использовать не "__" в качестве префикса, а "_" в качестве суффикса.
Данный проект не такой сухой как ранее выложенный SerialCom. Я с ним более менее активно работаю, так что должны быть точно улучшения. На работе, например, я его примастырил для гибко сконфирурированного фильтрования при журналировании. Есть, конечно, проблемы с производительностью (интерпретатор, все-таки, хоть и с виртуальной машиной), но есть пути улучшения.
Посты и ссылки по теме:
Ярлыки:
библиотека,
проекты,
эксперименты,
c++,
lua
воскресенье, 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, так как первое уже занято. Но это так, ерунда.
Лично мне пока все нравится. Будем искать проблемы, а то без них как-то пресно.
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.
Посты по теме:
Весьма занимательное видео, рассказывающее некоторые подробности о внедрении Mercurial на Google Code. Почему именно Mercurial, а не Git или Bazaar, какие особенности именно у Mercurial, отличающие от конкурентов (я, например, не знал, в Mercurial хеш-идентификатор каждого коммита задействует не только метаданные, но и само содержимое файлов, что конкретно ограничивает возможности "переписывания" истории, хотя с точки зрения гугловцев это преимущество, нежели недостаток), и, собственно, как все это легло в инфраструктуру Google.
Посты по теме:
понедельник, 1 июня 2009 г.
Обучение программированию на Лиспе
Вспоминая, как учили программированию меня, и как я сам потом учил программированию, сейчас я уверенно подошел к мысли, что учить с нуля просто необходимо на функциональных языках. Чтобы далеко не бегать - на любом из диалектов Лиспа.
Например, в школе, когда юный мозг так податлив и нежен, ничто так не уродует его как Бейсик, Рапира, Фокал, Лого или что-то там еще есть из разряда "простых языков для начинающих". Лисп же совершенно без навязывания угловатых конструций типа циклов, условий, да вообще "программных строк" так таковых помогает сходу въехать в краеугольные темы типа рекурсии, списков, деревьев и т.д., которые так тяжело даются пониманию потом, когда в голове уже сидят классы, процедуры, функции с циклами впридачу. В Лиспе же можно без нудного прогружения в замыслование механизмы языке сходу переходить к делу - к структурам данных и алгоритмам. И получается, что их изучение идет параллельно с изучением языка программирования, а не с огромным запозданием. А это очень полезно для формирования правильного программерского мышления.
И пусть человек стопудово потом придет к обычным языкам, но его мозг уже будет иметь иммунитет на порой угловатые рамки любой императивщины. Сделать переход от функционального языка с императивному просто, а порой даже приятно, а вот наоборот - увы.
Например, в школе, когда юный мозг так податлив и нежен, ничто так не уродует его как Бейсик, Рапира, Фокал, Лого или что-то там еще есть из разряда "простых языков для начинающих". Лисп же совершенно без навязывания угловатых конструций типа циклов, условий, да вообще "программных строк" так таковых помогает сходу въехать в краеугольные темы типа рекурсии, списков, деревьев и т.д., которые так тяжело даются пониманию потом, когда в голове уже сидят классы, процедуры, функции с циклами впридачу. В Лиспе же можно без нудного прогружения в замыслование механизмы языке сходу переходить к делу - к структурам данных и алгоритмам. И получается, что их изучение идет параллельно с изучением языка программирования, а не с огромным запозданием. А это очень полезно для формирования правильного программерского мышления.
И пусть человек стопудово потом придет к обычным языкам, но его мозг уже будет иметь иммунитет на порой угловатые рамки любой императивщины. Сделать переход от функционального языка с императивному просто, а порой даже приятно, а вот наоборот - увы.
Ярлыки:
мысли
Подписаться на:
Сообщения (Atom)