ruby​​でArray＃uniqメソッドの時間計算量はどのくらいですか？

Question

誰もが、Array#uniqメソッドを使ってルビーの配列から重複を取り除くために、どのアルゴリズムが内部的にrubyによって使われているか教えてください。

Answer 1

：

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)複雑

Answer 2

それを償却O（n）としてuses Hash internallyとする。 docsから

Answer 3

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

Answer 4

これは、あなたが話している "内部" に依存します。現時点では、生産現場で使用可能な7つのRuby実装があり、Ruby言語仕様は特定のアルゴリズムを規定していません。したがって、実際には実装に依存します。

例えば、これはthe implementation Rubinius usesある：

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 

これはthe one from 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; 

Answer 5

それの内部実装のハッシュを使用するように、時間複雑度は線形時間、すなわちO（N）であります アルゴリズム。