Ruby uniq có duy trì thứ tự không?

Question

Tài liệu không nói bất cứ điều gì về điều đó (http://www.ruby-doc.org/core-2.2.0/Array.html#method-i-uniq).

Ngoài ra, có phải nó đang sử dụng tìm kiếm ngây thơ O (n^2) hay cái gì khác giống như một băm không? Trong trường hợp thứ hai, tôi có nên hiểu rằng các yếu tố của tôi phải thực hiện đúng cách hash và eql? khi tôi muốn hợp nhất chúng không?

Answer 1

Với mã (trong C) cho 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; 
} 

Trong trường hợp tổng quát (các else khối), nó tạo ra một hash từ mảng (mà thống nhất chìa khóa mà không cần giữ trật tự). Sau đó, nó tạo ra một mảng trống mới với kích thước phù hợp. Cuối cùng nó đi qua mảng đầu tiên và khi nó tìm thấy khóa trong băm, nó xóa khóa đó và đẩy nó vào mảng trống.

Do đó, đơn đặt hàng được lưu giữ.

Tôi muốn nói độ phức tạp là O (độ phức tạp (ary_make_hash) + N) trong thời gian, có thể là O (N)