C++の std::unique と、Ruby の Array#uniq の本質的な違い

配列から重複した要素を取り除きたいとき、C++ では STLstd::unique を、Rubyでは Array#uniq を使うことが出来ます。

C++ Ruby
#include <iostream>
#include <algorithm>

int main(){

  int v[]  = {1, 2, 2, 3, 3, 3};
  int len  = sizeof(v) / sizeof(v[0]);
  int *end = std::unique(v, v+len);
  for(int *p = &v[0]; p != end; ++p)
    std::cout << *p << ' ';
  return 0;
}
v = [1, 2, 2, 3, 3, 3]
p v.uniq
1 2 3 1 2 3

これらの関数 (メソッド) は全く同じ働きをするように見えますが、よく調べてみると、実は微妙に異なる動作をすることが分かります。 異なる動作をするのは、具体的には次のようなケースです。

C++ Ruby
#include <iostream>
#include <algorithm>

int main(){

  int v[]  = {3, 2, 1, 2, 3, 3};
  int len  = sizeof(v) / sizeof(v[0]);
  int *end = std::unique(v, v+len);
  for(int *p = &v[0]; p != end; ++p)
    std::cout << *p << ' ';

  return 0;
}
v = [3, 2, 1, 2, 3, 3]
p v.uniqpre>
3 2 1 2 3 3 2 1

std::unique では望んだとおりの出力が得られません。 これは何故でしょうか。

実は、std::unique は「連続した同じ値の要素の並びから1つを残し、他は削除する」という動作をします。 つまり、上のケース

3 2 1 2 3 3

では、6つの値を

[3] [2] [1] [2] [3 3]

のようにグループに分け、各グループから1つずつ値を取ってきて並べるので、

3 2 1 2 3

が得られる、というわけなのです。

std::uniqueRubyArray#sort と同様に使いたいのなら、その前に要素をソートすることを忘れてはいけません。

C++
#include <iostream>
#include <algorithm>

int main(){

  int v[]  = {3, 2, 1, 2, 3, 3};
  int len  = sizeof(v) / sizeof(v[0]);

  std::sort(v, v+len)
  int *end = std::unique(v, v+len);
  for(int *p = &v[0]; p != end; ++p)
    std::cout << *p << ' ';       // => 1 2 3

  return 0;
}

というのが、一般的な C++ (STL) の参考資料に書かれている説明です。 さて、今日のトピックは、そもそも何故C++ではこのような仕様になっているのか、というお話です。 長くて恐縮ですが、ここまでが前フリ。

その疑問に答える前に、まずは2つの関数のアルゴリズムを見てみましょう。 Rubyuniq は、次のようなアルゴリズムで実装されます。 これらの実装は、以下のようなインタフェースを持ちます。 (注: 以下、アルゴリズムの実装例を示すのに、一貫してC++を使用します。)

/*
  uniqueする。
  第1引数 v[] にunique後のデータが格納され(元々の v[] は破壊される)、返値としてそれらの要素数が返される。
  * 引数
  T v[]: uniqueの対象となる配列
  int n: v の要素数
  * 返値
  int: uniqueした後の v の要素数
*/
template<class T>
int uniq(T v[], int n);
Ruby の Array#uniq のアルゴリズムの実装例
template<class T>
int uniq(T v[], int n){

  // exceptional case
  if(n == 0)
    return 0;

  int unique_count = 1; // number of unique items
  for(int i = 1; i < n; ++i){
    for(int j = 0; j < unique_count; ++j){
      if(v[i] == v[j])
        goto skip;
    }
    v[unique_count++] = v[i];

  skip:;
  }

  return unique_count;
}

二重ループを回し、ある要素が既出の要素と等しいならばそれを取り除く、という率直なアルゴリズムです。 結果を格納するためのバッファを用意せず、入力の配列を直接書き換えている点がトリッキーですが、少し考えれば問題なく動作することが分かるはずです。 あの悪名高い goto が使われていますが、この程度であればむしろ break やフラグ変数を使うよりも分かりやすいと個人的には思います。

一方 std::uniqueアルゴリズムは、「連続した同じ値の要素の並びから1つを残し、他は削除する」という仕様であることを思い出せば、次のように実装できます。

C++のstd::uniqueのアルゴリズムの実装例
template<class T>
int unique(T v[], int n){
  if(n == 0)
    return 0;

  int unique_count = 1; // number of unique items
  for(int i = 1; i < n; ++i){
    if(v[i] != v[i-1])
      v[unique_count++] = v[i];
  }

  return unique_count;
}

これは、「『左隣の要素と等しいような要素』を全て取り除く」というアイデアに基づいたアルゴリズムです。 Array#uniq よりも若干シンプルなものになっています。
同様に入力配列を直接書き換えていますが、やはりこれでも問題なく動作します。 それを証明するには、数学的帰納法を使いつつ、ところにより i = unique_count のケースと i > unique_count のケースに場合分けしてやったりすればいいでしょう。 詳細は割愛します。

これらのアルゴリズムの最も大きな違いは、計算量です。

Array#uniqアルゴリズムを見てみると、外側のループが約 n 回実行され、内側のループは unique_count 回 (つまり、最大約 n 回) 実行されるので、全体として O(n2) の計算量になります。
一方、std::uniqueアルゴリズムは、約 n 回実行される単純なループなので、O(n)の計算量です。 Array#uniq と同じ出力を得るにはあらかじめ配列をソートする必要がありますが、ソートは O(n log(n)) でできるので、合わせても O(n log(n)) で実行できます。
std::unique の方が圧倒的に速いのです。

C++ で書かれるプログラムは、高速に動作することを期待されることが少なくありません。 それを見越して、std::unique は (必要に応じてソートすることを要求するけれども) 高速で動作するように設計されているのでしょう。

さて、そうすると次の疑問は、「何故 Ruby でも std::unique と同じアルゴリズムを採用しないのか。ソートが必要ならば、Array#uniq の中でソートしてやればいいだけではないのか」ということになります。 しかし、ソートを行うためには要素の大小比較演算 (<, >, <=> など) を定義しなければなりません。 しかし Array#uniq が要求するのは、要素のが等しいかの判定 (.eql?) だけです。 つまり Array#uniq は、速度を犠牲にしても、最低限の手間さえかければ実行できるように設計されているのです。 ちなみに、同値判定のみを用いた unique には少なくとも O(n2) の計算量が必要です[要証明]unique という1つの関数を取っても、アルゴリズムの違いや設計思想の違いが透けて見えるのは興味深いですね。

ついでに、unique にまつわるいくつかのトピックを垂れ流していきます。

同値判定と大小比較さえできれば O(nlogn) の unique を利用することができます。 ここで言う大小比較は、数としての大小比較である必要はありません。 ただ全順序関係であれば問題ないのです。 具体的に言えば、一般的に複素数には大小関係は定義されません。 しかし便宜上、例えば「実部の大きな方が大きい。ただし実部が等しいときは、虚部の大きな方が大きい」という大小関係を定義すれば、ソートして unique をかけることが可能になります。
このように、適当な順序関係を決めてやる手間を惜しまなければ、どんなオブジェクトに対しても高速な unique を使うことができます。

しかしながら、たとえ手間をかける余裕があったとしても、O(n2) の unique を使った方がいいケースも存在します。 二次元平面上の座標もその一つです。 以下のような点を表すクラスがあったとしましょう。

struct Point{
  double x, y;
  bool operator<(const Point& p) const{
    if(eq(x, p.x)) return y < p.y;
    return x < p.x;
  }
  bool operator==(const Point& p) const{
    return eq(x, p.x) && eq(y, p.y);
  }

  // 誤差を許した実数の同値判定
  static bool eq(double a, double b){
    const double eps = 1e-9;
    return fabs(a-b) < eps;
  }
};

誤差が出やすい二次元平面上の実数座標を扱うときには、「極めて近い2点は同一の点として扱いたい」という要求が発生することがあります。 しかしながら、「極めて近い全ての2点が隣同士に並ぶ」ということを保障する全順序関係を定義するのは簡単ではありません。
このようなケースでは O(n2) の unique を使った方が、より多くのデータが取り除かれることが多いと考えられます。

ソートを使えば O(nlogn) で unique ができることを見てきました。 それでは、もっと速く unique する方法は無いのでしょうか。

あまり大きくない (T未満の) 非負の整数を対象とする場合、配列を用いた以下のようなアルゴリズムが考えられます。

const int T = 1024;
int unique_int(int v[], int n){
  bool *exist = new bool[T];
  for(int i = 0; i < T; ++i)
    exist[i] = false;

  for(int i = 0; i < n; ++i)
    exist[v[i]] = true;

  int unique_count = 0; // number of unique items
  for(int i = 0; i < T; ++i)
    if(exist[i])
      v[unique_count++] = i;

  delete [] exist;

  return unique_count;
}

[0, T - 1] の各値について、それが存在するかどうかを bool 配列にメモしていき、最後に出力用配列に書き戻す、というアルゴリズムです。
bool 配列の初期化のコストを含めると計算量は O(n + T) となり、特にTが小さく要素数が多い時に威力を発揮します。

さて、このアルゴリズムは要素が非負の整数であることを利用しましたが、一般のオブジェクトに適用できるようなやり方は無いものでしょうか。
解決策は簡単で、それぞれのオブジェクトに適切なハッシュ関数を用意し、非負整数に変換してやればよいのです。

しかしあらゆるオブジェクトに適切なハッシュ関数を用意することは口で言うほど簡単ではなく、このためにC++std::unique でもこの方法は採用されていないのだと考えられます。
あれ、でもRubyだと簡単に出来そうな気が・・・?

def unique_by_hash(arr)
  Hash[arr.map{|e| [e, nil] }].keys
end

p unique_by_hash([3, 2, 1, 2, 3, 3])  # => [1, 2, 3]