Ruby 这个 list 比数组快了百倍

chenge · 2013年04月12日 · 最后由 chenge 回复于 2016年07月04日 · 3274 次阅读
# create a struct with :value and :next
Cell = Struct.new(:value, :next)

# create a head of our list
list = Cell.new("head. hi", nil)

# array
a = []

# method which create one more cell and return the struct
def linked_list(value, cell)
  return Cell.new(value, cell)
end

# simple benchmark timer. t1 - t2 = waiting time ;)
def bench type
  t1 = Time.now
  yield
  t2 = Time.now
  p "#{type}'s took #{t2 - t1}s"
end


bench ("array") {
  100000.times { a.insert 0,10} # O(n)
}

bench ("linked list") {
  100000.times { list = linked_list(10, list) } # O(1)
}

http://khakimov.com/blog/2012/05/11/back-to-school-linked-list-with-ruby/

在头上插入链表比数组快不是很正常的事情么,这种数据结构特性不同啊,而且原文最后也说到:

Of course Arrays are cool, because you can do many other things faster than linked list (trade offs)

不同的数据结构有不同的特点嘛

记得大学时代上 C 的时候就讲过,链表的插入性能是比队列要快。但是老实说,通常一条数据修改的次数远远小于查询的次数。这个使用场景不多吧?

基本没实用意义的,一是有 map, reduce 等优化过性能的高级方法,我们很少需要操作底层插入,二是我们用数组的时候都是在尾插入而不是在头插入...

在尾插入数组,最后 reverse, 比 list 快多了:

bench ("array") {
  100000.times { a << 10 }
  a.reverse!
}

#3 楼 @luikore 没实用意义,不过有教学意义。

chenge Ruby 学习汇集,请推荐内容 提及了此话题。 07月04日 11:35
需要 登录 后方可回复, 如果你还没有账号请 注册新账号