रूबी में ऐरे # यूनिक विधि की समय जटिलता क्या है?

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

अमोरिज्ड ओ (एन) के रूप में 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 उत्पादन-तैयार रूबी कार्यान्वयन हैं, और रूबी भाषा विशिष्टता किसी विशेष एल्गोरिदम को निर्धारित नहीं करती है। तो, यह वास्तव में कार्यान्वयन पर निर्भर करता है।

जैसे, इस 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

समय जटिलता है रैखिक समय यानी हे (एन) के रूप में यह के आंतरिक कार्यान्वयन के लिए हैश का उपयोग करता है एल्गोरिदम।