8

Array#uniqメソッドを使用してルビー配列から重複を削除するためにルビーが内部的に使用するアルゴリズムを教えてください。

4

5 に答える 5

7

ドキュメントから： 

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;

O(N)複雑です

于 2013-01-07T17:08:42.710 に答える
3

内部でハッシュを使用するため、償却されたO（n）。

于 2013-01-07T17:07:19.607 に答える
3

これは、話している「内部」によって異なります。現在使用されている本番環境向けの Ruby 実装は 7 つあり、Ruby 言語仕様では特定のアルゴリズムは規定されていません。したがって、実際には実装に依存します。

たとえば、これはRubinius が使用する実装です:

Rubinius.check_frozen

if block_given?
  im = Rubinius::IdentityMap.from(self, &block)
else
  im = Rubinius::IdentityMap.from(self)
end
return if im.size == size

array = im.to_array
@tuple = array.tuple
@start = array.start
@total = array.total

self

そして、これはJRuby のものです:

RubyHash hash = makeHash();
if (realLength == hash.size()) return makeShared();

RubyArray result = new RubyArray(context.runtime, getMetaClass(), hash.size()); 

int j = 0;
try {
    for (int i = 0; i < realLength; i++) {
        IRubyObject v = elt(i);
        if (hash.fastDelete(v)) result.values[j++] = v;
    }
} catch (ArrayIndexOutOfBoundsException aioob) {
    concurrentModification();
}
result.realLength = j;
return result;
于 2013-01-07T22:27:28.827 に答える
1

アルゴリズムの内部実装にハッシュを使用するため、時間計算量は線形時間、つまり O(n) です。

于 2014-10-10T02:54:55.900 に答える
1

It compares elements using their hash (provided by the Object#hash method) then compares hashes with Object#eql?.

ソース: https://github.com/ruby/ruby/blob/trunk/array.c#L3976

于 2013-01-07T17:11:58.567 に答える