• Tweet
• 

• Tweet
• 

(この記事はC++メインの内容です。)

関数型言語のセンスも身につけておかないと、と思ってHaskellの簡単なお勉強をしようと思いました。

圏論のような背景や文法から把握するのもひとつのルートですが、まずは適当な例を見てみようと思ったわけです。
「関数型言語だとこんなことができる!」みたいな驚きがあったほうが楽しいですしね。

まずはHaskellでのクイックソートの実装例を探してみました。クイックソートというのはアルゴリズムの勉強を1からすると必ずと言っていいほど登場するほどのものですし、比較もできて面白そうです。

さて、「Haskell クイックソート」でGoogle検索にかけてみると、「C++だと35行のところがHaskellは5行で書ける」だの、「最も美しいコードのひとつ」だのとなかなか景気の良い記事が出てきます。

ところがもう少し読んでみると、「Haskellの5行クイックソートはクイックソートではない」みたいな議論がされているページがいくつか出てきます。

Togetterにいろいろな主張のまとめがありました。曰く、

「In-placeソートでないからだめ」「というか遅い」「いやHaskellに効率を求めてはいけない」「5行の例はPivotingをしていないのでだめ」「Pivotingはクイックソートの本質ではない」「メモリを抽象化していて扱えていないのでとても遅い」「Haskellでメモリの議論をするべきでないしIn-placeソートでなくてもよい」「Haskellでクイックソートをしっかり書きたいなら手続き型風に書くのが良い」

といった感じで、さっそく頭が痛くなってきました。

まあ今回はHaskellについては一旦置いておいて、その途中で出てきた「C++のクイックソートは35行」の部分についての話です。C++で普通に書いてももっと短くなっていいはずです。

結果から書きますと、普通に書いても9行くらいになりました。

---

Haskell風に

まずはHaskellで解説されていた5行コード風に書いてみましょう。Haskell版の5行コードはこれです。

qsort []     = []
qsort (p:xs) = qsort lt ++ [p] ++ qsort gteq
                 where
                   lt   = [x | x <- xs, x < p]
                   gteq = [x | x <- xs, x >= p]

Pivotingなし、In-placeでないクイックソートです。もちろんPivoting等を施したコードもあるのですが、長くなるので今回は取り上げません。

さて、同じノリでC++のSTLを使って書いてみたものが以下になります。

#include <vector>
#include <algorithm>
template<class T> void quick_sort(std::vector<T>& d){
  if(d.empty()) return;
  std::vector<T> left, right;
  for(auto it = d.begin()+1; it != d.end(); ++it)
    if(*it < d.at(0)) left.push_back(*it);
    else right.push_back(*it);
  quick_sort(left);
  quick_sort(right);
  d = std::vector<T>(1,d.at(0));
  d.insert(d.begin(), left.begin(), left.end());
  d.insert(d.end(), right.begin(), right.end());
}

関数の定義に12行。確かに長くなりますね。

ただしこれはC++がリストの内包表記や結合を簡単に書けなかったためでもあると思います。それにしても35行の約1/3程度で書けます。

C++風に

さて、今度はクイックソートをC++の得意なIn-placeソートで書いてみるとどうなるでしょう。

クイックソートは再帰でメモリの再配置を行わないIn-placeソートとして書くことができ、これが空間計算量を落として高速にソートを行えるひとつの理由となっています。(もっとも、マージソートやヒープソートもIn-placeで書けますが。)

「35行」と言われていたのもおそらくこちらのスタイルですね。

以下にこのスタイルで書いてみました。引数にはイテレータの始まりと終わりをとります。

#include <utility>
template<class T> void quick_sort2(T b, T e){
  if(b == e) return;
  auto l = b, r = e-1;
  while(l<r){
    while(*r>*b) r--;
    while(*l<=*b && l<r) l++;
    std::swap(*l, *r);}
  std::swap(*b, *l);
  quick_sort2(b, l);
  quick_sort2(l+1, e);
}

むしろ短くなりましたね。使っている関数も値を入れ替えるstd::swapだけです。

いくつかの工夫をすることでもう少し短くすることができます。

#include <utility>
template<class T> void quick_sort2(T b, T e){
  auto l = b, r = e-1;
  for(; l<r; std::swap(*l, *r)){
    while(*r>*b) r--;
    while(*l<=*b && l<r) l++;}
  std::swap(*b, *l);
  if(b != l)quick_sort2(b, l);
  if(l+1 != e)quick_sort2(l+1, e);
}

関数の定義に9行。確かに5行のインパクトには及びませんが、ざっと把握できる程度の分量にはなっていると思います。

 

(※注意: ここに書いたクイックソートをそのまま何かの実装には使わないようにして下さい。実際に使う場合はライブラリの関数を使うのが一番です。)

---

おまけ:1行クイックソート

可読性をかなぐり捨てて、行数を短くしたらどこまで短くなるか考えてみました。

例えばラムダ式などを使えば1つの変数定義にいくらでも書くことができますが、これは複数行をそのまま書いただけなので1行と呼べるものでもありません。

C++で複数個の記述を書いても一般に1行と見なされるものとしては、forループがあります。そこでforループをごりごり使えば1行に収めることができます。

例えばこんな感じになります。(途中ラムダ式がありますが、1つの文しか書いていません。)

template<class T> void quick_sort3(T itb, T ite){
  for(auto itl=itb,itr=ite-1;itl<itr;[&](){if(itl+1!=ite)quick_sort2(itl+1,ite);}())for(;itl<itr;[&](){if(itb!=itl)quick_sort2(itb,itl);}())for(;itl<itr;std::swap(*itb,*itl))for(;itl<itr;std::swap(*itl,*itr))for([&](){while(*itr>*itb)itr--;}();*itl<=*itb&&itl<itr;)itl++;
}

3行! 本文1行!!

まあでも、さすがにこれを1行と認めたくはないですね。わかりやすさの欠片もありません。

 

余談ですが、C++の長所は、抽象化の度合いが高いことでも低いことでもないと思っています。
「高級言語の皮をかぶった低級言語」と言われるように、普段は高級言語のように簡便にコーディングを行えながら、必要ならいつでも低級言語のレベルまで落としてしっかり書けることが長所だと思っています。

その分言語仕様が複雑ゴホンゴホン

 

それではみなさんも楽しいクイックソートライフをお送り下さい。