2004-05-29

is_sorted --sortの事後条件-- ・・・その前に

C++ STL

ここ2日ほど考えていたis_sortedですが，ようやく結論が出ました．ですがその結論の前に，多分多くの人にとっては全然面白くないであろうことを延々議論します．
結論は今日のblogの一番最後にありますので，結論だけ見たい人はid:Cryolite:20040529#p5へ飛んでください．

2004-05-29

値が等しいということ（Equality）

C++ STL 数学

まず最初に「値が等しいということ（Equality）」という概念について今一度確認してもらいます．C++（に限らず多くのprogramming言語）で普通"=="（及び"!="）で表される関係です．

int a = 1;
int b = 1;
int c = 2;
assert( a == b ); // `a' is equal to `b'
assert( a != c ); // `a' is not equal to `c'

上の例では，aとbはequalである，と言えます．
何のことは無い「値が等しい」という関係を表しているだけです（詳しく議論するとこれはこれで曲者ですが）．
なぜこれを確認してもらったかというと，後でこのequalityと似たような概念である"equivalence"という概念が出てくるからです．そして，このequivalenceという概念がSTLにおけるsort（広く言えば順序付け全般）において非常に重要な意味を持つからです．

2004-05-29

厳密で弱い順序（Strict Weak Order）

C++ STL 数学

STLにおいて，順序を定める述語を指定するときにはすべからく「厳密で弱い順序（Strict Weak Order）」という概念が出てきます．この概念がいかにSTLで重要な位置を占めているかは次の事実を見てもらえば一目瞭然です．

std::setで要素の比較に使われる述語（boolを返すファンクタ）には厳密で弱い順序であることが要求される
std::mapでkeyの比較に使われる述語には厳密で弱い順序であることが要求される
std::sortに渡される述語には厳密で弱い順序であることが要求される
・・・e.t.c.

いかにこの概念が重要かということは理解できましたでしょうか？この概念の重要性は，STLを扱っている書籍では必ずといっていいほど議論されているので，そちらもぜひ参考にしてください（e.x."Effective STL"第21項．後で分かりますが第19項も深く関連します）．
ここではさらに一歩踏み込んで「厳密で弱い順序とは何か？」，そして「厳密で弱い順序が何故ここまで重要視されるのか？」を議論します．
ある集合の要素を一列に並べるときに「大きい順」とか「小さい順」とかいうふうな基準を決めますが，この基準のことを普通は「順序」と呼びます．しかしここでは「順序」という言葉を数学的・抽象的な意味，即ち，ある集合の任意の2つの要素の間にある関係が有る（true）か無い(false)か，という意味で使います．この意味で，順序は2つの値を引数に取ってbool値を返す関数の形式を取ります．STLで使われる「順序」もこの形式を取っているのはご存知の通りです．

int a = 1;
int b = 2;
assert( less()(a, b) ); // STLがデフォルトで使う「順序」であるless

順序には様々な種類があり，厳密で弱い順序はこの種類の中の一つです．まず先に代表的な順序の種類である「全順序（Total Order）」を説明した方が良いと思われるので，そちらからやります．
全順序とは以下の性質を満たしている順序です（より正確には「厳密な（strict）」全順序の定義）．ここで，f(x, y)は2つの要素xとyの順序を定義する関数とします．

（非）反射性：f(x, x)は常にfalseである
（非）対称性：f(x, y)がtrueならば!f(y, x)もtrueである
推移性：f(x, y)がtrueでありf(y, z)がtrueであるならf(x, z)はtrueである
f(x, y)がfalseでありf(y, x)もfalseであるならば，xとyは等しい(equal)

よく分かりませんので具体的な全順序の例としてlessに登場してもらって，条件の意味を順に追っていきます．

（非）反射性

int i = 3;
assert( !less()(i, i) );

要するに同じ値に対して常にfalseを返す，というのが一つ目の条件「（非）反射性」です．
この条件に関して非常に重要な指摘として，less_equalやgreater_equalはこの条件を満たさないということです．これらの「順序」は同じ値に対してtrueを返してしまいます．このような「順序」はSTLにおける比較の条件として絶対に使えません．この制約を破ると何が起きるか具体的に知りたい方は，例えば以下のコードを実行してみてください．

set > s;
s.insert(1); // 1を挿入
s.insert(1); // すでに1はsに入っているからこの挿入では何も起こらないはずだ！
copy(s.begin(), s.end(), ostream_iterator(cout, "\n"); // ありゃりゃ？

この現象の解説の詳細については"Effective STL"をどうぞ．

（非）対称性

int i;
int j;
...
if( less()(i, j) ){
  assert( !less()(j, i) );
}

これは「順序」という言葉から直感的に分かる条件です．具体的には例えば「aはbより小さい」なら「bはaより小さくない」と言えるのは当然でしょう，ということです．

推移性

int i;
int j;
int k;
...
if( less()(i, j) && less()(j, k) ){
  assert( !less()(i, k) );
}

これまた「順序」という言葉から直感的に理解できる条件です．言葉で言えば「aはbより小さい」かつ「bはcより小さい」なら「aはcより小さい」ということです．

最後の条件

int i, j;
...
if( !less()(i, j) && !less()(j, i) ){
  assert( i == j );
}

これも分かりやすい条件です．「iがjよりも小さいことはない」かつ「jがiよりも小さいことはない」なら「iとjは同じ値である」ということは，通常の順序なら当然でしょう．そもそも，「全」順序という言葉は異なる2つの要素x, yの間全てにf(x, y)またはf(y, x)が成り立つことから来ている名前で，そのどちらも成り立たないということは，そもそもxとyは同じ要素だったのだ，ということが言えるわけです．
さて，これを踏まえた上で，次に厳密で弱い順序の定義を見てみます．
厳密で弱い順序では全順序の最後の条件だけが緩められています（緩められているのかどうかパッと見て分からないですが）．

（非）反射性：f(x, x)は常にfalseである
（非）対称性：xとyが（equalityの意味で）等しくないとき，f(x, y)がtrueならば!f(y, x)もtrueである
推移性：f(x, y)がtrueでありf(y, z)がtrueであるならf(x, z)はtrueである
equivalenceに対する推移性：xとyがequivalentでありyとzもequivalentであるとき，xとzもequivalentである

ここで初めてequivalenceという言葉が出てきます．xとyがequivalentであるというのは，f(x, y)がfalseでありかつf(y, x)がfalseである，ということです．
具体的な例で見てみます．厳密で弱い順序として一番有名なのが「大文字小文字を無視した文字列の大小比較」です．この文字列比較の実装は簡単なので省略して，この順序（文字列として小さいほうが前にきたらtrue）を定義した述語をci_lessとします．

assert( ci_less("ABC", "acb") );

さて問題は"ABC"と"aBc"にこのci_lessで順序をつけるとどうなるか，です．当然，ci_less("ABC", "aBc")もci_less("aBc", "ABC")も両方falseを返します．
ここで，全順序の定義の最後の条件を思い出してください．全順序の定義では上のように双方の比較がfalseだった場合，その値は等しい（equal）ことが必要でした．ところがci_lessによる順序付けができないこの"ABC"と"aBc"は値が等しいとはいえません．要するにci_lessは，異なる値である"ABC"と"aBc"の大小を決定できないのです．
この，ci_lessにおける"ABC"と"aBc"の比較のように，値として等しくないにもかかわらず，双方の順序関係が定義できないような比較が存在します．つまり，値は違うけれどもある順序付けによっては「等しいとみなされる」値の関係が存在するわけです．これが"Equivalence"です．例えば上の例で言えば，ci_lessにおいては"ABC"と"aBc"はequivalentである，というふうに言うことができます．
さて，もう一度厳密で弱い順序の定義に戻ります．

（非）反射性：f(x, x)は常にfalseである
（非）対称性：xとyが等しくないとき，f(x, y)がtrueならば!f(y, x)もtrueである
推移性：f(x, y)がtrueでありf(y, z)がtrueであるならf(x, z)はtrueである
equivalenceに対する推移性：xとyがequivalentでありyとzもequivalentであるとき，xとzもequivalentである

実はさっき例に出したci_lessは4番目の条件を満たします．具体的に言うと，ci_lessでは"abc"と"abC"の順序を決められません．同時に，"abC"と"aBc"の順序も決められません．このとき，"abc"と"aBc"の順序も決められない，というのが最後の条件です．
一見，「だからどうした？」と思えるようなこの最後の条件こそ，STLにおいて決定的な意味を持つことが後で分かります．
ここで2点だけ．全順序の最後の条件は，f(x, y)でもf(y, x)でもないとき，xとyは値が等しい（equal），となっていましたが，このequalityというのはequivalenceよりもキツイ条件です．というのも，f(x, x)もf(x, x)も（←x同士の順番を入れ替えたつもり）falseを返すので，値が等しい（equal）なら当然equivalentでもある，ということになります．また，equalityはxとyが値が等しくyとzも値が等しいならxとzも値が等しいという推移性（厳密で弱い順序の最後の条件）を満たすので，結局，全順序は厳密で弱い順序の条件がキツイ形である，ということが分かります．
もう一つ．equivalenceの関係は，数学の言葉で言うところの「同値関係（equivalent relation）」になっています．equivalenceの関係が反射律と対称律を満たしているのはすぐに確認できます．推移律は最後の条件そのものですね．equivalenceという言葉は恐らくここから来ているのでしょう．
＃追記：上の言い方は数学的に非常にまずいか？「無関係」の関係が同値関係になるような半順序が「厳密で弱い順序」だというべき．

2004-05-29

何故，厳密で弱い順序が重要なのか？

C++ STL 数学

さて，ようやく自分の疑問の核心部にたどり着きました．
厳密で弱い順序が何故STLにおいてここまで重要視されているのか，多くの書籍は「数学的な詳細には立ち入らない」としてこの部分の議論を避けているので，ここではあえてそれに踏み入ってみます．
厳密で弱い順序で私が一番疑問に思っていたのが最後の条件です．

equivalenceに対する推移性：xとyがequivalentでありyとzもequivalentであるとき，xとzもequivalentである

この条件はいったい何なのか？何のために必要なのか？ということが非常に疑問だったのです．
これは，逆に言えばこの条件を外すとどうなるのか？ということにもつながります．実はこの条件を厳密で弱い順序から外した以下の3つの定義は「半順序（Partial Order）」と呼ばれる順序の種類の定義になります．

（非）反射性：f(x, x)は常にfalseである
（非）対称性：xとyが等しくないとき，f(x, y)がtrueならば!f(y, x)もtrueである
推移性：f(x, y)がtrueでありf(y, z)がtrueであるならf(x, z)はtrueである

自分の疑問は「何故この3条件だけではダメなのか」と言い換えることもできます．
また，もう一つの大きな疑問がありました．以下のことはどうやって証明できるのか，ということです．
a < b, b <> c $\Rightarrow$ a < c
ここでは，分かりやすく書くためにf(a, b)をa < b，bとcがequivalentであることをb <> cと書いています．この関係を仮に「equivalenceを通した順序の推移性」と呼ぶことにします．
これが何故重要なのか？今以下のような場合を想定してみます．
a < b <> c < d
これは，a, b, c, dをソートした結果の隣接要素間の順序関係を表したものです．bとcがequivalentだったというわけです．
で，sortしたということは当然a < c, a < d, b < dであるべきです．これが保証されるためにはどうしても「equivalenceを通した順序の推移性」が必要です．
つまり，sortの事後条件として隣接要素間の順序だけを見れば良い，ということを保証するためにはどうしても「equivalenceを通した順序の推移性」が必要になります．
今日暇な時間があったのでその時間の間このことをぼけ〜っと考えていたのですが，最終的に上の2つの疑問は同時に解決しました．
結論は，「equivalenceの推移性」と上の「equivalenceを通した順序の推移性」は同値である，です．証明は余白が無いので省略します・・・簡単な証明ですがｗ．
これによって，厳密で弱い順序は「equivalenceを通した順序の推移性」を保証する，ということになります．従って，厳密で弱い順序によるソートの事後条件を確認するためには隣接要素間だけをみれば良い，ということになります．
さらに言うと，この「equivalenceを通した順序の推移性」はソートを行う多くのアルゴリズムにとって非常に重要な意味を持ちます．何故かというと，quick sortのように陽に全ての異なる要素間を比較しないソートでは部分的な要素の順序と順序の推移性によって全体の順序関係が保証されるということを仮定しているので，「equivalenceを通した順序の推移性」が無いと結果的にquick sortではsortされない（また他のsortの機能，例えばmulti_setやmulti_mapの実装における赤黒木によるkeyの順序の保証などが働かない）ということになります．
＃追記：別の言い方をすると「ソートアルゴリズムの複雑性がO(N logN)であるための必要最低限の要求こそ『厳密で弱い順序』である」といえる．
これが，STLで厳密で弱い順序が強調されている理由である，と私は結論付けました．
(´-｀).。oＯ（多分，ものの本読めばこういう事ってさらっと書いてあるんだろうなぁ・・・）
最後に，上のことを例示するコードとして，ただの半順序でstd::sortを使った場合の例を示します．ここで使っている半順序f(a, b)は「aがbの約数ならtrue，それ以外はfalse（ただし非反射性が要るのでa == bならfalse）」というものです．これを「順序」と呼ぶのは非常に違和感を感じると思いますが，実際これは厳密で弱い順序から最後の条件だけを除いた，半順序の3条件を全て満たす「順序」です（それにこの「順序」は半順序としては代表的なものです）．

#include 
#include 
#include 
#include 
#include 

struct is_measure
  : std::binary_function
{
  bool operator()(int lhs, int rhs) const
  {
    return lhs != rhs && rhs % lhs == 0;
  }
};

int main(int argc, char *argv[])
{
  using namespace std;

  vector v;

  for(int i = 20; i >= 1; --i){
    v.push_back(i);
  }

  sort(v.begin(), v.end(), is_measure());

  copy(v.begin(), v.end(), ostream_iterator(cout, "\n"));

  return 0;
}

自分の環境では，上のコードは以下のように表示されました．

1, 5, 10, 20, 19, 18, 17, 16, 14, 13, 12, 11, 9, 8, 7, 6, 4, 3, 2

ちなみに上のコードによって期待している「ソート」の結果とは，「ある要素の約数が必ずそれよりも前にある」です．ソートが全く機能していないのは一目瞭然ですね（ですか？）．これはis_measureが厳密で弱い順序の4つ目の条件を満たしていない「順序」だからです（注意：これがちゃんとソートされないのは，std::sortの実装がクイックソートだからだ，とも言えます．バブルソートなどのアルゴリズムでは正しく「ソート」されます）．
逆に，厳密で弱い順序の条件を満たした順序によるソートの例として，以下のコードを挙げておきます．

#include 
#include 
#include 
#include 
#include 

struct modulo_less
  : std::binary_function
{
  bool operator()(int lhs, int rhs) const
  {
    return lhs % 3 < rhs % 3;
  }
};

int main(int argc, char *argv[])
{
  using namespace std;

  vector v;

  for(int i = 20; i >= 1; --i){
    v.push_back(i);
  }

  sort(v.begin(), v.end(), modulo_less());

  copy(v.begin(), v.end(), ostream_iterator(cout, "\n"));

  return 0;
}

上の結果がきちんと「ソート」されているのが分かりますか？（ちなみに上のソートではequivalenceが3の剰余系に対応しています）

2004-05-29

is_sorted --sortの事後条件--

C++ STL

というわけで，ここまで長々訳の分からないことを書いておきながら，結論は至ってシンプルです．自前のfor文回すのが一番楽ですが，ここはあえて既存のアルゴリズムでやってみました．

template
inline
bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrder pred)
{
  ForwardIterator it(first);
  return equal(++first, last, it, std::not2(pred));
}

上のコードはcomp.lang.c++で書かれていたものを若干変更したものです．predがadaptableであることを要求しているのが唯一残念なところです．equalの使い方が本来期待されている使い方と異なっていますが，規格書読む限りはこれも正しい使い方であると思われます．ただし2つのiterator範囲がoverlapするので，equalが本来要求しているInputIteratorではなく，ForwardIteratorが必要になります．というかこのequalの使い方は結構(　・∀・)つ〃∩ ヘェーヘェーヘェーな感じ．
1つだけ注意として，Strict Weak Orderの否定が何を意味するかですが，上の議論から「!(a < b)」は「a > b または a <> b」を表すことになります．そしてこのequalは結局，隣接する要素a, b（要素の順序はこの順とする）において「a < b または a <> b が成り立つ」ということを確認しています．これがsortの事後条件をきちんと確認していることは上の議論のとおりです．
最後に余計ながら，自分が考えたコードを示しておきます．

template
inline
bool is_sorted(ForwardIterator first, ForwardIterator last, StrictWeakOrder pred)
{
  return std::adjacent_find(
    first, last, 
    boost::lambda::bind(pred, boost::lambda::_2, boost::lambda::_1)) 
      == last;
}

lambda::bind持ち出していますが，やっていることは非常に単純です．ちなみにこのコードはequalによるis_sortedのコードとまったく等価です（一見しただけでは分かりにくいですが）．
後，他にiteratorを逆回しにしてアルゴリズムに突っ込むコードもありましたが，iteratorに対する要求がForwardからBidirectionalになってしまうので避けました．