打开主菜单

目录

引言编辑

列表在Mathematica中是最重要的数据结构,同时在一些函数式编程语言中比如LISP也是这样。任何复杂数据结构都能够被表示为一些(可能是复杂的和嵌套的)列表。例如,n维数组可以被表示成一个具有深度n[1]的列表。任何树状结构[2]可以看成是一个列表。

列表可以在程序执行的过程中动态地生成,正确书写的函数可以作用在任意长度的列表上,而并没有把列表的长度看成一个直接的参数。这样得到了一个相当“干净”的代码,同时容易书写。列表的另一个优点在于通常可以容易地调试作用在其上的函数,我们将会看到许多具有这种特征的例子。本章我们将会介绍几个用来产生和处理列表的内置函数。

使用列表的一般准则编辑

当我们在Mathematica中使用列表时,特别是规模大的列表,遵循以下规则是很有用的:我们必须把任何列表看成一个简单的单元,避免把它们碎片化的操作,例如数组索引化(array indexing)。换句话说,最好的编程方式是尝试使用一些操作,使其能把列表看成一个整体来进行处理。这种方法在函数式编程中是特别重要的,它对于提高代码效率有非常重大的意义。我们将介绍大量例子来阐述这个问题,尤其是在介绍函数式编程的第五章。

列表的内容编辑

列表并不要求只能包含一种类型的元素,列表里面可以包含任何Mathematica表达式,甚至是这些表达式任意混合的产物。这些表达式可以是列表或者普通的Mathematica表达式,可以有任意的大小和深度。本质上,加上头部List之后,列表是普通的Mathematica表达式的一种特别形式。

In[]:= Clear[x];
       List[Sin[x],Cos[x],Tan[x]]
Out[]= {Sin[x],Cos[x],Tan[x]}

列表的产生编辑

有很多方式可以产生列表。

手动产生列表编辑

首先,当然是可以手工产生列表。也就是说,程序中一些固定列表还是要靠程序员自己定义。比如:

In[]:= Clear[testlist,a,b,c,d,e];
       testlist={a,b,c,d,e}
       Clear[testlist];
Out[]= {a,b,c,d,e}

用Range产生等距离数字列表编辑

实际上产生等距离数字列表是很有必要的。特别是在函数式编程方法中,因为它们不是以循环的方式产生于这样的列表。这样的等距离数字列表可以使用内置函数Range。例子:

In[]:= Range[5]
       Range[2,10]
       Range[2,11,3]
       Range[0,1,0.1]
Out[]= {1,2,3,4,5}
Out[]= {2,3,4,5,6,7,8,9,10}
Out[]= {2,5,8,11}
Out[]= {0.,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.}

用Table产生列表编辑

在我们需要具有更一般性质的列表时,经常使用内置函数Table。例子:

In[]:= Table[1,{i,1,10}]
       Table[i^2,{i,1,10}]
       Table[i*j,{i,1,3},{j,1,3}]
       Table[i+j,{i,1,4},{j,1,i}]
       Table[i+j+k,{i,1,2},{j,1,3},{k,1,3}]
       Table[Sin[i],{i,1,10}]
Out[]= {1,1,1,1,1,1,1,1,1,1}
Out[]= {1,4,9,16,25,36,49,64,81,100}
Out[]= {{1,2,3},{2,4,6},{3,6,9}}
Out[]= {{2},{3,4},{4,5,6},{5,6,7,8}}
Out[]= {{{3,4,5},{4,5,6},{5,6,7}},{{4,5,6},{5,6,7},{6,7,8}}}
Out[]= {Sin[1],Sin[2],Sin[3],Sin[4],Sin[5],Sin[6],Sin[7],Sin[8],Sin[9],Sin[10]}

就如这些例子所示,在Table中用于设定迭代边界的列表的数目可以有多个。填充入列表的元素可以是以迭代体的计数器为自变量的函数。当迭代体多于一个时,我们将获得一个嵌套列表,而这个列表的最外层则是由最内层的迭代体产生的。就如我们所见,较外层迭代体的边界可能是依赖于较内层迭代体里的变量(和计数器是一个东西)的,因此我们可以用Table得到具有不等长子列表的列表。[3]这就是我们开始看到的,列表比多维数组更加一般,因为子列表不一定要有一样的维数。而且,认识到用Table产生的列表不一定是数字列表,它们可以是函数列表:

In[]:= Clear[i,x];
       Table[x^i,{i,1,10}]
Out[]= {x,x^2,x^3,x^4,x^5,x^6,x^7,x^8,x^9,x^10}

在这里作为例子,我们产生一个3*3单项式列表[4]

In[]:= Clear[i,j,x];
       Table[x^{i+j},{i,1,3},{j,1,3}]
Out[]= {{{x^2},{x^3},{x^4}},{{x^3},{x^4},{x^5}},{{x^4},{x^5},{x^6}}}

关于Table的另一个阐述就是它是一个局部结构(scoping construct),具有这样的意义:它确定了它的迭代变量(iterator variables)。它有效地使用了Block[] 这样的局部结构来实现。结果就是通常得伴随着Block[]的使用(将会在4.8节介绍)。特别地,我们天真地希望符号<f[i]>在下面的例子中出现5次,但是在<f>的定义中用到了全局变量<i>

In[]:= Clear[f,i];
       f:=i^2;
       Table[f,{i,5}]
Out[]= {1,4,9,16,25}

而全局变量<i>仍然没有得到任何值:

In[]:= i
Out[]= i

最后关于Table要说的是,虽然它是一种局部结构,内置函数Return[]却不能被用来退出(break out of it),不像其他一些我们遇到的局部结构:

In[]:= Table[If[i>3,Return[],i],{i,10}]
Out[]= {1,2,3,Return[],Return[],Return[],Return[],Return[],Return[],Return[]}

小议Range的普适性编辑

就像第一个和第二个例子所呈现的,我们仍然可以用Range产生相同的结果:

In[]:= Range[10]^0
       Range[10]^2
Out[]= {1,1,1,1,1,1,1,1,1,1}
Out[]= {1,4,9,16,25,36,49,64,81,100}

其他的例子也可以使用Range和一点点函数式编程的方法:

In[]:= (Range[3]*#)&/@Range[3]
Out[]= {{1,2,3},{2,4,6},{3,6,9}}
In[]:= Range[#+1,2*#]&/@Range[4]
Out[]= {{2},{3,4},{4,5,6},{5,6,7,8}}
In[]:= Nest[Partition[#,3,1]&,Range[3,8],2]
Out[]= {{{3,4,5},{4,5,6},{5,6,7}},{{4,5,6},{5,6,7},{6,7,8}}}
In[]:= Map[Sin,Range[10]]
Out[]= {Sin[1],Sin[2],Sin[3],Sin[4],Sin[5],Sin[6],Sin[7],Sin[8],Sin[9],Sin[10]}
In[]:= Clear[x];
       x^Range[10]
Out[]= {x,x^2,x^3,x^4,x^5,x^6,x^7,x^8,x^9,x^10}

上面的例子对于现在的我们来说并不容易理解。在这里我们涉及这部分是想表明Range是很有用的,并且澄清Table的角色。实际上,Table可以认为是一种优化的循环。通常用Table产生列表比Do,For或者While 要更快一些。但是在函数式编程中,Table并不常用,不像Range,现在我们可以看到为什么我们能够得到同样的结果,并且,后者运行起来会更快。

在循环结构中产生列表编辑

用Append或者Prepend产生列表编辑

这种循环产生列表的方式是可能的,它很接近过程式编程语言。在Mathematica中,通常这是一种效率最低的方式。同时Table实际上就是一种循环,但是它优化了列表产生过程,从而快一点。从一个空列表开始,使用循环直接产生列表需要内置函数Append,Prepend,AppendTo,PrependTo。Append的作用是在列表的后面添加一个元素,这就是我们即将解释对于较大型列表来说,Append效率低的原因所在。让我们用例子来阐述一下。这里是一个简单的用Append产生的列表:

In[]:= For[testlist={};i=1,i<=10,i++,testlist=Append[testlist,Sin[i]]];
       testlist
Out[]= {Sin[1],Sin[2],Sin[3],Sin[4],Sin[5],Sin[6],Sin[7],Sin[8],Sin[9],Sin[10]}

然后,这是用Range

In[]:= Sin[Range[10]]
Out[]= {Sin[1],Sin[2],Sin[3],Sin[4],Sin[5],Sin[6],Sin[7],Sin[8],Sin[9],Sin[10]}

题外话:myTiming:一个计量运行时间的函数编辑

在这里,我介绍一个自己定义的实用函数myTiming,接下来的内容中我将大量地在各种性能测量中使用它:

Clear[myTiming];
myTiming[x_]:= Module[
                     {z = 0, y = 0, timelim = 0.1, p, q, iterlist = (Power[10, #]& /@ Range[0, 10]),
                        nm = If[ToExpression[StringTake[$Version, 1]] < 6, 2, 1]
                      },
                     Catch[If[(z = Nest[First, Timing[(y++; Do[x, {#}]);], nm]) > timelim,
                     Throw[{z, y}]]& /@ iterlist] /. {p_, q_} :> p / iterlist[[q]]
                    ];
              Attributes[myTiming]={HoldAll};

这个代码现在还有一点复杂,但是当读完整本书,再回来看它是一个不错的主意,因为它阐述了很多关键点。不管怎样,现在我们只是纯粹的使用者。

效率陷阱:用Append构造列表编辑

让我们用Range产生列表逝去的时间与之做个对比,使用函数myTiming:

In[]:= myTiming[For[testlist={};i=1,i<1000,i++,testlist=Append[testlist,Sin[i]]];]
Out[]= 0.19

In[]:= myTiming[Sin[Range[1000]];]
Out[]= 0.0013

我们看到构造一个Sin的(符号值)列表,同样是1000个自然数,Append比Range慢100倍。但是真相是计算的复杂性是不同的,较大的计算在于列表,更多的内部演算在于使用了Append。我们也可以看到Table是怎么运作的:

In[]:= myTiming[Table[Sin[i],{i,1000}];]
Out[]= 0.0023

还是比Range慢一点。

除了慢一点以外,用循环方式的产生过程会引进一个全局的副作用——变量testlist。因此,为了使代码更加clean[5],人们会通过把循环放在一个额外的模块化结构中,这样,代码就更笨了。

因此,我会彻底地劝阻读者在一个循环中直接产生列表。第一,我们几乎完全有更好的设计,方法来避免这个问题。第二,确实是存在变通的方案来得到一个线性的时间绩效来处理这个问题,比如使用嵌套列表(在下面将要进行讨论),或者是索引变量。最后,从版本5开始,有特别的内置函数Reap和Sow被引进特别地用来有效率的生成和收集在计算中起媒介作用的结果——我们会在第二部分有一整章的内容介绍这两个函数。

列表的完全形式编辑

让我再一次强调列表的内部形式满足Mathematica内部的标准表达式的一般要求。例如简单的和嵌套的列表:

In[]:= Clear[testlist,complextestlist];
       testlist=Range[10]
       complextestlist=Range/@Range[5]
Out[]= {1,2,3,4,5,6,7,8,9,10}
Out[]= {{1},{1,2},{1,2,3},{1,2,3,4},{1,2,3,4,5}}

接下来的是它们的完全角式(full forms):

In[]:= FullForm[testlist]
Out[]//FullForm= List[1,2,3,4,5,6,7,8,9,10]
In[]:= FullForm[complextestlist]
Out[]//FullForm= List[List[1],List[1,2],List[1,2,3],List[1,2,3,4],List[1,2,3,4,5]]

这表明了,特别地,列表索引化可以与更一般的Mathematica表达式的索引用相同的方式执行,这在第一章已经强调过了。我们会在下一部分使用这个事实。

Clear[testlist,complextestlist];

使用列表和它们的零件编辑

列表索引和用Part取出元素编辑

简单列表编辑

考虑一个简单列表:

In[]:= Clear[testlist];
       testlist=Range[1,20,3]
Out[]= {1,4,7,10,13,16,19}

然后我们取出一个元素,可以按以下显示内容来完成:

In[]:= testlist[[3]]
Out[]= 7

或者,同样地,就像这样:

In[]:= Part[testlist,3]
Out[]= 7

现在,我们需要取出第二,四,五个元素:

In[]:= testlist[[{2,4,5}]]
Out[]= {4,10,13}

或者,这样:

In[]:= Part[testlist,{2,4,5}]
Out[]= {4,10,13}

列表元素能够从列表的末尾计算。这样的话,它们的位置按照惯例就是负的:

In[]:= testlist[[-1]]
Out[]= 19

关于嵌套列表编辑

考虑一个更复杂的列表:

In[]:= complextestlist=Range[5*#,5*#+4]&/@Range[5]
Out[]= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{25,26,27,28,29}}

它的每一层的元素(层是指到树干的距离[6]见1.1.7)是它的子列表:

In[]:= complextestlist[[2]]
Out[]= {10,11,12,13,14}
In[]:= complextestlist[[{1,4,5}]]
Out[]= {{5,6,7,8,9},{20,21,22,23,24},{25,26,27,28,29}}

为了得到列表中的数字元素,我们需要用两个数字来组成索引(a 2-number indexing)(因为所有子列表具有一层深度,如果它们有深度n的话,那么我们就需要用n+1个数字来组成的索引。并且不同的子列表深度可以是不同的,因而所需要用来组成索引的数字个数也是不同的。)

In[]:= complextestlist[[1,1]]
Out[]= 5

这就意味着“第一个元素的第一个元素”(我们可以把该列表看成为一个2维数组)。注意到语句“In[]:= complextestlist[[{1,1}]] ”将会在语法上理解为原来列表的第一个元素重复两次,也就是第一个子列表重复两次:

In[]:= complextestlist[[{1,1}]]
Out[]= {{5,6,7,8,9},{5,6,7,8,9}}

对于简单列表也是同样的道理:

In[]:= complextestlist[[-1]]
       complextestlist[[-1,-1]]
Out[]= {25,26,27,28,29}
Out[]= 29

Clear[testlist,complextestlist];

Extract编辑

这个函数与Part类似,但它还具有其他的功能,有时候非常有用,但是目前对我们来说并不重要。现在重要的是,它可以一次性在不同的层中取出几个元素(Part也可以取出几个元素,但它们必须是在同一层中)。而且,Extract有一个不同的语法特征——在比第一层更深的另一层中取出一个元素(并且当我们每次取出不止一个元素时),被取出的元素的位置要以列表的形式来表示:

In[]:= testlist=Range[1,20,3];
       complextestlist=Range[5*#,5*#+4]&/@Range[5]
Out[]= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{25,26,27,28,29}}
In[]:= Extract[testlist,1]
       Extract[complextestlist,1]
       Extract[complextestlist,{1,2}]
Out[]= 1
Out[]= {5,6,7,8,9}
Out[]= 6
In[]:= Extract[complextestlist,{{1,2},{3},{4,5}}]
Out[]= {6,{15,16,17,18,19},24}

Take和Drop编辑

这两个函数用来提取和扔掉一个列表里的几个元素。这是我们的列表:

In[]:= testlist=Range[1,20,3]
       complextestlist=Range[5*#,5*#+4]&/@Range[5]
Out[]= {1,4,7,10,13,16,19}
Out[]= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{25,26,27,28,29}}

接下来是一些例子关于Take和Drop怎样工作的:

In[]:= Take[testlist,3]
Out[]= {1,4,7}
In[]:= Take[testlist,{2,4}]
Out[]= {4,7,10}
In[]:= Take[testlist,-3]
Out[]= {13,16,19}
In[]:= Take[testlist,{-4,-3}]
Out[]= {10,13}
In[]:= Drop[testlist,3]
Out[]= {10,13,16,19}
In[]:= Drop[testlist,{2,4}]
Out[]= {1,13,16,19}
In[]:= Drop[testlist,-3]
Out[]= {1,4,7,10}
In[]:= Drop[testlist,{-4,-3}]
Out[]= {1,4,7,16,19}

Take和Drop也有一些扩展的功能,能够自动地对于嵌套列表进行结构上的操作,比如从矩阵中抽取子矩阵。我们并不在这里叙述,详见Mathematica帮助文档。

First,Rest,Last 和Most编辑

这一组函数原则上是多余的,因为

First[list]实际上等价于list[[1]],

Rest[list]等价于Drop[list,1],

Last[list]等价于list[[-1]],

Most[list]等价于Drop[list,-1]。

然而它们可以改善代码的阅读性。

Length编辑

该函数返回列表的长度,比如:

In[]:= testlist=Range[1,20,3]
       complextestlist=Range[5*#,5*#+4]&/@Range[5]
Out[]= {1,4,7,10,13,16,19}
Out[]= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{25,26,27,28,29}}
In[]:= {Length[testlist],Length[complextestlist]}
Out[]= {7,5}

如果我们想要计算complextestlist子列表的长度,可以这样:

In[]:= Table[Length[complextestlist[[i]]],{i,1,Length[complextestlist]}]
Out[]= {5,5,5,5,5}

明显地,i用来表示子列表的索引,因此它取遍1到complextestlist的长度,同时操作Part([[i]])作用其上,表示抽取子列表。

用Part修改列表元素编辑

Part的简单使用编辑

如果需要替代列表中的一些元素,前提已知了一些新表达式或者变量的位置,这样可以直接完成。这是我们的列表:

In[]:= Clear[a];
       testlist=Range[1,20,3]
       complextestlist=Range[5*#,5*#+4]&/@Range[5]
Out[]= {1,4,7,10,13,16,19}
Out[]= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{25,26,27,28,29}}

现在我们要在位置{5}用a替代:

In[]:= testlist[[5]]=a;
       testlist
Out[]= {1,4,7,10,a,16,19}

接着,在列表complextestlist中的每一个子列表中用a随机替代一个元素:

In[]:= For[i=1,i<=Length[complextestlist],i++,complextestlist[[i,Random[Integer,{1,5}]]]=a];
       complextestlist
Out[]= {{5,6,7,8,a},{10,11,a,13,14},{15,16,17,18,a},{20,21,a,23,24},{25,26,27,a,29}}


注意到上述这样的修改只有在列表被储存在变量里才有可能实现(在C语言里,可以说成是左值(L-value))。特别地,如下的输入会出错:

In[]:= Range[10][[3]]=a
Set::setps: Range[10] in the part assignment is not a symbol. >>
Out[]= a

本质上,在上述所有例子中函数Part被用做表达式的修改。我们也认识到用Part来修改列表元素会引发副作用,因为就是原来储存列表的变量被修改,而不是修改列表的一个复制品。

用Part高效修改大型结构编辑

有一点我想提及,Part有一个非常强大的扩展功能,它可以一次性修改很多元素。比如,如果我想修改complextestlist的每一个子列表中的第二个元素,分别用b,c,d,e,f来替代,我可以这样做:

In[]:= Part[complextestlist,All,2]={b,c,d,e,f};
      complextestlist
Out[]= {{5,b,7,8,a},{10,c,a,13,14},{15,d,17,18,a},{20,e,a,23,24},{25,f,27,a,29}}

这表明可以一次性修改很多元素是极其方便的。但是,它局限于当这些部分是来自于一些特殊的结构位置(就像子矩阵)的情况。若欲获悉更多细节,参见Mathematica帮助文档,或者是Ted Ersek的网站[7]

ReplacePart编辑

这是另一个用来修改列表元素的内置函数。但是与上面的直接修改元素的方式和功能上(比如用Part)有很大的差别。认识到作为Part作用后的结果,原来的列表已经被修改了。然而,在Mathematica的更多程序中,我们更希望不去修改原来的列表,而只是改动它的复制品,以保持原来列表不变。这种编程风格可以说更简洁但是要求更多的内存因为原来的对象被复制了。大多数的内置函数采取这样的方式。特别地,ReplacePart也是这样工作的:

In[]:= Clear[a];
       testlist=Range[1,20,3]
Out[]= {1,4,7,10,13,16,19}
In[]:= ReplacePart[testlist,a,5]
Out[]= {1,4,7,10,a,16,19}

但是原来的列表并没有发生改变:

In[]:= testlist
Out[]= {1,4,7,10,13,16,19}

这意味着ReplacePart并不要求左值(L-value)来对一个对象进行操作:

In[]:= ReplacePart[Range[10],a,5]
Out[]= {1,2,3,4,a,6,7,8,9,10}

咦,没有出错哦,因为它没有改变原来的列表只是改变它的复制品。

ReplacePart可以一次性改变多个元素,即使这些元素在表达式不同的层上,例子:

In[]:= ReplacePart[Range[10],a,{{2},{5},{8}}]
Out[]= {1,a,3,4,a,6,7,a,9,10}

我们发现关于元素位置的语法表示和Extract是一样的。在Mathematica帮助文档里关于ReplacePart有更详细的内容。

在这里,我必须提及的是,如果你想一次性在一个大型列表里改变大量的元素,ReplacePart可能会运行得非常慢。在附录C中会有更多的细节阐述。

我并没有马上介绍使用ReplacePart一个接一个地(one by one)改变列表元素(也就是说,在一个循环里)而是一次性改变。理由就是既然它有效地复制整个列表,然后再在复制品上执行修改操作,那么它将在这种连续的方式中复制整个列表,而复制的次数和要做修改的次数是一样的。这就严重导致了效率低下,就像Append和Prepend一样。在另一些情况中,我们还是可以有效地利用Part一次性修改大量元素,我们将会在第六章考虑这个问题(见6.5.5.1)

Position编辑

Position用来确定元素在列表(或者是更普遍的Mathematica表达式)中的位置。这些元素可以匹配一个已给的表达式,或者确切地说,通过模式。

Position的基本用法编辑

最简单地,Position的用法结构是Position[list,element]。让我们来给几个例子: 首先,我们初始化我们的列表:

In[]:= testlist=Range[1,20,3]
       complextestlist=Range[5*#,5*#+4]&/@Range[5]
Out[]= {1,4,7,10,13,16,19}
Out[]= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{25,26,27,28,29}}

我们将要用Position最简单的用法(没有涉及模式)来得到数字“4”在这个列表里的所谓位置:

In[]:= Position[testlist,4]
Out[]= {{2}}

这表示数字“4”在列表testlist中的第二个位置

In[]:= Position[complextestlist,12]
Out[]= {{2,3}}

这表明数字“12”在列表complextestlist的第二个元素的第三个位置上(即complextestlist的第二个子列表的第三个位置上)。

Position能够和Extract一起使用,因为它们使用一样的位置描述方式:

In[]:= Extract[complextestlist,Position[complextestlist,10]]
Out[]= {10}

Position的琐碎使用编辑

这个看起来并不起眼,但是我还是希望能够取出包含数字“10”的整个子列表。我们所要做的就是建立一个新的位置列表,采取扔掉原来位置列表中的最后的元素的方式。

In[]:= Map[Most,Position[complextestlist,10]]
Out[]= {{2}}

Map的作用会在随后得到阐述,现在关键的是它使得如果位置列表包含几个位置,最后一个元素将会被扔掉。比如,我们定义另一个嵌套列表,这个列表中的一些元素会出现不止一次:

In[]:= complextestlist1=Range/@Range[6]
Out[]= {{1},{1,2},{1,2,3},{1,2,3,4},{1,2,3,4,5},{1,2,3,4,5,6}}

这里是数字“4”的所有位置列表:

In[]:= plist=Position[complextestlist1,4]
Out[]= {{4,4},{5,4},{6,4}}

如果我们利用这些位置列表,再结合Extract,我们会取出3次数字“4”:

In[]:= Extract[complextestlist1,plist]
Out[]= {4,4,4}

然而,如果我们想要取出所有包含数字“4”的所有子列表,我们需要更进一步。为了只的到子列表的位置,我们不得不扔掉列表plist中的最后一个元素:

In[]:= Map[Most,plist]
Out[]= {{4},{5},{6}}

现在,我们可以取出子列表了:

In[]:= Extract[complextestlist1,Map[Most,plist]]
Out[]= {{1,2,3,4},{1,2,3,4,5},{1,2,3,4,5,6}}

例子:取出含有已给元素的子列表编辑

现在我们将会写出我们的第一个“serious”的函数:它将从一个列表中取出含有已给元素的子列表。

Clear[sublistsWithElement];
sublistsWithElement[main_List,elem_]:=Extract[main,Map[Most,Position[main,elem]]];

作为例子,这些是在列表complextestlist中含有数字“5”的子列表:

In[]:= sublistsWithElement[complextestlist1,5]
Out[]= {{1,2,3,4,5},{1,2,3,4,5,6}}

我借助这个机会阐明几点在Mathematica中用户自定义函数的一般特征。第一,函数的形成:从一些简单的测试例子开始通常是最好的,就像上面我们一步步演绎的方式来,之后在把所有的东西打包成一个函数。第二,我们看到在一个函数定义中左边的参数中含有一个下划线。这是一个使用模式的标志。目前为止,我将会简要地描述模式x_代表“any expression”然后自动地使得“x”在右边。而SetDelayed(:=)在定义中使用了(在函数中是很正常的)。模式“x_h”表示任何头部为h的表达式(“anything with the head h”)。因此上面出现的模式main_List会与任何列表匹配,而不可以是其他更一般头部不是List的表达式。它构成了一个简单的类型约束。

另一些内容关于函数Position:记住Position是一个已优化的,运行得很快的函数是很重要的,它仍然是一个“general-purpose”函数。特别地,如果你把一个列表按照某些条件分类,对于在大型列表中搜寻一个元素,采取二进制的搜索方式要比Position(具有线性的复杂性)快很多。这种二进制的搜索方式可以在Mathematica中实施(当然它有对数式的复杂性)。

更复杂的例子——具有奇数个奇数元素的子列表编辑

问题: 我们将要阐述Position和模式在一个稍微复杂的例子上一起使用。请你忽略还不熟悉的语法结构,而是要更加注意概念上的部分和把这些看成为一个说明。这个问题是从列表complextestlist1中取出所有含有奇数个奇数元素的子列表。我们的解决方案会一步步来:

In[]:= complextestlist1=Range/@Range[6]
Out[]= {{1},{1,2},{1,2,3},{1,2,3,4},{1,2,3,4,5},{1,2,3,4,5,6}}

解决方案的形成: 步骤一:找到所有奇数元素的位置

In[]:= step1list=Position[complextestlist1,_?OddQ]
Out[]= {{1,1},{2,1},{3,1},{3,3},{4,1},{4,3},{5,1},{5,3},{5,5},{6,1},{6,3},{6,5}}

在每一个小子列表中,我们已经知道,位置列表的第一个元素给出了子列表在complextestlist1出现的位置,第二个元素给出了奇数元素在子列表中的位置。

步骤二:我们把这些联系着同一个子列表的位置结合起来——它们具有相同的第一个元素:

In[]:= step2list=Split[step1list,First[#1]==First[#2]&]
Out[]= {{{1,1}},{{2,1}},{{3,1},{3,3}},{{4,1},{4,3}},{{5,1},{5,3},{5,5}},{{6,1},{6,3},{6,5}}}

函数Split是另一个我们马上就要谈到的内置函数,它的作用是把一个列表按照“相同”的元素分离开形成子列表。“相同”的定义可以由用户自定义。特别地,在我们的例子中,我们告诉Split按照如果step1list的两个子列表具有相等的第一个元素,那么这两个子列表就是“相同”的。那么现在它们被组合在一个额外的列表里。

步骤三:留下第一个元素:

In[]:= step3list=Map[First,step2list,{2}]
Out[]= {{1},{2},{3,3},{4,4},{5,5,5},{6,6,6}}

步骤四:在上面的列表里,只能留下具有奇数个元素的子列表(这些子列表的长度相当于complextestlist1的子列表里的奇数元素的个数,并且还是这些奇数元素在complextestlist1的位置)

In[]:= step4list=Cases[step3list,x_List/;OddQ[Length[x]]]
Out[]= {{1},{2},{5,5,5},{6,6,6}}

函数Cases用来找到列表里所有匹配模式的列表 [8],以后我们会谈到它。

步骤五:用它们的第一个元素代替所有的子列表

In[]:= step5list=Union[Flatten[step4list]]
Out[]= {1,2,5,6}

函数Flatten压平任何列表,函数Union可以除掉重复的元素并且对得到的结果进行排序。

In[]:= complextestlist1[[step5list]]
Out[]= {{1},{1,2},{1,2,3,4,5},{1,2,3,4,5,6}}

把代码打包正一个函数: 我们可以把所有的步骤压缩成一个简单的函数:

Clear[oddSublists];
oddSublists[x_List]:=Part[x,Union[Flatten[Cases[Map
[First,Split[Position[x,_?OddQ],First[#1]==First[#2]&],{2}],y_List/;OddQ[Length[y]]]]]]

我们来检验一下:

In[]:= oddSublists[complextestlist1]
Out[]= {{1},{1,2},{1,2,3,4,5},{1,2,3,4,5,6}}

一个可选择的函数编程手段: 这是一个更简单但是不明显的方式来书写上面的函数oddSublists,它运用了混合的规则和函数式编程风格。在这里我只是作为一个说明罢了:

Clear[oddSublistsNew];
oddSublistsNew[x_List]:=Map[If[EvenQ[Count[#,_?OddQ]],#/.#->Sequence[],#]&,x];

检验一下:

In[]:= oddSublistsNew[complextestlist1]
Out[]= {{1},{1,2},{1,2,3,4,5},{1,2,3,4,5,6}}

第一点,虽然质疑这种编程风格相对于一个传统的过程式编程方式(以嵌套循环为基础)首先变得意味深长的复杂,但是在这里我的主要目的是说明函数Position的使用,也许“give a flavor of a few others”。

第二点,这样书写会更短,便于快速书写。

一个过程式编程版本: 这比基于两个嵌套循环有更少的错误倾向:

Clear[oddSublistsProc];
oddSublistsProc[x_List]:=Module[
                                {pos={},ctr,i,j},For[i=1,i<=Length[x],i++,
                                 For[j=1;ctr=0,j<=Length[x[[i]]],j++,If[OddQ[x[[i,j]]],ctr++];];
                               If[OddQ[ctr],AppendTo[pos,i]];];Return[x[[pos]]]
                               ];

检验:

In[]:= oddSublistsProc[complextestlist1]
Out[]= {{1},{1,2},{1,2,3,4,5},{1,2,3,4,5,6}}

这样的代码除了“clumsier”之外,它还使用了AppendTo来在列表里添加元素,这样使得代码对于大型列表的效率很低,就像我们在前面的例子中谈到的。

Clear[complextestlist1,step1list,step2list,step3list,step4list,
step5list,oddSublists,oddSublistsNew,oddSublistsProc];

列表元素的添加和删除编辑

Append,Prepend,AppendTo和PrependTo编辑

这里面的一些函数我们已经遇到过了。它们在列表的末尾或者开头出添加一个元素,例子:

In[]:= Clear[a];
       testlist=Range[5]
Out[]= {1,2,3,4,5}
In[]:= Append[testlist,a]
Out[]= {1,2,3,4,5,a}
In[]:= Prepend[testlist,a]
Out[]= {a,1,2,3,4,5}
In[]:= testlist
Out[]= {1,2,3,4,5}


最后一个结果表明列表testlist并没有发生改变。正如我们讨论的,没有副作用在Mathematica的内置函数中是特有的。在这里,Append和Prepend加工列表testlist的复制品并修改这个复制品。如果我们要修改原来的列表,我们还可以这样写:

In[]:= testlist=Append[testlist,a];
       testlist
Out[]= {1,2,3,4,5,a}

或者,等价地,用函数AppendTo,确实可以实现的:

In[]:= testlist=Range[5]
Out[]= {1,2,3,4,5}
In[]:= AppendTo[testlist,a];
       testlist
Out[]= {1,2,3,4,5,a}

Prepend和PrependTo是完全类似的。同时,回忆起先前的讨论,我们会怀疑AppendTo或者PrependTo作用在一个列表上,而这样的作用方式不是被分配给任何变量(不是一种左值(L-value))是一个错误。然而我们是对的:[9]

In[]:= Append[Range[5],a]
Out[]= {1,2,3,4,5,a}
In[]:= AppendTo[Range[5],a]
Set::write: Tag Range in Range[5] is Protected. >>
Out[]= {1,2,3,4,5,a}

我们已经讨论过,最好避免使用这些函数(Append等等)来修改大型列表。随后我们会考虑几个更有效方法。

Clear[testlist];

Insert和Delete编辑

从它们的名字看就再明显不过了,这两函数用来在一个列表里插入和删除一个元素,或者是在更一般的Mathematica表达式里作用。它们的操作详见Mathematica帮助文档。我将提供一些简单的例子。Insert的格式是Insert[list,new,pos]——它会将新元素nes插到列表list的位置pos上。Delete的格式是Delete[list,pos],它把列表list位置pos上的元素删除。例子:

In[]:= Clear[a];
       testlist=Range[3,15,2]
Out[]= {3,5,7,9,11,13,15}
In[]:= Delete[testlist,4]
Out[]= {3,5,7,11,13,15}
In[]:= Insert[testlist,a,5]
Out[]= {3,5,7,9,a,11,13,15}

再一次注意到,这两函数作用在列表的复制品上,所以原来的列表没有改变:

In[]:= testlist
Out[]= {3,5,7,9,11,13,15}

同时,这两函数可以作用在嵌套列表里(或者更一般的Mathematica表示式),并且位置将是一个索引列表。而且,它们会接受一些位置组成的列表而不仅仅只是一个位置——在这中情况里,一个元素会马上被插入(删除)到许多位置。

然而,对于Insert的情况,同时插入大量元素时它会变得非常缓慢。在附录C中会有更多详细介绍。

关于嵌套列表编辑

经常会涉及到处理嵌套列表,嵌套列表就是元素是列表的一种列表。我们曾经见过一些嵌套列表。让我们强调一下,总之,嵌套列表和多维数组不是完全相同的,实际上它更一般,因为每一层子列表的长度可以不同。关于一般的嵌套列表,我们唯一可以说的是它代表树。

这里我们只考虑一些特殊作用的函数,它们是为了高效处理某些特殊类型的嵌套列表而设计的。

Partition编辑

该函数用来把列表切割成一个个子列表(可以是重叠)。最简单的形式是Partition[list,size,shift]。它把列表切成长度为size的子列表,然后依据shift来移动到下一个子列表。如果参数shift没有给出,那么列表将会被切割成没有重叠的子列表。还是看例子理解吧:

一个简单的例子编辑

In[]:= testlist=Table[Sqrt[i],{i,1,10}]
Out[]={1,Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2 Sqrt[2],3,Sqrt[10]}
In[]:= Partition[testlist,3]
Out[]={{1,Sqrt[2],Sqrt[3]},{2,Sqrt[5],Sqrt[6]},{Sqrt[7],2 Sqrt[2],3}}
In[]:= Partition[testlist,7]
Out[]= {{1,Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7]}}

在最后的例子中,剩下的部分少于7个,所以剩下的部分就被“吃光”了。现在我们来看看有重叠部分的例子:

In[]:= Partition[testlist,7,1]
Out[]= {{1,Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7]},
 {Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2 Sqrt[2]},
 {Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2 Sqrt[2],3},
 {2,Sqrt[5],Sqrt[6],Sqrt[7],2 Sqrt[2],3,Sqrt[10]}}

实际运用的例子:列表的moving average的计算编辑

这个例子是基于在Wagner’96里的一个简单讨论 问题: 一个列表的m-moving average是这样的平均值:一个列表中的一个元素,考虑个邻居,它和邻居们的平均值(意味着这个平均值是在点(元素)上定义的,这个点(元素)至少有m个左邻右舍)。因此,moving average实际上是一些平均值组成的列表,长度为len-2m ,而len是原来列表的长度。

形成解决方案: 为了解决这个问题,我们首先定义一个辅助的函数,这个函数计算一个列表的平均值。然而,它说明我们的函数也可以作用在一个数字列表上。这次把列表里所有的元素求和(包括具有相同个数的元素)。所以:

Clear[listAverage];
listAverage[x_List]:=Apply[Plus,x]/Length[x];

表达式Apply[Plus,x]计算列表里的每一个元素的和,它的意思会在第五章介绍。

现在我们定义另一个辅助函数:

Clear[neighborLists];
neighborLists[x_List,m_Integer]:=Partition[x,Length[x]-2*m,1];

比如:

In[]:= neighborLists[testlist,1]
Out[]={{1,Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2 Sqrt[2]},
 {Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2Sqrt[2],3},
 {Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2 Sqrt[2],3,Sqrt[10]}}

现在我们意识到中间的那个列表代表“middle points”的列表,第一个列表和最后一个列表就是这些“middle points”的最近的邻居。因此,剩下唯一要做的是使用我们自定义的函数listAverage作用在其结果上:

In[]:= listAverage[neighborLists[testlist,1]]
Out[]= {1/3 (1+Sqrt[2]+Sqrt[3]),1/3 (2+Sqrt[2]+Sqrt[3]),1/3 (2+Sqrt[3]+Sqrt[5]),1/3 (2+Sqrt[5]+Sqrt[6]),
 1/3 (Sqrt[5]+Sqrt[6]+Sqrt[7]),1/3 (2 Sqrt[2]+Sqrt[6]+Sqrt[7]),1/3 (3+2 Sqrt[2]+Sqrt[7]),1/3 (3+2 Sqrt[2]+Sqrt[10])}

把代码打包成一个函数: 因此,我们最终的函数movingAverage就是这样:

Clear[movingAverage,neighborLists,listAverage];
neighborLists[x_List,m_Integer]:=Partition[x,Length[x]-2*m,1];listAverage[x_List]:=Apply[Plus,x]/Length[x];
movingAverage[x_List,m_Integer]:=listAverage[neighborLists[x,m]];

作为例子,我们计算两边各有2个邻居的moving average:

In[]:= movingAverage[testlist,2]
Out[]= {1/5 (3+Sqrt[2]+Sqrt[3]+Sqrt[5]),1/5 (2+Sqrt[2]+Sqrt[3]+Sqrt[5]+Sqrt[6]),
1/5 (2+Sqrt[3]+Sqrt[5]+Sqrt[6]+Sqrt[7]),1/5 (2+2 Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7]),
1/5 (3+2 Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7]),1/5 (3+2Sqrt[2]+Sqrt[6]+Sqrt[7]+Sqrt[10])}

使用函数式编程方式消除辅助函数: 在函数式程序语法的帮助下,我么可以写出下面简单的函数并且消除对辅助函数的需要:

Clear[movingAverage];
movingAverage[x_List,m_Integer]:=(Plus@@#)/Length[#]&@Partition[x,Length[x]-2*m,1];

检验:

In[]:= movingAverage[testlist,2]
Out[]= {1/5 (3+Sqrt[2]+Sqrt[3]+Sqrt[5]),1/5 (2+Sqrt[2]+Sqrt[3]+Sqrt[5]+Sqrt[6]),
1/5 (2+Sqrt[3]+Sqrt[5]+Sqrt[6]+Sqrt[7]),1/5 (2+2 Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7]),
1/5 (3+2 Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7]),1/5 (3+2 Sqrt[2]+Sqrt[6]+Sqrt[7]+Sqrt[10])}

一个过程式程序版本: 这个是同样的东西,用过程式程序实现:

movingAverageProc[x_List,m_Integer]:=Module[
                                            {i,j,ln=Length[x],aver,sum},aver=Table[0,{ln-2*m}];For[i=m+1,i<=ln-                      m,i++,sum=0;
                                            For[j=i-m,j<=i+m,j++,sum=sum+x[[j]]];aver[[i-m]]=sum/(2*m+1)];aver];

检验:

In[]:= movingAverageProc[testlist,2]
Out[]= {1/5 (3+Sqrt[2]+Sqrt[3]+Sqrt[5]),1/5 (2+Sqrt[2]+Sqrt[3]+Sqrt[5]+Sqrt[6]),
1/5 (2+Sqrt[3]+Sqrt[5]+Sqrt[6]+Sqrt[7]),1/5 (2+2Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7]),
1/5 (3+2 Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7]),1/5 (3+2 Sqrt[2]+Sqrt[6]+Sqrt[7]+Sqrt[10])}

效率对比: 过程式程序的问题不仅仅是代码更长,而是更容易出错(数组界限(array bounds),变量初始化等等)。另外,它的效率极低。让我们用大型列表来对比一下:

In[]:= Timing[movingAverage[Range[10000],10];]
Out[]= {0.016,Null}
In[]:= Timing[movingAverageProc[Range[10000],10];]
Out[]= {1.172,Null}

当然,我们也可以通过更加方便的内置函数来完成这一过程甚至可以拓展成MovingAverage的样子。例如RotateRight,Take或者ListCorrelate,但是这些就太像MovingAverage本身了。 这里也给出例子:

ma1[x_List,m_Integer]:=ListCorrelate[ConstantArray[1,m],x]/m

ma2[x_List,ker_List]:=ListCorrelate[ker,x]/Total@ker

ma3[x_List,m_Integer]:=Average[RotateRight[x,#]&/@Range[0,m-1]] [ [m;;] ]

这两个函数在快速解决和计算各类问题的时候也非常有用,尤其是让一个元素和左右元素有关联的时候这样的整体式的处理方法会很快和有效。

在这里,我们看到了100倍的差距(因为列表的长度)!更多的是,这不是一个不变的因素,但是随着列表长度的增加差距会进一步拉大。当然,在过程式编程语言例如C’语言里,后者的程序更自然而且更快。但在Mathematica却不是这样!然而,我们还是可以通过函数式编程方法得到简洁,快速,高雅的代码。

Clear[testlist];

Transpose编辑

这是最有用的内置函数之一。它的名字来源于代表2维列表的列表——矩阵,它执行调换操作(transposition operation)。然而,我们并不总是一定要把2维数组翻译成列表,特别如果该数组里的元素是不同类型的。这也表明了Transpose可以完成大量的任务。让我们先从数字列表开始,我们现在有一个已知的以列表作为元素的列表(它们可以是列表本身,但是这不影响我们):

简单例子:调换一个简单列表编辑

In[]:= testlist=Table[i+j,{i,1,2},{j,1,3}]
Out[]= {{2,3,4},{3,4,5}}

然后,

In[]:= Transpose[testlist]
Out[]= {{2,3},{3,4},{4,5}}

例子:调换一个列表的列表编辑

另一个例子:

In[]:= testlist=Table[{i,j},{i,1,2},{j,1,3}]
Out[]= {{{1,1},{1,2},{1,3}},{{2,1},{2,2},{2,3}}}

这是一个2维数组。

In[]:= Transpose[testlist]
Out[]= {{{1,1},{2,1}},{{1,2},{2,2}},{{1,3},{2,3}}}

例子:成绩和姓名结合编辑

另一个例子:我们已经有了考试的一些分数——作为第一个列表,和学生的姓名——作为第二个列表。我们想做一个简单的裂变就像这个样子{{学生1,成绩1}……}。

Clear[names,scores];
names={"Smith","Johnson","Peterson"};
scores={70,90,50};

然后我们这样做:

In[]:= Transpose[{names,scores}]
Out[]= {{Smith,70},{Johnson,90},{Peterson,50}}

但是我们用Transpose,再结合函数式程序会得到更多,因为Transpose确实是在高效率结构重整中频繁使用。在本章接下来的内容里,我们将看到很多关于使用它的例子。

当然,我们也可以通过Thread来完成: Thread[{names,scores}] <\code>

Flatten编辑

这个函数用来破坏嵌套列表的结构,因为它搬走所有内部的花括号并将任何复杂的嵌套列表转换成一个平坦的列表。

简单例子:压平一个嵌套列表编辑

In[]:= teselist=Table[{i,j},{i,1,2},{j,1,3}]
Out[]= {{{1,1},{1,2},{1,3}},{{2,1},{2,2},{2,3}}}
In[]:= Flatten[testlist]
Out[]= {1,1,1,2,1,3,2,1,2,2,2,3}

压平列表的特定层编辑

我们可以令Flatten更仁慈些和有选择性的,通过命令它去破坏表达式的某个层。被破坏的层可以在Flatten的可选择的第二个参数中给出。比如:

In[]:= Flatten[testlist,1]
Out[]= {{1,1},{1,2},{1,3},{2,1},{2,2},{2,3}}

例子:一层层地压平一个嵌套列表 另一个例子:

In[]:= testlist=Table[{i,j,k},{i,1,2},{j,1,2},{k,1,3}]
Out[]= {{{{1,1,1},{1,1,2},{1,1,3}},{{1,2,1},{1,2,2},{1,2,3}}},{{{2,1,1},{2,1,2},{2,1,3}},{{2,2,1},{2,2,2},{2,2,3}}}}
In[]:= Flatten[testlist,1]
Out[]= {{{1,1,1},{1,1,2},{1,1,3}},{{1,2,1},{1,2,2},{1,2,3}},
 {{2,1,1},{2,1,2},{2,1,3}},{{2,2,1},{2,2,2},{2,2,3}}}
In[]:= Flatten[testlist,2]
Out[]= {{1,1,1},{1,1,2},{1,1,3},{1,2,1},{1,2,2},{1,2,3},{2,1,1},{2,1,2},{2,1,3},{2,2,1},{2,2,2},{2,2,3}}
In[]:= Flatten[testlist,3]
Out[]= {1,1,1,1,1,2,1,1,3,1,2,1,1,2,2,1,2,3,2,1,1,2,1,2,2,1,3,2,2,1,2,2,2,2,2,3}

实际上,会更频繁地用Flatten[expr]来得到一个完全平坦的列表。或者用Flatten[expr,1]来去掉一些内部的花括号当我们只需要一些起媒介作用的步骤而不再做其他操作。

应用:计算的二次规范的任意秩张量(向量,矩阵等)编辑

问题和解决方案 这里我们会展示Flatten是怎样戏剧性地简化任意秩的张量的二次范数计算的用处。令人吃惊的是我们将不需要把张量的秩作为一个单独的参数。所以,我么将从这个代码开始:

Clear[tensorNorm];
tensorNorm[x_List]:=Sqrt[Plus@@Flatten[x^2]];

这里说明了这个简洁的代码是解决问题的主要部分。

解剖代码: 让我们先用一个例子来说明它是怎么工作的。这是我们的矩阵:

In[]:= testmatr=Table[i+j,{i,1,3},{j,1,3}]
Out[]= {{2,3,4},{3,4,5},{4,5,6}}

范数就是对矩阵的所有元素的平方和开根号。首先,我们要利用一个事实:算数操作比如(raising to some power)能够作用在整个列表上。因为它们能够自动地贯穿整个列表(具有这种性质的函数说成是Listable)。因此,我们首先平方所有元素:

In[]:= testmatr^2
Out[]= {{4,9,16},{9,16,25},{16,25,36}}

既然我们并不关心元素确切的位置而只需要对它们求和,我们用Flatten来去掉内部的花括号:

In[]:= Flatten[testmatr^2]
Out[]= {4,9,16,9,16,25,16,25,36}

现在我们有了所有的元素组成的列表了,而且我们已经看到这个可以靠Plus@@来建造:

In[]:= Plus@@Flatten[testmatr^2]
Out[]= 156

最后,我们还要开平方:

In[]:= Sqrt[Plus@@Flatten[testmatr^2]]
Out[]= 2 Sqrt[39]

哈,我们得到函数代码啦。我们看到函数很漂亮地作用具有任意秩的张量上而没有作修改!没有了Flatten是很难做到的,尤其是在像C语言的那些语言里,我们会需要嵌套循环来完成。(在C语言里,也是有一个叫做压平数组的技巧,但是它存在于利用row-major order,而这个row-major order储存在内存中并且 多维数组 虽然它能够发挥作用,但那将是非法的如果你想严格遵照C语言的标准)。[10]


Clear[tensorNorm,testmatr];

应用:用Flatten(相当地)快地产生列表编辑

就像我们曾经谈到的,在效率方面,在循环中直接生成列表可能是最糟糕的方式。我们可以使用Flatten来对这个过程进行提速,这是可以考虑的。我们想生成一个从1到10的列表(最简单的,当然,只要Range[10]就能完成),我们用接下来的方式来做:

步骤一:我们生成一个嵌套列表(这种列表在Mathematica中也叫做linked lists):

In[]:= For[testlist={};i=1,i<=10,i++,testlist={testlist,i}];
       testlist
Out[]= {{{{{{{{{{{},1},2},3},4},5},6},7},8},9},10}

步骤二:我们使用Flatten:

In[]:= Flatten[testlist]
Out[]= {1,2,3,4,5,6,7,8,9,10}

让我们来用之前使用Append的方式来对比一下运行时间

In[]:= For[testlist={};i=1,i<5000,i++,AppendTo[testlist,i]];//Timing
Out[]= {0.25 Second,Null}

现在是我们的新方法:

In[]:= (For[testlist={};i=1,i<5000,i++,testlist={testlist,i}];Flatten[testlist];)//Timing
Out[]= {0.016 Second,Null}

我们看到差距至少就在于命令的长度。即使这个方法本身并不是最有效率的,但是我们将会看到嵌套列表是怎样被用来戏剧性地在某些问题中提高效率。

Clear[testlist];

列表间的集合运算编辑

经常会用到两个或两个以上列表的并集,交集和补集,也经常要去掉列表中的重复的元素。这些可以用内置函数Join,Intersection,Complement和Union来完成。

Join编辑

函数Join把两个或两个以上的列表连接起来。格式是Join[list1,…,listn],<list1,…,listn>是列表,不要求具有相同的深度和结构。如果列表包含相同的元素,这些相同的元素并没有被删除,也就是列表被连接起来,而在它们的内部结构中没有更多的修改。例子:

Clear[a,b,c,d,e,f];
In[]:= Join[{a,b,c},{d,e,f}]
Out[]= {a,b,c,d,e,f}
In[]:= Join[{{a,b},{c,d}},{e,f}]
Out[]= {{a,b},{c,d},e,f}

Join从左往右把列表连接在一起,没有对列表进行任何排序和变换。

Intersection编辑

函数Intersection找到两个或两个以上列表的共同元素,也就是说它将得到属于所有列表的所有元素。格式是:Intersection[list1,…,listn]。例子:

In[]:= Clear[a,b,c,d,e,f];
       Intersection[{a,b,c},{b,c,d,e}]
Out[]= {b,c}
In[]:= Intersection[{a,b,c,d,e,f},{a,b,c},{c,d,e}]
Out[]= {c}
In[]:= Intersection[{a,b,c},{d,e,f}]
Out[]= {}

在最后的例子中我们得到一个空列表,因为两个列表的交集是空集。

函数Intersection有一个选项SameTest,这个选项可以用来提供一个定制的“sameness”函数——即我们可以定义“same”的概念,与默认情况下是不同的。请看函数Union关于这个选项运用的例子。同时,有了这个选项,Intersection会变得很慢,比它单纯的形式更慢。在附录C中有详细的描述。

Complement编辑

函数Complement[listAll,list1,…listn]给出其他列表<list1,…listn>的并集在列表<listAll>中的补足元素。换句话说,它返回在列表<listAll>中的而不再任何一个列表<listk>的元素。而且Complement还对结果排序。例子:

In[]:= Complement[{a,b,c,d,e,f},{b,c,e}]
Out[]= {a,d,f}
In[]:= Complement[{a,b,c,d,e,f},{b,c,e},{d,e,f}]
Out[]= {a}
In[]:= Complement[{a,b,c,d,e,f},{b,c,e},{d,e,f},{a,b,c}]
Out[]= {}

函数Complement,就像Intersection一样也有选项SameTest。它允许我们定义关于“same”的观念。所有的我对Intersection关于这个选项的注解,将在这本书里应用。

和列表排序相关的函数编辑

这里我们讨论非常和列表排序有关的有用的内置函数。函数Sort对列表进行排序。函数Union去除列表中的重复元素并且对结果排序。函数Split将列表分割为由相同的靠近的元素构成的子列表。对这三个函数都可以定义“sameness”的概念,而与默认的定义不同。下面,我们给出更多的细节和每个函数用法的例子。

Sort编辑

基础Sort编辑

这个函数用来对列表进行排序。比如:

In[]:= Clear[a,b,c,d,e,f,g,t];
       Sort[{a,d,e,b,g,t,f,d,a,b,f,c}]
Out[]= {a,a,b,b,c,d,d,e,f,f,g,t}


In[]:= Sort[{5,7,2,4,3,1}]
Out[]= {1,2,3,4,5,7}

函数Sort可以对任意Mathematica表达式进行排序。由于疏忽(by default),Sort是依照词典编撰对符号进行排序,按数字的升序进行或者依照列表的第一个元素。总之,这就是Mathematica中的标准排序顺序,查询Mathematica帮助文档可以得到更多信息。

作为例子,我们对一个嵌套正数列表进行排序:

In[]:= nested=Table[Random[Integer,{1,15}],{5},{Random[Integer,{3,10}]}]
Out[]= {{13,3,11,7},{15,15,14,11,15,14},{11,10,2},{11,12,9,11,1,4},{7,4,15,11,9}}
In[]:= Sort[nested]
Out[]= {{11,10,2},{13,3,11,7},{7,4,15,11,9},{11,12,9,11,1,4},{15,15,14,11,15,14}}

我们看到排序是在按照子列表的第一个元素进行的。[11]

按照用户定义的排序函数进行排序编辑

作为一个选项的第二个参数,Sort接受一个对比函数来替代默认函数。例子:

In[]:= Sort[{5,7,2,4,3,1},Greater]
Out[]= {7,5,4,3,2,1}

我们可以按照子列表的长度来排序嵌套列表。首先定义一个排序函数:

Clear[sortFunction];
sortFunction[x_List,y_List]:=Length[x]<Length[y];

然后我们来进行排序:

In[]:= Sort[nested,sortFunction]
Out[]= {{11,10,2},{13,3,11,7},{7,4,15,11,9},{11,12,9,11,1,4},{15,15,14,11,15,14}}

初识纯函数编辑

Mathematica提供一个途径来构造和使用函数,而没有给出这些函数的名称或者单独的定义,这些就叫做“纯函数”(pure function)(在一些语言中也叫做 函数(lambda function))。我们将系统性地介绍它,但是现在我们只是为了理解上面的排序过程才提及纯函数。

In[]:= Sort[nested,Length[#1]<Length[#2]&]
Out[]= {{11,10,2},{13,3,11,7},{7,4,15,11,9},{11,12,9,11,1,4},{15,15,14,11,15,14}}

任何可以返回True或者False的带有两个变量的函数都可以称为排序函数。这是假定了给出True或者False依赖于那一个元素更“大”。

我必须提到人们使用Sort——定义了排序函数,会使得程序变慢,在附录C中有详细讨论。

Ordering编辑

该函数给出列表中元素按Sort顺序排列的位置。它里头也可以有用户定义的“纯”形式——定义对比函数。它给出的信息比仅仅只有Sort的情况下更多,特别是结合Orderding和Part来排序列表。

列表:

In[]:= listtosort={a,d,e,b,g,t,f,d,a,b,f,c}
Out[]= {a,d,e,b,g,t,f,d,a,b,f,c}
In[]:= Ordering[listtosort]
Out[]= {1,9,4,10,12,2,8,3,7,11,5,6}
In[]:= listtosort[[Ordering[listtosort]]]
Out[]= {a,a,b,b,c,d,d,e,f,f,g,t}

Ordering是一个很有用的函数,正是因为它给出的信息比仅仅只有Sort的情况下更多,而且和Sort本身具有一样的效率。我们将会在第六章看到它的例子。

Union编辑

函数Union格式是Union[list]返回的列表<list>所有不同元素的标准排序结果。

基础Union编辑

在它的基本形式里,Union把列表看成一个单独的变量,在一个列表里返回已排序的唯一的元素。排序过程是在Mathematica默认排序函数下进行的(按照词典编撰顺序对符号表达式排序,对数字进行升序排列,依照列表的第一个元素等等)。例子:

In[]:= Union[{a,d,e,b,g,t,f,d,a,b,f,c}]
Out[]= {a,b,c,d,e,f,g,t}
In[]:= testlist=Table[Random[Integer,{1,10}],{15}]
Out[]= {9,7,4,3,1,1,8,2,2,10,7,4,9,1,4}
In[]:= Union[testlist]
Out[]= {1,2,3,4,7,8,9,10}

Union对结果进行排序这一事实,本质上是和Union内部算法有关系的。如果元素没有被排序,人们可以写出一个传统的union函数(我们会在5.2.6.2.5考虑一些这方面的实现),这个函数将会比内置函数Union慢。

带有SameTest选项的Union编辑

函数Union也有选项SameTest,它允许我们给出关于那些元素是“一样”的定义。比如,我们认为只要两个元素都是以3为模,那么它们就是相同的:

In[]:= Union[testlist,SameTest->(Mod[#1-#2,3]==0&)]
Out[]= {1,2,3}

带有SameTest选项的Union函数会变得很慢,比不带选项的Union慢的多。在附录C有更多的讨论。

Split编辑

该函数用来把列表切成几个子列表,以致于每个子列表的元素是相同的。它也可以接受“sameness”函数作为第二个可选的参数。它从头到尾查看列表,并比较相邻的元素,使用默认“sameness”函数(SameQ)或者是我们自己给出的“sameness”函数。每当相邻的两个元素不是一样的,它就把已经是相同的元素放进一个列表里,然后再重新开始另一个子列表。

基础Split编辑

在基本形式中,Split把列表切成子列表,当只有一个参数时,使用SameQ来断定元素的比较。这里我们引入一个列表和它的排序结果:

In[]:= testlist=Table[Random[Integer,{1,15}],{20}]
       sorted=Sort[testlist]
Out[]= {8,12,10,3,13,15,13,6,6,2,4,9,5,11,6,10,7,4,15,5}
Out[]= {2,3,4,4,5,5,6,6,6,7,8,9,10,10,11,12,13,13,15,15}

因为一般在一个没有被排序的列表里相邻的元素是不同的,我们看到大多数子列表会含有一个单独的元素;

In[]:= Split[testlist]
Out[]= {{8},{12},{10},{3},{13},{15},{13},{6,6},{2},{4},{9},{5},{11},{6},{10},{7},{4},{15},{5}}

而一个已经排序的列表却不是这样:

In[]:= Split[sorted]
Out[]= {{2},{3},{4,4},{5,5},{6,6,6},{7},{8},{9},{10,10},{11},{12},{13,13},{15,15}}

带有用户定义的sameness函数的Split编辑

我们现在可以定义两个元素的“相同”,如果它们除以3有相同的余数.然而,在使用Split把相同的元素放在一起之前,我们将会用不同的排序函数来排序列表。以致于当相邻的两个数除以3有相同的余数时,就把它们放在一个已经排好序的列表里:

In[]:= mod3sorted=Sort[testlist,Mod[#1,3]<Mod[#2,3]&]
Out[]= {15,6,9,6,6,15,3,12,4,7,10,4,13,13,10,5,11,5,2,8}

现在我们可以split这个列表了:

In[]:= Split[mod3sorted,Mod[#1,3]==Mod[#2,3]&]
Out[]= {{15,6,9,6,6,15,3,12},{4,7,10,4,13,13,10},{5,11,5,2,8}}

Split是一个很有用的函数。因为它对列表执行一个简单的扫视,而且只是比较相邻的元素,具有线性的复杂性。再者,因为比较的次数等于列表的长度减一,和用户定义的sameness函数(在函数Sort和Union那里曾经讨论过的)联系在一起时,它并不会碰到严重的性能上的障碍。

例子:run-length 编码编辑

Split的一个标准应用是run-length编码。给出一个含有尽可能重复元素的列表,这个编码由用一个像{{num1,freqk1},…}列表替换原来的列表。<freqk>给出<numk>出现的总次数。比如,以我们第一个例子的结果来说明:我们需要做的是把每一个子列表变成我们刚才所说的那种形式,可以这样做:

Clear[runEncodeSplit];
runEncodeSplit[spl_List]:=Table[{spl[[i,1]],Length[spl[[i]]]},{i,Length[spl]}];
Clear[runEncode];
runEncode[x_List]:=runEncodeSplit[Split[x]];

检验:

In[]:= runEncode[sorted]
Out[]= {{2,1},{3,1},{4,2},{5,2},{6,3},{7,1},{8,1},{9,1},{10,2},{11,1},{12,1},{13,2},{15,2}}

用函数式编程方法,我们可以去掉一个辅助函数runEncodeSplit:

Clear[runEncodeFP];
runEncodeFP[x_List]:=Map[{First[#],Length[#]}&,Split[x]];

检验:

In[]:= runEncodeFP[testlist]
Out[]= {{8,1},{12,1},{10,1},{3,1},{13,1},{15,1},{13,1},{6,2},{2,1},{4,1},
 {9,1},{5,1},{11,1},{6,1},{10,1},{7,1},{4,1},{15,1},{5,1}}[12]

例子:计算相同元素的频率编辑

作为另一个与Split有关的应用,我们将会结合Sort来实现一个可以计算列表中相同元素的频率的函数。如果我们注意到我们刚才已经对原来的列表进行排序了,就是刚才的runEncode函数作用在一个已经排好序的列表上,这是极其容易的。

Clear[frequencies];
frequencies[x_List]:=runEncode[Sort[x]];

检验:

In[]:= frequencies[testlist]
Out[]= {{2,1},{3,1},{4,2},{5,2},{6,3},{7,1},{8,1},{9,1},{10,2},{11,1},{12,1},{13,2},{15,2}}

实际上,本质上函数Frequencies被应用在附加的‘Statistics‘DataManipulation程序包中。

在很多其他情况下Split是很有用的,我们在接下来的章节中会给出更深入的例子。 Clear[testlist,sorted,mod3sorted,listDivide,frequencies,runEncodeSplit,runEncode,runEncodeFP];

小结:编辑

本章我们介绍了列表——在Mathematica中数据结构最重要的砖块。我们考虑了几种列表操作比如生成列表,元素的取出,添加,替换和删除,在列表中定位具有某种特性的元素,还有几种特别的函数:在一个或集合列表上进行快速的结构性操作。还有一些关于排序列表的函数。一下内置函数得到详细的讨论:Range,Table,Part,Extract,Take,Drop,First,Rest,Most,Last,Position,Length,Append,Prepend,AppendTo,PrependTo,Partition,Transpose,Flatten,Join,Union,Intersection,Complement,Sort,Split。

有了这些函数武装起来的我们,已经对解决各种各样的问题有了很大的帮助。然而,我们需要serious program building另一个主要的组成部分——对Mathematica函数的理解:它们是什么?怎么定义它们?等等。这是下一章的主题。

注记编辑

  1. 详见Mathematica帮助文档 ref/Depth
  2. 详见Mathematica帮助文档tutorial/ExpressionsAsTrees和ref/TreeForm
  3. 这里译得不好!原文:As these examples show,Table accepts one or more lists which indicate the iteration bounds,but we can fill the lists with some functions computed on the counters being iterated.In cases when we have more than one iterator, we create a nested list where the innermost iterators correspond to the outermost lists.As we see,the bounds of the more outermost iterators may depend on the variables of more innermost ones,in which case the lists will have sublists of different lengths.
  4. 原文在是用matrix的,但是考虑到在Mathematica中矩阵和列表还是有区别的,为了避免麻烦,故译成列表。
  5. 此处的clean不能光是理解为“简洁”,还有“避免产生其他的麻烦”的意思。
  6. 参见Mathematica帮助文档tutorial/LevelsInExpressions中的“从树结构的观点看层次时,将树的顶部看成第0层,一个表达式中的某一项所在的层次简单地说就是它到顶层的距离.”准确些。
  7. Ted Ersek's Mathematica Tricks - Verbeia.com
  8. 原文:Cases is the command used to find the list of all occurrences of some expression or pattern in a larger expression.
  9. 我不确定这样翻译是否正确,原文:The situation with Prepend and PrenpendTo is completely analogous.And also,recalling the previous discussions, we may suspect that the application of AppendTo of PrependTo to a list which is not assigned to any variable(not an L-value)is a mistake,and we will be correct:
  10. 这里出现严重的问题!!!原文:in C,there is also a technique called flattening an array,which consists in exploiting the row-major order in which it is stored in memory and going through the multidimensional array with just a pointer to an integer(or whatever is the type of the smallest array .
  11. 原文最后一个程序结果是有问题的,译者已修改。参见Mathematica帮助文档ref/Sort,对于表达式排序,Sort 首先将较短表达式的放在前面,然后按深度优先的方式比较子集。
  12. 这里的testlist=Table[Random[Integer,{1,15}],{20}],即testlist={8,12,10,3,13,15,13,6,6,2,4,9,5,11,6,10,7,4,15,5}