第3章 元素列表
目录 |
1 介绍
列表(List),有时称元素列表,或简称为表,是Mathematica 中最主要的数据结构。这在其他的函数式编程语言如 LISP 中也是如此。任意的复杂的数据结构皆能表达为某种形式(可以是复杂的含嵌套的)的元素列表。例如:N维的数组(array)可表示为深度为 N 的元素列表。任意的树图也可以表示为元素列表。
列表可以在程序运行过程当中即时地被产生,所以设计优良的函数应该能对任意的未知长度的列表进行操作,且不须要将表的长度直接作为参数。这种设计原则往往使得程序既简短又容易构造。列表的另一个优点是对它进行操作的函数一般来说很容易调试――我们会在本章给出很多实例。这一章中我们先介绍一些用以产生和操作列表的系统函数。
2 Mathematica 中列表操作的基本原则
用Mathematica 对列表,尤其是很大的表,进行操作的时候,一般应遵循一个原则:任意一个需要处理的表都应当被当做一个对象,而不应将它分成(比如用元素的指标拆分)若干部分分别处理。换句话说,最佳的程序设计应该是把列表当成一个整体进行操作的。这个原则对于函数式编程特别重要,可以大大提高程序的效率。我们将对此详细举例说明,特别是在第5章讲解函数式编程时。
3 列表的内容
列表并非只能含有数据类型一致的元素,相反,它们可以是任意的Mathematica 表达式(expression),甚至,列表元素本身也可以是表,不论长度和深度。本质上说,元素列表只是一般Mathematica 表达式的一个特例而已,它的特性是它的头(head)是 List
:
In[X]:= Clear[x];
In[X]:= List[Sin[x], Cos[x], Tan[x]]
Out[X]:= {Sin[x], Cos[x], Tan[x]}
4 构造列表
构造列表的方法很多:
4.1 手动构造
最基本的方法是手动地、显式地定义列表,如:
In[X]:= Clear[testlist, a, b, c, d, e]; testlist = {a, b, c, d, e} Clear[testlist];
Out[X]:= {a,b,c,d,e}
4.2 构造等差数列列表
应用问题中经常遇到需要构造以等差数列为元素的列表。这在函数式编程中尤为常见,原因是对等差数列列表进行操作的函数取代了循环(loop)的作用,例如:
In[X]:= Range[5] Range[2, 10] Range[2, 11, 3] Range[0, 1, 0.1]
Out[X]:= {1, 2, 3, 4, 5} {2, 3, 4, 5, 6, 7, 8, 9, 10} {2, 5, 8, 11} {0.,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.}
4.3 用Table构造列表
还可以用Table更一般地构造列表,如:
In[X]:= 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[X]:= {1,1,1,1,1,1,1,1,1,1} {1,4,9,16,25,36,49,64,81,100} {{1,2,3},{2,4,6},{3,6,9}} {{2},{3,4},{4,5,6},{5,6,7,8}} {{{3,4,5},{4,5,6},{5,6,7}},{{4,5,6},{5,6,7},{6,7,8}}} {Sin[1],Sin[2],Sin[3],Sin[4],Sin[5],Sin[6],Sin[7],Sin[8],Sin[9],Sin[10]}
如上例子所示,Table可以接受一个或更多的表示迭代界限的列表为参数,且列表元素可以用含迭代变量的通项公式表达。如果有多个迭代变量,生成的列表则为多层嵌套的列表(nested lists),最内层的迭代变量对应结果中最外层的列表。而且(从第四例中)我们可以看出,外层迭代变量(j
)的界限可以依赖于内层变量(i
)的值,于是结果就会含有长度不一的子列表(sublists)。这也说明,列表比(多维)数组(array)更一般,因为作为列表元素的子列表不一定要有一致的长度。另外,用Table生成的列表不一定只含数字,它的元素可以是表达式:
In[X]:= Clear[i, x]; Table[x^i, {i, 1, 10}]
Out[X]:= {x, x^2, x^3, x^4, x^5, x^6, x^7, x^8, x^9, x^10}
我们来产生一个3×3的矩阵并使其各矩阵元均为单项式:
In[X]:= Clear[i, j, x]; Table[x^(i+j), {i, 1, 3}, {j, 1, 3}]
Out[X]:= {{x^2, x^3, x^4}, {x^3, x^4, x^5}, {x^4, x^5, x^6}}
值得一提的是Table对它的循环变量进行了作用域的限定。它的限定效果和 Block[]
的限定效果一致(见第4章 规则、模式和函数)。在下例中,我们可能自然地认为 f[i]
的值会被打印5次,因为 f
的定义用到了全局变量 i
:
In[X]:= Clear[f, i]; f := i^2; Table[f, {i, 5}]
Out[X]:= {1, 4, 9, 16, 25}
但实际上全局变量 i
并没有被赋值:
In[X]:= i
Out[X]:= i
虽然有限定作用域的效果,但它却不像别的限定作用域的结构那样,可以用 Return[]
从中跳出:
In[X]:= Table[If[i>3, Return[], i], {i, 10}]
Out[X]:= {1, 2, 3, Return[], Return[], Return[], Return[], Return[], Return[], Return[]}
【编译者按】实际上可以用 Return[res, Table]
从 Table
的某次迭代中跳出并返回 res
。∎
4.4 关于 Range[]
的普遍性
以上第一、二个例子中实现的效果我们还可以用 Range[]
达到:
In[X]:= Range[10]^0
In[X]:= Range[10]^2
Out[X]:= {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Out[X]:= {1, 4, 9, 16, 25, 36, 49, 64, 81, 100}
而另外几个例子也可以用 Range[]
和函数式编程的方式来做:
In[X]:= (Range[3]*#) & /@ Range[3]
Out[X]:= {{1, 2, 3}, {2, 4, 6}, {3, 6, 9}}
In[X]:= Range[#+1, 2*#] & /@ Range[4]]
Out[X]:= {{2}, {3, 4}, {4, 5, 6}, {5, 6, 7, 8}}
In[X]:= Nest[Partition[#, 3, 1] &, Range[3, 8], 2]
Out[X]:= {{{3, 4, 5}, {4, 5, 6}, {5, 6, 7}}, {{4, 5, 6}, {5, 6, 7}, {6, 7, 8}}}
In[X]:= Map[Sin, Range[10]]
Out[X]:= {Sin[1], Sin[2], Sin[3], Sin[4], Sin[5], Sin[6], Sin[7], Sin[8], Sin[9], Sin[10]}
In[X]:= Clear[x];
In[X]:= x^Range[10]
Out[X]:= {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那样特别常用,原因之一就是两者常有类似的功能,且Range常能达到更高的效率。
4.5 在循环中产生列表
4.5.1 用Append和Prepend产生列表
如此产生列表是可行的,并且和大多数过程式编程语言的方法最接近。但是在Mathematica 中,这样做往往是效率最低的方法。Table本质上已然是一个循环语句,并且对于产生列表这一操作是被优化过了的,所以很快。如果要在循环中直接产生列表,则需用到Append,Prepend,AppendTo,PrependTo。 从一个空列表开始,Append在此列表的末尾出添加一个元素,在Mathematica 中这样做的效率是很低的,特别是对特别大的列表而言。我们先用一个例子来说明这个问题。这里是一个用Append产生的列表:
In[X]:= For[testlist = {}; i = 1, i <= 10, i++, testlist = Append[testlist, Sin[i]]];
In[X]:= testlist
Out[X]:= {Sin[1], Sin[2], Sin[3], Sin[4], Sin[5], Sin[6], Sin[7], Sin[8], Sin[9], Sin[10]}
而如果用Range的话:
In[X]:= Sin[Range[10]]
Out[X]:= {Sin[1], Sin[2], Sin[3], Sin[4], Sin[5], Sin[6], Sin[7], Sin[8], Sin[9], Sin[10]}
4.5.2 题外话:myTiming
:一个方便的计时工具
这里我们介绍一个本书中常用的的测量程序运行效率的计时工具:
Clear[myTiming];
Attributes[myTiming] = {HoldAll};
myTiming[x_] := Module[
{
z = 0,
y = 0,
p, q,
timelim = 0.1,
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};
【编译者按】
- Shifrin 的 myTiming 最主要的功能是可以根据被测表达式
x
的完成时间,动态确定一个循环次数,计算多次后计算x
一次运行时间的平均值。
- Timing 和 AbsoluteTiming 的差别:
下例测出的结果比每个循环内用Pause强制停顿的时间还要短,为什么呢: myTiming[(Pause[0.5]; Sin[RandomReal[Pi/2]])]
Out[X]:= 0.284198
如果把 myTiming
中的Timing替换为AbsoluteTiming则能得到约0.5秒的结果。Timing是Mathematica 核用来运算所花费的时间,
而AbsoluteTiming是墙上的钟表走过的时间,所以核空闲着的时间应该也包括了,所以比Timing的结果长。
- 还有一点值得注意的是,
timelim
是允许myTiming
花费的时间有关,但不是允许的最大时限;它应该可以根据被测表达式x
进行手动设置。
下面我们将 myTiming 稍作修改为 ℳTiming[expr, timingFunc_: Timing, timeLimit_: 100, iterationLimit_: 10^5
] (ℳ
在 Mathematica 的 InputForm 形式为 \[ScriptM]
)
∎
4.5.3 用Append构造列表效率低下
我们用 myTiming
来比较一下用Append和Range构造列表的效率差异:
In[X]:= myTiming[For[testlist = {}; i = 1, i < 1000, i++, testlist = Append[testlist, Sin[i]]]]
Out[X]:= 0.0276495
In[X]:= myTiming[Sin[Range[1000]]]
Out[X]:= 0.000335556
构造一个含1000个整数的正弦符号值(比如 Sin[8]
)的列表,用Append比用Range慢约100倍。更重要的是,两者的运算复杂度不同,被运算的表越长,Append的额外开销就越严重。我们再和Table比较一下:
In[X]:= myTiming[Table[Sin[i], {i, 1000}]]
Out[X]:= 0.0010265712
看来Table比Range略慢。
除了效率低下,用循环来构造列表还引入了一个全局的副作用――变量 testlist
。所以,如果要让使不对上下文产生干扰,还得在外面再套上一层模块(比如Module),复添累赘。
所以,结论是,一般不推荐的直接通过循环语句构造列表。一,几乎总是能找到更合理的设计,避免循环带来的诸多问题;二,存在能够获得线性时间复杂度的方法,譬如用链表(后文有讨论),或带指标的变量;三,Mathematica 第5版之后,引入了高效产生和收集运算过程中间结果的专门函数Reap和Sow,这在本书第二部分有详尽讨论。
5 列表的内部形式
需要强调的是列表的内部形式满足所有Mathematica 标准表达式的要求(见第1章)。比如,简单列表和嵌套列表:
In[X]:= Clear[testlist,complextestlist]; testlist = Range[10] complextestlist = Range/@Range[5]
Out[X]:= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Out[X]:= {{1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4, 5}}
以下是它们的完全形式:
In[X]:= FullForm[testlist]
Out[X]:= //FullForm= List[1,2,3,4,5,6,7,8,9,10]
In[X]:= FullForm[complextestlist]
Out[X]:= //FullForm= List[List[1],List[1,2],List[1,2,3],List[1,2,3,4],List[1,2,3,4,5]]
【编译者按】注意这里的 //FullForm
提示你结果以完全形式显示。∎
这说明列表索引也可以用于列表上,就像用在其他更一般的Mathematica 标准表达式上一样,这在第1章中有概述。我们下一节中会用到这个事实。
6 对列表及其部分的操作
6.1 用Part命令进行列表索引和元素提取
6.1.1 简单列表
考虑以下这个简单列表:
In[X]:= Clear[testlist]; testlist=Range[1,20,3]
Out[X]:= {1,4,7,10,13,16,19}
如果我们想提取第一个元素,可以这样操作:
In[X]:= testlist[[3]]
Out[X]:= 7
也可以这样:
In[X]:= Part[testlist,3]
Out[X]:= 7
现在如果我们想提取第二、第四和第五个元素,那么:
In[X]:= testlist[[2,4,5]]
Out[X]:= {4,10,13}
列表元素也可以倒着数。这时,它们的位置约定俗成是负的:
In[X]:= testlist[[-1]]
Out[X]:= 19
6.1.2 嵌套列表
现在考虑一个更复杂的列表:
In[X]:= complextestlist=Range[5*#,5*#+4]&/@Range[5]
Out[X]:= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{26,26,27,28,29}}
它第一层(第几层指的是到茎(stem)的距离,见章节1.1.7)的元素是它的子列表:
In[X]:= complextestlist[[2]]
Out[X]:= {10,11,12,13,14}
In[X]:= complextestlist[[1,4,5]]
Out[X]:= {{5,6,7,8,9},{20,21,22,23,24},{25,26,27,28,29}}
要想提取出单个数字,这里就需要用到两个数字组成的指标(因为所有的子列表的深度为1。如果深度为N
的话,我们就需要N+1
个指标;如果子列表的深度也不一样的话,所需的指标个数也会相应地不同)
In[X]:= complestestlist[[1,1]]
Out[X]:= 5
上面这段代码的意思是取出第一个元素里的第一个元素(我们可以把它看作是一个二维数组)。需要注意的一点是complextestlist[[{1,1}]]
的写法会被解释成提取重复提取原列表的第一个元素,也就是第一个子列表会被取出来两次:
In[X]:= complextestlist[[{1,1}]]
Out[X]:= {{5,6,7,8,9},{5,6,7,8,9}}
对简单列表进行的操作也可以作用在这个复杂列表上:
In[X]:= complextestlist[[-1]]
In[X]:= complextestlist[[-1,-1]]
Out[X]:= {25,26,27,28,29}
Out[X]:= 29
In[X]:= Clear[testlist,complextestlist];
6.2 提取(Extract)
Extract和Part的用法相似,只不过前者相比后者有一些额外的功能,这些功能有时会很有用,但这不是我们现在关注的点。现在我们需要关注的一点是Extract可以同时提取不同深度的元素(Part也可以同时提取多个元素,但这些元素必须在同一层)。此外,Extract的语法也和Part有些不同——如果想要提取深度超过一层的元素(或者每次我们想提取多个元素时),这些元素的地址需要写成指标列表的形式:
In[X]:= testlist=Range[1,20,3]; complextestlist=Range[5*#,5*#+4]/@Range[5]
Out[X]:= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{26,26,27,28,29}}
In[X]:= Extract[testlist,1] Extract[complextestlist,1] Extract[complextestlist,{1,2}]
Out[X]:= 1 {5,6,7,8,9} 6
In[X]:= Extract[complextestlist,{{1,2},{3},{4,5}}]
Out[X]:= {6,{15,16,17,18,19},24}
6.3 取出(Take)和丢弃(Drop)
这两个命令用于取出或丢弃连续的若干元素。比如我们还是用之前的那个list
:
In[X]:= testlist=Range[1,20,3]; complextestlist=Range[5*#,5*#+4]/@Range[5]
Out[X]:= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{26,26,27,28,29}}
然后Take和Drop的作用如下:
In[X]:= Take[testlist,3]
Out[X]:= {1,4,7}
In[X]:= Take[testlist,{2,4}]
Out[X]:= {4,7,10}
In[X]:= Take[testlist,-3]
Out[X]:= {13,16,19}
In[X]:= Take[testlist,{-4,-3}]
Out[X]:= {10,13}
In[X]:= Drop[testlist,3]
Out[X]:= {10,13,16,19}
In[X]:= Drop[testlist,{2,4}]
Out[X]:= {1,13,16,19}
In[X]:= Drop[testlist,-3]
Out[X]:= {1,4,7,10}
In[X]:= Drop[testlist,{-4,-3}]
Out[X]:= {1,4,7,16,19}
Take和Drop的功能并不止于此,它们都能对嵌套列表自动进行结构操作,比如从矩阵里提取出子矩阵。我们这里不会展开,但在Mathematica Help中有详细叙述。
6.4 First,Rest,Last和Most
这些命令从效果上来看是多余的,因为First[list]
等价于list[[1]]nowiki>
,Rest[list]
等价于Drop[list,1]
,Last[list]
等价于list[[-1]]
,Most[list]
等价于Drop[list,-1]
,但它们的代码阅读性更强。
6.5 长度(Length)
这个命令用于返回列表的长度。比如:
In[X]:= testlist=Range[1,20,3]; complextestlist=Range[5*#,5*#+4]/@Range[5]
Out[X]:= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{26,26,27,28,29}}
In[X]:= {Length[testlist],Length[complextestlist]}
Out[X]:= {7,5}
如果我们想计算complextestlist
里子列表的长度,则可以这么写:
In[X]:= Table[Length[complextestlist[[i]]],{i,1,Length[complextestlist]}]
Out[X]:= {5,5,5,5,5}
这里的指标i
很明显是用来索引子列表的,即i
从1开始遍历至主列表的长度,与此同时Part提取对应的子列表。
6.6 通过使用Part直接索引来操作列表元素
6.6.1 Part的简单用法
如果我们想要把列表中某些地址已知的元素替换成新的表达式或值(比如符号a
的话),我们可以直接进行操作。我们的列表如下:
In[X]:= Clear[a]; testlist=Range[1,20,3]; complextestlist=Range[5*#,5*#+4]/@Range[5]
Out[X]:= {1,4,7,10,13,16,19}
Out[X]:= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{26,26,27,28,29}}
假设我们想把地址为{5}
的元素替换成a
的话:
In[X]:= testlist[[5]]=a; testlist
Out[X]:= {1,4,7,10,a,16,19}
现在我们把每个子列表里随机一个元素替换为a
:
In[X]:= For[i=1,i<=Length[complextestlist],i++,complextestlist[[i,Random[Integer,{1,5}]]]=a]; complextestlist
Out[X]:= {{5,6,7,8,a},{10,11,a,13,14},{15,16,17,18,a},{20,21,a,23,24},{26,26,27,a,29}}
要实现这种操作的必要条件是列表存储在某些变量中(比如在C语言中它是一个L值(L-value)),而下面这种写法则是错误的:
In[X]:= Range[10][[3]]=a
Set::setps: Range[10] in the part assignment is not a symbol.>>
a
在上面所有的例子中,Part命令([[]])都用来对表达式进行修改。
要注意的一点是使用Part命令会引入副作用,因为其实是存储列表的原始变量被修改,而非列表的副本被修改。
6.6.2 使用Part高效地修改大型结构
这里我想提一点,那就是Part有一个很强大的功能,它可以同时修改多个元素。比如我想把complextest
每个子列表里的第二个元素依次替换成从b
到f
的序列,那么我可以这么写:
In[X]:= Part[complextestlist,All,2]={b,c,d,e,f}; complextestlist
Out[X]:= {{5,b,7,8,a},{10,c,a,13,14},{15,d,17,18,a},{20,e,a,23,24},{26,f,27,a,29}}
这在需要一次性修改多个元素时十分便捷,不过它也有局限之处,那就是需要喜欢的部分要能组成像子矩阵这样的规则的结构。如果想了解更多,可以参考Mathematica Help和Mathematica Book,也可以看看Ted Ersek网站上的描述(链接请见附录)。
6.7 ReplacePart
Mathematica 中还有另一个内置的命令用于修改列表元素——ReplacePart,但它与Part通过指标直接作修改不同。注意到使用了Part之后,原始列表已经被修改,而在Mathematica 中,更常见的是修改列表的副本,这样原始列表就能保持不变。这种编程方式显然更加好用一些,但也因为复制原始对象而消耗了更多的内存。绝大多数内置函数的作用方式都是如此,ReplacePart就是其中一个例子:
In[X]:= Clear[a]; testlist=Range[1,20,3]
Out[X]:= {1,4,7,10,13,16,19}
In[X]:= ReplacePart[testlist,5->a]
Out[X]:= {1,4,7,10,a,16,19}
但原始列表仍保持不变:
In[X]:= testlist
Out[X]:= {1,4,7,10,13,16,19}
这就意味着ReplacePart操作一个表达式时并不需要L值:
In[X]:= ReplacePart[Range[10],5->a]
Out[X]:= {1,2,3,4,a,6,7,8,9,10}
这个命令没有任何错误——因为它操作的是列表的副本而非原始列表本身。
ReplacePart也可以用来一次性修改多个元素,也可以修改处于不同层上的元素。比如:
In[X]:= ReplacePart[Range[10],{{2},{5},{8}}->a]
Out[X]:= {1,a,3,4,a,6,a,9,10}
这里用到的表示位置的列表的语法和Extract命令相同。在Mathematica Help中有对ReplacePart的详细介绍。
不过这里要提一点,如果想对一个大型表达式的多个部分同时进行修改操作,使用ReplacePart则会显得相当慢。关于这个话题的具体讨论请见附录C。
同时我也不推荐使用ReplacePart一个一个地修改元素而不是一次性全部改完。原因在于每次操作都会先复制整个列表形成副本,然后在这个副本上进行操作,这样每进行一次修改就会复制一次列表。它和Append和Prepend一样是极其低效的。在某些情形下,我们可以一次性地用Part来修改元素——我们会在第六章(章节6.5.5.1)中考虑这样的一个例子。
6.8 位置(Position)
Position命令用于确定一个列表(或更一般的Mathematica 表达式)中匹配给定表达式或模式的元素的位置。
6.8.1 Position的基本用法
Position的最简单用法的语法是:Position[list,element]
。让我们来看几个例子:
首先我们先新建一个列表:
In[X]:= testlist=Range[1,20,3]; complextestlist=Range[5*#,5*#+4]/@Range[5]
Out[X]:= {{5,6,7,8,9},{10,11,12,13,14},{15,16,17,18,19},{20,21,22,23,24},{26,26,27,28,29}}
现在我们要用Position最简单的用法(不用模式)来找到列表中所有的数字4
的位置:
In[X]:= Position[testlist,4]
Out[X]:= {{2}}
这说明数字4
在列表testlist
的第二个元素里。
In[X]:= Position[complextestlist,12]
Out[X]:= {{2,3}}
这说明12
是complextestlist
列表的第二个元素的第三项。
Position命令还可以和Extract命令一起使用,因为它们使用的是相同的位置指定方式:
In[X]:= Extract[complextestlist,Position[complextestlist,10]]
Out[X]:= {10}
6.8.2 Position的不常见用法
如果我们想提取所有含有数字10
的整个子列表,则可以构造一个新的位置列表,然后把最后一个元素(指标)去掉:
In[X]:= Map[Most,Position[complextestlist,10]]
Out[X]:= {{2}}
Map的用法会在后面的章节中提到,这里它的作用是确保当位置列表含有多个位置时,每一个位置的末尾的指标会被去掉。比如,我们现在构造一个嵌套列表,其中的一些元素重复出现:
In[X]:= complextestlist1=Range/@Range[6]
Out[X]:= {{1},{1,2},{1,2,3},{1,2,3,4},{1,2,3,4,5},{1,2,3,4,5,6}}
数字4
出现的所有位置为:
In[X]:= plist=Position[complestestlist1,4]
Out[X]:= {{4,4},{5,4},{6,4}}
如果我们把这些位置放到Extract中,则会把数字4
取出来3次:
In[X]:= Extract[complextestlist1,plist]
Out[X]:= {4,4,4}
但如果我们想提取所有含有数字4
的子列表,我们还需更进一步。要想得到子列表的位置,我们需要把plist
中所有子列表中的最后一项删去:
In[X]:= Map[Most,plist]
Out[X]:= {{4},{5},{6}}
现在我们就可以提取这些子列表了:
In[X]:= Extract[complextestlist1,Map[Most,plist]]
Out[X]:= {{1,2,3,4},{1,2,3,4,5},{1,2,3,4,5,6}}
6.8.3 提取含有给定元素的子列表的例子
现在我们可以写出第一个“正儿八经”的函数来了:这个函数会从一个列表中提取出所有含有某个给定元素的子列表。
In[X]:= Clear[sublistWithElement]; sublistWithElement[main_List,elem_]:=Extract[main,Map[Most,Position[main,elem]]];
比如,complextestlist1
中所有含有数字5
的子列表为:
In[X]:= sublistWithElement[complextestlist11,5]
Out[X]:= {{1,2,3,4,5},{1,2,3,4,5,6}}
这里我想讲一点Mathematica 中用户自定义函数的一些常见问题。首先,函数的构造方式:通常来说应该先用几个简单的例子尝试一下,像上面一样一步一步地写出代码,然后再把所有代码打包到一个函数中去。其次,我们看到在函数定义的左边参数之后跟着一个下划线,这个符号意味着我们在这里用到了模式。这里我只想简单地提一下它的含义:如果用到了延迟赋值(:=)的话(函数一般都是用延迟赋值定义的),那么x_
对于函数定义式右边来说意味着名字为x
的任何(局部)表达式。而模式x_h
则表示任何具有头部h
的表达式。因此,main_List
只会匹配列表,而不会匹配其他头部不是List
的更一般的表达式,它在这里起到了一个类型检查的作用。
对于Position另一个要提到的一点是,虽然它是内置函数,经过了优化速度也很快,但它的作用还是很一般化的。尤其是如果有一个根据某些规则排序过的列表,用某种形式的二分法去搜索某个元素通常来说都会更快一些,二分法可以在Mathematica 中做到(并且复杂度是对数级别,而Position函数的复杂度则是线性的)。
6.8.4 更复杂的例子:含有奇数个奇数元素的子列表
需要解决的问题
现在要向你展示Position不那么常见的用法。请先不要理会那些你不怎么理解的语法格式,你只需要理解其中的思路。我们现在要从complextestlist1
中提取所有含有奇数个奇数元素的子列表,现在我们来一步一步实现这个目的:
In[X]:= complextestlist1=Range/@Range[6]
Out[X]:= {{1},{1,2},{1,2,3},{1,2,3,4},{1,2,3,4,5},{1,2,3,4,5,6}}
解决问题
第一步:找出所有奇数的位置:
In[X]:= step1list=Position[complextestlist1,_?OddQ]
Out[X]:= {{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[X]:= step2list=Split[step1list,First[#1]==First[#2]&]
Out[X]:= {{{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具有相同的第一个指标的子列表是“相同”的。注意到step2list
比step1list
多了一层括号。
第三步:只保留每个子列表的第一个元素:
In[X]:= step3list=Map[First,step2list,{2}]
Out[X]:= {{1},{2},{3,3},{4,4},{5,5,5},{6,6,6}}
第四步:在上面的这个列表中,只留下奇数长度的子列表(这些子列表的长度等于原始列表的子列表中奇数元素的个数,这些子列表的位置则是上面每个子列表中重复的那个数字)
In[X]:= step4list=Cases[step3list,x_List/;OddQ[Length[x]]]
Out[X]:= {{1},{2},{5,5,5},{6,6,6}}
Cases命令用于找出某个更大的表达式中符合某些模式或表达式的所有元素。我们会在之后的章节中提到它。
第五步:把所有的子列表替换为它们各自的第一个元素:
In[X]:= step5list=Union[Flatten[step4list]]
Out[X]:= {1,2,5,6}
Flatten命令会把任何列表压平,Union命令则会删去重复的元素,然后把得到的结果按照顺序排列。
第六步:提取子列表:
In[X]:= complextestlist1[[step5list]]
Out[X]:= {{1},{1,2},{1,2,3,4,5},{1,2,3,4,5,6}}
把所有的代码打包成一个函数
我们现在就可以把所有的步骤都放到一个函数里去:
In[X]:= Clear[oddSubists]; 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[X]:= oddSublists[complextestlist1]
Out[X]:= {{1},{1,2},{1,2,3,4,5},{1,2,3,4,5,6}}
函数式解决方法
如果能混合规则替换和函数式编程的话,整个函数会简洁许多,但易读性会有所下降:
In[X]:= Clear[oddSublistsNew]; oddSublistsNew[x_List]:=Map[If[EvenQ[Count[#,_?OddQ]],#/.#->Sequence[],#]&,x];
检查一下:
In[X]:= oddSublistsNew[complextestlist1]
Out[X]:= {{1},{1,2},{1,2,3,4,5},{1,2,3,4,5,6}}
虽然第一种实现方式的编程方式的复杂程度与传统的基于嵌套循环的过程式编程相比不见得有什么优势,但我这里这么写的主要目的是展示Position命令的使用方法,顺便让你感受一下其他命令的魅力。
不过,第二种实现方式明显要短许多。这种编程方式可以很快地写出来,通常来说长度也很短。
过程式编程实现方式
如果用两个嵌套循环用过程式编程来实现的话,出错的几率会小很多:
In[X]:= 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[X]:= oddSublistsProc[complextestlist1]
Out[X]:= {{1},{1,2},{1,2,3,4,5},{1,2,3,4,5,6}}
除了变得更加繁琐之外,这段代码还用到了AppendTo命令来把元素添加到一个列表中去,对于大型列表来说这种操作效率很低,正如我们在之前的一些例子中看到的那样。
In[X]:= Clear[complextestlist1,complextestlist,step1list,step2list,step3list,step4list,step5list,oddSublists,oddSublistsNew,oddSublistsProc];
7 列表元素的添加和删除
7.1 Append, Prepend, AppendTo和PrependTo
其中的一些命令我们在之前的章节中已经碰到过,它们可以向一个列表的头部或尾部添加一个元素,比如:
In[X]:= Clear[a]; testlist=Range[5]
Out[X]:= {1,2,3,4,5}
In[X]:= Append[testlist,a]
Out[X]:= {1,2,3,4,5,a}
In[X]:= Prepend[testlist,a]
Out[X]:= {a,1,2,3,4,5}
In[X]:= testlist
Out[X]:= {1,2,3,4,5}
从最后一个输出中我们可以看出testlist
本身并没有发生变化,这种不直接修改原始对象的特性是大多数Mathematica 内置函数所共有的。在上面的例子中,Append和Prepend创建了testlist
的一个副本,并在这个副本上做修改。如果我们一定要修改原始列表,那么我们要么写成:
In[X]:= testlist=Append[testlist,a]; testlist
Out[X]:= {1,2,3,4,5,a}
或者使用专门用来实现这个目的的AppendTo:
In[X]:= testlist=Range[5]
Out[X]:= {1,2,3,4,5}
In[X]:= AppendTo[testlist,a]; testlist
Out[X]:= {1,2,3,4,5,a}
Prepend和PrependTo的用法则与之完全类似。如果你还记得之前的内容的话,你可能会觉得把AppendTo和PrependTo用到没有赋给任何一个变量上的列表可能会出错。你的这个想法是正确的:
In[X]:= Append[Range[5],a]
Out[X]:= {1,2,3,4,5,a}
In[X]:= AppendTo[Range[5],a]
Set::write: Tag Range in Range[5] is Protected. More...
{1,2,3,4,5,a}
正如我们之前提到的那样,最好避免用这些函数修改大型列表。之后我们会看到几个更为有效的方法。
In[X]:= Clear[testlist];
7.2 插入(Insert)和删除(Delete)
从这两个函数的名字就可以看出来,它们的作用是在列表(或其他更一般的Mathematica 表达式)中插入或删除一个元素,具体的用法在Mathematica Help中有详细介绍。我们这里举一些例子。Insert的语法是Insert[list,new,pos]
,它会在list
中pos
指定的位置插入元素new
。Delete的语法与之相似——Delete[list,pos]
,它会把list
中位置为pos
的元素删去。比如:
In[X]:= Clear[a]; testlist=Range[3,15,2]
Out[X]:= {3,5,7,9,11,13,15}
In[X]:= Delete[testlist,4]
Out[X]:= {3,5,7,11,13,15}
In[X]:= Insert[testlist,a,5]
Out[X]:= {3,5,7,9,a,11,13,15}
这里需要再次注意这两个命令是作用在原始列表的副本上的,所以原始列表并没有被修改:
In[X]:= testlist
Out[X]:= {3,5,7,9,11,13,15}
这两个命令都可以用在嵌套列表(或其他更一般的表达式)上,这时某个元素的地址就是若干指标组成的列表。同时这两个命令都可以接受多个位置,这样一个元素可以同时在多个地方被添加或删除。
不过对于Insert来说,同时在许多地方插入元素速度会很慢。进一步的讨论在附录C中可以看到。
8 嵌套列表
我们经常要用到嵌套列表,即元素也是列表的列表。我们之前也看到过简单的这些列表的例子。这里我想强调的一点是广义上来说这种列表和多维数组并不一样,事实上这种列表更加一般化,因为每一层的子列表的长度是可以不同的。对于广义的嵌套列表我只想说它代表了某种意义上的树。
这里我们将了解几个为高效处理一些特殊种类的这种列表而设计的命令。
8.1 Partition
这个命令用于将列表“切”成多个(相互重叠的)部分。最简单的用法是Partition[list,size,shift]
。它会把list
切割成长度为size
的几个部分,并根据shift
来位移切割后的片段。如果shift
参数没有指定的话,列表就不会被切割成重叠的片段。比如:
8.1.1 简单的例子
In[X]:= testlist=Table[Sqrt[i],{i,1,10}]
Out[X]:= {1,Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2Sqrt[2],3,Sqrt[10]}
In[X]:= Partition[testlist,3]
Out[X]:= {{1,Sqrt[2],Sqrt[3]},{2,Sqrt[5],Sqrt[6]},{Sqrt[7],2Sqrt[2],3}}
In[X]:= Partition[testlist,7]
Out[X]:= {{1,Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7]}}
在最后一个例子中,由于剩余的第二部分的长度小于7
,所以它就被“吞掉”了。如果我们允许重叠的话:
In[X]:= Partition[testlist,7,1]
Out[X]:= {{1,Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7]},{Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2Sqrt[2]},{Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2Sqrt[2],3}, {2,Sqrt[5],Sqrt[6],Sqrt[7],2Sqrt[2],3,Sqrt[10]}}
8.1.2 实际应用的一个例子:计算列表的移动平均值
这个例子是基于Wagner' 96一个相似的讨论之上的。
问题
一个列表的 m-移动平均值是对列表中每一个左右都有m
个邻居的列表中的所有元素求平均得到的值,这意味着移动平均值只能用于左右至少有m
个邻居的元素。因而移动平均值实际上是一系列这种平均值组成的列表,长度为len-2m
,其中len
是原始列表的长度。
一步步得出解决方法
要解决这个问题,我们首先要定义一个辅助函数用来计算一个列表的平均值。之后我们会发现这个函数甚至可以用在列表的列表上,它可以计算一个大列表中每个小列表中相同位置的元素的平均值。因而:
In[X]:= Clear[listAverage]; listAverage[x_List]:=Apply[Plus,x]/Length[x];
Apply[Plus,x]
这个表达式会计算列表中所有元素的和,它的用法会在第五章中讲到。
现在我们要定义另一个辅助函数:
In[X]:= Clear[neighborLists]; neighborLists[x_List,m_Integer]:=Partition[x,Length[x]-2*m,1];
比如:
In[X]:= neighborLists[testlist,1]
Out[X]:= {{1,Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2Sqrt[2]},{Sqrt[2],Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2Sqrt[2],3},{Sqrt[3],2,Sqrt[5],Sqrt[6],Sqrt[7],2Sqrt[2],3,Sqrt[10]}}
现在我们注意到中间的列表其实是一系列“中点”组成的列表,而第一个和最后一个列表则是这些中点离得最近的“邻居”。因此,剩下的部分只要交给listAverage
就好了:
In[X]:= listAverage[neighborLists[testlist,1]]
Out[X]:= {(1+Sqrt[2]+Sqrt[3])/3,(2+Sqrt[2]+Sqrt[3])/3,(2+Sqrt[3]+Sqrt[5])/3,(2+Sqrt[5]+Sqrt[6])/3,(Sqrt[5]+Sqrt[6]+Sqrt[7])/3,(2Sqrt[2]+Sqrt[6]+Sqrt[7])/3, (3+2Sqrt[2]+Sqrt[7])/3,(3+2Sqrt[2]+Sqrt[10])/3}
打包成一个函数
因而movingAverage
函数最后看起来是这样的:
In[X]:= 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]]
比如说,下面是两边各两个邻居的移动平均值:
In[X]:= movingAverage[testlist,2]
Out[X]:= {(3+Sqrt[2]+Sqrt[3]+Sqrt[5])/5,(2+Sqrt[2]+Sqrt[3]+Sqrt[5]+Sqrt[6])/5,(2+Sqrt[3]+Sqrt[5]+Sqrt[6]+Sqrt[7])/5,(2+2Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7])/5, (3+2Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7])/5,(3+2Sqrt[2]+Sqrt[6]+Sqrt[7]+Sqrt[10])/5}
用函数式编程从而避免使用辅助函数
如果我们能使用函数式编程的语法,那么只需一个函数就可以实现,完全用不着辅助函数:
In[X]:= Clear[movingAverage]; movingAverage[x_List,m_Integer]:=(Plus@@#)/Length[#]&@Partition[x,Length[x]-2*m,1];
检查一下:
In[X]:= movingAverage[testlist,2]
Out[X]:= {(3+Sqrt[2]+Sqrt[3]+Sqrt[5])/5,(2+Sqrt[2]+Sqrt[3]+Sqrt[5]+Sqrt[6])/5,(2+Sqrt[3]+Sqrt[5]+Sqrt[6]+Sqrt[7])/5,(2+2Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7])/5, (3+2Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7])/5,(3+2Sqrt[2]+Sqrt[6]+Sqrt[7]+Sqrt[10])/5}
过程式编程版本
用过程式编程也能达到相同的效果:
In[X]:= 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[X]:= movingAverageProc[testlist,2]
Out[X]:= {(3+Sqrt[2]+Sqrt[3]+Sqrt[5])/5,(2+Sqrt[2]+Sqrt[3]+Sqrt[5]+Sqrt[6])/5,(2+Sqrt[3]+Sqrt[5]+Sqrt[6]+Sqrt[7])/5,(2+2Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7])/5, (3+2Sqrt[2]+Sqrt[5]+Sqrt[6]+Sqrt[7])/5,(3+2Sqrt[2]+Sqrt[6]+Sqrt[7]+Sqrt[10])/5}
速度比较
过程式编程的弊病不仅在于代码更长,而且更容易出错(数组的上下界,变量的初始化等等)。即使不算这些,它的速度也远远慢于函数式编程。我们不妨比较一下大列表下的速度:
In[X]:= Timing[movingAverage[Range[10000],10];]
Out[X]:= {0.016 Second, Null}
In[X]:= Timing[movingAverageProc[Range[10000],10];]
Out[X]:= {1.172 Second, Null}
这里我们可以看到两者的速度相差100倍(即使在这个列表长度下)!除此而外,两者的速度差并非一个定值,而是会随着列表的增大而增大。诚然,像C语言这样的过程式语言写起来很自然也很快,但在Mathematica 中事情并非如此,使用函数式编程我们可以既快速又简介地写出优雅的代码。
In[X]:= Clear[testlist];
8.2 转置(Transpose)
这是最有用的命令之一。它会把矩阵(通常表示称二维的列表的列表)的行和列互换,它的名字也因此而来。不过我们并不经常把二维数组称作矩阵,因为其中的元素的种类并不一定要一样。这么说来用Transpose可以做的事就更多了。不过我们先从简单的数值列表入手:比如我们现在有一个元素的列表的列表(这个元素本身也可以是列表,不过对我们没什么影响):
8.2.1 简单的例子:转置一个简单的矩阵
In[X]:= testlist=Table[i+j,{i,1,2},{j,1,3}]
Out[X]:= {{2,3,4},{3,4,5}}
然后,
In[X]:= Transpose[testlist]
Out[X]:= {{2,3},{3,4},{4,5}}
8.2.2 转置一个列表矩阵
另一个例子:
In[X]:= testlist=Table[{i,j},{i,1,2},{j,1,3}]
Out[X]:= {{{1,1},{1,2},{1,3}},{{2,1},{2,2},{2,3}}}
这是一个二维的列表数组。
In[X]:= Transpose[testlist]
Out[X]:= {{{1,1},{2,1}},{{1,2},{2,2}},{{1,3},{2,3}}}
8.2.3 把名字和成绩配对起来
再来一个例子:我们的一个列表是某次考试的成绩,另一个列表是学生的姓。我们想把它们弄成{{student1,score1},...}
的样子。
In[X]:= Clear[names,scores]; names={"Smith","Johnson","Peterson"}; scores={70,90,50};
于是,
In[X]:= Transpose[{names,scores}]
Out[X]:= {{Smith,70},{Johnson,90},{Peterson,50}}
由于Transpose经常用于结构的重新调整,而且效率很高,因而当我们在用函数式编程时才能最大限度地体验到Transpose给我们带来的好处。在接下去的章节中我们会引入很多相关的例子。
8.3 压平(Flatten)
这个命令可以把嵌套列表的嵌套结构去除,它会删除所有内部的尖括号,把任何复杂的嵌套列表压平成一层。比如:
In[X]:= testlist=Table[{i,j},{i,1,2},{j,1,3}]
Out[X]:= {{{1,1},{1,2},{1,3}},{{2,1},{2,2},{2,3}}}
In[X]:= Flatten[testlist]
Out[X]:= {1,1,1,2,1,3,2,1,2,2,2,3}
8.3.1 压平指定层
从上面的例子我们可以看到Flatten命令十分凶残,但其实我们可以告诉它只压平表达式中某一层以下的所有结构,而指定这个“某一层”的则是Flatten函数的第二个参数。比如:
In[X]:= Flatten[testlist,1]
Out[X]:= {{1,1},{1,2},{1,3},{2,1},{2,2},{2,3}}
一层一层压平嵌套列表
另一个例子:
In[X]:= testlist=Table[{i,j,k},{i,1,2},{j,1,2},{k,1,3}]
Out[X]:= {{{{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[X]:= Flatten[testlist,1]
Out[X]:= {{{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[X]:= Flatten[testlist,2]
Out[X]:= {{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[X]:= Flatten[testlist,3]
Out[X]:= {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]
去掉一层内部的尖括号,一般来说不会再压平更多层。
8.3.2 应用:计算任意秩的张量(向量,矩阵等)的二次范数
问题和解决方法
下面我们会看到Flatten的使用是如何大幅减少任意秩的张量的范数计算的。令人惊奇的是,甚至都不用把张量的秩数作为单独的变量,代码如下:
In[X]:= Clear[tensorNorm]; tensorNorm[x_List]:=Sqrt[Plus@@Flatten[x^2]];
之后我们就将发现这段短短的代码可以计算任意秩数的张量的范数。
代码解析
让我们用一个例子来了解代码的运作方式。我们的test
矩阵是:
In[X]:= testmatr=Table[i+j,{i,1,3},{j,1,3}]
Out[X]:= {{2,3,4},{3,4,5},{4,5,6}}
范数是所有矩阵元素的平方和开根号得到的值。首先我们这里用到一个性质,那就是像乘方这样的代数运算能够作用于整个列表上,因为它会自动遍历列表中的所有元素(函数的这种性质叫做Listable
)。因而我们先计算所有元素的平方和:
In[X]:= testmatr^2
Out[X]:= {{4,9,16},{9,16,25},{16,25,36}}
由于我们并不关心各个元素的位置,只需要把它们都加起来,所以这里我们用Flatten把内部所有的尖括号都去除:
In[X]:= Plus@@Flatten[testmatr^2]
Out[X]:= 156
最后我们进行开方运算:
In[X]:= Sqrt[Plus@@Flatten[testmatr^2]]
Out[X]:= 2Sqrt[39]
这就是这个函数的所有代码。我们发现不用作任何修改,任何秩数的张量都能用这个函数计算范数。如果没有Flatten的话就很难做到,特别是在像C语言这样的编程语言中,我们要用嵌套列表才能达到这个目标(在C语言中也有一种技巧叫数组压平,由于在C语言中数组在内存中的存储是按行来的,利用这个特性我们可以只用一个指向一个整数(或数组的最小元素的种类)的指针来遍历多维数组中的每一个元素)。虽然这种方法确实可行,但严格来说它并没有遵循C语言的标准。
In[X]:= Clear[tensorNorm,testmatr];
8.3.3 应用:用Flatten较快地生成列表
之前我们也提到了,按效率来说用循环来生成列表恐怕是最差的方法,其实我们可以用Flatten来大幅加速这一过程。比如我们要生成一个从1到10的列表(用Range[10]
当然是最简单的):
第一步 我们生成一个嵌套列表(这种列表在Mathematica 中又被称为链表):
In[X]:= For[testlist={};i=1,i<=10,i++,testlist={testlist,i}];testlist
Out[X]:= {{{{{{{{{{{},1},2},3},4},5},6},7},8},9},10}
第二步 用Flatten:
In[X]:= Flatten[testlist]
Out[X]:= {1,2,3,4,5,6,7,8,9,10}
让我们比较一下这种方式和之前提到过的用AppendTo的方法的执行速度:
In[X]:= For[testlist={};i=1,i<=5000,i++,AppendTo[testlist,i]];//Timing
Out[X]:= {0.25 Second, Null}
In[X]:= (For[testlist={};i=1,i<=5000,i++,testlist={testlist,i}];Flatten[testlist];)//Timing
Out[X]:= {0.016 Second, Null}
可以看出速度的差距至少为一个数量级,而且这种方法本身也不是最高效的。我们之后会看到链表在某些问题中是如何大幅提高执行效率的。
In[X]:= Clear[testlist];
9 多个列表
在遇到两个或多个列表时,求交集、并集、补集,或者删除重复的元素是很常见的情况。这些操作都可以由Join
、Intersection
、Complement
和Union
这些内置函数完成。
9.1 Join
Join命令会合并两个或多个列表。语法是Join[list1,...,listn]
,其中list1,...,listn
是不同的列表,深度或结构并不一定要一致。如果这些列表含有重复的元素,这些元素不会被删去,也就是说求的是并集,不会做进一步的操作改变内部结构。比如:
In[X]:= Clear[a,b,c,d,e,f]; Join[{a,b,c},{d,e,f}]
Out[X]:= {a,b,c,d,e,f}
In[X]:= Join[{{a,b},{c,d}},{e,f}]
Out[X]:= {{a,b},{c,d},e,f}
Join只会把多个列表从左至右依次连到一起,不过对元素进行排序或交换操作。
9.2 Intersection
Intersection命令会求两个或多个列表的交集,也就是在所有列表里都出现的元素。语法为Intersection[list1,...,listn]
,比如:
In[X]:= Clear[a,b,c,d,e,f]; Intersection[{a,b,c},{b,c,d,e}]
Out[X]:= {b,c}
In[X]:= Intersection[{a,b,c,d,e,f},{a,b,c},{c,d,e}]
Out[X]:= {c}
In[X]:= Intersection[{a,b,c},{d,e,f}]
Out[X]:= {}
最后一个例子中我们得到的结果是空集,因为两个列表中的元素互不相同。
Intersection命令有一个SameTest
选项,可以用来自定义“元素相同”的定义。关于这个选项的用法请见Union命令。此外,如果应用了这个选项,Intersection的运行效率会比不使用要慢上许多,有关于此的讨论请见附录C。
9.3 Complement
Complement命令Complement[listAll,list1,...,listn]
会求listAll
相对于其他所有列表listk
的补集。换言之,它会返回所有在listAll
中但不在任何listk
中的元素,而且Complement会给结果排序。比如:
In[X]:= Complement[{a,b,c,d,e,f},{b,c,e}]
Out[X]:= {a,d,f}
In[X]:= Complement[{a,b,c,d,e,f},{b,c,e},{d,e,f}]
Out[X]:= {a}
In[X]:= Complement[{a,b,c,d,e,f},{b,c,e},{d,e,f},{a,b,c}]
Out[X]:= {}
和Intersection一样,Complement也有SameTest
选项,可以自定义“元素相同”的定义。上面关于Intersection中这个选项的讨论也适用于Complement。
10 排序
我们现在讨论一些对元素列表进行排序的很有用的 Mathematica 内置函数。Sort
函数对列表进行排序。Union
函数对一个列表进行排序并剔除重复元素。Split
函数将一个列表分成若干由连续出现的相同元素组成的子列表。这三个列表操作函数都可以使用自定义的“元素相同”判断条件。以下我们详细解释。
10.1 Sort命令
10.1.1 简单排序
这个函数是用来对列表进行排序,例如:
In[X]:= Clear[{a,b,c,d,e,f,g,t}];
In[X]:= Sort[{a,d,e,b,g,t,f,d,a,b,f,c}]
Out[X]:= {a,a,b,b,c,d,d,e,f,f,g,t}
In[X]:= Sort[{5,7,2,4,3,1}]
Out[X]:= {1,2,3,4,5,6,7}
Sort可以对元素为任意Mathematica 表达式的列表进行排序。默认的排序法则是对符号使用字典序、对数字使用升序、对列表的相同位置的元素进行顺次排序。这样的排序法则称为Mathematica 正则排序——请参考 Mathematica 文档。
我们举一个对只含有整数元素的复合列表进行排序的例子:
In[X]:= nested=Table[Random[Integer,{1,15}],{5},{Random[Integer,{3,10}]}]
Out[X]:= {{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[X]:= Sort[nested]
Out[X]:= {{11,10,2},{13,3,11,7},{7,4,15,11,9},{11,12,9,11,1,4},{15,15,14,11,15,14}}
可以看到首先是按照子列表的长度排序,再按照子列表的第一个元素进行排序。
10.1.2 用户自定义排序
Sort有一个可选的参数,可以根据用户自定义的规则来排序。比如:
In[X]:= Sort[{5,7,2,4,3,1},Greater]
Out[X]:= {7,5,4,3,2,1}
我们也可以按照子列表的长度进行排序。我们先定义一个排序函数:
In[X]:= Clear[sortFunction]; sortFunction[x_List,y_List]:=Length[x]<Length[y];
然后我们进行排序:
In[X]:= Sort[nested,sortFunction]
Out[X]:= {{11,10,2},{13,3,11,7},{7,4,15,11,9},{11,12,9,11,1,4},{15,15,14,11,15,14}}
10.1.3 初遇纯函数
Mathematica 内部的一个机制允许用户构造或使用一个函数而无需给出它的名字或单独的定义,这种函数叫做“纯函数(pure function)”(在其他语言中称作λ函数)。在之后的章节我们会系统地介绍这种函数,不过我们在这里可以先看一看在排序中如何使用纯函数:
In[X]:= Sort[nested,Length[#1]<Length[#2]&]
Out[X]:= {{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。
10.1.4 Ordering命令
这个命令会返回排序一个列表所需要的指标的的组合。和Sort一样,它也有“纯形式”和用户自定义两种模式,但它给出的信息比Sort更多,例如我们可以用Ordering和Part来实现给一个列表排序。
比如,考虑这个之前出现过的列表:
In[X]:= listtosort={a,d,e,b,g,t,f,d,a,b,f,c}
Out[X]:= {a,d,e,b,g,t,f,d,a,b,f,c}
In[X]:= Ordering[listtosort]
Out[X]:= {1,9,4,10,12,2,8,3,7,11,5,6}
In[X]:= listtosort[[Ordering[listtosort]]]
Out[X]:= {a,a,b,b,c,d,d,e,f,f,g,t}
Ordering是一个很有用的函数,不仅因为它能比Sort提供更多的信息,而且还能跟Sort一样快。在第六章中我们会看到它的一个应用。
10.2 Union命令
Union[list]
会返回list
中所有不重复元素的正则排序。
10.2.1 基本的Union用法
在最基本的用法中,Union接受一个列表作为参数,返回所有不重复元素经过排序后的结果。排序是由Mathematica 内置的默认排序函数(对符号使用字典序、对数字使用升序、对列表的相同位置的元素进行顺次排序)完成。比如:
In[X]:= Union[{a,d,e,b,g,t,f,d,a,b,f,c}]
Out[X]:= {a,b,c,d,e,f,g,t}
In[X]:= testlist=Table[Random[Integer,{1,10}],{15}]
Out[X]:= {9,7,4,3,1,1,8,2,2,10,7,4,9,1,4}
In[X]:= Union[testlist]
Out[X]:= {1,2,3,4,7,8,9,10}
Union命令会给返回列表排序的特性和Union内置的算法有关。如果不希望返回的结果排序,我们可以编写自定义的Union函数(我们会在之后的章节5.2.6.2.5里讲到有关于此的应用),当然它的速度也要比内置的Union慢一些。
10.2.2 带SameTest
选项的Union
Union命令也有一个SameTest
选项,能够让我们自定义“元素相同”的定义。比如,我们可以认为能被3整除的元素是相同的:
In[X]:= Union[testlist,SameTest->(Mod[#1-#2,3]==0&)]
Out[X]:= {1,2,3}
需要注意的一点是带有SameTest
函数的Union运行起来可能会比不用稍慢一些,甚至慢上许多。有关于此的具体讨论请参考附录C。
10.3 Split命令
这个命令用于把列表拆分成多个列表,使得每个子列表中的所有元素都是一样的。这个函数能够接受“相同性”函数作为可选的参数。它会遍历整个列表,用默认的相同性函数(SameQ)或自定义的相同性函数比较相邻的两个元素。如果相邻的两个元素不相同的话,它要么把这个元素扔到之前已经创建的含有相同元素的子列表里,要么就新建一个子列表把这个元素放进去。
10.3.1 基本的Split用法
在最基本的用法中,Split接受一个列表作为唯一的参数,然后用SameQ来进行比较。比如,我们这里有一个排序之后的列表:
In[X]:= testlist=Table[Random[Integer,{1,15}],{20}]
In[X]:= sorted=Sort[testlist]
Out[X]:= {8,12,10,3,13,15,13,6,6,2,4,9,5,11,6,10,7,4,15,5}
Out[X]:= {2,3,4,4,5,5,6,6,6,7,8,9,10,10,11,12,13,13,15,15}
因为一般来说在未经排序的列表里相邻两个元素是不相同的,因而我们可以看到绝大多数子列表都只含有一个元素:
In[X]:= Split[testlist]
Out[X]:= {{8},{12},{10},{3},{13},{15},{13},{6,6},{2},{4},{9},{5},{11},{6},{10},{7},{4},{15},{5}}
但对于一个经过排序的列表来说:
In[X]:= Split[sorted]
Out[X]:= {{2},{3},{4,4},{5,5},{6,6,6},{7},{8},{9},{10,10},{11},{12},{13,13},{15,15}}
10.3.2 带自定义相同性函数的Split
现在我们定义如果两个元素除以3之后的余数相同的话,这两个元素就是相同的。不过,在使用Split把这些元素放在一起之前,我们要先用排序函数给列表排个序,这样除以3后余数相同的元素就会被排在一起:
In[X]:= mod3sorted=Sort[testlist,Mod[#1,3]<Mod[#2,3]&]
Out[X]:= {15,6,9,6,6,15,3,12,4,7,10,4,13,13,10,5,11,5,2,8}
然后我们对列表进行拆分:
In[X]:= Split[mod3sorted,Mod[#1,3]==Mod[#2,3]&]
Split是一个很有用的函数,因为它只会遍历一次整个列表,只比较相邻的两个元素,因而它的复杂度是线性的。此外,由于它进行比较的次数等于列表长度减一,因而在使用用户自定义的相同性函数的时候性能损失不如Sort和Union函数那么厉害。
10.3.3 游程长度编码(run-length encoding)
Split的一个标准应用是游程长度编码。给定由许多重复数字构成的列表,这种编码会把这个列表替换成{{num1,freq1},...,}
的形式,其中freqk
是numk
出现的次数。就拿第一个例子来说,我们只需把各个子列表做一些修改:
In[X]:= Clear[runEncodeSplit]; runEncodeSplit[sp1_List]:=Table[{sp1[[i,1]],Length[sp1[[i]]]},{i,Length[sp1]}]; Clear[runEncode]; runEncode[x_List]:=runEncodeSplit[Split[x]];
检查一下:
In[X]:= runEncode[sorted]
Out[X]:= {{2,1},{3,2},{4,3},{5,1},{6,2},{8,2},{9,1},{11,4},{12,2},{14,1},{15,1}}
如果使用函数式编程,我们就可以去除辅助函数runEncodeSplit
:
In[X]:= Clear[runEncodeFP]; runEncodeFP[x_List]:=Map[{First[#],Length[#]}&,Split[x]];
检查一下:
In[X]:= runEncodeFP[testlist]
Out[X]:= {{1,1},{2,3},{3,1},{4,2},{8,3},{9,3},{10,4},{13,1},{15,2}}
10.3.4 计算重复列表元素的频率
Split另一个相关的应用是和Sort连用构造出一个能够计算列表中重复元素的频率的函数。如果你能注意到其实我们只需对原始列表进行排序,然后用runEncode
来处理这个排序后的列表的话,事情将变得非常简单:
In[X]:= Clear[frequencies]; frequencies[x_List]:=runEncode[Sort[x]];
检查一下:
In[X]:= frequencies[testlist]
Out[X]:= {{2,1},{3,2},{4,3},{5,1},{6,2},{8,2},{9,1},{11,4},{12,2},{14,1},{15,1}}
事实上,在'Statistics'DataManipulation
扩展包中的Frequencies函数用的也几乎是同一种方法。
在其他地方Split也十分重要,我们会在后面的章节中给出更多的例子。
In[X]:= Clear[testlist,sorted,mod3sorted,listDivide,frequencies,runEncodeSplit,runEncode,runEncodeFP];
11 小结
在这一章中我们介绍了作为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。
有了这些函数,我们就已经能解决相当多的问题了。不过我们还需要另一个严谨编程的重要组成部分——对Mathematica 函数的理解:知道它们是什么,如何定义等等。这些是下一章要讲到的话题。