qual è la complessità temporale del metodo array # uniq in ruby?

Question

Qualcuno può dirmi quale algoritmo è utilizzato internamente da Ruby per rimuovere i duplicati da un array di ruby ​​usando il metodo Array#uniq?

Answer 1

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

Ha O(N) complessità

Answer 2

Ammortizzato O (n) come uses Hash internally.

Answer 3

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

Fonte: https://github.com/ruby/ruby/blob/trunk/array.c#L3976

Answer 4

Dipende da che "interni" si sta parlando. Ci sono 7 implementazioni di Ruby pronte per la produzione in uso corrente e la Specifica del linguaggio Ruby non prescrive alcun algoritmo particolare. Quindi, dipende davvero dall'implementazione.

esempio, questo è 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 

E questo è 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

La complessità ora è tempo lineare cioè O (n) in quanto utilizza Hash per l'implementazione interna del Algoritmo .