понедельник, 30 мая 2011 г.

CERN ROOT и надписи на русском языке

Как это ни странно, но проблема поддержки кириллицы в CERN ROOT действительно существует. Я не буду утверждать, что такая проблема присутствует в версии ROOT для Windows, но в Linux она актуальна. Однако, если учесть как эта поддержка реализована в нативной графической подсистеме ROOT, а также то, насколько глючно реализован Qt бекэнд, который поддерживает более широкий набор шрифтов, чем нативный вариант, такая проблема должна существовать и в Windows.

В качестве примера возьмем простой скрипт, с помощью которого можно создать следующее изображение:


Будем считать, что нашей целью является создание изображения в формате eps или pdf с целью дальнейшей вставки его в статью для публикации. Сам скрипт выглядит следующим образом:

void  createHisto( void )
{
    TCanvas *  c1 = new TCanvas();
    TH1 *      histo = new TH1F( "h1", "DCS vs. Energy", 10, 400., 600. );
    Double_t   content[] = { 0.0, 0.115, 0.145, 0.158, 0.170, 0.182, 0.180,
                             0.172, 0.154, 0.140, 0.132, 0.0 };
    Double_t   errors[] = { 0.0, 0.0015, 0.0012, 0.0008, 0.0016, 0.0023, 0.0018,
                            0.0013, 0.0014, 0.0006, 0.0002, 0.0 };
    histo->SetContent( content );
    histo->SetError( errors );
    histo->GetXaxis()->SetTitle( "E_{cm}, MeV" );
    histo->GetYaxis()->SetTitle( "d#sigma/d#Omega, mb/sr" );
    histo->SetStats( kFALSE );          // do not draw stats box
    histo->Draw();
    c1->SaveAs( "c1.eps" );
}

void histoTest( void )
{
    gROOT->SetStyle( "Plain" );
    gStyle->SetTitleBorderSize( 0 );    // do not draw frames around title
    gStyle->SetTitleOffset( 1.2, "xy" );// do not let axes' titles overlap ticks
    createHisto();
    if ( gROOT->IsBatch() )
        exit( 0 );
}
Обратите внимание, что в подписях к осям гистограммы используется вариант Latex для ROOT, стиль gStyle установлен в Plain, а рамка вокруг титула удалена. Отсутствие рамки вокруг титула упрощает решение задачи в первом и третьем подходах (см. ниже).

Для сохранения картинки наверху в файле c1.eps нужно создать скрипт histoTest.C с указанным содержимым и запустить root в пакетном режиме:
root -b histoTest.C
Пусть нашей задачей будет замена титула изображения на ДСР в зависимости от энергии и меток mb/sr, MeV и cm на мб/ср, МэВ и цм соответственно.

Наивная подстановка русских надписей в скрипт histoTest.C приведет к выводу в изображение c1.eps "кракозябр". Что же не так с ROOT? Нативный графический бэкенд ROOT не поддерживает кириллицу. Точка. Для решения проблемы ниже представлены три подхода, которые приводятся в порядке улучшения качества решения и полноты, хотя ни один из них не является идеальным. Идеи второго и третьего подходов взяты из обсуждений здесь и здесь.
  1. Наиболее простое решение - сохранить исходное изображение в векторном формате svg и отредактировать его в каком-нибудь векторном редакторе, например в inkscape. Минусы здесь очевидны. Редактировать придется вручную. Кроме изменения текста придется изменять обрамляющие его элементы, например компоненты рамки вокруг титула (которую мы предусмотрительно убрали в исходном скрипте).
  2. Использование Qt бэкенда (Qt layer) . Это был бы идеальный вариант, если бы не невообразимая глючность данного бэкенда. Из основных глюков стоит упомянуть: полупрозрачный или полностью прозрачный фон и шрифт абсолютно всех меню, невозможность использовать диалог сохранения файлов (!), невозможность сохранить валидное изображение в форматах eps и pdf (!). В данном подходе пришлось сохранять изображение как Save -> c1.png. Для использования Qt бэкенда нужно записать в файл ~/.rootrc следующие строки:
    Gui.Backend:                $(ROOTGUI)
    Gui.Factory:                $(ROOTGUI)
    Gui.DefaultFont:            -*-helvetica-medium-r-*-*-12-*-*-*-*-*-iso8859-5
    Gui.MenuFont:               -*-helvetica-medium-r-*-*-12-*-*-*-*-*-iso8859-5
    Gui.MenuHiFont:             -*-helvetica-bold-r-*-*-12-*-*-*-*-*-iso8859-5
    Gui.DocFixedFont:           -*-courier-medium-r-*-*-12-*-*-*-*-*-iso8859-5
    Gui.DocPropFont:            -*-helvetica-medium-r-*-*-12-*-*-*-*-*-iso8859-5
    Gui.IconFont:               -*-helvetica-medium-r-*-*-10-*-*-*-*-*-iso8859-5
    Gui.StatusFont:             -*-helvetica-medium-r-*-*-10-*-*-*-*-*-iso8859-5
    
    Использование переменной среды ROOTGUI позволяет сохранить нативный бэкенд по умолчанию (однако придется добавить строку
    export ROOTGUI=native
    
    в ~/.bash_profile). Для того, чтобы запустить root с Qt бэкендом нужно ввести
    ROOTGUI=qt root histoTest_qt.C
    
    Скрипт histoTest_qt.C выглядит так:
    void  createHisto( void )
    {
        //TCanvas *  c1 = new TCanvas();
        TH1 *      histo = new TH1F( "h1", "´ÁÀ Ò ×ÐÒØáØÜÞáâØ Þâ íÝÕàÓØØ",
                                     10, 400., 600. );
        Double_t   content[] = { 0.0, 0.115, 0.145, 0.158, 0.170, 0.182, 0.180,
                                 0.172, 0.154, 0.140, 0.132, 0.0 };
        Double_t   errors[] = { 0.0, 0.0015, 0.0012, 0.0008, 0.0016, 0.0023, 0.0018,
                                0.0013, 0.0014, 0.0006, 0.0002, 0.0 };
        histo->SetContent( content );
        histo->SetError( errors );
        histo->GetXaxis()->SetTitle( "E_{æÜ}, ¼í²" );
        histo->GetYaxis()->SetTitle( "d#sigma/d#Omega, ÜÑ/áà" );
        histo->SetStats( kFALSE );          // do not draw stats box
        histo->Draw();
        //c1->SaveAs( "c1_qt.eps" );
    }
    
    void histoTest_qt( void )
    {
        gROOT->SetStyle( "Plain" );
        gStyle->SetTitleBorderSize( 0 );    // do not draw frames around title
        gStyle->SetTitleOffset( 1.1, "xy" );// do not let axes' titles overlap ticks
        createHisto();
        if ( gROOT->IsBatch() )
            exit( 0 );
    }
    
    Заметили "кракозябры" внутри скрипта? Это еще одно неудобство. Скрипт выведен в общепринятой на сегодня кодировке UTF-8, а был записан в кодировке ISO-8859-5. В vim сохранение файла в данной кодировке обеспечивается командой
    :set fenc=iso-8859-5
    
    Однако при повторной загрузке этого файла в vim появятся всё те же "кракозябры" и новые русские записи не удастся добавить без полного переписывания русских символов заново. Возможно существуют редакторы, в которых проблема перевода в разные кодировки решается проще.

    Еще один интересный момент. Создание канваса c1 в данном варианте закомментировано. Если оставить его незакомментированным, то диапазон оси ординат изменится, и на месте гистограммы окажется чистое белое поле (!). Это еще раз подтверждает тот факт, что с текущей реализацией Qt бэкенда нужно быть очень осторожным.

    Изображение, полученное с помощью Qt бэкенда, выглядит так:


    Заметьте также, что Qt бэкенд применил преобразования локали: вместо точек в вещественных числах на координатных осях стоят запятые. 
  3. Третий подход основан на Latex и двух латеховских модулях - standalone и psfrag. Оба модуля можно найти на ctan.org. В пакет texlive для Fedora 14 они не входят, однако существует отдельный репозиторий texlive, в котором эти модули присутствуют. Информация об этом репозитории здесь. Преимущество данного подхода в том, что он полностью автоматизирован. Скрипт histoTest_latex.C выглядит так:
    void  createHisto( void )
    {
        TCanvas *  c1 = new TCanvas();
        TH1 *      histo = new TH1F( "h1", "CT", 10, 400., 600. );
        Double_t   content[] = { 0.0, 0.115, 0.145, 0.158, 0.170, 0.182, 0.180,
                                 0.172, 0.154, 0.140, 0.132, 0.0 };
        Double_t   errors[] = { 0.0, 0.0015, 0.0012, 0.0008, 0.0016, 0.0023, 0.0018,
                                0.0013, 0.0014, 0.0006, 0.0002, 0.0 };
        histo->SetContent( content );
        histo->SetError( errors );
        histo->GetXaxis()->SetTitle( "CX" );
        histo->GetYaxis()->SetTitle( "CY" );
        histo->SetStats( kFALSE );          // do not draw stats box
        histo->Draw();
        c1->SaveAs( "c1_latex.eps" );
    }
    
    void histoTest_latex( void )
    {
        gROOT->SetStyle( "Plain" );
        gStyle->SetTitleBorderSize( 0 );    // do not draw frames around title
        gStyle->SetTitleOffset( 1.2, "xy" );// do not let axes' titles overlap ticks
        createHisto();
        if ( gROOT->IsBatch() )
            exit( 0 );
    }
    
    Главным отличием от исходного скрипта является то, что оригинальные титул и подписи к осям заменены метками CT, CX и CY, которые будут обрабатываться в теховском скрипте с помощью psfrag. Идея psfrag весьма проста - заменить метки в исходном ps или eps файле указанными значениями. Отмечу сразу, что метки для подстановки следует выбирать короткие, иначе psfrag может сгенерировать ломаный файл dvi. Скрипт c1_latex.tex выглядит так:
    \documentclass{standalone}
    
    \usepackage[T2A]{fontenc}
    \usepackage[utf8x]{inputenc}
    
    \usepackage[dvips]{graphicx,color}
    \usepackage{psfrag}
    
    \begin{document}
    \psfrag{CT}[lt][lt][1.8]{\bf ДСР в зависимости от энергии}
    \psfrag{CX}[rt][rt][1.4]{\bf $\mathbf{E_{\mbox{цм}}}$, МэВ}
    \psfrag{CY}[rt][rt][1.4]{\bf $\mathbf{d\sigma/d\Omega}$, мб/ср}
    \includegraphics{c1_latex.eps}
    \end{document}
    
    О параметрах psfrag можно прочитать в документации к данному пакету; кратко, первый параметр в фигурных скобках является заменяемой меткой, последний параметр в фигурных скобках - подстановкой, первые два параметра в квадратных скобках после метки - позиционными якорями, третий параметр в квадратных скобках - коэффициентом масштабирования шрифта. Пакет standalone позволяет сохранить исходные размеры изображения.

    Русификация надписей может быть произведена с помощью отдельного шелл-скрипта mkrus:
    #!/bin/sh
    # source root macro
    root -b histoTest_latex.C
    # run psfrag
    latex c1_latex
    # make pdf
    dvips c1_latex
    ps2pdf c1_latex.ps
    # delete temporary files
    rm c1_latex.eps c1_latex.ps c1_latex.dvi c1_latex.aux c1_latex.log
    # make eps
    pdftops -eps c1_latex.pdf
    
    Этот скрипт создает два изображения: c1_latex.eps и c1_latex.pdf, которые выглядят так:


    В данном изображении используется шрифт Serif - просто в моем дистрибутиве texlive не нашлось русского Sans Serif шрифта c кодировкой T2A (которая используется в c1_latex.tex). Если необходим шрифт Sans Serif, нужно установить его из внешних источников.

суббота, 28 мая 2011 г.

Fedora 15 и wicd

Так уж получилось, что на моем ноутбуке Lenovo B560 вместо NetworkManager установлен wicd: просто на момент покупки (в феврале этого года) NetworkManager не умел работать с броадкомовским сетевым интерфейсом, установленном в B560 (да и сейчас наверное не умеет); кcтати и дрова для этого драйвера пришлось брать проприетарные - из rpmfusion (broadcom-wl). Как бы то ни было, но wicd мне вполне понравился и менять его обратно на NetworkManager я не собираюсь.

После того, как совсем недавно вышел релиз Fedora 15, я решил опробовать его на данном ноутбуке, перед тем как переносить на десктоп. Теперь я могу сказать совершенно точно, что обновлять десктоп с Fedora 14 до Fedora 15 я не буду, подожду следующего релиза. И, конечно же, огромное спасибо за такое решение хочется сказать разработчикам Gnome 3 :) Ну да ладно, это тема отдельного разговора.

Итак, вернемся к B560 и wicd. После обновления до Fedora 15 на ноутбуке отвалился wi-fi. Апплет wicd-gtk ругался на dbus и отказывался сканировать wi-fi источники. Первое, что удалось установить, это отсутствие модуля wl в списке загруженных модулей ядра. Оказывается, rpmfusion еще не удосужились обновиться до Fedora 15 (на момент написания этих строк репозитория rpmfusion Fedora 15 так и не появилось). В rpmfusion rawhide я этого драйвера тоже на тот момент не нашел (хотя сейчас он там уже присутствует). Поэтому я снес akmod-wl и kmod-wl и переустановил их из russianfedora. Команда modprobe wl вернула броадкомовскую железяку к жизни.

Однако это никак не повлияло на работу апплета wicd-gtk, который упорно ругался на dbus. Как выяснилось, демон wicd, который на Fedora 15 управляется новой системой загрузки systemd, умирал сразу же, как только systemd его стартовал. В багзилле Red Hat имеется соответствующий баг #327829, который был создан в апреле этого года и почему-то ни разу не комментировался. Если кому-то интересно, скрипт systemd для запуска демона wicd находится в файле /lib/systemd/system/wicd.service. Проверка статуса осуществляется командой systemctl status wicd.service, аналогично запуск и остановка - stop и start. Хотя старая добрая service wicd status тоже работает, просто перенаправляя действия на systemctl (обратите внимание, что в systemctl сначала указывается команда, а потом сервис). Как бы то ни было, но возиться с этим мне было некогда, мне нужен был рабочий wi-fi сразу после загрузки.

Очевидное решение - поместить строку /usr/sbin/wicd в файл /etc/rc.local - сработало. Остается ждать, когда разработчики починят баг #327829 и вернуть управление демоном wicd системе systemd.

воскресенье, 15 мая 2011 г.

Сравнение подходов в реализации алгоритмов на C++ и Haskell

Классический пример краткой и ясной реализации алгоритма на Haskell - это быстрая сортировка:
quickSort [] = []
quickSort (x:xs) = quickSort [ y | y <- xs, y < x ] ++ [ x ] ++
                   quickSort [ y | y <- xs, y >= x ]
Обычно рядом с этим кодом приводят какую-нибудь 20-строчную реализацию быстрой сортировки на C или C++. И конечно же сравнение идёт не в пользу C++. Откровенно говоря, здесь заключена немалая доля лукавства: как можно сравнивать высокоуровневые определители списков (list comprehensions - выражения в квадратных скобках в данном примере) с низкоуровневыми итерациями в коде C++? С другой стороны, определители списков являются встроенным механизмом Haskell, поэтому подобное сравнение всё-таки допустимо.

Ниже приводятся реализации одного алгоритма на C++ и Haskell. Алгоритм был взят из книги Ф. Меньшикова "Олимпиадные задачи по программированию". Задача формулируется следующим образом:
Дана последовательность из N целых чисел чисел. Необходимо удалить из последовательности минимальное количество чисел так, чтобы оставшаяся часть последовательности оказалась строго возрастающей. Иными словами нужно найти самую длинную возрастающую подпоследовательность.
Базовый алгоритм для решения этой задачи приводится в этой же книге:
Начиная с первого элемента последовательности и заканчивая последним найти максимальную длину возрастающей подпоследовательности из предшествующих элементов, меньших данного, и прибавить к ней 1. Эта величина будет соответствовать максимальной длине возрастающей подпоследовательности, которую можно построить начиная с 1-ого элемента исходной последовательность вплоть до данного элемента. Так, для 1-ого элемента последовательности из предшествующих элементов не существует, поэтому ему соответствует длина 1. Для произвольного i-ого элемента нужно совершить обратный проход к началу последовательности, найти меньший по значению элемент с максимальным значением длины и прибавить к нему 1. После того как длины найдены (при условии, что они сохранены в некотором вспомогательном массиве), нужно в исходной последовательности найти элемент, которому соответствует  максимальное значение длины и, двигаясь к началу последовательности, находить первые элементы, для которых соответствующая длина уменьшилась на единицу. Эти элементы (вместе с исходным) и будут составлять искомую подпоследовательность наибольшей длины.
Несколько замечаний. Во-первых, существуют модификации этого алгоритма, в которых финальный проход от элемента, которому соответствует максимальная длина возрастающей подпоследовательности к началу исходной последовательности не требуется. Поскольку моей целью является не написание самого оптимального алгоритма, а качественное сравнение подобных реализаций на C++ и Haskell, то я использовал базовый алгоритм. Во-вторых, очевидно, что в базовом варианте класс этого алгоритма соответствует O(n^2), так как присутствуют вложенные итерации (обратные проходы к началу последовательности) внутри базовой итерации по всем элементам. В-третьих, могут существовать несколько подпоследовательностей максимальной длины, нам нужно выбрать любую из них.

Итак, реализация этого алгоритма на C++ выглядит следующим образом:
typedef std::vector< int >  VIn;

typedef VIn::value_type     VInElem;

typedef std::vector< int >  VCnt;

void  findLongestIncSeq( const VIn &  vIn, VIn &  vRes )
{
    VCnt                 vCnt( vIn.size() );
    VCnt::iterator       vCntIt( vCnt.begin() );
    VIn::const_iterator  vMaxIt( vIn.begin() );
    VCnt::iterator       vCntMaxIt( vCnt.begin() );
    int                  maxLen( 0 );

    for ( VIn::const_iterator  k( vIn.begin() ); k != vIn.end(); ++k, ++vCntIt )
    {
        int                           maxVal( 0 );
        VCnt::const_reverse_iterator  vCntBackIt( vCntIt );

        for ( VIn::const_reverse_iterator  l( k ); l != vIn.rend();
                                                            ++l, ++vCntBackIt )
        {
            if ( *k <= *l )
                continue;

            if ( *vCntBackIt > maxVal )
                maxVal = *vCntBackIt;
        }

        *vCntIt = maxVal + 1;
        if ( *vCntIt > maxLen )
        {
            maxLen = *vCntIt;
            vMaxIt = k;
            vCntMaxIt = vCntIt;
        }
    }

    std::cout << "Lengths:  ";
    printVec( vCnt );

    if ( vMaxIt == vIn.begin() )
        return;

    std::stack< VInElem >   reverseSeq;
    VCnt::reverse_iterator  vCntBackIt( vCntMaxIt + 1 );

    for ( VIn::const_reverse_iterator  k( vMaxIt + 1 ); k != vIn.rend();
                                                            ++k, ++vCntBackIt )
    {
        if ( *vCntBackIt == maxLen )
        {
            reverseSeq.push( *k );
            --maxLen;
        }
    }

    while ( ! reverseSeq.empty() )
    {
        vRes.push_back( reverseSeq.top() );
        reverseSeq.pop();
    }
}
Вспомогательная функция printVec() реализуется так:
template  < typename  VElem >
struct  PrintVec
{
    void  operator()( VElem  value )
    {
        std::cout << value << " ";
    }
};

template  < typename  Vec >
void  printVec( Vec  v )
{
    std::for_each( v.begin(), v.end(), PrintVec< typename Vec::value_type >() );
    std::cout << std::endl;
}
В функцию findLongestIncSeq() передаются ссылки на исходную последовательность vIn и последовательность vRes, которую нужно заполнить. Внутри функции создаем вспомогательный массив целых чисел vCnt, в котором будем хранить длины максимальной возрастающей последовательности до i-ого элемента включительно. Внутри первого цикла for происходит основная итерация, в которой заполняется массив vCnt, кроме того попутно вычисляются максимальная длина возрастающей подпоследовательности maxLen и соответствующие ей элементы в vIn и vCnt: vMaxIt и vCntMaxIt - они будут нужны для определения элемента, с которого нужно начать финальный проход по исходной последовательности вниз к первому элементу. Этот финальный проход осуществляется в последнем цикле for функции findLongestIncSeq(), в котором заполняется вспомогательный стек reverseSeq. Теперь, чтобы заполнить искомую последовательность vRes, нужно опустошить reverseSeq и сложить его элементы в vRes, что и происходит в последнем цикле while.

Я не буду приводить функцию main() - это детали. Укажу только, что для тестовой последовательности [67 5 34 89 65 12 90 75 8 9 3] выводится следующий результат:
Original: 67 5 34 89 65 12 90 75 8 9 3 
Lengths:  1 1 2 3 3 2 4 4 2 3 1 
Sequence: 5 34 65 90
В строке Original выводится исходная последовательность, в строке Lengths - вспомогательная последовательность длин возрастающих подпоследовательностей, а в строке Sequence - результирующая возрастающая подпоследовательность максимальной длины.

А теперь внимание. Подобный алгоритм написанный на Haskell (я привожу весь код вместе с тестовой частью, так что его можно сразу скомпилировать):
{-find longest increasing subsequence-}

getPrevLength [] = 0
getPrevLength x  = maximum $ doGetLengths x

doGetLengths []     = []
doGetLengths (x:xs) = getPrevLength [ y | y <- xs, y < x ] + 1 : doGetLengths xs

getLengths = reverse . doGetLengths . reverse

doCutTail [] _                                          = []
doCutTail a@(x:xs) maxLen
    | getPrevLength [ y | y <- xs, y < x ] + 1 < maxLen = doCutTail xs maxLen
    | otherwise                                         = a

cutTail [] = []
cutTail x  = reverse $ doCutTail ( reverse x ) ( maximum $ getLengths x )

doFindLongestIncSec' [] _   = []
doFindLongestIncSec' (x:xs) maxLen
    | maxLen - prevLen == 1 = x : doFindLongestIncSec' xs prevLen
    | otherwise             = doFindLongestIncSec' xs maxLen
        where prevLen = getPrevLength [ y | y <- xs, y < x ] + 1

doFindLongestIncSec [] = []
doFindLongestIncSec x  =
    doFindLongestIncSec' ( reverse x ) ( maximum ( getLengths x ) + 1 )

findLongestIncSec = reverse . doFindLongestIncSec . cutTail

{-do some testing-}

doTest x = do
    putStrLn $ "Original: " ++ show x
    putStrLn $ "Lengths:  " ++ ( show $ getLengths x )
    putStrLn $ "Trimmed:  " ++ ( show $ cutTail x )
    putStrLn $ "Sequence: " ++ ( show $ findLongestIncSec x )

main = mapM_ doTest [ [ 10, 5, 89, 16, 78, 67, 56, 34, 12, 10 ],
                      [ 67, 5, 34, 89, 65, 12, 90, 75, 8, 9, 3 ] ]
Я назвал этот алгоритм подобным, поскольку его невозможно реализовать тем же самым способом, что и в C++ (во всяком случае без использования монад). В Haskell отсутствуют итерации и состояния (то бишь переменные), и это означает, что создать вспомогательный массив длин подпоследовательностей и использовать его на том же уровне программного потока не удастся. По той же причине невозможно сначала запомнить индекс элемента с максимальным значением возрастающей подпоследовательности, а затем использовать его по своему усмотрению в параллельной последовательности вызовов функций. В Haskell возможность параллельной последовательности вызовов функций появляется только с использованием монад (см. реализацию doTest выше), а в общем случае вызовы функций могут быть только вложены друг в друга. Это означает, что обычно решение любой задачи в Haskell представляет собой вызов единственной функции, которая в свою очередь вызывает единственную функцию и т.д. Это создает впечатление решения одним махом. В самом деле, в приведенном коде всё решение заключается в вызове единственной функции findLongestIncSeq x. Параллельные вызовы getLengths и cutTail, организованные в doTest нужны только для демонстрации промежуточных состояний исходной последовательности и никоим образом не влияют на результат финального вызова findLongestIncSeq.

Приведенные выше особенности программирования на Haskell требуют более частого использования рекурсивных вызовов, чем в C++, где рекурсия чаще всего заменяется итерацией. Так, функция getPrevLength, которая используется в программе для поиска длины максимальной подпоследовательности, является косвенно рекурсивной благодаря вызову doGetLengths, которая в свою очередь является рекурсивной и косвенно, и явно. Функция cutTail возвращает подпоследовательность исходной последовательности от начала до последнего элемента, которому соответствует максимальная длина возрастающей подпоследовательности. Основная функция findLongestIncSeq является композицией функций reverse, doFindLongestIncSeq и cutTail - это отражено в ее определении.

Нельзя не заметить, что в коде часто употребляется обращение последовательности с помощью reverse. Если учесть, что скорость reverse должна соответствовать O(n), это должно настораживать. Проблема в том, что семантика конструктора списков Haskell предполагает добавление элементов в начало, а не в конец списка, а в нашем алгоритме чаще всего приходится выделять последний элемент подпоследовательности и проходить вниз к началу списка. Таким образом, от reverse можно избавиться, видоизменив исходный алгоритм. Однако проблема обращения списка не такая уж серьезная, как кажется сначала. Дело в том, что reverse не вызывается рекурсивно, а только счётное количество раз, соответственно общая скорость алгоритма остается прежней - O(n^2).

Еще одно важное замечание. Что если мы захотим изменить тип элементов последовательности? Например, захотим искать максимальную подпоследовательность вещественных чисел или строк. В коде на C++ такой вариант предусмотрен с помощью объявления типов VIn и VInElem - стоит поменять тип элемента вектора и всё должно заработать. В коде на Haskell вообще ничего менять не нужно! И это не потому, что в Haskell нет статической проверки типов данных, она там есть, причем более сильная, чем в C++. Просто в данном случае работает параметрический полиморфизм, реализованный в Haskell.
Осталось привести вывод программы на Haskell:
Original: [10,5,89,16,78,67,56,34,12,10]
Lengths:  [1,1,2,2,3,3,3,3,2,2]
Trimmed:  [10,5,89,16,78,67,56,34]
Sequence: [5,16,34]
Original: [67,5,34,89,65,12,90,75,8,9,3]
Lengths:  [1,1,2,3,3,2,4,4,2,3,1]
Trimmed:  [67,5,34,89,65,12,90,75]
Sequence: [5,34,65,75]
Видно, что последний элемент одной и той же тестовой последовательности отличается от результата программы на C++. Это связано с тем, что в C++ варианте последний проход начинался от первого элемента с максимальным значением возрастающей подпоследовательности, а в Haskell варианте - с последнего. Как я уже говорил, могут существовать несколько возрастающих подпоследовательностей максимальной длины, поэтому оба случая являются правильным решением задачи.

среда, 13 апреля 2011 г.

Презентация по языку Haskell

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

суббота, 12 марта 2011 г.

Завершение всех процессов в подгруппе (на примере Tcl)

Предыстория вопроса такова: решил я привести в порядок старый код, написанный в начале 2000-ых  и реализующий набор программ для физического моделирования экспериментальной установки. Ядро программы было написано на фортране с использованием библиотеки Geant3. В результате компиляции и линковки создавались две версии программы - интерактивная и пакетная (batch).

Для удобства использования программ были написаны интерфейсы на Tcl/Tk: большой интерфейс для работы с конфигурацией, графикой, с возможностью запуска обеих версий программ, и малый, который позволял запускать программу в пакетном режиме, следить за ее статусом с помощью прогрессбара (нужно отметить, что программы моделирования и на современных процессорах могут работать в течении суток, а то и недель), и останавливать ее работу при двойном нажатии на специальную кнопку Kill.

Внутри большого интерфейса интерактивная программа моделирования запускалась с помощью открытия канала на запись tcl-командой open, соответственно управление и выход из нее не составляли труда, например для прерывания выполнения программы достаточно было записать в канал, созданный open, последовательность Ctrl-C, а для выхода - последовательность quit. Малый интерфейс мог запускаться самостоятельно, или из большого интерфейса как фоновый процесс.

Поскольку пакетная программа не имела средств для взаимодействия с пользователем, то малый интерфейс запускал ее не с помощью open, а как активный (foreground) процесс. Архитектура запуска процессов малого интерфейса была такова:
  1. В начале работы интерфейса (практически одновременно):
    • Процесс диалога с прогрессбаром и кнопкой Kill (background). В этом диалоге:
      • Отдельный процесс, считывающий результаты программы моделирования, сохраняемые в файле на диске, интерпретирующий их и посылающий с помощью tcl-команды send команды родительскому процессу для отображения статуса выполнения на прогрессбаре (background). В случае прочтения специальной метки end, сигнализирующей о завершении пакетной программы моделирования, данный процесс посылает с помощью send своему родительскому процессу команду exit и завершается сам - такое развитие событий соответствует нормальному завершению работы программы.
    • Процесс пакетной программы моделирования (foreground)
  2. По завершении работы программы моделирования:
    • Процесс диалога, предоставляющего возможность записи результатов программы в базу данных.
Волшебная кнопка Kill должна по замыслу завершить все процессы, включая родительский - т.е. процесс с малым интерфейсом, по желанию пользователя до завершения работы программы моделирования.

Моим старым решением было удалить все процессы в группе процессов:
catch {exec kill 0}
Эта tcl-команда запускает обычную команду оболочки kill 0, что соответствует посылке сигнала TERM текущей группе процессов. Это решение прекрасно работает в случае, если малый интерфейс запускается из терминала, но, к сожалению, если он был запущен из большого интерфейса, то последний тоже завершается, что не является правильным поведением. Проблема в том, что вся совокупность процессов, запущенная как единая команда из терминала, рассматривается как единая группа процессов. Соответственно, kill 0 убивает все процессы-предки вплоть до того, который был запущен из терминала.

К сожалению, создать новую группу процессов на уровне интерфейса оболочки, похоже, не представляется возможным: функция для установки группы процессов setsid() существует только на уровне языка C.

Следующим вариантом было:
set ppid [string trim [exec ps -p [pid] --no-headers -o ppid]]
catch {exec kill -TERM -$ppid}
Здесь ищется pid родительского процесса с помощью обычной команды оболочки ps, команда string trim необходима, т.к. ps форматирует вывод и может предварять pid пробелами. В команде kill -TERM -$ppid формальное указание типа сигнала (-TERM) обязательно, т.к. мы используем отрицательное значение pid. Команда kill с отрицательным pid применяется для посылки сигнала всем процессам в группе процессов, соответствующей pid. Фактически, эта команда ничем не отличается от kill 0, кроме возможности формально указывать некоторую группу процессов, а не текущую, но в нашем случае это неважно. Этот вариант так же хорошо работает, если родительский процесс (малый интерфейс) был запущен из терминала, однако в случае с большим интерфейсом последний не завершается как раньше - на этот раз при нажатии на кнопку Kill  просто ничего не происходит. Дело в том, что при запуске малого интерфейса из большого процесс, соответствующий малому интерфейсу не образует группу, так как он был запущен не из терминала. Соответственно, команда kill -TERM -$ppid завершается аварийно, но, поскольку ее вызов обрамлен командой catch, пользователь не видит вообще никакой реакции.

Следующее решение оказалось окончательным и в итоге завершение пакетных программ нажатием на кнопку Kill заработало и в большом интерфейсе. Идея связана с рекурсивным завершением всех подпроцессов родительского процесса, начиная с нижних, включая подпроцессы процесса, активизировавшего завершение, но исключая его самого. После рассылки сигнала завершения всем указанным подпроцессам, посылается сигнал родительскому процессу, а затем процесс, активизировавший завершение, завершает свою работу с помощью exit. Рекурсивная функция rec_kill() выполняет первую часть алгоритма:
proc rec_kill pid {
    set procs [list]
    foreach x [split [exec ps -o pid,ppid ax | \
                           awk "{if ( \$2 == \"$pid\" ) { print \$1 }}"] \
                     "\n"] {
        lappend procs [string trim $x]
    }
    foreach x $procs {
        rec_kill $x
        if {$x != [pid]} {
            catch {exec kill -TERM $x}
        }
    }
    #puts $procs
}
В первом цикле foreach создается список дочерних процессов процесса-аргумента функции pid. Делается это с помощью следующей команды оболочки:
ps -o pid,ppid -ax | awk "{if ( \$2 == \$pid ) { print \$1 }}"
Во втором цикле происходит рекурсивный вызов rec_kill() самой себя и посылка сигнала завершения всем элементам-процессам, найденным в предыдущем foreach, если те не являются собственным процессом. Pid собственного процесса находится с помощью tcl-команды pid, которая стоит в квадратных скобках (этот синтаксический элемент Tcl называется командной подстановкой), обратите внимание, что эта команда в скобках не имеет никакого отношения к одноименному аргументу функции rec_kill().

Теперь в обработчике двойного клика кнопки Kill нужно выполнить следующее:
set ppid [string trim [exec ps -p [pid] --no-headers -o ppid]]
rec_kill $ppid
exec kill -TERM $ppid
exit
После вызова rec_kill() для родительского процесса (который не трогает собственно родительский процесс) посылаем сигнал для завершения родительскому процессу и выходим с помощью exit.

Одно важное замечание. Будьте очень внимательны с удалением родительского процесса. Родительский процесс может завершиться преждевременно и его pid в дочернем процессе изменится (например, станет 1). В нашем случае, если родительским процессом вдруг станет init, то возможны неприятные последствия, такие как неожиданное завершение пользовательской сессии, ввиду последующего каскадного удаления дочерних процессов init.

Update. Еще 2 важных замечания:
Касательно предыдущего замечания: для того чтобы обезопаситься от случайного завершения процесса, неожиданно ставшего родительским, достаточно в дочернем процессе посылать родителю некий пользовательский сигнал вместо TERM, например сигнал USR1, а в родительском процессе (в том, который нужно завершить) определить обработчик для этого сигнала. В Tcl это можно сделать с помощью команды trap из пакета Expect, для подключения которого в начале программы нужно добавить:
package require Expect
Собственно обработчик сигнала USR1:
trap {exit} USR1
Теперь, если родительский процесс завершится по какой-то причине преждевременно, то новый родительский процесс (скорее всего init) будет игнорировать этот сигнал. Однако это не спасает от каскадного удаления его дочерних процессов функцией rec_kill(). В простейшем случае, чтобы обезопаситься от удаления всех процессов сессии, нужно убедиться, что pid родительского процесса не равен 1.

Второе замечание: как было отмечено, родительский процесс (малый интерфейс) запускает по завершении активного процесса (программы моделирования) процесс-диалог для записи результатов в базу данных. Поскольку rec_kill(), которая посылает сигнал завершения программе моделирования вызывается раньше, чем посылка нашего нового сигнала USR1 (или, как раньше, TERM - это не принципиально), то возможен интересный race condition - малый интерфейс может успеть запустить этот процесс-диалог (так как активная задача была завершена, а сам процесс еще нет), а может и не успеть (если планировщик ОС раньше прибьет малый интерфейс после посылки сигнала из дочернего процесса). Чтобы избежать ненужного вызова процесса-диалога, следует сначала убить родительский процесс, а затем вызвать rec_kill() для его подпроцессов. Однако теперь ситуация осложняется тем, что, поскольку rec_kill() определяет дочерние процессы в своем теле, а сигнал завершения уже был послан родительскому процессу, то он может быть уже завершен и нас может ожидать еще один неприятный race condition, при котором rec_kill() не завершит ничего, либо завершит не те процессы. Чтобы избежать такого развития ситуации, нужно получить список дочерних процессов малого интерфейса до посылки ему сигнала USR1. Теперь обработчик двойного клика кнопки Kill будет выглядеть немного неуклюже:
set ppid [string trim [exec ps -p [pid] --no-headers -o ppid]]
if {$ppid == 1} {exit}
set procs [list]
foreach x [split [exec ps -o pid,ppid ax | \
                       awk "{if ( \$2 == \"$ppid\" ) { print \$1 }}"] \
                 "\n"] {
    lappend procs [string trim $x]
}
exec kill -USR1 $ppid
foreach x $procs {
    rec_kill $x
    if {$x != [pid]} {
        catch {exec kill -TERM $x}
    }
}
exit
, но эту неуклюжесть легко устранить введением вспомогательных функций.

суббота, 5 февраля 2011 г.

Подсветка в vim на основе тегов ctags (perl скрипт прилагается)

Из серии было и стало (картинки кликабельны):


Итак, наша задача - обеспечить подсветку в vim не только ключевых слов, но, по возможности, всего исходного кода: собственных функций, классов, пространств имен, переменных и т.д. Эта задача хорошо решается в vim-скрипте ctags_highlighting. Как ясно из названия, этот скрипт использует базу данных ctags (строит сам или берет уже готовую). В состав ctags_highlighting входит питоновский скрипт mktypes.py, который проделывает основную работу, главным результатом которой является vim-скрипт со списком групп подсветки, в случае языков C и C++ этот файл будет называться types_c.vim. Группы подсветки в этом файле не являются стандартными, соответственно используемая цветовая схема должна их поддерживать. Автор ctags_highlighting предлагает собственную цветовую схему bandit. При использовании другой цветовой схемы, ей нужно "сообщить" о новых группах подсветки. В разных схемах это делается по-разному. Я использую цветовую схему xterm16. Для того, чтобы xterm16 знала о новых группах подсветки, я добавил в нее следующие определения:
    "my highlight groups for ctags_highlight
    call s:hi( 'Namespace'   , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Function'    , 'none', 'cyan'      , 'none'      )
    call s:hi( 'DefinedName' , 'none', 'cyan'      , 'none'      )
    call s:hi( 'EnumerationValue'  , 'none', 'cyan'      , 'none'      )
    call s:hi( 'EnumeratorName', 'none', 'cyan'      , 'none'      )
    call s:hi( 'Member'      , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Union'       , 'none', 'cyan'      , 'none'      )
    call s:hi( 'GlobalVariable', 'none', 'cyan'      , 'none'      )
    call s:hi( 'LocalVariable', 'none', 'cyan'      , 'none'      )
    call s:hi( 'GlobalConstant', 'none', 'cyan'      , 'none'      )
    call s:hi( 'Conditional' , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Repeat'      , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Label'       , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Exception'   , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Operator'    , 'none', 'cyan'      , 'none'      )
    call s:hi( 'PreCondit'   , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Include'     , 'none', 'cyan'      , 'none'      )
    call s:hi( 'Macro'       , 'none', 'cyan'      , 'none'      )
    call s:hi( 'StorageClass', 'none', 'green'     , 'none'      )
    call s:hi( 'Class'       , 'none', 'green'      , 'none'      )
    call s:hi( 'Structure'   , 'none', 'green'      , 'none'      )
    "my highlight groups from after/syntax/c.vim
    call s:hi( 'Delimiter'   , 'none', 'green'      , 'none'      )
    call s:hi( 'Boolean'     , 'none', 'green'      , 'none'      )
    "my ColorColumn highlight
    call s:hi( 'ColorColumn' , 'none', 'none'      , 'cyan'      )
Эти объявления следует разместить где-нибудь среди похожих объявлений в ~/.vim/colors/xterm16.vim. Кроме объявлений, связанных с ctags_highlighting, здесь добавлены группы подсветки для скрипта after/syntax/c.vim, а также подсветка для вертикальной колонки, которая появилась с выходом в vim 7.3 и в xterm16 пока отсутствует. Конкретные цвета (cyan, green и т.д.) здесь не важны, так как я переопределяю их в файле .vimrc:
syntax on
let xterm16_brightness = 'high'
let xterm16_colormap = 'soft'
let xterm16fg_Comment = 'grey'
let xterm16fg_Identifier = '#87ffaf'
let xterm16fg_Namespace = '#df875f'
let xterm16fg_Function = '#87ffaf'
let xterm16fg_Statement = '#87afdf'
let xterm16fg_EnumerationValue = '#5fafdf'
let xterm16fg_EnumeratorName = '#00afdf'
let xterm16fg_GlobalConstant = '#87875f'
let xterm16fg_GlobalVariable = '#87875f'
let xterm16fg_DefinedName = 'purple'
let xterm16fg_LocalVariable = '#00df87'
let xterm16fg_Class = '#afff87'
let xterm16fg_Structure = '#dfffaf'
let xterm16fg_Member = '#00af87'
let xterm16fg_Conditional = '#5fafff'
let xterm16fg_Repeat = '#5fafff'
let xterm16fg_Label = '#5fdfff'
let xterm16fg_Exception = '#ff5f87'
let xterm16fg_PreCondit = '#af5faf'
let xterm16fg_Include = '#df5f00'
let xterm16fg_Macro = 'purple'
let xterm16fg_StorageClass = '#5faf5f'
let xterm16fg_Operator = '#ffafaf'
let xterm16fg_Delimiter = '#5fffdf'
let xterm16fg_Boolean = '#87afdf'
let xterm16bg_ColorColumn = '#949494'
if $DISPLAY != '' && !has('gui_running')
    let xterm16bg_Normal = 'none'
endif
colo xterm16
Теперь для обновления подсветки тегов можно воспользоваться командами, предоставляемыми плагином ctags_highlighting. К сожалению, на мой взгляд, это не самое лучшее решение. И причин тому несколько. Прежде всего, я не хочу хранить файлы типа tags и types_c.vim в рабочей директории. Во-вторых, в ctags_highlighting нет выраженной модульности, в частности, если я работаю с некой библиотекой (или несколькими библиотеками), то хочу, чтобы теги используемой библиотекой и моего рабочего кода были четко разделены. Это позволит быстро перестраивать теги для рабочего кода, не изменяя, а только добавляя в файл подсветки теги из библиотеки. В-третьих, ctags часто ошибается, что приводит к появлению псевдотегов типа const, а также переопределению объявлений используемой библиотеки как локальных переменных рабочего кода (если установлено использование локальных переменных).
Представленный здесь скрипт основан на использовании mktypes.py и призван обойти указанные недостатки. Для просмотра опций достаточно набрать имя скрипта MakeVimHlTags без аргументов. В скрипте используется понятие проекта; проекты расположены в директории ~/opt/tags/. В сущности, проект напрямую соответствует модулям в том смысле, о котором говорилось выше. То есть, если в собственном исходном коде используются библиотеки lib1 и lib2, и есть желание подсветить теги из этих библиотек, то можно создать два проекта lib1 и lib2. Для этого следует перейти в каталоги с исходным кодом этих библиотек и выполнить команды:
MakeVimHlTags -r -e const,true,false -p lib1
и
MakeVimHlTags -r -e const,true,false -p lib2
Скорее всего библиотеки находятся в системных директориях и запускать скрипт придется от рута, поскольку mktypes.py создает временные файлы tags и types_c.vim, которые будут удалены по окончании работы скрипта. К счастью, обновлять теги системных библиотек достаточно только при их обновлении. Опция -r означает, что теги будут искаться во всех поддиректориях, начиная с указанных (или как здесь - с текущей). В опции -e перечислены через запятую теги, которые следует игнорировать. В моем случае ctags пытался переопределить слова const, false и true, поэтому я указал, что их следует игнорировать. Опция -e поддерживает простейшие шаблоны, в которых символ "точка" представляет собой последовательность любых символов кроме пробельных; точка может находиться в начале или конце шаблона. Например шаблон "Lib1." обозначает все теги, которые начинаются с "Lib1". Опция -p указывает название проекта.
Теперь следует создать теги для собственного исходного кода. Пусть наш проект называется Proj и использует библиотеки lib1 и lib2. Для того, чтобы добавить в проект теги из другого проекта используется опция -a:
MakeVimHlTags -r -l -a lib1,lib2 -e Lib1.,Lib2. -p Proj
Опция -l нужна для того, чтобы ctags сгенерировал теги для локальных переменных. Это хорошая идея для собственного кода, но плохая - для кода библиотек, поэтому мы не использовали ее для построения тегов проектов lib1 и lib2. В принципе, в случае с C++, теги для локальных переменных не всегда хороши (в частности, если в коде часто используется инициализация в стиле конструктора), поэтому использовать опцию -l следует с осторожностью. С помощью опции -e мы удаляем все теги, которые начинаются с "Lib1" и "Lib2": поскольку в нашем проекте используются имена из lib1 и lib2, то, особенно если включена опция -l, возможны ложные срабатывания ctags для таких имен.
После выполнения трех команд в директории ~/opt/tags/ появятся 3 новых файла: lib1_c.vim, lib2_c.vim и Proj_c.vim. Эти файлы содержат команды для vim, которые необходимы для подсветки тегов, при этом файл Proj_c.vim будет содержать теги из lib1_c.vim и lib2_c.vim.
Осталось самое простое: сделать так, чтобы при открытии файла из рабочей директории проекта Proj скрипт Proj_c.vim выполнялся автоматически. Для этого в файле .vimrc можно ввести следующую команду:
if (filereadable($HOME . "/opt/tags/Proj_c.vim"))
    autocmd BufRead,BufNewFile */part/of/path/to/Proj/* 
        \ execute 'source' . $HOME . "/opt/tags/Proj_c.vim"
endif
где /part/of/path/to/Proj/ - часть относительного пути к рабочей директории проекта Proj.
Для обновления тегов подсветки достаточно выполнить последнюю приведенную команду MakeVimHlTags, при этом теги проектов lib1 и lib2 не перестраиваются, а просто включаются из готовых файлов.

Скрипт MakeVimHlTags можно взять здесь.