list - 在 Mathematica 中前置与附加性能

Question

在类 Lisp 系统中，cons 是将元素添加到列表中的常规方式。附加到列表的函数要昂贵得多，因为它们将列表遍历到末尾，然后用对附加项的引用替换最后的 null。 IOW(伪Lisp)

(prepend list item) = (cons item list) = cheap!
(append list item) = (cond ((null? list) (cons item null))
                           (#t (cons (car list (append (cdr list) item)))))

问题是 Mathemtica 中的情况是否类似？在大多数方面，Mathematica 的列表似乎像 lisp 的列表一样是单链接的，如果是这样，我们可以假设 Append[list,item] 比 Prepend[list,item] 昂贵得多.但是，我无法在 Mathematica 文档中找到任何内容来解决这个问题。如果 Mathematica 的列表是双向链接的或更巧妙地实现，例如，在堆中或仅维护指向最后的指针，那么插入可能具有完全不同的性能配置文件。

如有任何建议或经验，我们将不胜感激。

Answer 1

Mathematica 的列表不是像 Common Lisp 中那样的单向链表。最好将 Mathematica 列表视为类似数组或向量的结构。插入的速度是O(n)，但检索的速度是常数。

看看这个 page的 Data structures and Efficient Algorithms in Mathematica其中更详细地介绍了 Mathematica 列表。

另外请查看 this关于链表的 Stack Overflow 问题及其在 Mathematica 中的表现。