Ruby中Array＃uniq方法的時間複雜度是多少？

Question

任何人都可以請告訴我哪種算法是由紅寶石內部使用從紅寶石數組中刪除重複使用Array#uniq方法？

Answer 1

從docs：

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。

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）的，因爲它使用散列對內部執行 算法。