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

Перевод статьи "Поиск ассоциативных правил при интеллектуальном анализе данных"

Обнаружил статью Раймонда Лэма "Discovering Association Rules in Data Mining", посвященную поиску ассоциативных правил. Подробный и широкий обзор темы - что такое ассоциативные правила, в чем суть проблемы, какие типы правил существуют (булевые, обобщенные, количественные, временные), алгоритм Apriori и его предшественники, усовершенствованные версии алгоритма Apriori (AprioriTid, AprioriHybrid), DHP, SSM, распараллеливание и масштабируемость Apriori, не-apriori алгоритмы (FP-деревья), новые подходы генерации правил, APACS2, Evolutionary Algorithm, негативные ассоциации...

На мой взгляд, прекрасная обзорная статья. Автору респект за проделанную работу - такие статьи редко встречаются и бывают крайне полезны. Лично для меня особенно любопытной оказалась информация об алгоритме APACS2, позволяющем генерировать ассоциативные правила не указывая confidence, а так же сведения о распараллеленных и масштабируемых версиях алгоритма Apriori - Intelligent Data Distribution и Hybrid Distribution.

Статью перевел на русский язык и выложил перевод.

среда, 14 января 2009 г.

Синглетон Мейерса в смешанных сборках CLI/C++

В текущем проекте, разрабатываемым под Microsoft .Net 2.0, столкнулся со следующей ошибкой:

The exception unknown software exception (0xc00200001) occured in the application at location 0x7c812a5b.

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

Стал разбираться в чем дело. Проект включает две сборки: интерфейсная часть написана на C#, реализация движка - на CLI/C++.  Поискав ошибку в интернете обнаружил, что подобные ошибки встречаются в случае наличия  в C++-ной сборке статических объектов с нетривиальными деструкторами. Как раз мой случай - один из классов в моей сборке включал реализацию синглетона Мейерса. 

class Kernel { 
     Kernel(void);
     ~Kernel(void) {  /*удаление unmanaged объектов*/  }
public:
      static Kernel GetInstance() {
         static Kernel k;  //Синглетон Мейерса
         return k;
     } 
  ...
}

Никаких вызовов управляемого кода в моем статическом объекте вообще нет - Kernel, это чистый native-класс.

Поскольку  без синглетонов при разработке приложений обойтись трудно, решил разобраться, как можно реализовать синглетон Мейерса в сборке, написанной на CLI/C++, в которой управляемый и неуправляемый коды смешаны.  

Написал простой тестовый проект, включающий две сборки. Первая сборка Test написана на CLI/С++ и содержит управляемый класс Managed и неуправляемый Unmanaged, причем неуправляемый вызывается из управляемого. Вторая сборка написана на C# и вызывает класс Managed из первой. Управляемая сборка включает тест NUnit, через который производится запуск приложения (можно, конечно, запускать приложение и напрямую, но через NUnit проблем вылазит больше).

Код на C# тривиален:
class Class1 {
       public void Test1() {
           Test.ManagedClass m = new Test.ManagedClass();
              m.Dispose(); 
        } 
}

class Program {
/*Функция Main для запуска приложения напрямую, без NUnit*/
static void Main(string[] args)  {
           Class1 c = new Class1();
           for (int i = 0; i < 10; ++i) c.Test1();
}
}

[TestFixture] 
public class test {
[Test] /*Тест NUnit для запуска приложения*/
public void Execute() {
Class1 c = new Class1();
for (int i = 0; i < 10; ++i) c.Test1();
}
}
Код на CLI/C++ взятый за основу:
class Unmanaged1 {
    int *m_p;
public:
    Unmanaged1(void) : m_p(new int()) {}
    ~Unmanaged1(void) {   delete m_p; /*non trivial destructor*/   }
   static Unmanaged1& GetInstanceRef() {
   static Unmanaged1 u;
      return u;
    } 
    int* GetPtr() { return m_p; }
};

Вариант 1. Использование #pragma managed

Первое, что приходит в голову - это явно указать, что класс Unmanaged является неуправляемым.
#pragma managed(push, off)
class Unmanaged {
......
};
#pragma managed(pop)
Не работает. При завершении работы приложения возникает исключение 0xc0020001: The string binding is invalid. Вызов деструктора класса производится при выгрузке DLL, когда деинициализация CLR уже фактически проведена. Если в деструкторе вызывается управляемый код, то возникает ошибка. Явно у меня управляемый код нигде не вызвается. Есть какой-то неявный вызов (?)

Вариант 2a. Разделение кода на cpp и h-файлы

Вынесем функцию GetInstanceRef() в cpp-файл:
/*unmanaged.cpp*/
Unmanaged& Unmanaged::GetInstanceRef() {
static Unmanaged2 u;
return u;
}
Тоже не работает. При вызове возникает ошибка: This function must be called in the default domain.

Вариант 2b. Вынос статической переменной за пределы класса

Вынесем переменную u из GetInstanceRef.
/*unmanaged.cpp*/
static Unmanaged2 u;
Unmanaged2& Unmanaged2::GetInstanceRef() {
    return u;
}
Такой вариант срабатывает.Почему он срабатывает объяснено в книге Expert Visual C++/CLI: .NET for Visual C++ Programmers. Дело в том, что инициализация статических и глобальных переменных, объявленных в cpp-модулях, компилируемых с ключем /clr, производится в специальном конструкторе модуля. Конструктор модуля, по сути, представляет из себя инициализатор сборки и является первой управляемой функцией, вызываемой CLR. Соответственно, деинициализация переменных производится не при выгрузке DLL, а непосредственно перед завершением работы CLR. В итоге - все работает. Кстати, порядок инициализации переменных в смешанной сборке таков. Вначале производится инициализация всех глобальных и статических объектов, объявленных в cpp-модулях, компилируемых без ключа /clr. Затем производится инициализация всех глобальных и статических объектов, объявленных в cpp-модулях, компилируемых с ключем /clr.

Вариант 2c. Инициализация синглетона из неуправляемого кода.

Возможно проблема варианта 2а в том, что синглетон инициализируется вызовом управляемого кода. А что если его инициализировать заранее?
/*unmanaged.cpp*/
Unmanaged2& dummy = Unmanaged2::GetInstanceRef();
Unmanaged2& Unmanaged2::GetInstanceRef() {
static Unmanaged2 u; 
    return u;
}
Такой код тоже срабатывает.

Вариант 3. Компиляция без ключа /clr

В моем случае класс Unmanaged не вызывает никакого управляемого кода. Теоретически, статические переменные этого класса можно было бы инициализировать при загрузке DLL, уничтожать при выгрузке DLL и проблем быть не должно. Что если этот класс откомпилировать без ключа /clr? В книге Хиджа приведен детальный алгоритм, как сделать обычный неуправляемый проект DLL (который будет компилироваться без ключа /clr) и включить в него несколько исходных файлов с управляемым кодом (которые будут компилироваться с ключем /clr). Для этого нужно создать второй precompiled header - stdafx_clr.h, и задать отдельные свойства компиляции (с ключом /clr) для файла stdafx_clr.cpp и всех cpp-файлов, содержащих управляемый код. Попробовал. Вариант 2a заработал. Вариант 1 не работает и в этом случае. Если вызывать текстовый класс через unit test, то получаем ошибку Managed Debugging Assistant 'LoaderLock' has detected a problem in 'C:\Program Files\NUnit 2.4.8\bin\nunit.exe'. Additional Information: Attempting managed execution inside OS Loader lock. Do not attempt to run managed code inside a DllMain or image initialization function since doing so can cause the application to hang. Если вызывать приложение напрямую, то ошибка "0xC0020001: The string binding is invalid.".

Итоги

Итак, как можно реализовать синглетон Мейерса в неуправляемом коде в смешанной сборке? Реализовать синглетон в заголовочном файле C++ (вариант 1) не удается - такой синглетон нельзя вызвать из управляемого кода без появления ошибки при закрытии приложения. Если вынести реализацию в cpp-шный файл (вариант 2), то ситуация меняется. В случае, когда весь проект компилируется с ключом /clr, статическую переменную необходимо вынести за пределы класса и объявить глобально в теле cpp-файла (вариант 2b). Альтернативный вариант - можно предварительно инициализировать синглетон из неуправялемого кода, до его первого вызова из управляемого кода (вариант 2c). Если проект компилируется без ключа /clr, а ключ /clr включен лишь для файлов с управляемым кодом, то статическую переменную можно оставлять локальной (вариант 2a). Исходники тестового проекта можно взять здесь. Тестирование велось под VS 2005. Update: недавно налетел на столь же неприятную проблему с синглетонами на Android. Реализация синглетона - вещь непростая..

вторник, 13 января 2009 г.

посылки из-за границы

Последние несколько лет наловчился покупать товары в интернет-магазине cabelas.com.  В основном - одежду. Качество отличное, цены существенно меньше наших,  даже с учетом доставки, да еще и скидки порой можно отловить хорошие. С доставкой проблем ни разу не было - посылка доставляется курьерской службой UPS, курьер привозит посылку по любому адресу. Вернее - проблем не было раньше. А недавно неожиданно появились.

В декабре  заказал себе куртку. Обычно посылку привозят за пять дней, а тут - проходит неделя, никто не звонит. Захожу на сайт, смотрю информацию по заказу. В Tracking Information написано:

THE VALUE OF THE COMMODITY EXCEEDS THE LIMIT
> ALLOWED BY UPS / RETURNED TO SHIPPER MOSCOW RU

Т.е. посылка доехала до Москвы - и поехала обратно.  Я очень удивился - стоимость посылки была ~$200, т.е. значительно меньше разрешенных беспошленных 10 тыс руб. Несколько месяцев назад я получал с cabelas посылку примерно с такой же стоимостью и все было в порядке. 

В итоге, перерыв интернет, я разобрался в чем дело.  Оказывается, беспошлинный лимит при пересылке составляет 10 тысяч рублей только для организаций, "обладающих правом работы с международными почтовыми отправлениями".  Т.е. для почты.  А для курьерских служб беспошлинный лимит составляет всего лишь 5 тысяч рублей.   Если лимит превышен, то посылку автоматически отправляют назад. И меня, естественно, никто в уведомление не ставит.  Т. к. курс доллара в декабре значительно вырос, я со своими $200 выскочил за этот лимит.  В итоге - с Cabelas мне вернули деньги за заказ, но не полностью, а удержав стоимость курьерских расходов.

Правила отправки посылок в Россию можно посмотреть на сайте таможни.  Плюс есть хорошая статья  на эту тему .


Update: с 1 июля 2010 г правила изменились. Теперь в течении одного месяца на один адрес можно получать беспошлино посылки суммарной стоимостью до 1000 евро и суммарным весом до 31 кг. Правила для почты и курьерских служб практически одинаковые.

Update апрель,2011: Похоже, курьерские службы устанавливают собственные лимиты на стоимость посылок, например I have just received email from our FedEx account representative, that limit to Russia has been increased to $260.. Узнал случайно - сделал очередной заказ на cabelas, а мне говорят - в Россию не более $250...