jaka jest złożoność czasu metody Array # uniq w ruby?

Question

Czy ktoś może mi powiedzieć, który algorytm jest używany wewnętrznie przez ruby ​​do usunięcia duplikatów z tablicy ruby ​​przy użyciu metody Array#uniq?

Answer 1

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

Ma O(N) złożoność

Answer 2

Amortyzowane O (n) jako uses Hash internally.

Answer 3

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

Źródło: https://github.com/ruby/ruby/blob/trunk/array.c#L3976

Answer 4

To zależy który "wewnętrzne", o której mówisz. Istnieje 7 gotowych do wykonania implementacji Ruby w bieżącym użyciu, a specyfikacja języka Ruby nie określa żadnego konkretnego algorytmu. Tak naprawdę to zależy od implementacji.

przykład, jest 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 

I jest 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

Złożony czas czas liniowy tzn O (n), jak to stosuje mieszania dla wewnętrznego wdrażania Algorytm .