文档对此没有任何说明(http://www.ruby-doc.org/core-2.2.0/Array.html#method-i-uniq)。
此外,它是使用简单的 O(n^2) 搜索还是其他类似 hashmap 的东西?在后一种情况下,我是否应该理解我的元素必须具有 hash
和 eql 的正确实现?
当我想将它们统一化时?
最佳答案
给定 Array#uniq
的代码(C 语言)
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
block ),它从数组中创建一个散列(在不保持顺序的情况下统一键)。然后它创建一个具有正确大小的新空数组。最后它遍历第一个数组,当它在散列中找到键时,它删除该键并将其推送到空数组。
因此顺序保持不变。
我会说复杂度是 O(complexity(ary_make_hash) + N) 在时间上,这可能是 O(N)
关于ruby - Ruby uniq 是否保留顺序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28113933/