ruby中Array＃uniq方法的时间复杂度是多少？

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

Answer 1

来自文档 ：

 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 

它具有O(N)复杂性

Answer 2

分摊O（n），因为它在内部使用Hash 。

Answer 3

这取决于你所谈论的“内部”。 目前使用的有7个生产就绪的Ruby实现，而Ruby语言规范没有规定任何特定的算法。 所以，这实际上取决于实施。

例如，这是Rubinius使用的实现 ：

 Rubinius.check_frozen if block_given? im = Rubinius::IdentityMap.from(self, &block) else im = Rubinius::IdentityMap.from(self) end return if im.size == size array = im.to_array @tuple = array.tuple @start = array.start @total = array.total self 

这是来自JRuby的那个 ：

 RubyHash hash = makeHash(); if (realLength == hash.size()) return makeShared(); RubyArray result = new RubyArray(context.runtime, getMetaClass(), hash.size()); int j = 0; try { for (int i = 0; i < realLength; i++) { IRubyObject v = elt(i); if (hash.fastDelete(v)) result.values[j++] = v; } } catch (ArrayIndexOutOfBoundsException aioob) { concurrentModification(); } result.realLength = j; return result; 

Answer 4

It compares elements using their hash (provided by the Object#hash method) then compares hashes with Object#eql?.

资料来源： https ： //github.com/ruby/ruby/blob/trunk/array.c#L3976

Answer 5

时间复杂度是线性时间，即O（n），因为它使用Hash进行算法的内部实现。