Полезный алгоритм - Modular exponentiation

Суть алгоритма в вычислении a^b mod c без вычесления значения a^b.

Подробное описание алгоритма

(Псевдо)код

Bignum modpow(Bignum b, Bignum e, Bignum m) {

 

   Bignum result = 1;

 

   while (e > 0) {

      if ((e & 1) == 1) result = (result * b) % m;

      e >>= 1;

      b = (b * b) % m;

   }

   return result;

}

Поверь я сердцем чист. Враньем по горло сыт.

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



Мое отношение к произошедшему совпадает на 100% с такими выводами:

Что делать Супу: повесить большую надпись "Простите нас", ввести обратно бесплатные аккаунты и заняться делом.

Взято отсюда (ссылка на архив поскольку автор удалил журнал. толи в знак поддержки акции, толи еще по каким причинам)

Синхронизация файлов через интернет

Новый сервис - dropbox, пока в стадии beta тестирования. Видео впечатляет. Как всегда в подобных случаях вопрос - почему это не было сделано раньше.

Как я МАК полюбил, аутотренинг

Это серией заметок "Как я Мак полюбил" я хочу выработать в себе любовь к продуктам Apple в целом и к макам в частности. К тому времени, как это случится, мои финансы теоритически должны достигнуть той планки, при которой я буду способен обеспечить себя МакБуком той или иной модели.

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

Project Euler, problem 127

Чем мне нравится Project Euler - практически на любой задаче можно что-то для себя открыть/переоткрыть.

The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.
We shall define the triplet of positive integers (a, b, c) to be an abc-hit if:
1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
2. a < b
3. a + b = c
4. rad(abc) < c
For example, (5, 27, 32) is an abc-hit, because:
1. GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
2. 5 < 27
3. 5 + 27 = 32
4. rad(4320) = 30 < 32
It turns out that abc-hits are quite rare and there are only thirty-one abc-hits for c < 1000, with ∑c = 12523.
Find ∑c for c < 110000.

После некоторого достаточно бесплодного с точки зрения результата размышления(о котором тоже в принципе интересно было бы написать) я пришел к решению проблемы практически "в лоб" - перебираем все числа a b c такие что a<b,a+b=c и с<110000
и проверяем выполняются ли для них условия 1. и 4.
Код:

    int count = 0;

    ulong64  sum = 0;

    for(int a=1;a<limit ;++a){

        int b = a+1;//a < b

        int c = a+b;//c = a + b

        while(c<limit){

            if( ! (cross(dpf[a],dpf[b]) || cross(dpf[a],dpf[c]) || cross(dpf[b],dpf[c]))){//GCD(a, b) = GCD(a, c) = GCD(b, c) = 1

                if(rad[a]*rad[b]*rad[c]<c_long){//rad(abc) < c

                    ++count;

                    sum+=c;

                }

            }

            c = a+(++b);

        }

    }

Здесь dpf[i] - массив из простых делителей числа i (например для 504 это будет [2,3,7])
rad[i] - произведение все чисел из массива dpf[i].
Функция cross(a,b) возвращает false если массивы a и b не пересекаются, т.е. нет такого числа i входящего одновременно в оба массива.
соответственно
if( ! (cross(dpf[a],dpf[b]) || cross(dpf[a],dpf[c]) || cross(dpf[b],dpf[c]))){
соответствует условию
1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
Далее из этого же условия следует что rad(a*b*c) == rad(a)*rad)b)*rad(c), соответственно
if(rad[a]*rad[b]*rad[c]<c_long)
соответствует условию
4.rad(abc) < c

Вообщем надеюсь логика более менее понятна. На тестовом условии (для c<1000 count == 31 и sum == 12523) этот подход отрабатывал. Оставалась мелочь - запустить его же для c<110000.

Первая проблема была - ну оооочень долго выполняется. Когда спустя минут 10 я добрался до a=4000 я прервал выполнение.

Первая попытка оптимизации - если а и b четные их можно не проверять. Поэтому добавилось условие
if(a%2 == 1 || b%2 == 1)

Все равно очень долго...да и явно неправильный результат.
В чем проблема? переполнение... переполнение может происходить при проверке условия rad(a)*rad)b)*rad(c). Переходим к unsigned long long. Результат вроде становится правильным...но все равно ооочень долго.

Хм...хм...
Возможно кому-то решение видно сразу. Я думал достаточно долго. Даже было желание вновь придумать другой подход.
В результате прогнав несколько тестов (на меньшем значении c) я понял в чем дело.
Во внутреннем цикле используются два условия - 1. и 4. Результат должен удовлетворять обеим условиям. С этой точки зрения условия равнозначны. Но - они не равнозначны с точки зрения времени выполнения и частоты срабатывания.
Условие 4. срабатывает реже чем условие 1. И в то же время выполняется намного быстрее.

Поэтому все что нужно - поменять условия 1. и 4. местами...
Результат (я убрал переход к unsigned long long для наглядности):

    int count = 0;

    ulong64  sum = 0;

    for(int a=1;a<limit ;++a){

        int b = a+1;//a < b

        int c = a+b;//c = a + b

        while(c<limit){

            if(a%2 == 1 ||  b%2 == 1){

                if(rad[a]*rad[b]*rad[c]<c_long){//rad(abc) < c

                    if( ! (cross(dpf[a],dpf[b]) || cross(dpf[a],dpf[c]) || cross(dpf[b],dpf[c]))){//GCD(a, b) = GCD(a, c) = GCD(b, c) = 1

                        ++count;

                        sum+=c;

                    }

                }

            }

            c = a+(++b);

        }

    }

Время выполнения стало 29 секунд.

Выводы.
Порядок выполнения проверок имеет значение... Вывод в общем то очевидный. Но про него часто забывают.

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

Есть два отсортированных по возрастанию массива целых чисел. Определить пересекаются ли эти массивы за время O(n+m), где n и m - длина массивов.

Монополия, стандарты, IE

Только факты.
CSS1 спецификация получила статус рекомендации в 1996 году. Первый броузер который поддерживал CSS1 был Internet Explorer 3.
Первый броузер который полностью поддерживал CSS1 был Internet Explorer 5.0 дла Мac, и вышел он в марте 2000 года.
Опера начала более-менее поддерживать CSS1 в 1998 году.
Ни один броузер не имел нормальной поддержки CSS2. Ни один и никогда. Именно это вынудило W3C пересмотреть CSS2 и выпустить CSS2.1

CSS2.1 получил статус Candidate Recommendation в феврале 2004 года, но в июне 2005 года его статус был изменен на "черновик". Статус Candidate Recommendation обратно он получил в июле 2007 года.

По состоянию на июль 2006 года (на эту дату ссылается статья в википедии) ни один броузер не поддерживал полностью CSS2.1. Ни один, включая FireFox 1.5 в котором была значительно улучшенна поддержка CSS2.1
Firefox 1.0 вышел в ноябре 2004 года.
Internet Explorer 6 вышел в августе 2001 года.

Firefox 2.0 вышел в конце 2006 года.
Internet Explorer 7 вышел в октябре 2006 года.

Firefox 2.0 не проходит acid2. Internet Explorer 7 не проходит acid2.
Выход Internet Explorer 8 и FireFox 3 планируется на 2008 год.
Internet Explorer 8 и FireFox 3 будут проходить acid2.

По состоянию на январь 2008 года IE7 занимает 43% рынка броузеров, IE6 - 32%, FF2 - 16%, SF 3 - 4%, FF1.x и IE5 меньше 0.5%.

Принцип 80/20

Думаю если не все то многие знакомы с этим принципом. Формулируется он обычно так - "20% усилий приносят 80% результата". Ну или "в любом сообществе 20% нормальные люди. Ну а остальные...".
Всегда считал что это такая "народная мудрость".
Оказывается нет. Оказывается у этого принципа есть автор, и зовут его Вильфредо Парето, а сам принцип называется законом Парето. И был..эээ..открыт... в 1897 году.

Важнейшие положения закона Парето

• Значимых факторов немного, а факторов тривиальных множество — лишь единичные действия приводят к важным результатам.


• Большая часть усилий не даёт желаемых результатов.


• То, что мы видим, как правило отличается от того, что мы получаем, — всегда существуют скрытые силы.


• Обычно слишком сложно и утомительно разбираться в том, что происходит, а часто это и не нужно: необходимо лишь знать — работает ли Ваша идея или нет, и изменять её так, чтобы она заработала, а затем поддерживать ситуацию до тех пор, пока идея не перестанет работать.


• Большинство удачных событий обусловлено действием небольшого числа высокопроизводительных сил; большинство неприятностей связано с действием небольшого числа высокодеструктивных сил.


• Бо́льшая часть действий, групповых или индивидуальных, являет собой пустую трату времени. Они не дают ничего реального для достижения желаемого результата.

О подготовке к интервью в Google

Get that job at Google

А неплохой у них отбор...
Выдержки:

Algorithm Complexity: you need to know Big-O. It's a must. If you struggle with basic big-O complexity analysis, then you are almost guaranteed not to get hired. It's, like, one chapter in the beginning of one theory of computation book, so just go read it. You can do it.

Sorting: know how to sort. Don't do bubble-sort. You should know the details of at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.

For God's sake, don't try sorting a linked list during the interview.

Hashtables: hashtables are arguably the single most important data structure known to mankind. You absolutely have to know how they work. Again, it's like one chapter in one data structures book, so just go read about them. You should be able to implement one using only arrays in your favorite language, in about the space of one interview.

Trees: you should know about trees. I'm tellin' ya: this is basic stuff, and it's embarrassing to bring it up, but some of you out there don't know basic tree construction, traversal and manipulation algorithms. You should be familiar with binary trees, n-ary trees, and trie-trees at the very very least. Trees are probably the best source of practice problems for your long-term warmup exercises.

You should be familiar with at least one flavor of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree. You should actually know how it's implemented.

You should know about tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.

You might not use trees much day-to-day, but if so, it's because you're avoiding tree problems. You won't need to do that anymore once you know how they work. Study up!

Graphs

Graphs are, like, really really important. More than you think. Even if you already think they're important, it's probably more than you think.

There are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list), and you should familiarize yourself with each representation and its pros and cons.

You should know the basic graph traversal algorithms: breadth-first search and depth-first search. You should know their computational complexity, their tradeoffs, and how to implement them in real code.

You should try to study up on fancier algorithms, such as Djikstra and A*, if you get a chance. They're really great for just about anything, from game programming to distributed computing to you name it. You should know them.

Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it's about a 50-50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can't think of a way to solve it using graphs before moving on to other solution types. This tip is important!

Project Euler, problem 107

Project Euler, problem 107 - переизобретая алгоритмы на графах...
Интересная задача, особенно для тех кто не знает изначальный алгоритм. Собственно для таковых состоять она будет в том чтобы (пере)изобрести нужный алгоритм.

Мой первый вариант был очень похож на Prim's algorithm, но я просто не поверил(и не смог доказать) что он ведет к верному результату.
Финальный вариант больше подходил на алгоритм Дейкстры.

А в целом данная задача называется задачей нахождения Minimum spanning tree и решается с помощью алгоритмов Prim's algorithm и Kruskal's algorithm. Первоначальным же алгоритмом для этого класса задач является Borůvka's algorithm. Что характерно - все три алгоритма принадлежат к классу "жадных" алгоритмов.

Просто так

Задачка -

имеется возрастающая последовательность из n разных чисел. Определить минимальное число сравнений для того чтобы убедиться что не существует двух пар чисел из этой последовательности с одинаковой суммой.
Например - в последовательности [1,2,3,4] такие пары [1,4] и [2,3]

Фукнциональное решение на питоне (мне не совсем нравится. но что придумал то придумал)

def functional_approach(length):

    data=filter(lambda x: x[0]<x[1],iselectmany(xrange(1,length+1),curry1(izipwith,xrange(1,length+1))))

    def count(pair,li):

        return len(filter(lambda x:x[0]> pair[0] and x[1]<pair[1],li))

    print reduce(lambda x,y:x+count(data[y],data[y+1:]),xrange(0,len(data)))

Императивное решение:

def iter_approach(length):

    data = []

    for a in xrange(1,length):

        for b in xrange(a+1,length+1):

            data.append((a,b));

    c = 0

    for l in xrange(0,len(data)-1):

        for n in xrange(l+1,len(data)):

            if data[l][0]<data[n][0] and data[l][1]>data[n][1]:

                c = c + 1

    print c

Вот как хотите но по мне императивное решение проще, понятнее, интуитивние и т.д. Вообщем по всем критериям кроме краткости является лучшим решением. Ну может конечно функциональное написано коряво...не знаю.

Впомогательные фукнции-генераторы izipwith и iselectmany

def izipwith(seq,n):

    for s in seq:

        yield (n,s)

def iselect_many(seq,func):

    for s in seq:

        for s1 in func(s):

            yield s1

Функциональное программирование - я потихоньку учусь плохому

Project Euler, problem 105

Почти весь код на Питоне:

def euler_105_test(li):

    dest=sorted(select_combinations(li),lambda x,y:x[1]-y[1])

    return all(take(len(dest)-1,izip(dest,dest[1:])),lambda x:x[0][1] != x[1][1] and x[0][0] <= x[1][0])   

 

def euler_105():

    data = [[int(n) for n in line.split(',')] for line in file(r"d:\download\sets.txt")]

    print sum(map(sum,filter(euler_105_test,data)))

Обратите внимание на строчки

all(take(len(dest)-1,izip(dest,dest[1:])),lambda x:x[0][1] != x[1][1] and x[0][0] <= x[1][0])   

и

sum(map(sum,filter(euler_105_test,data)))

Мне даже сложно описать словами что выполняет первыя строчка.
Вторая строчка фактически суммирует двумерный массив.

Не приведен код функции select_combinations, но ее пока я не могу написать "красиво".

Доступны исходники Singularity

Singularity RDK
Забавная ситуация с подобными исходниками. Врядли я когда либо буду их серьезно смотреть..но...качаю. Думаю у большенства качающих тот же подход.

Забавная фраза характеризующая синтаксис языка

"eye-poking syntax"

Project Euler, статистика

Попробывал собрать статистику по странам из top 1000 Project Euler.
Получилось вот что:
('USA', 257)
('Sweden', 47)
('Germany', 45)
('England', 45)
('Netherlands', 41)
('Russia', 36)
('Canada', 33)
('France', 31)
('Australia', 26)
('India', 20)

Скрипт -

import urllib

import re

countries = {}

p = re.compile("<img src=.*?images/flags/(.*?)\.gif")

for page in xrange(1,11):

    for e in p.finditer(urllib.urlopen("http://projecteuler.net/index.php?section=top&page=%u"%(page,)).read()):

        countries[e.group(1)] = 1 + countries.get(e.group(1),0)

countries = sorted(countries.items(), key=lambda (k,v): (v,k))

countries.reverse()

for c in countries[0:10]:

    print c

От Украины 15 участников в top 1000.
Интерпритировать результаты не берусь. Просто забавно.

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

В принципе вопрос можно считать закрытым...
Electronic Arts Standard Template Library
описание собственной версии STL используемой в Electonic Arts, описание причин ее возникновения, проблем с текущей реализацией STL с точки зрения gane developming, да и вообще много много интересного.

Навскидку:

A common high-performance technique is to create a temporary hash table with a fixed-size memory buffer, do processing with it, and then "nuke" the hash table when done instead of going through the process of clearing and deallocating its nodes.

EASTL explicitly supports this programming pattern via the reset function. The supplied allocator generally must cooperate with this, lest memory leaks occur. However, it can work safely only with value types that have a trivial destructor.

People have been recommending the "swap trick" for years, but this is an obfuscated and easy-to-forget workaround in place of what should be built-in functionality. If a workaround is well-known enough that there are hundreds of pages on the Internet devoted to it and it has its own nickname, it probably should be built into the standard library. set_capacity is the same thing as resize_capacity which has been suggested by some.

Existing std STL implementations implement insertion operations by copying from an element. For example, resize(size() + 1) creates a throw-away temporary object. There is no way in existing std STL implementations to add an element to a container without implicitly or explicitly providing one to copy from (aside from some existing POD optimizations). For expensive-to-construct objects this creates a potentially serious performance problem. A typical suggested workaround to this problem with std STL is to store pointers instead of objects; however, such external memory allocation is undesirable for reasons described elsewhere in this document.

list and deque have both push_back(void) and push_front(void). slist has push_front(void). map, multimap, hash_map, and hash_multimap have insert(key). insert(key) is the same thing as the lazy_insert function that has been suggested by some. Other related proposals have been put forward.

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

Еще интересная ссылка - Technical Report on C++ Performance

Project Euler, problem 84 - Монополия!!!

Project Euler, problem 84

Задача сводится к тому чтобы найти три наиболее часто посещаемых поля для четырёхгранного кубика. Но интересно не это. Интересно то как раз другое - какие наиболее посещаемые поля для стандартных условий для шестигранного кубика.
Так вот - самая выгодная покупка будет поле E3 на картинке. Поле E3 - второе по частоте посещаемости после "тюрьмы". Я это как говорится "нутром чуствовал" - когда играл в Монополию всегда старался скупить именно эту линию.

GO	A1	CC1	A2	T1	R1	B1	CH1	B2	B3	JAIL
H2										C1
T2										U1
H1										C2
CH3										C3
R4										R2
G3										D1
CC3										CC2
G2										D2
G1										D3
G2J	F3	U2	F2	F1	R3	E3	E2	CH2	E1	FP

Project Euler, problem 100

Расту. Быстро набросав brute force переклчился на "листик и ручку". Оказалось - и тут Diophantine Equation

Потом посмотрел что там у меня набрутфорсилось...оказалось таки да, Diophantine Equation.

Дальше все было уже просто.

On-Line Encyclopedia of Integer Sequences - вообще полезный ресурс для этих задач

Умерла Софико Чиаурели

Comparison of string performance using C#,C++(STL,boost) and C - part 3, results

Previous parts:
Compare string performance using C#,C++(STL,boost) and C - part 1, C#
Compare string performance using C#,C++(STL,boost) and C - part 2, C\C++

This comparison was inspired by STL vector performance

Task -

you have array of strings "word1-word2", "word3-word4", "word5-word6", you need to transform it to string "word1:word2:word3:word4:word5:word6"

I was doing this on Windows so I use QueryPerformanceCounter to test performance to keep performance testing the same with C# and C++.

Goal - compare string performance on plain C with permormance of C++ code using STL and boost. I try to be as fear as possible and select "real-life"-like task. I add C# performance only when I notice difference between plain C and "C++ with STL".

For C/C++ I use VS 2005, release version, speed optimization. For C# I use VS 2008, Express Edition. My computer is Athlon 64 2-core 2.8 GHz, 2Gb of ram. Windows Vista.

Results, sorted by speed (I do many test runs and this is "average" results for 10000 iterations)

Boost String Algorithms Library	0.596665 sec
select_many	0.100862 sec
boost::tokenizer	0.086117 sec
"naive" C++	0.053814 sec
C#	0,041314 sec
C	0.003925 sec

Conclusion - C code is still 10 times faster then C# code, and still may be a bit optimized. But I didn't optimize C# code, even more, I try to write it in modern C#3.0 style using lambda/generics. When I rewrite C# code using StringBuilder it was 4 times slower then C code.

As for C++ code ("naive" or with boost) - either I don't familiar with some secret STL optimization technics...or...

And results using Boost String Algorithms Library looks really bad.

I see that C code use different algorithm then C++ or C# code. But this was C "idiomatic" way, again at least as I understand it.
Also I see that C code is not "general" enought, it will fail on strings like "word1--word2","word1-word2-". But my goal was to solve the problem. Pre-generalization is almost as bad as needless pre-optimization.

Compare string performance using C#,C++(STL,boost) and C - part 2, C++(STL) and C.

Compare string performance using C#,C++(STL,boost) and C - part 1, C#
Compare string performance using C#,C++(STL,boost) and C - part 3, results
Task:

you have array of strings "word1-word2", "word3-word4", "word5-word6", you need to transform it to string "word1:word2:word3:word4:word5:word6"

I use something that I call "idiomatic C" and 4 different "idiomatic" C++ solutions:

1. Using "Boost String Algorithms Library".
2. Using "select_many" kind of function.
3. Using Boost Tokenizer
4. Using "naive" С++ with std::strings.

C code:

char* do_the_job_in_plain_c(char** array, size_t size, char c1,char c2)

{

    size_t desc_size=size;

 

    for(size_t i=0;i<size;++i)

        desc_size+=strlen(array[i]);

    char* res_str = new char[desc_size];

    char* res_str_t = res_str;

    for(size_t i=0;i<size;++i,*res_str_t++ = c2){

        char* p = array[i];

        do{

            *res_str_t++ = (*p == c1)?c2:*p;

        }while(*(++p));

    }

    res_str[desc_size-1] = 0;

    return res_str;

}

Using "Boost String Algorithms Library".

        std::string result;

        typedef std::vector< std::string > split_vector_type;

        split_vector_type split_vec_res;

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

            split_vector_type split_vec;

            boost::split( split_vec, *v, boost::is_any_of("-") );

            std::copy(split_vec.begin(),split_vec.end(),std::back_inserter(split_vec_res));

        }

        std::string res = boost::join(split_vec_res,":");

Using "select_many" kind of function

std::string res = join_string(select_many(w,boost::bind(split_string,_1,("-"))),":");

Using Boost Tokenizer

        std::string result;

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

            boost::char_separator<char> sep("-");

            tokenizer tok(*v,sep);   

            for (tokenizer::iterator tok_iter = tok.begin();tok_iter != tok.end(); ++tok_iter){

                if(!result.empty())

                    result+=":";

                result+=*tok_iter;

            }

        }

Using "naive" С++ with std::strings

        std::string result;

 

        size_t length = w.size()+1;

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

            length+=v->length();

        result.reserve(length);           

 

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

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

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

                if(!result.empty())

                    result+=":";

                result+=*v1;

            }

        }

Whole programm code:

#include "stdafx.h"

#include <string>

#include <algorithm>

 

#include <boost/tokenizer.hpp>

#include <boost/algorithm/string.hpp>

#include <boost/bind.hpp>

 

#define NUM_ITERATIONS 10000

 

class HiPerfTimer

{

public:

    void start()

    {

        QueryPerformanceFrequency(&freq);

        QueryPerformanceCounter(&begin);

    }

    void stop(){QueryPerformanceCounter(&end);}

 

    double duration(){return (double)(end.QuadPart-begin.QuadPart)/freq.QuadPart;}

protected:

    LARGE_INTEGER begin,end,freq;

};

 

 

template<class _container_type,class _Fn1> inline

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

{   

    _container_type result;

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

    {

        _container_type tmp = _Func(*v);

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

            result.push_back(*v1);

    }

    return result;

}

 

std::vector<std::string>    split_string    (const std::string& str, const std::string& delimiters)

{

    std::vector<std::string> v;

    size_t offset = 0;

    while(true)

    {

        size_t token_start = str.find_first_not_of(delimiters, offset);

        if (token_start == std::string::npos)

        {

            v.push_back( str.substr(token_start,str.length()  - token_start));

            break;

        }

        size_t token_end = str.find_first_of(delimiters, token_start);

        if (token_end == std::string::npos)

        {

            v.push_back(str.substr(token_start));

            break;

        }

        v.push_back(str.substr(token_start, token_end - token_start));

        offset = token_end;

    }

 

    return v;

}

 

std::string    join_string        (const std::vector<std::string>& v,const std::string& delimiters)

{

    std::string s;

    size_t reserve = 0;

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

        reserve+=the_str->length();

    reserve+=delimiters.length()*v.size();

    s.reserve(reserve);

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

    {

        if(!s.empty())

            s+=delimiters;

        s+=*the_str;

    }

    return s;

}

 

 

char* do_the_job_in_plain_c(char** array, size_t size, char c1,char c2)

{

    size_t desc_size=size;

 

    for(size_t i=0;i<size;++i)

        desc_size+=strlen(array[i]);

    char* res_str = new char[desc_size];

    char* res_str_t = res_str;

    for(size_t i=0;i<size;++i,*res_str_t++ = c2)

    {

        char* p = array[i];

        do

        {

            *res_str_t++ = (*p == c1)?c2:*p;

        }while(*(++p));

    }

    res_str[desc_size-1] = 0;

    return res_str;

}

 

 

 

void test_select_many(std::vector<std::string>& w){

    HiPerfTimer pt;

    pt.start();

    for (int i = 0; i < NUM_ITERATIONS; ++i)

        std::string res = join_string(select_many(w,bind(split_string,_1,("-"))),":");

    pt.stop();

    printf("select_many- %f sec\n",pt.duration());

}

 

void test_boost_string_algorithm(std::vector<std::string>& w){

    HiPerfTimer pt;

    pt.start();

 

    for (int i = 0; i < NUM_ITERATIONS; ++i)

    {

        std::string result;

        typedef std::vector< std::string > split_vector_type;

        split_vector_type split_vec_res;

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

            split_vector_type split_vec;

            boost::split( split_vec, *v, boost::is_any_of("-") );

            std::copy(split_vec.begin(),split_vec.end(),std::back_inserter(split_vec_res));

        }

        std::string res = boost::join(split_vec_res,":");

    }

    pt.stop();

    printf("Boost String Algorithms Library - %f sec\n",pt.duration());

}

 

void test_boost_tokenizer(std::vector<std::string>& w)

{

    HiPerfTimer pt;

    pt.start();

 

    typedef boost::tokenizer<boost::char_separator<char> > tokenizer;

    for (int i = 0; i < NUM_ITERATIONS; ++i) {

        std::string result;

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

            boost::char_separator<char> sep("-");

            tokenizer tok(*v,sep);   

            for (tokenizer::iterator tok_iter = tok.begin();tok_iter != tok.end(); ++tok_iter){

                if(!result.empty())

                    result+=":";

                result+=*tok_iter;

            }

        }

    }

    pt.stop();   

    printf("Boost Tokenizer - %f sec\n",pt.duration());

}

 

void test_plain_cpp(std::vector<std::string>& w)

{

    HiPerfTimer pt;

    pt.start();

 

    for (int i = 0; i < NUM_ITERATIONS; ++i) {

        std::string result;

 

        size_t length = w.size()+1;

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

            length+=v->length();

        result.reserve(length);           

 

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

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

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

                if(!result.empty())

                    result+=":";

                result+=*v1;

            }

        }

    }

    pt.stop();   

    printf("naive C++ - %f sec\n",pt.duration());

}

 

void test_plain_c(char** array,size_t size)

{

    HiPerfTimer pt;

    pt.start();

    for (int i = 0; i < NUM_ITERATIONS; ++i)

        std::auto_ptr<char> res_str ( do_the_job_in_plain_c(array,size,'-',':') );

    pt.stop();   

    printf("plain C - %f sec\n",pt.duration());

}

int _tmain(int argc, _TCHAR* argv[])

{

    std::vector<std::string> w;

    w.push_back("word1-word2");w.push_back("word3-word4");w.push_back("word5-word6");

    w.push_back("word7-word8");w.push_back("word9-word0");

 

    test_boost_string_algorithm(w);

    test_select_many(w);

    test_boost_tokenizer(w);

    test_plain_cpp(w);

 

    char* w1[]={"word1-word2","word3-word4","word5-word6","word7-word8","word9-word0"};

    test_plain_c(w1,5);

    return 0;

}