Mathematica 中的 Prepend 与 Append 性能

Question

在类似 Lisp 的系统中，cons 是在列表中 PREPEND 元素的正常方法。附加到列表的函数要昂贵得多，因为它们将列表遍历到末尾，然后用对附加项的引用替换最终的空值。 IOW (pseudoLisp)

(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)，但检索的速度是恒定的。

看看这个 页 href="http://library.wolfram.com/infocenter/Conferences/321/" rel="nofollow noreferrer">Mathematica 中的数据结构和高效算法，其中更详细地介绍了 mathematica 列表。

另外，请查看这个关于链表的Stack Overflow问题及其在mathematica中的表现。

Answer 2

作为一个小补充，这里是 M- 中“AppendTo”的有效替代方案

myBag = Internal`Bag[]
Do[Internal`StuffBag[myBag, i], {i, 10}]
Internal`BagPart[myBag, All]

Answer 3

正如已经提到的，由于 Mathematica 列表是作为数组实现的，因此每次添加元素时，诸如 Append 和 Prepend 之类的操作都会导致列表被复制。更有效的方法是预先分配一个列表并填充它，但是我下面的实验并没有显示出我预期的那么大的差异。显然，更好的是链表方法，我将不得不研究它。

Needs["PlotLegends`"]
test[n_] := Module[{startlist = Range[1000]},
   datalist = RandomReal[1, n*1000];
   appendlist = startlist;
   appendtime = 
    First[AbsoluteTiming[AppendTo[appendlist, #] & /@ datalist]];
   preallocatedlist = Join[startlist, Table[Null, {Length[datalist]}]];
   count = -1;
   preallocatedtime = 
    First[AbsoluteTiming[
      Do[preallocatedlist[[count]] = datalist[[count]]; 
       count--, {Length[datalist]}]]];
   {{n, appendtime}, {n, preallocatedtime}}];
results = test[#] & /@ Range[26];
ListLinePlot[Transpose[results], Filling -> Axis, 
 PlotLegend -> {"Appending", "Preallocating"}, 
 LegendPosition -> {1, 0}]

比较 AppendTo 与预分配的时序图。 （运行时间：82 秒）

编辑

使用 nixeagle 的建议修改大大改善了预分配时序，即 preallocatedlist = Join[startlist, ConstantArray[0, {Length[datalist]}]];

第二次编辑

形式为 {{{startlist},data1} 的链接列表,data2} 效果更好，并且有一个很大的优点，即不需要像预分配那样提前知道大小。

Needs["PlotLegends`"]
test[n_] := Module[{startlist = Range[1000]},
   datalist = RandomReal[1, n*1000];
   linkinglist = startlist;
   linkedlisttime = 
    First[AbsoluteTiming[
      Do[linkinglist = {linkinglist, datalist[[i]]}, {i, 
        Length[datalist]}];
      linkedlist = Flatten[linkinglist];]];
   preallocatedlist = 
    Join[startlist, ConstantArray[0, {Length[datalist]}]];
   count = -1;
   preallocatedtime = 
    First[AbsoluteTiming[
      Do[preallocatedlist[[count]] = datalist[[count]]; 
       count--, {Length[datalist]}]]];
   {{n, preallocatedtime}, {n, linkedlisttime}}];
results = test[#] & /@ Range[26];
ListLinePlot[Transpose[results], Filling -> Axis, 
 PlotLegend -> {"Preallocating", "Linked-List"}, 
 LegendPosition -> {1, 0}]

链表与预分配的时序比较。 （运行时间：6 秒）

Answer 4

如果您知道结果将有多少个元素并且可以计算元素，那么整个 Append、AppendTo、Linked-List 等都是不必要的。在克里斯的速度测试中，预分配才起作用，因为他提前知道元素的数量。对datelist的访问操作代表对当前元素的虚拟计算。

如果是这样的情况，我绝对不会使用这样的方法。一个简单的表与连接相结合会更快。让我重用 Chris 的代码：我将预分配添加到时间测量中，因为当使用 Append 或链表时，也会测量内存分配。此外，我确实使用结果列表并检查它们是否相等，因为聪明的解释器可能会识别简单、无用的命令并优化它们。

Needs["PlotLegends`"]
test[n_] := Module[{
    startlist = Range[1000],
    datalist, joinResult, linkedResult, linkinglist, linkedlist, 
    preallocatedlist, linkedlisttime, preallocatedtime, count, 
    joinTime, preallocResult},


   datalist = RandomReal[1, n*1000];
   linkinglist = startlist;
   {linkedlisttime, linkedResult} = 
    AbsoluteTiming[
     Do[linkinglist = {linkinglist, datalist[[i]]}, {i, 
       Length[datalist]}];
     linkedlist = Flatten[linkinglist]
     ];

   count = -1;
   preallocatedtime = First@AbsoluteTiming[
      (preallocatedlist = 
        Join[startlist, ConstantArray[0, {Length[datalist]}]];
       Do[preallocatedlist[[count]] = datalist[[count]];
        count--, {Length[datalist]}]
       )
      ];

   {joinTime, joinResult} =
    AbsoluteTiming[
     Join[startlist, 
      Table[datalist[[i]], {i, 1, Length[datalist]}]]];
   PrintTemporary[
    Equal @@@ Tuples[{linkedResult, preallocatedlist, joinResult}, 2]];
   {preallocatedtime, linkedlisttime, joinTime}];

results = test[#] & /@ Range[40];
ListLinePlot[Transpose[results], PlotStyle -> {Black, Gray, Red}, 
 PlotLegend -> {"Prealloc", "Linked", "Joined"}, 
 LegendPosition -> {1, 0}]

在我看来，有趣的情况是，当您事先不知道元素的数量并且您必须临时决定是否必须附加/前置某些内容。在这些情况下，Reap[] 和 Sow[] 可能值得一看。一般来说，我会说，AppendTo 是邪恶的，在使用它之前，请看看替代方案：

n = 10.^5 - 1;
res1 = {};
t1 = First@AbsoluteTiming@Table[With[{y = Sin[x]},
      If[y > 0, AppendTo[res1, y]]], {x, 0, 2 Pi, 2 Pi/n}
     ];

{t2, res2} = AbsoluteTiming[With[{r = Release@Table[
        With[{y = Sin[x]},
         If[y > 0, y, Hold@Sequence[]]], {x, 0, 2 Pi, 2 Pi/n}]},
    r]];

{t3, res3} = AbsoluteTiming[Flatten@Table[
     With[{y = Sin[x]},
      If[y > 0, y, {}]], {x, 0, 2 Pi, 2 Pi/n}]];

{t4, res4} = AbsoluteTiming[First@Last@Reap@Table[With[{y = Sin[x]},
        If[y > 0, Sow[y]]], {x, 0, 2 Pi, 2 Pi/n}]];

{res1 == res2, res2 == res3, res3 == res4}
{t1, t2, t3, t4}

Gives {5.151575, 0.250336, 0.128624, 0.148084}。 幸运的是，该结构

Flatten@Table[ With[{y = Sin[x]}, If[y > 0, y, {}]], ...]

确实具有可读性并且速度很快。

备注

在家里尝试最后一个例子时要小心。在这里，在我的 Ubuntu 64 位和 Mma 8.0.4 上，n=10^5 的 AppendTo 需要 10GB 内存。 n=10^6 占用我所有的 RAM（32GB）来创建一个包含 15MB 数据的数组。有趣的。