ruby中Array#uniq方法的时间复杂度是多少？
发布时间：2020-12-17 04:30:52 所属栏目：百科 来源：网络整理
导读：谁能告诉我 ruby内部使用哪种算法来使用Array#uniq方法从ruby数组中删除重复项？ 解决方法 从 docs： static VALUErb_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 =
|
谁能告诉我
ruby内部使用哪种算法来使用Array#uniq方法从ruby数组中删除重复项？
解决方法
从
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)复杂性 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |