четверг, 13 августа 2009 г.

Взялся за изучение Erlang-а.
Написал quicksort:
  1 myqsort([])->[];
2 myqsort([First|Rest])->
3 myqsort([X || X<-Rest, X<First])++[First]++myqsort([X || X<-Rest,X>=First]).
4

Прикольно.
Для сравнения написал аналогичный quicksort на C++:
  1 std::vector<int>    sort(const    std::vector<int>&    list)
2 {
3 if (list.empty())
4 return list;
5
6 int elem = *list.begin();
7 std::vector<int> left,right;
8 std::vector<int>::const_iterator it = list.begin()+1;
9
10 for(;it!=list.end();++it)
11 if (*it<elem)
12 left.push_back(*it);
13 else
14 right.push_back(*it);
15
16 std::vector<int> res_l = sort(left),res_r = sort(right);
17
18 res_l.push_back(elem);
19 res_l.insert(res_l.end(),res_r.begin(),res_r.end());
20 return res_l;
21 };
22

Очевидно что фунцкциональный код короче и понятнее. Отсортировал однинаковый входной список из 2 млн записей. По скорости получилось так: C++ - 7 секунд, Erlang - 12 секунд.
В общем очень интересно, буду продолжать изыскания дальше

0 comments:

Отправить комментарий