Techioz Blog

Ruby の Uniq は順序を保持しますか?

概要

ドキュメントにはそれについて何も記載されていません (http://www.ruby-doc.org/core-2.2.0/Array.html#method-i-uniq)。

また、単純な O(n^2) 検索またはハッシュマップのような他のものを使用していますか?後者の場合、要素にはハッシュと eql が適切に実装されている必要があることを理解する必要がありますか?統一したいときは？

解決策

Array#uniq のコード (C 言語) を考えると、

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;
}

一般的なケース (else ブロック) では、配列からハッシュが作成されます (順序を維持せずにキーを統合します)。次に、適切なサイズの新しい空の配列を作成します。最後に、最初の配列を通過し、ハッシュ内にキーが見つかると、そのキーを削除して空の配列にプッシュします。

したがって、秩序は保たれます。

時間的には複雑さは O(complexity(ary_make_hash) + N) になると思います。おそらく O(N) です。

はい、まさに、ハッシュと eql の両方を実装する必要がありますか?メソッド。これはほぼすべてのオブジェクトで行われます。

ハッシュ メソッドを定義していない基本オブジェクトの配列に対して unique を呼び出すと、エラーが発生することがわかります。

irb(main):023:0> [BasicObject.new, BasicObject.new].uniq
Traceback (most recent call last):
        5: from /usr/bin/irb:23:in `<main>'
        #...
NoMethodError (undefined method `hash' for #<BasicObject:0x000000014311a1e0>)