uniqが先かsortが先か？ - Mae向きなブログ

ある程度大きな配列で考えたとき、sortしてuniqするのと、uniqしてsortするのでは、前者の方が効率的ですよね？
2012-09-15 15:12:15 via twmode

という疑問を持ちましたので調べてみました。ツィートしたときは、sortしてuniqするほうが早いと直感的(根拠が今となっては思い出せません…)に思ったのですが、array.cのArray#uniqを実装している部分のelse節を見ると、

配列の要素からハッシュを作成する
配列の各要素をkeyとして、ハッシュから削除できたら、配列uniqにデータを追加

することにより、データの重複を排除しているように見えます。この方法だと、sortしてからuniqしようが、uniqしてからsortしようがuniqにかかる手間は同じだと思うので、性能の差はsortにかかる手間によるのではと思われます。そうすると、uniqしてからsortするほうが、sortする際の要素の数が小さくなっていることが期待できますので、uniqしてからsortするほうが効率的のように思えてきます。

array.cから引用

static VALUE
rb_ary_uniq(VALUE ary)
{
    VALUE hash, uniq, v;
    long i;

    if (RARRAY_LEN(ary) <= 1)
        return rb_ary_dup(ary);
    if (rb_block_given_p()) {
        hash = ary_make_hash_by(ary);
        uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash));
        st_foreach(RHASH_TBL(hash), push_value, uniq);
    }
    else {
        hash = ary_make_hash(ary);
        uniq = ary_new(rb_obj_class(ary), RHASH_SIZE(hash));
        for (i=0; i<RARRAY_LEN(ary); i++) {
            st_data_t vv = (st_data_t)(v = rb_ary_elt(ary, i));
            if (st_delete(RHASH_TBL(hash), &vv, 0)) {
                rb_ary_push(uniq, v);
            }
        }
    }
    ary_recycle_hash(hash);

    return uniq;
}

uniq_or_sort.rb

以下のスクリプトで実験してみました。

実験結果

実験結果を見ると、最初に自分が思った直感通りでしたが、先にuniqをしたほうが、配列が小さくなりsortが早くなるのではという自分の予想とは反対の結果になりました。

Rehearsal ----------------------------------------------
uniq->sort  12.800000   0.300000  13.100000 ( 13.143518)
sort->uniq  10.670000   0.280000  10.950000 ( 10.960329)
------------------------------------ total: 24.050000sec

                 user     system      total        real
uniq->sort  12.510000   0.240000  12.750000 ( 12.759015)
sort->uniq  10.580000   0.240000  10.820000 ( 10.814251)