вторник, 24 февраля 2009 г.

Как получить hardware id. Исходники DiskID32 на Delphi

Потребовалось защитить приложение, написанное на Delphi, от копирования. Точнее, потребовалось обеспечить возможность привязывать приложение к конкретному компьютеру, на котором оно устанавливается.

Чтобы "привязать" программу к компьютеру, необходимо уметь генерировать уникальный идентификатор для его "железа" - hardware id. По hardware id генерируется серийный номер, который будет работать только на заданному компьютере. Такой подход активно используется для защиты ПО, хотя для пользователей он порой не слишком удобен - при апгрейде компьютера серийный номер может перестать работать.

Вопрос - как сгенерировать hardware id?

Изучение интернета показало, что имеется три основных варианта.
  1. Использовать MAC-адрес сетевой карты.
  2. Использовать информацию из WMI.
  3. Использовать серийный номер жесткого диска, на котором установлена операционная система.
Недостатки использования MAC-адреса описаны здесь:
  • Сетевых карт может быть несколько.
  • При включении bluetooth/wi-fi появляется новая "сетевая карта".
  • При отключенном сетевом проводе MAC-адрес не определяется.
Недостатки WMI:
  • В Me/2000/XP эта служба встроена, но в более ранних версиях Windows ее нужно доставлять.
  • Под Vista, с включенным UAC, без прав администратора доступ к WMI не получить.
  • Cлужба WMI может быть отключена.
  • Получение информации из WMI - очень медленный процесс. Несколько секунд задержки при запуске гарантированы.
Вариант с серийным номером жесткого диска - хорош. Тем более, что есть программа DiskID32, с открытыми исходными кодами, которая позволяет получать серийный номер жесткого диска в любых версиях Windows (от 9X до 64-bit), причем как при наличии прав администратора, так и при их отсутствии. Бери и пользуйся.

Беда только в том, что у нас приложение написано на Delphi. Значит и процедура получения hardware id нужна на Delphi (вариант с DLL не подходит). А DiskID32 написан на С++...

Делать нечего. Вооружился отладчиком и перевел исходные коды DiskID32 с C++ на Delphi. Основные проблемы, с которыми столкнулся: в Delphi нет битовый полей (они использовались при описании ряда структур) и нет полноценной адресной арифметики. К счастью, битовые поля оказались не принципиальны и я их просто отбросил. Операции над указателями (инкремент, декремент) заменил на аналогичные операции с массивами. Не слишком изящно, но работает. Код старался транслировать один в один, ничего не удаляя. Оригинальные исходники DiskID содержат код для определения MAC-адресов сетевых карт. В моем случае MAC-адрес не требовался, поэтому эти функции я не транслировал.

Код был протестирован на Windows XP, Vista, Server 2003 (с рейдом и без), а так же под Vista 64-bit. Под 9x код не тестировался, поэтому гарантий, что он заработает, нет никаких. Если вы найдете ошибку в коде - пожалуйста, сообщите мне о ней на email, указанный в исходных кодах.

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

Скачать исходные коды DiskID32 for Delphi.

Update: В первой версии исходных кодов нашлась ошибка, см. комментарии. Исправил ее и, заодно, перевел проект на Delphi 2010 (совместимость с Delphi 7 сохранена):

Скачать исходные коды DiskID32 for Delphi 2010.

Download source codes of DiskId32 for Delphi.
Download source codes of DiskId32 for Delphi (updated 16.01.2012)

View source codes of DiskId32 for Delphi.
Short description in English.

P.s. если вы не хотите, чтобы diskID выводил информацию на консоль, закомментируйте
макрос {$DEFINE PRINTING_TO_CONSOLE_ALLOWED}. В таком виде исходники пригодны для использования в неконсольных приложениях.

Update: Под x64 нет crtdll.dll. Вместо нее следует использовать msvcrt.dll. Т.е. в crtdll_wrapper объявить crt-функции следующим образом:
function crt_isspace(ch: Integer): Integer; cdecl; external 'msvcrt.dll' name 'isspace';
function crt_isalpha(ch: Integer): Integer; cdecl; external 'msvcrt.dll' name 'isalpha';
function crt_tolower(ch: Integer): Integer; cdecl; external 'msvcrt.dll' name 'tolower';
function crt_isprint(ch: Integer): Integer; cdecl; external 'msvcrt.dll' name 'isprint';
function crt_isalnum(ch: Integer): Integer; cdecl; external 'msvcrt.dll' name 'isalnum';
Библиотека crtdll.dll нужна только если требуется совместимость с win95.

Update: август 2013: Прислали на email обновление: "1. Сделал рабочей ReadIdeDriveAsScsiDriveInNT - char/ansichar ошибка; 2. Избавился от msvcrt.dll (переписал функции на дельфи); 3. Немного оптимизации." Обновленную версию следует брать в svn.

понедельник, 23 февраля 2009 г.

Чай. Как заваривать и где покупать.

Несколько лет назад я побывал в Китае. С тех пор, все мои вкусы и привычки, касающиеся чая, изменились координально.

До поездки в Китай я считал, что существует два типа чая: черный и зеленый. Я пил только черный - зеленый мне не нравился принципиально. Когда я приехал в Пекин, то быстро выяснилось, что альтернативы зеленому чаю нет. Либо пьешь зеленый, либо не пьешь никакой. Поэтому в первый же день я сходил в магазин, купил пачку чая за 60 юаней (240 рублей) и мы стали заваривать его по вечерам прямо в стаканах (заварочного чайника у нас не было ни в одном отеле). Когда через две недели я вернулся домой, то НИКАКОЙ другой чай я уже пить не хотел :)

Довольно быстро выяснилось, что пили мы вовсе не зеленый чай, а улунский, oolong, что означает "черный дракон". От черного и зеленого он отличается степенью окисления. При изготовлении зеленого чая окисление не используется вообще, черные чаи окислены на 100%, а улуны - с серединки на половинку, на 10-70%. (Подробно о процессе окисления и о шести возможных видах чаев: зеленый, желтый, белый, улун, черный, и пуэр, - можно прочитать здесь). Улуны сразу полюбились мне больше всего и даже сейчас, когда я попробовал множество других видов чая, я предпочитаю именно их.

Второй важный момент, который я выяснил в Китае - как правильно заваривать чай. Оказывается всю жизнь я заваривал его не правильно. Насыпаешь заварки в заварочный чайник, завариваешь кипятком, ждешь пока настоится, наливаешь заварки на четверть чашки, доливаешь кипятка... Заварку используешь несколько раз, несколько дней... кто на что горазд.

На чайной церемонии в Китае нам рассказали, как заваривать чай правильно. Нужно положить листья чая в чайник. Залить кипятком и дать настояться. Недолго - 5-10 секунд (У разных чаев время первой заварки может существенно различаться. Лично я его всегда определяю экспериментально. Если чай получается горький, просто уменьшаю время). Далее чай разливается по чашкам. При этом воду из чайника нужно выливать полностью, листья чая ни в коем случае не должны оставаться в воде. Это - принципиальный момент. Как говорят китайцы, если вы оставите листья чая в воде, то на следующий день этим чаем можно будет очень хорошо мыть ноги (полезно для кожи), но пить его будет невозможно.

Одну и ту же заварку можно использовать 4-5 раз. Вторая и третья заварка - самые лучшие. Чай получается наиболее вкусным и насыщенным. Китайцы утверждают, что первую заварку вообще выливают. Ее цель - дать листьям размокнуть. Но для меня такой подход не рентабелен, поэтому я его не практикую.

Китайцы заваривают чай во френч-прессах. Для китайского метода заварки чая он подходит идеально.

Естественно, просто так в магазине чай не продают. Вернее то, что продают у нас в магазинах, это совсем не тот чай. Настоящий китайский чай продают в Китае и покупать его нужно именно там. (Пара магазинов с настоящим китайскием чаем у нас в Красноярске есть, но цены там очень высокие).

К счастью, в наше время это не проблема - чай легко покупается через Интернет. Лично я несколько лет покупаю чай на сайте www.teaspring.com.

Здесь продают множество различных видов чаев, в том числе, зеленые, улуны и черные. Черные чаи я заказывал дважды, на пробу и оба раза они мне не понравились. Зато улуны там великолепные. Yong Chun Fo Shou, Dong Ding Oolong, Huang Jin Gui, Tie Guan Yin, Gui Hua Oolong, Feng Huang Dan Cong - любой из этих чаев я могу смело порекомендовать. Стоят они правда недешево. Самый недорогой (но очень достойный чай) Yong Chun Fo Shou - $8 за 100 г, остальные по $11, $15, $20 и т.п. При выборе обратите внимание, что цены на сайте для разных чаев указаны за разное количество грамм.

Оплата заказов - кредитной карточкой. На этом сайте при оплате карточкой требуется указывать код CVV, так что подходит подавляющее большинство карточек, даже обычные карты ВТБ24. Но я для интернет платежей давно уже завел специальную карточку в Промсвязьбанке - ей можно рассчитываться без указания CVV (например, на www.cabelas.com), у нее нет никаких дурацких ограничений в 500 долларов в месяц и стоит она всего $4 в год. Подобные карты есть и в других банках.

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

Сумма заказа должна быть более $70 - тогда доставка почтой бесплатная, при меньшей стоимости доставка стоит $3.8. Общая сумма посылки должна быть менее 10 тыс руб, а еще лучше - менее 5 тыс, иначе могут начаться неприятности с таможней (ранее я уже писал об этой проблеме). Следует иметь в виду, что в период 7 дней можно получить не более одной посылки из-за границы - при покупке в разных интернет магазинах одновременно это ограничение надо учитывать.

Посылка доставляется обычно в течении 3х недель - в наш Красноярск она идет окольными путями, через Москву. Если заказывать на новогодние праздники, то посылка может идти месяц и больше. Я стараюсь не заказывать слишком большие посылки, т.к. при превышении определенного веса (кажется 1.5 кг) посылки начинают идти как-то по другому, получать их приходится не в почтовом отделении, а на ж/д вокзале и идут они в два раза дольше.

На сайте есть система бонусов - поинтов. При покупке на $100 вы получаете бонусы на $10 - эти бонусы можно использовать в виде скидки при следующей покупке. Дополнительные бонусы можно зарабатывать, если писать на сайте отзывы о купленном чае.

Конечно, есть и другие сайты, на которых продается чай. Например, перечисленные здесь:Но сам, лично, я их пока не проверял.

"Чай" из пакетиков я теперь пить совсем не могу. В связи с кризисом придется, видимо, думать о том, чтобы перейти с чая на обычную воду :)

Update 2011: топик в блоге Экслера на тему чая - народ накидал ряд полезных ссылок на магазины.

пятница, 20 февраля 2009 г.

В помощь начинающему писателю.

"Комиссия в детском саду спрашивает заведующую:
- Скажите, почему у вас дети так странно говорят: "пришедши", "ушедши"?
- Да они у нас так привыкши..."

Грамотная речь всегда понятнее, чем безграмотная. Как научиться грамотно и доступно излагать свои мысли? Основные приемы известны.

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

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

Добавлено:

среда, 18 февраля 2009 г.

О пользе LinkedIn

Прислали ссылку на интересную статью How to Close $100,000 in Business With LinkedIn Using 4 Quick Steps. О том, какую пользу может принести участие в LinkedIn.

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

P.s. LinkedIn - социальная сеть для поиска и установления деловых контактов. Сеть ориентирована на IT-специалистов.

вторник, 17 февраля 2009 г.

Модель-представление-контроллер. Раз модель, два модель.

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

Я с такой задачей столкнулся при разработке программы, в которой главное окно способно отображать множество различных видов. Окно разделено на две части. Слева - панель, аналогичная Navigation Pane, справа - вид. Один из видов - это графический редактор с нарисованными объектами. Если выбрать этот вид, то слева на панели будет дополнительно выведен полный список объектов. Объекты можно выделять мышкой как в редакторе, так и в списке объектов. Вопрос - где хранить состояние выделенности объектов? Эта информация интересна только для двух представлений: редактора и списка объектов. Ни к модели, ни к вычислительному процессу, ни к другим видам она не имеет отношения.

Попробуем разобраться. Для начала напомню, вкратце, что такое паттер "Model-View-Controller", он же "Модель-Представление-Контроллер", он же MVC.

Паттерн MVC разделяет приложение на три части: обработка данных, вывод и ввод. В модели хранятся данные и реализуется их обработка. Данные в модели представлены в том виде, в котором их удобно обрабатывать (а вовсе не в том, в котором удобно отображать). Модель совершенно не зависит от представления данных в интерфейсе пользователя. Интерфейсом занимаются представления. Они считывают данные из модели, приводят в требуемый вид и отображают пользователю. Если данные нужно показывать разными способами, представлений будет несколько.

Каждое представление, по идее, имеет связанный с ним контроллер. Контроллер занимается обработкой ввода данных. Он принимает разнообразные события, поступающие от мышки и с клавиатуры, и транслирует их в команды для представления или модели. При этом контроллер вовсе не является "посредником" между моделью и представлением. Единственная функция контроллера - это обработка ввода данных. Представление может свободно обращаться к модели напрямую, контроллер для этого вовсе не требуется.

Поскольку представлений несколько, необходимо позаботиться о синхронизации изменений. Если контроллер одного представления изменяет модель, то все остальные представления должны быть поставлены об этом в известность. Т.е. в моделе необходим механизм подписки на рассылку уведомлений. Изменились данные, модель послала уведомление, все заинтересованные лица его получили - и обновились.

Вот, собственно, и вся архитектура. Осталось заметить, что контроллер нужен далеко не всегда. Разделение "контроллер-представление" нужно вводить только тогда, когда оно действительно требуется. Если их не разделять, то получается частный случай архитектуры MVC, называемый Document-View. Document - это модель, View - это представление + контроллер.

Возвращаемся к вопросу о хранении информации о состоянии выделенности объектов. Варианты:
  • Ввести дополнительное свойство у объекта - флаг "выделен"/"не выделен". Это простейшее решение, но тогда в модели мы будем хранить данные, которые связаны только с представлением - это плохо. А если таких данных нам будет требоваться со временем все больше и больше? И что делать, если у нас подобных представлений "с состоянием" будет несколько и каждому потребуются подобные флаги?
  • Хранить данные прямо в представлении. Хорошая идея, но в каком из двух? Предположим, мы храним информацию о состоянии в представлении A, а представление B знает об этом и берет ее из A. Сразу появляется проблема синхронизации. Если мы изменили состояние выделенности объекта в A, как об этом узнает B?
Мне кажется ответ на поверхности - нужно ввести вторую модель.

Другими словами, я предлагаю применить шаблон дважды. Представления A и B будут работать с двумя моделями. Первая модель глобальная, с ней работают все представления в программе. Вторая модель локальная, к ней имеют доступ только представления A и B. Эта локальная модель хранит состояние отображения данных в A и B и отвечает за синхронизацию при изменении этого состояния. Кроме того, локальная модель должна быть подписана на получение сообщений от глобальной модели. Если, например, объект будет уничтожен, то наша локальная модель об этом узнает и удалит информацию о его отображении. Появится новый объект - она добавит для него информацию по умолчанию.

В программе такая локальная модель может выглядеть как объект, который хранится в главном окне программы, передается в конструкторы представлений A и B и регистрируется, наравне со всеми представлениями, для получения уведомлений от глобальной модели.

Вот как будет выглядеть схема MVC с двумя моделями.Теперь осталось реализовать идею на практике и посмотреть, насколько удобно будет работать, и какие недостатки вылезут. Поживем - увидим.

P.s. Информацию по паттерну MVC можно найти в книжке
Мартин Фаулер "Архитектура корпоративных программных приложений", 2004 год. У Фаулера книжки интересные и очень полезные, но конкретно эту, лично мне, читать было довольно сложно. Бесконечные перекрестные ссылки на паттерны здорово запутывают. Далее, на сайте у Фаулера есть статья GUI Architectures, написанная примерно в том же стиле. Там рассказывается и про MVC, и про MVP. Но лично мне больше всего понравилось, как тема MVC изложена в книге, которую Фаулер рекомендует: Frank Buschmann "Pattern-oriented software architecture. A system of patterns. Volume 1", 2001. Написано и проще, и подробнее.

воскресенье, 15 февраля 2009 г.

Ловим исключения

Вот еще интересный пример, который встретился также в тесте по С++
struct BaseException {
virtual void Output() {
std::cout << "Base" << std::endl; }
};
struct DerivedException : public BaseException{
virtual void Output() {
std::cout << "Derived" << std::endl; }
};
void Test() {
try {
throw DerivedException();
} catch (BaseException& e) {
e.Output();
} catch (DerivedException& e) {
e.Output();
} catch (...) {
std::cout << "Unhandled exception" << std::endl;
}
};

Вопрос стандартный: какой catch сработает и что будет выведено на печать? Ответ: срабатывает первый catch, на печать будет выведено "Derived".

Теперь чуть-чуть изменим код

} catch (BaseException e) {
И на печать будет выведено уже "Base". Рассчитано, конечно, на невнимательность. Я, когда проходил тест, больше задумывался, попадет ли DerivedException в catch с BaseException. Оказалось, что попадет. А на тонкость с "&" я бы внимание вообще не обратил, если бы (так уж вышло) мне не встретилось практически подряд два "одинаковых" вопроса.

template Run(T process); Что бы это значило?

При прохождении теста по С++ столкнулся вот с такой конструкцией
template Run(T process); 
В тесте спрашивается, что именно эта конструкция может означать: нешаблонную функцию-член класса, определение шаблонной функции, объявление шаблонной функции, определение шаблонного класса, объявление шаблонного класса?

Поначалу решил - ошибка. Разве есть конструкции со словом template без скобочек? Но в памяти что-то смутно зашевелилось :) Полез в справочник по шаблонам (есть такая замечательная книжка - Дэвид Вандевурд, Николаи М. Джосаттис, "Шаблоны С++", 2003 год). И нашел такую конструкцию. Называется - директива явного инстанцирования (стр. 87). Сравните:
template int const& max(int const&, int const&);
Это - явное инстанцирование шаблона функции max() для int. Таким образом, "template Run(T process);" может означать следующее: явное инстанцирование шаблона функции Run, принимающего один параметр типа T и возвращающего int.

C неявным int, правда, есть проблема. Стандарт С++ не поддерживает default int. В частности, в Visual C++ 2005 при попытке откомпилировать объявления функции, в которой не указан возвращаемый тип, мы получаем ошибку C4430: "missing type specifier - int assumed. Note: C++ does not support default-int". В более ранних версиях компилятора такие конструкции были разрешены. Ошибку можно исключить с помощью pragma, поэтому следующий код компилируется на ура:

typedef int T;
template<class T1>
int Run(T1 process) {
return 1;}
#pragma warning(disable: 4430)
template Run(T process);
#pragma warning(default: 4430)
Осталось ответить на вопрос теста. Собственно, выбирать остается между вариантами 2 и 3. В справочнике написано следующее: "Директива явного инстанцирования содержит ключевое слово template, за которым следует объявление объекта, экземпляр которого необходимо сгенерировать, с полностью выполненными подстановками". Так что похоже правильный ответ на вопрос - 3. Это - объявление шаблонной функции. Правда, как видите, с небольшими оговорками.

пятница, 13 февраля 2009 г.

Функциональные адаптеры C++.

Любой программист С++ при написании кода стремится достичь, как минимум, трех целей: сделать код производительным, наглядным и максимально компактным. Активное использование алгоритмов STL здесь может существенно помочь. Если алгоритм выбран правильно, то в большинстве случаев он выполнит задачу быстрее, чем самописный код. Использование алгоритмов вместо обычных циклов повышает наглядность кода, поскольку алгоритмы в тексте программы гораздо более четко отражают намерения программиста, чем однотипные циклы for. Возможность "налету" генерировать объекты функций и передавать их в алгоритмы в качестве предикатов обеспечивает коду компактность.

С предикатами в C++ все не так просто. По большому счету - предикат, это функция, возвращающая тип bool. Поэтому в качестве предикатов в алгоритмы можно передавать указатели на обычные функции. Однако, объекты функций гораздо предпочтительнее. Причина проста - объекты функций обеспечивают более эффективный код. В книге Скотта Мейерса на этот случай приводится пример с функцией std::sort - использование объектов функций всегда работает быстрее, выигрыш в скорости может составлять от 50% до 160%. Объясняется все тривиально - при использовании объекта функции компилятор способен встроить передаваемую функцию в тело алгоритма, а при использовании обычной функции встраивания не производится.

Но с объектам функций тоже все не просто! Прежде всего, из-за огромного количества вариантов подобных объектов, которые встречаются на практике. Может потребоваться вызов обычной функции или функции-члена класса. Алгоритм может требовать бинарную или унарную функцию. Подходящая для наших целей функция может требовать передачи дополнительных параметров. Объект, которому принадлежит функция, может быть константым или не константым. Аргументы в функцию могут передаваться по значению или по ссылке. Функция может быть реализована в класее. Наконец, требуемую функциональность могут реализовывать ни одна, а несколько разных функций, так что потребуется как-то скомбинировать их вызовы в одном функциональном объекте.

Впрочем, разработчики STL были прекрасно осведомлены обо всех этих сложностях. В состав STL включен отдельный файл <functional>, содержащий массу функциональных адаптеров, позволяющих "налету" создавать подходящие объекты функций в самых разнообразных случаях. Дело за малым - осталось разобраться какие адаптеры когда применять.

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

std::vector<int> t;
bool f(int Value) {
  return Value == 2;
}
std::vector<int>::iterator p =
  std::find_if(t.begin(), t.end(), f); //находим 2

тот же самый вызов алгоритма можно переписать вот так

std::vector<int>::iterator p =
  std::find_if(t.begin(), t.end(), std::ptr_fun(f));
Код работает одинаково. Но во втором случае в алгоритм передается уже не просто функция, а сгенерированный "налету" объект функции.

Использование объектов функции, помимо потенциального прироста производительности, предоставляет новые возможности. Предположим, мы хотим повысить гибкость функции поиска и передавать в f() искомое значение в качестве дополнительного параметра. Пожалуйста:

bool f2(int Value1, int Value2) {
  return Value1 == Value2;
}
int n = 10;
std::vector<int>::iterator p =
  std::find_if(t.begin(), t.end()
   , std::bind1st(std::ptr_fun(f2), n));
Теперь наша функция f2() принимает два значения. Но алгоритму find_id требуется функция, которая принимает только ОДИН параметр - элемент из списка. Поэтому, мы воспользовались функцией std::bind1st. Эта функция создает экземпляр функционального адаптера std::binder1st, который "заворачивает" вызов функции с двумя параметрами в функцию с одним параметром. В итоге, алгоритм вызывает правильную функцию с одним параметром. Вызов этой функции преобразуется адаптером std::binder1st в вызов f2, причем в качестве значения дополнительного параметра адаптер подставляет то значение, которое мы передали ему при вызове std::bind1st.

В STL два связывающих адаптера: std::binder1st и std::binder2nd. Первый подставляет переданное нами значение в качестве первого параметра функции, второй - в качестве второго. Поскольку оба этих адаптера представляют из себя шаблоны с несколькими параметрами, их обычно создают через вспомагательные функции std::bind1st и std::bind2st, которые позволяют не указывать типы параметров шаблона вручную.

Пусть нам теперь требуется решить обратную задачу - найти в векторе значение, НЕ РАВНОЕ заданному. Можем ли мы для ее решения обойтись все той же функцией f2? Элементарно:

std::vector::iterator p =
  std::find_if(t.begin(), t.end()
   , std::not1(std::bind1st(std::ptr_fun(f2), n)));

Бинарные функции

До сих пор мы работали с унарными функциями. Между тем, многие алгоритмы STL требуют бинарных функций. Пусть нам требуется отсортировать тот же целочисленный вектор. Сортируем:

bool less(int lhs, int rhs) {
return lhs < rhs;
}
//используем собственную функцию сравнения
std::sort(t.begin(), t.end(), std::ptr_fun(less));

//используем стандартные функции меньше, больше
std::sort(t.begin(), t.end(), std::less<int>() );
std::sort(t.begin(), t.end(), std::greater<int>() );

//используем стандартные функции больше/меньше или равно
std::sort(t.begin(), t.end(), std::greater_equal<int>() );
std::sort(t.begin(), t.end(), std::less_equal<int>() );

//Комбинируем адаптеры: НЕ "больше или равно"
std::sort(t.begin(), t.end()
  , std::not2(std::greater_equal<int>()));
Другой пример. Переместим в начало списка все элементы удовлетворяющие заданному условию:

//все элементы равные двум
std::partition(t.begin(), t.end()
  , std::bind2nd(std::equal_to<int>(), 2));
//все элементы НЕ равные двум
std::partition(t.begin(), t.end()
  , std::bind2nd(std::not2(std::equal_to<int>()), 2));
Логические операции "меньше", "больше", "не", "больше или равно" и т.д. используются настолько часто, что шаблоны для определения подходящих функциональных объектов уже включены в STL. Та же история со стандартными арифметическими и логическими операциями.

std::vector<int> a, b;

//n = N % a1 % a2 % a3...
n = std::accumulate(a.begin(), a.end(), N
  , std::modulus<int>());

//n = n0 - (a1*b1) - (a2*b2) - (a3*b3) - ...
n = std::inner_product(a.begin(), a.end(), b.begin(), n0
  , std::minus<int>()
  , std::multiplies<int>());

//n = n0 + (a1/b1) + (a2/b2) + (a3/b3) + ...
n = std::inner_product(a.begin(), a.end(), b.begin(), n0
  , std::plus<int>()
  , std::divides<int>());

//n = N || a1 || a2 || a3...
n = std::accumulate(a.begin(), a.end(), N
  , std::logical_or<int>());

//n = N && a1 && a2 && a3...
n = std::accumulate(a.begin(), a.end(), N
  , std::logical_and<int>());

Переходим к объектам

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

struct x {
  bool f() {
    return true;}
};
std::vector<x> v;
Нам требуется найти объект, у которого функция f вернет "true". Как это сделать?

Вместо std::ptr_fun нужно использовать std::mem_fun_ref:

std::vector<x>::iterator p = std::find_if(v.begin(), v.end()
  , std::mem_fun_ref(&x::f));
Если в векторе хранятся указатели на объекты, то нужен адаптер std::mem_fun:

std::vector<x*> w;
std::vector<x*>::iterator p = std::find_if(w.begin(), w.end()
  ,std::mem_fun(&x::f1));

Собственные объекты функций

Если вы определяете собственные функциональные объекты, то их желательно наследовать от std::binary_function или std::unary_function. Эти функции добавят в определение ваших классов необходимые объявления типов и, в результате, стандартные функциональные адаптеры, типа std::bind1st, std::not1 и т.п. смогут с ними работать точно так же, как со стандартными.

Чего не хватает для счастья

Очень много. При использовании стандартных адаптеров можно налететь на проблему "ссылка на ссылку". Нужно не забывать указывать std::ptr_fun. Нет стандартных функций для создания композиций функциональных адаптеров (как, например, найти в векторе 2 ИЛИ 3?). Адаптеры std::bindXXX не пригодны для работы с функциями, у которых больше двух параметров. Наконец, в нашем распоряжении нет функторов!

Все проблемы решаются с помощью boost. Библиотека реализует улучшенный набор функциональных адаптеров, которые идентичны по синтаксису стандартным и, одновременно, свободны от проблемы "ссылки на ссылку" и не требуют явного указания std::ptr_fun. Но главная прелесть не в этом. В boost есть замечательные библиотеки: boost::bind, boost::function, boost::mem_fn и boost::lambda, которые позволяют снять указанные выше проблемы как класс и на порядок упростить создание функциональных объектов. Библиотеки boost::bind, boost::function, boost::mem_fn вошли в TR1 и теперь являются стандартными. Однако обсуждение этих библиотек - тема слишком обширная, так что отложим ее до другого раза.

среда, 4 февраля 2009 г.

Инкремент даты в XSLT 1.0.

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

В XSLT 1.0 встроенных средств нет. В XSLT 2.0, насколько я понимаю,
можно выкрутится встроенными средствами, но мне требуется XSLT 1.0.

Можно подключить JavaScript и написать скрипт для инкремента даты. Однако, как оказалось, можно обойтись и без JavaScript'а.

Вот здесь приведены исходные коды двух функций, позволяющих преобразовать дату в количество дней, прошедших с 31-декабря 0-ого года, и обратно. Если у нас в распоряжении есть такие функции, то выполнить инкремент даты не составит проблем:
int date; //количество дней
itod(&date, 2009, 2, 3); //получаем количество дней для даты 3.02.2009

int y, m, d;
dtoi(date+1, &y, &m, &d); //получаем год, месяц, число для 4.02.2009.


Приложение на С выглядит так:
void dtoi (int date, int &year, int &month, int &day) {
// the date specified as the number of days elapsed since 
//31 Dec of year 0. So 1 Jan 0001 is 1.
  int Z = date + 306;
  int H = 100*Z - 25;
  int A = H/3652425;
  int B = A - A/4;
  year = (100*B + H) / 36525;
  int C = B + Z - 365*year - year / 4;
  month = (5*C + 456) / 153;
  day = C - (153*month - 457) / 5;
  if (month > 12) { year += 1; month -= 12; }
}

int itod (int y, int m, int d) {
  if (m < 3) { m += 12; y -= 1; }
  return d + (153*m - 457) / 5 + 365*y + y/4 - y/100 + y/400 - 306;
}

int _tmain(int argc, _TCHAR* argv[])
{
  int date = itod(2009, 12, 31);
  int y, m, d;
  dtoi(date+1, y, m, d);
}



Перевел код на XSLT. Получилось следующее:
<xsl:template name="date_to_int">
  <xsl:param name="y" />
  <xsl:param name="m" />
  <xsl:param name="d" />
  <xsl:choose>
    <xsl:when test="number($m) < 3">
    <xsl:call-template name="date_to_int_auxilary">
        <xsl:with-param name="y" select="number($y)-1"/>
        <xsl:with-param name="m" select="number($m)+12"/>
        <xsl:with-param name="d" select="$d"/>
      </xsl:call-template>
    </xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="date_to_int_auxilary">
        <xsl:with-param name="y" select="$y"/>
        <xsl:with-param name="m" select="$m"/>
        <xsl:with-param name="d" select="$d"/>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

<xsl:template name="date_to_int_auxilary">
  <xsl:param name="y" />
  <xsl:param name="m" />
  <xsl:param name="d" />

  <xsl:value-of select="number($d) + floor((153.0*number($m) - 457.0) div 5.0) + 365*number($y) + floor(number($y) div 4 ) - floor(number($y) div 100) + floor(number($y) div 400) - 306"/>
</xsl:template>


<!-- Convert number of days to date (year, month, day - required part of the date is selected by 'required_value' parameter -->
<xsl:template name="int_to_date">
  <xsl:param name="g"/>
  <xsl:param name="required_value" select="'year'"/> <!-- 'year' or 'month' or 'day'-->

  
  <xsl:variable name="Z" select="floor(number($g) + 306)"/>
  <xsl:variable name="H" select="floor(100*number($Z) - 25)"/>
  <xsl:variable name="A" select="floor(number($H) div 3652425)"/>
  <xsl:variable name="B" select="floor(number($A) - number($A) div 4)"/>
  <xsl:variable name="year" select="floor((number($B)*100 + number($H)) div 36525)"/>
  <xsl:variable name="C" select="floor(-365.0*number($year) + number($B) + number($Z)- floor(number($year) div 4))"/>
  <xsl:variable name="month" select="floor((number($C)*5 + 456) div 153)"/>
  <xsl:variable name="day" select="number($C) - floor(( floor(153*number($month)) - 457) div 5)"/>

  <xsl:choose>
    <xsl:when test="number($month) > 12">
  <xsl:call-template name="int_to_date_helper">  
    <xsl:with-param name="year" select="number($year)+1"/>
    <xsl:with-param name="month" select="number($month)-12"/>
    <xsl:with-param name="day" select="number($day)"/>
    <xsl:with-param name="required_value" select="$required_value"/>
  </xsl:call-template>
    </xsl:when>
    <xsl:otherwise>
  <xsl:call-template name="int_to_date_helper">  
    <xsl:with-param name="year" select="number($year)"/>
    <xsl:with-param name="month" select="number($month)"/>
    <xsl:with-param name="day" select="number($day)"/>
    <xsl:with-param name="required_value" select="$required_value"/>
  </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>
  
<xsl:template name="int_to_date_helper">
  <xsl:param name="year"/>
  <xsl:param name="month"/>
  <xsl:param name="day"/>
  <xsl:param name="required_value"/> <!-- 'year' or 'month' or 'day'-->

  <xsl:choose>
    <xsl:when test="$required_value='year'">
       <xsl:value-of select="round($year)"/>
    </xsl:when>
    <xsl:when test="$required_value='month'">
       <xsl:value-of select="round($month)"/>
    </xsl:when>
    <xsl:when test="$required_value='day'">
       <xsl:value-of select="round($day)"/>
    </xsl:when>
  </xsl:choose>
</xsl:template>


Функция int_to_date соответствует C-шной функции itod, функция date_to_int - функции dtoi. Функция date_to_int принимает два параметра - количество дней и название требуемой части даты - 'year', 'month' или 'day' (передавать прямо в апострофах). Таким образом, если вы хотите напечатать дату в виде "Год.Месяц.День", то функцию date_to_int придется вызвать трижды - один раз, чтобы получить год, второй - месяц, третий - день. Впрочем, совсем несложно изменить шаблон так, чтобы функция возвращала дату целиком, в виде строки в подходящем формате.

Полный текст тестового преобразования с примером вызова можно взять здесь.

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

понедельник, 2 февраля 2009 г.

Интеллект карта для C# 2.0

Тем, кто готовится проходить тестирование по какому-либо языку программирования, может оказаться крайне полезной возможность посмотреть на него "сверху" - охватить взглядом его возможности, тонкости и особенности. Можно легко определить слабые места в своих знаниях и, даже, обнаружить особенности языка, о которых вообще не имеешь представления.

Такая возможность есть для C#. На сайте FreeMind опубликована интеллект-карта для C# 2.0. Для просмотра ничего не требуется кроме браузера с установленным флеш-плеером. Там же есть аналогичная карта для Python 2.5.



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

воскресенье, 1 февраля 2009 г.

Что выбрать: std::map, std::vector или boost::unordered_map?

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

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

"Стандартных" контейнера, которые подойдут в данном случае, как минимум три: std::map, сортированный std::vector и boost::unordered_map, который уже вошел в TR1. Вопрос, какой из них лучше подойдет для данной задачи?

Чтобы определить, какой вариант лучше, написал небольшое тестовое приложение. В нем содержатся три класса, реализующие варианты подсчета токенов с помощью разных ассоциативных контейнеров, два класса для генерации случайной последовательности токенов (int и string) и тестовая функций, выполняющая тестовый перебор последовательности несколько раз и определяющая среднее время, затрачиваемое на его выполнение. У программы два параметра: максимальное количество токенов и длина последовательности. Программа тестировалась на VS2005 с родной реализацией STL.


Результаты тестирования для последовательности из 1e5 целочисленных токенов


Кол-во токенов:101e21e31e41e5
std::map, int373531464716
std::vector, int403731511446
boost::unordered_map, int35312340427


Результаты тестирования для последовательности из 1e5 строковых токенов


Кол-во токенов:101e21e31e41e5
std::map, string556270493391
std::vector, string7174871071-
boost::unordered_map, string47463893437


Вектор работает плохо, но это и следовало ожидать. boost::unorderd_map демонстрирует лучшую производительность, чем std::map, однако если по началу их результаты примерно одинаковы, то потом следует резкий перекос (производительность boost::unorderd_map в 5-10 раз лучше), а затем маятник качается в обратную сторону, так что производительность std::map становится даже лучше. Посмотрим, как ведет себя производительность при других соотношениях длины последовательноси и количества токенов.

Кол-во токенов/длина последовательности:1e5/1e61e5/1e71e6/1e7
std::map, int625503113875
boost::unorderd_map, int98425786062
std::map, string17961534328875
boost::unorderd_map, string132863751125


Выводы


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

boost::unordered_map работает быстрее std::map при условии, что длина последовательности гораздо больше количества токенов, т.е. каждый токен в среднем входит в последовательность множество раз.

Если же длина последовательности и количество токенов примерно совпадают (т.е. все токены входят в последовательность один-несколько раз ), то std::map может оказаться быстрее, но в редких случаях..

Итог - для моей задачи boost::unordered_map предпочтителен. И как хорошо, что это теперь стандартный контейнер :)

Исходные коды тестового проекта можно взять здесь.