任何人都可以请告诉我哪种算法是由红宝石内部使用从红宝石数组中删除重复使用Array#uniq
方法?Ruby中Array#uniq方法的时间复杂度是多少?
7
A
回答
5
从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)
复杂
3
摊销为O(n),因为它uses Hash internally。
1
It compares elements using their hash (provided by the Object#hash method) then compares hashes with Object#eql?.
3
这取决于其 “内部” 你在说什么。目前有7种可用于生产的Ruby实现,Ruby语言规范并未规定任何特定的算法。所以,这实际上取决于实施。
例如,这是the implementation Rubinius uses:
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
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;
1
的时间复杂度是线性的时间,即O(n)的,因为它使用散列对内部执行 算法。
相关问题
- 1. Collection.toArray()的时间复杂度是多少?
- 2. NavigableMap的floorEntry()方法的时间复杂度是多少?
- 3. list.index(obj)方法的时间复杂度是多少?
- 4. heapifyUp()方法的时间复杂度是多少?
- 5. addFirst(e)和removeFirst()方法的时间复杂度是多少?
- 6. 方案中'assoc'函数的时间复杂度是多少?
- 7. 分时排序算法的时间复杂度是多少?
- 8. AngularJS的脏检查算法的时间复杂度是多少?
- 9. 爬山算法的时间复杂度是多少?
- 10. 整个算法的时间复杂度是多少?
- 11. 这个算法的时间复杂度是多少?
- 12. 这个算法的时间复杂度是多少?
- 13. 这个算法的时间复杂度是多少?
- 14. 这个算法(代码)的时间复杂度是多少?
- 15. 通配符匹配算法的时间复杂度是多少?
- 16. 根据Big-O表示法,下列方法的时间复杂度是多少?
- 17. 减少时间复杂度
- 18. 我的代码中的时间复杂度是多少
- 19. Java中TreeSet的lower()/ higher()的时间复杂度是多少?
- 20. Python中collections.Counter()的时间复杂度是多少?
- 21. TreeSet中有序操作的时间复杂度是多少?
- 22. Python中dict.keys()的时间复杂度是多少?
- 23. Java中LinkedList.getLast()的时间复杂度是多少?
- 24. clojure中count函数的时间复杂度是多少?
- 25. C++中std :: next_permutation()函数的时间复杂度是多少?
- 26. java中lastIndexOf的时间复杂度是多少?
- 27. java中StringBuilder.append()的时间复杂度是多少?
- 28. Python中zip()的时间复杂度是多少?
- 29. java中HashMap.containsValue()的时间复杂度是多少?
- 30. 链式散列表中的时间复杂度是多少