Поддерживает ли Ruby uniq заказ?

Question

В документации ничего не говорится об этом (http://www.ruby-doc.org/core-2.2.0/Array.html#method-i-uniq).

Кроме того, используется ли наивный поиск O (n^2) или что-то еще, например, hashmap? В последнем случае, следует ли понимать, что мои элементы должны иметь правильную реализацию hash и eql?, когда я хочу их разделить?

Answer 1

Учитывая код (в C) для 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; 
} 

В общем случае (else блок), он создает хэш из массива (который объединяет ключ без поддержания порядка). Затем он создает новый пустой массив с нужным размером. Наконец, он проходит через первый массив, и когда он находит ключ в хэше, он удаляет этот ключ и выталкивает его в пустой массив.

Следовательно, заказ сохраняется.

Я бы сказал, что сложность O (сложность (ary_make_hash) + N) во времени, что, вероятно, O (N)