Czy Ruby uniq zachowuje zamowienie?

Question

Dokumentacja nic o tym nie mówi (http://www.ruby-doc.org/core-2.2.0/Array.html#method-i-uniq).

Czy używa on naiwnego wyszukiwania O (n^2) lub czegoś podobnego do hashmap? W tym drugim przypadku, czy powinienem zrozumieć, że moje elementy muszą mieć właściwą implementację hash i eql?, kiedy chcę je unicize?

Answer 1

Biorąc kod (w C) dla Array#uniq

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

w ogólnym przypadku (blok else), tworzy skrót z tablicy (która jednoczy klucz bez zachowania kolejności). Następnie tworzy nową pustą tablicę o odpowiednim rozmiarze. W końcu przechodzi przez pierwszą tablicę i po znalezieniu klucza w haszu kasuje ten klucz i przenosi go do pustej tablicy.

Dlatego zamówienie jest przechowywane.

Powiedziałbym złożoność wynosi O (złożoność (ary_make_hash) + N) w czasie, który jest prawdopodobnie O (N)