Ruby 中 Array#uniq 方法的时间复杂度是多少? [英] what is the time complexity of Array#uniq method in ruby?

问题描述

谁能告诉我 ruby​​ 内部使用哪种算法来使用 Array#uniq 方法从 ruby​​ 数组中删除重复项?

Can anyone please tell me which algorithm is internally used by ruby to remove duplicates from an ruby array using Array#uniq method?

推荐答案

来自 文档:

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)复杂度

这篇关于Ruby 中 Array#uniq 方法的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！