четверг, 28 февраля 2008 г.

Разединяем строки...обьединяем строки.

Итак...задачка. Есть массив строк. Каждую строку в массиве нужно разделить по указанному разделителю, потом все полученные строки обьединить по еще одному указанному разделителю.

Если не очень понятно - нужно из таких строк: "word1-word2", "word3-word4", "word5-word6"
получить вот такую строку:
word1:word2:word3:word4:word5:word6

C#:

Увы, стандартная функция Join не работает с IEnumerable. Поэтому пришлось написать свою. Также нет стандартной функции reduce. Поэтому пришлось написать свою. Это не так уж и важно, поскольку к выводам не относится. Итак, код:

Способ1:

string[] a = { "word1-word2", "word3-word4", "word5-word6" };

Console.WriteLine(":".join(a.SelectMany(x=>x.Split('-'))));


Способ 2:

string[] a = { "word1-word2", "word3-word4", "word5-word6" };

Console.WriteLine(a.SelectMany(x => x.Split('-')).reduce((x, y) => x + ":" + y));



Python. Тут ничего дописывать не пришлось.

Способ 1:

a = ["word1-word2", "word3-word4", "word5-word6"]

print ":".join([x for word in a for x in word.split('-')])


Способ 2:

a = ["word1-word2", "word3-word4", "word5-word6"]

print reduce(lambda x,y:x+":"+y,[x for word in a for x in word.split('-')])



К чему это я...
С++, решение "в лоб"

    vector<string> w;

    w.push_back("word1-word2");

    w.push_back("word3-word4");

    w.push_back("word5-word6");

 

    string result;

 

    for(vector<string>::const_iterator v = w.begin();v!=w.end();++v)

    {

        const vector<string>& w1 = split_string(*v,"-");

        for(vector<string>::const_iterator v1 = w1.begin();v1!=w1.end();++v1)

        {

            if(!result.empty())

                result+=":";

            result+=*v1;

        }

    }

    cout << result << endl;


Попробуем функционально? "Без проблем":

    vector<string> w;

    w.push_back("word1-word2");

    w.push_back("word3-word4");

    w.push_back("word5-word6");

 

    cout << join_string(select_many(w,bind(split_string,_1,("-"))),":") << endl;

Почему "без проблем" в кавычках...?
Потому что сначала я попытался достигнуть результата используя только std::for_each и bind. Не получилось. Пришлось написать (ну помимо join_string и split_string функцию select_many.

template<class _Container,class _Fn1> inline

_Container select_many(const _Container& container, _Fn1& _Func)

{   

    _Container res;

    for(_Container::const_iterator v = container.begin();v!=container.end();++v)

    {

        _Container tmp = _Func(*v);

        for(_Container::const_iterator v1 = tmp.begin();v1!=tmp.end();++v1)

            res.push_back(*v1);

    }

    return res;

}



В принципе по своей сути она похожа на аналогичные в C# и Python, но увы - фактически до них ей ну очень далеко. Разница огромна, даже расписывать не буду.

К чему это я...

Если бы у меня была возможность выбрать какую возможность добавить в следующую версию С++ я бы пожалуй выбрал питоновские генераторы (они же шарповые IEnumerable).

среда, 27 февраля 2008 г.

Visual Studio Gallery

Visual Studio Gallery - сборник расширений и дополнений для Visual Studio

производительность STL

По наводке - STL vector performance

Выводы неутешительны - std::vector в среднем в 30 (ТРИДЦАТЬ) раз медленнее чем работа с чистым массивом на C (ну либо голом C++ без STL).

Но это только на первый взгляд.

1. Тестирование для STL pre-alloc было не совсем правильным. Нужно использовать reserve.
2. Размер NUM_ITERATIONS имеет значение...
3. Способ реаллокации памяти имеет значение...

Я повторил эти тесты, добавил reserve в код для "STL pre-alloc". А также расширил код, протестировав boost::array и boost::scoped_array.

Также я протестировал для различных значений NUM_ITERATIONS (от 10000 до 150000 с шагом 10000).

Результат (только для Average, CPI)

STL re-alloc  - Average, CPI: 65
C re-alloc - Average, CPI: 62

STL pre-alloc - Average, CPI: 10
C pre-alloc - Average, CPI: 9
boost::array - Average, CPI: 2
boost::scoped_array - Average, CPI: 10


Забавным здесь является не только то что нет разницы между "STL pre-alloc", "C pre-alloc",boost::array,boost::scoped_array.

Нет заявленной разницы между "STL re-alloc" и "C re-alloc". Я удивился, поскольку предполагал что разница будет... Удивление прошло когда я начал _уменьшать_ значение NUM_ITERATIONS. При NUM_ITERATIONS равном 5000 и меньше возникла разница в 2 раза.

Откуда берется эта разница? Смотрим в реализацию и видим что код реалокации памяти на С++ всегда выделяет новый больший блок памяти, потом копирует туда старый блок. Как по мне это имеет смысл в свете возможности использования vector с не POD типами.

Когда я изменил код реалокации в "C re-alloc" на:

                // Match STL vector allocation algorithm

                int* new_work =  (int *)malloc((size + size / 2) * sizeof(int));

                for ( long c = 0; c < array_size; ++c ) new_work[c] = work[c];

                free(work);

                work = newwork;

                size = size + size / 2;

разница в производительности между "C re-alloc" и "STL re-alloc" исчезла навсегда.

Еще о забавном тестировании производительности - C plus plus:Modern C plus plus:Vectors

Читаем секцию Safe & Fast, много смеемся...
The std::vector version builds its array 256 times larger, and yet is roughly 60 times faster.

Код на "С" с которым они "сравнивали" производительность (фрагмент с реалокацией массива)

void append_to_array(long *&array, long &array_size, long what) {

        long *newarray = new long[array_size+1];

        for ( long i = 0; i < array_size; ++i ) newarray[i] = array[i];

        newarray[array_size] = what;

        delete[] array;

        array = newarray;

        ++array_size;

}



Вывод - если вы работаете с POD типами, хотите работать с динамическим массивом и вам нужна максимальная производительность - пишите на С напишите свою реализацию vector :). А можете просто использовать "reserve".

пятница, 22 февраля 2008 г.

Project Euler, problem 78

4 дня...4 дня...4 дня я изобретал формулу Эйлера, потом переоткрывал пентагональные числа...потом оптимизировал все это...

четверг, 21 февраля 2008 г.

А вот за что я не люблю пропагандистов ФП

Так это за некорректные сравнения.

Статья Making Haskell faster than C!

В статье приводится пример оптимизации кода на Haskell таким образом что его выполнение происходит быстрее чем выполнение кода написанного на С. Это было бы приятно и интересно...если бы исходный код на С и на Haskell был бы хоть примерно эквивалентен.

Задача простая - подсчет количества слов в файле. Слова - это части текста отделенные пробелами/табуляцией/переносом строк.

Вот исходный код на С:

int main() {

    int i = 0;

    int c, last_space = 1, this_space;

    while ((c = getchar()) != EOF) {

        this_space = isspace(c);

        if (last_space && !this_space)

            i++;

        last_space = this_space;

    }

    printf("%i\n", i);

    return 0;

}



Вот исходный код на Haskell:

main = print . length . words =<< getContents

С момощью оптимизатора автор добивается того чтобы код на Haskell выполнялся быстрее кода на С. Потрясающий результат, если бы не одно "но".

Программа на С сделана явно с одной целью - написать ее самым медленным способом. Как добиться того чтобы программа выполнялась максимально медленно? Найти самую медленную опрацию и испльзовать ее максимально часто. В данном случае самая медленная операция это чтение из файла/потока. Как использовать ее максимально часто? Читать посимвольно...

Это ясно и понятно большенству программистов на С\С++. Т.е. программисты на С\С++ видят что автор сделал совершенно некорректное сравнение. Сознательно сделав код на С максимально медленным. Автор жулик.... и неважно сделал он это сознательно или нет.

В результате вместо того чтобы заинтересовать программистов на С\С++ возможностями Haskell в частности и ФП в целом мы получаем отторжение.

"Haskell is pure functional langues" - зачем это нужно.

Кажется я наконец разобрался с вопросом почему программисты на haskell настойчиво подчеркивают тот факт что haskell так называемый pure ("чистый") язык. И причем здесь side effects.

Зачем вообще нужны эти "чистые" функции?

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

Пример -
int f(int x) { return 3+x;} - чистая функция
int g(int x) { return random()+x;} - не чистая функция

Как видно в С/С++ чистые функции тоже возможны. Более того, если мы пробежимся по любому коду на С/С++ то мы увидем что большенство функций по крайней мере выглядят как "чистые". Да и большенство алгоритмов записанных на С/С++ неявно предполагает что на одни и те же входные данные мы будем получать один и тот же результат. Иначе программировать было бы сложновато...

Разница между С/С++ и Haskell состоит в том что в Haskell нет (пока забудем о монадах) возможности записать не "чистую" фукнцию.

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

Ну а на второй...В С\С++ нет возможности явно указать является ли функция "чистой" или нет. И все функции по умолчанию считаются не "чистыми".

Допустим есть язык в котором такая возможность есть (Haskell). Что это дает собственно языку? Да толком то ничего... Так зачем же...

Тут возникает вопрос - а что это дает компилятору? А вот компилятору это дает многое. В частности это дает возможность компилятору оптимизировать написанный алгоритм. С использованием "ленивости", отложенных вычислений и прочих плюшек. В идеале получив на вход базовый алгоритм состоящий из вызовов "чистых" функций компилятор(путем оптимизации) может составить некий "идеально быстрый" алгоритм. Т.е. компилятор языка воспринимает подаваемую ему на вход программу как некую функцию над которой он может производить оптимизирующие действия. Банальный пример - получив на вход функцию
(функция получающая два указателя на функции и число и возвращающая число, пишу в псевдокоде)
int f( g(x),k(x),x)
{
return g(x)*g(x)+2*g(x)*k(x)+k(x)*k(x);
}

компилятор может не особо долго думая преобразовать ее в нечто вроде

int f( g(x),k(x),x)
{
int temp = g(x)+k(x);
return temp*temp;
}

Возможна ли такая оптимизация компилятором в С/С++? Нет, компилятор С/С++ не может быть уверен что вызовы g(x) всегда возвращают одни и те же значения.

Т.е. в языке в котором можно явно указать что функция является "чистой" становится возможной оптимизация на уровне алгоритма.

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

среда, 20 февраля 2008 г.

Project Euler, problem 117

What I really like about "Project Euler" competition is - sometimes problems that looks very hard have very easy solution. Actually they may be solved using "p&p" (paper and pencil)programing language.

Problem 117 looks beautiful. Its very easy to make complex recursive solution and a bit harder to think and make very simple solution without any recursion.

Here is mine:

LONGLONG euler_117()

{

    map<int,LONGLONG> _set;

    _set[0]=1;_set[1]=1;_set[2]=2;_set[3]=4;

    for(int i=4;i<=50;++i)

        _set[i]=_set[i-1]+_set[i-2]+_set[i-3]+_set[i-4];

 

    return _set[50];

}

суббота, 9 февраля 2008 г.

Project Euler Problem 145 - slap in the face...

Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (10^9)?


Sounds simple? Sure...brute force it. Just like I do. Then go check the other solutions and feel yourself stupid bruteforcer...

This problem can be solved analytically.

пятница, 8 февраля 2008 г.

Find if digits in two numbers are permutations of each other

I was working on Project Euler problem 72

One subtask was to create function to check where numbers "a" and "b" are permutations of each other...
When I finish this problem and check other solutions on forum...I found few C++ solutions. The realization of this function was awful..and extremely slow.

Here is mine:

bool is_permutation(int a,int b)

{

    char test1[10]={0};

    char test2[10]={0};

    while(a>0 && b>0)

    {

        ++test1[a%10];

        ++test2[b%10];

        a/=10;b/=10;

    }

    if(a!=b)

        return false;

    return memcmp(test1,test2,10)==0?true:false;

}



There was one really close realization...
(you can ++test1[a%10];--test2[b%10]; and at the end check if test1=={0} )

But the others...

1st (O(n^2) on sorting numbers... cmon man can't you just qsort then):

#define CAP_LENGTH 8

inline int permutation(int a, int b){

    static int a_digits[CAP_LENGTH];

    static int b_digits[CAP_LENGTH];

    static int i,j, a_length, b_length;

    i=0;

    do{

        a_digits[i]=a%10;

        i++;

    } while( (a/=10)!=0 );

    a_length=i;

    i=0;

    do{

        b_digits[i]=b%10;

        i++;

    } while( (b/=10)!=0 );

    if(a_length!=i)

        return 0; //even digit number differ between a and b

    b_length=i;

    for(i=0; i<a_length; i++){

        // cycle on all a digits

        for (j=0; j<b_length; j++){

            // cycle on all the (remaining, valid) b digits

            if(a_digits[i]==b_digits[j]){

                b_digits[j]=-1;

                break;

            }

        }

        if(j==b_length)

            return 0;

    }

    return 1;

}



2nd (gogo STL...):

bool are_permutations (int num1, int num2)

{

    /* Must have the same number of digits. */

    if ((int) log10 (num1) != (int) log10 (num2))

        return false;

 

    std::deque<char> digits1, digits2;

    int sorted1 = 0, sorted2 = 0;

 

    while (num1 > 0)

    {

        digits1.push_back (num1 % 10);

        num1 *= 0.1;

    }

 

    while (num2 > 0)

    {

        digits2.push_back (num2 % 10);

        num2 *= 0.1;

    }

 

    std::sort (digits1.begin (), digits1.end ());

    std::sort (digits2.begin (), digits2.end ());

 

    for (std::deque<char>::iterator i = digits1.begin (); i != digits1.end ();

        ++i)

        sorted1 = sorted1 * 10 + *i;

 

    for (std::deque<char>::iterator i = digits2.begin (); i != digits2.end ();

        ++i)

        sorted2 = sorted2 * 10 + *i;

 

    return sorted1 == sorted2;

}



3rd (and the winner is...sprintf, qsort,strlen...):

bool perm(int a, int b)

{

    static char b1[1024];

    static char b2[1024];

 

    sprintf(b1, "%d", a);

    sprintf(b2, "%d", b);

 

    int l1 = strlen(b1);

    int l2 = strlen(b2);

 

    if (l1 != l2)

        return false;

 

    qsort(b1, l1, 1, cmp);

    qsort(b2, l2, 1, cmp);

 

    return !strcmp(b1, b2);

}

среда, 6 февраля 2008 г.

About one math puzzle...

If you feel your algorithm is too complex - you are right. Find another one, more simple.
If you feel your algorithm is too ugly - you are right. Find another one,more beautiful solution exists.

Project Euler, Problem 73

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8 (*)

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 10,000?


Why was this task interesting for me? Only because using mathematical knowledge I come to wrong solution...

So... Sequence (*) is so called Farey Sequence. One of the characteristics of this sequence:
let p/q, p'/q', and p''/q'' be three successive terms in a Farey series.
then p'/q'==(p+p'')/(q+q'')

It comes from that characteristics that if you have two terms in a Farey series you can produce p'/q', such as p/q<p'/q'<p''/q'' and
p'=p+p''
q'=q+q''
And then normalize p' and q' so HCF(p',q')=1

So we come to simple algorithm - take border elements (p/q=1/3,p''/q''=1/2), produce one more element from the sequence p'\q', then look how may more elements between (p/q,p'/q') and between (p'/q',p''/q'').
The only question - when we should stop? The first answer come to mind - when q'>limit.

So here is first solution:
LONGLONG fractions_between(int a,int c,int b,int d,int limit)
{
int _a1 = a+b;
int _c1 = c+d;
normalize(_a1,_c1);
LONGLONG result=0;
if(_c1>limit)
return 0;
return 1+fractions_between(a,c,_a1,_c1,limit)+fractions_between(_a1,_c1,b,d,limit);
}

LONGLONG euler_73()
{
return fractions_between(1,3,1,2,10000);
}


I run it for (1/3,1/2) and 8 as a limit and got 3, just as expected.
fractions_between(1,3,1,2,8)==3

So I run it for 10000 and got...stack overflow :).

Ok, some optimization to get rid of stack overflow...but when I check my result I got only "Sorry, but the answer you gave appears to be incorrect". I start to study the logic of my code and found that the logic was fine...

So if my answer is wrong the problem is in algorithm...but it so simple! I check again my assumption about algorithm - we should stop when q'>limit... Is it really true? Let's check sequence (1/8, 1/7, 1/6, 1/5) with limit 8. Elements 1/8 and 1/5 produce 2/13, so we should stop? No, because 1/8 and 2/13 produce 1/7, and 1/7 is tolerated fraction. So...when we should stop?

Ok, better assumption - we should stop when p/q and p''/q'' can't produce such p'/q' (and all other nested elements) such as q'limit...

Sounds logical...but... at this moment I have a filling that something is really wrong. The solution became too complex. It takes too long to produce the result. There must be a more simple solution.

And I usually trust myself...so I delete my solution and start to think about another one. Few minutes later it come to my mind:)

This leads me to common principle I write at the beginning.