在Racket中,列表相对于向量的优势是什么？

Question

根据我迄今为止对Racket的经验,我没有太多考虑过向量,因为我认为他们的主要好处 - 对元素的持续时间访问 - 在你使用大量元素之前并不重要.

但是,这似乎不太准确.即使使用少量元素,向量也具有性能优势.例如,分配列表比分配向量要慢:

#lang racket

(time (for ([i (in-range 1000000)]) (make-list 50 #t)))
(time (for ([i (in-range 1000000)]) (make-vector 50 #t)))

>cpu time: 1337 real time: 1346 gc time: 987
>cpu time: 123 real time: 124 gc time: 39

检索元素也比较慢:

#lang racket

(define l (range 50))
(define v (make-vector 50 0))

(time (for ([i (in-range 1000000)]) (list-ref l 49)))
(time (for ([i (in-range 1000000)]) (vector-ref v 49)))

>cpu time: 77 real time: 76 gc time: 0
>cpu time: 15 real time: 15 gc time: 0

如果我们增加到1000万,那么这个性能比如何:

#lang racket

(define l (range 50))
(define v (make-vector 50 0))

(time (for ([i (in-range 10000000)]) (list-ref l 49)))
(time (for ([i (in-range 10000000)]) (vector-ref v 49)))

>cpu time: 710 real time: 709 gc time: 0
>cpu time: 116 real time: 116 gc time: 0

当然,这些都是合成的例子,大多数程序都没有list-ref在循环中分配结构或使用一百万次.(是的,我故意抓住第50个元素来说明性能差异.)

但它们也不是,因为在整个依赖于列表的程序中,每次触摸这些列表时都会产生一些额外的开销,而所有那些效率低下的问题都会导致整体运行时间变慢程序.

因此我的问题是:为什么不一直只使用矢量？我们应该在什么情况下从列表中获得更好的性能？

我最好的猜测是,因为从列表前面获取项目的速度同样快,例如:

#lang racket

(define l (range 50))
(define v (make-vector 50 0))

(time (for ([i (in-range 1000000)]) (list-ref l 0)))
(time (for ([i (in-range 1000000)]) (vector-ref v 0)))

>cpu time: 15 real time: 16 gc time: 0
>cpu time: 12 real time: 11 gc time: 0

...列表在递归过程中是首选,因为你主要使用consand car和cdr,并且它节省了空间来处理列表(向量不能被破坏并放回到一起而不复制整个向量,对吧？)

但是在存储和检索数据元素的情况下,无论长度如何,向量似乎都具有优势.

Answer 1

由于list-ref使用时间线性指数,除非是短列表,否则很少使用.如果访问模式是顺序的,并且元素的数量可以变化,那么列表就可以了.看到用于总结50个元素长的fixnums列表的元素的基准将是有趣的.

但是,数据结构的访问模式并不总是顺序的.

以下是我如何选择在Racket中使用的数据结构:

DATA STRUCTURE   ACCESS       NUMBER     INDICES
List:            sequential   Variable   not used
Struct:          random       Fixed      names
Vector:          random       Fixed      integer
Growable vector: random       Variable   integer
Hash:            random       Variable   hashable
Splay:           random       Variable   non-integer, total order

Answer 2

在大多数编程语言中,向量与数组相同.由于任何阵列都具有固定大小,因此它们具有O(1)访问/更新.增加大小是很昂贵的,因为您需要将每个元素复制到更大尺寸的新矢量.如果你跨所有元素循环,你可以做O(n).

列表是单链表.它们具有动态大小,但随机访问/更新是O(n).访问/修改列表的头部是O(1)所以如果你从头到尾迭代或从头到尾创建.由于列表迭代完成了每个步骤,因此在n个元素上的整个迭代仍然与向量一样完成O(n).这样做list-ref反而会使它为O(n ^ 2),所以你不知道.

你有这两个列表和向量的原因是因为它们都有优点和缺点.列表是函数式编程语言的核心,因为它们可以用作不可变对象.您在每次迭代中链接一对和一对,最终得到一个大小由完整过程确定的列表.成像:

(define odds (filter odd? lst)) 

这将获取任意大小的数字列表,并创建一个包含列表中所有奇数的新列表.为了使用矢量执行此操作,您需要执行两次传递.检查结果向量应具有的大小,以及将旧元素从旧元素复制到新元素的大小.但是,如果你需要在任何时候随机访问任何元素向量(或哈希表,如果你在#!racket编程)是显而易见的选择.

Answer 3

在你的第一个例子中:

(time (for ([i (in-range 1000000)]) (make-list   50 #t))) ;50 million list nodes
(time (for ([i (in-range 1000000)]) (make-vector 50 #t))) ; 1 million vectors

请记住,您要求使用列表进行50倍分配.事实上,GC时间约为20倍,实际时间约为10倍.

还有初始#t值.虽然我不知道Racket是否以这种方式实现它,但对于一个概念上只需要一malloc加一的数组memset- "给我一系列的内存,并在它上面输入这个值." 有一个5000万mov秒的名单吗？

list-ref恕我直言是一个"代码味道" - 或者,至少,我检查预期的列表长度将是非常小的东西.如果你真的需要索引一个大的东西,你可能希望这个东西是一个向量(或者可能是一个哈希表).

那么,什么是名单上的载体优势？我认为链接列表与其他语言中的数组基本相同的优点和缺点.

你还可以建立超越单向链表事情cons,car以及cdr(如树).虽然我不是Lisp历史的专家,但我想这部分是选择这些构建块的动机吗？

最后,我认为值得记住的是,像这样的微观基准确实......就目前而言.他们不一定告诉你的是真实/完整申请中的情况.如果您的应用程序主要是分配一百万个固定长度数据结构的时间,那么您可能需要一个向量而不是列表.否则,它可能要考虑的优化列表相当远.