楼主:
LPH66 (-6.2598534e+18f)
2014-12-21 03:28:46※ 引述《Serenede (Serenede)》之铭言：
: sav = 0; iter = 10000000;
: For[i = 1, i <= iter, i++,
: If[Random[]^2 < 1/2, sav = sav + 1;]
: ] // Timing
: 2 sav/iter // N
这里有几个点可以提:
首先, i 这个只有计数不参加计算的变量可以拿掉
这种单纯做某事 n 次的可以使用不带变量的 Do
此例就是改写成 Do[If[Random[]^2 < 1/2, sav = sav + 1;], {it}]
在我的电脑上这样就可以只用 70% 的时间
接下来要怎么进步其实有两个方向
一个是把高阶的 If 变成低阶的
这里有一个平常少用的函式叫做 UnitStep
当所有参数都大于等于 0 时回传 1, 有参数小于 0 时则回传 0
由于图形就像一阶阶梯一样所以叫做 UnitStep (“单位阶梯”)
这里你是想要让 Random[]^2 < 1/2 时累积变量加 1
因此将 1/2 - Random[]^2 送进 UnitStep 就可以得到对应的 1 或 0 的结果
再把它全部加进 sav 里就行了
这里之所以说是把高阶 If 变成低阶是因为
UnitStep 把这个判断给包起来了, 它变成底层运算里的一部份
相对于我们做出比较再使用 If 判断效率会高一点
只不过单纯这样做会把另一个问题给显露出来
Do[sav = sav + UnitStep[1/2-Random[]^2], {it}]
这一行在我的电脑上的执行时间是一开始的 80%
问题在于原本因为 If 的关系, sav 这个变量只会在有更新时才会改写
现在却是每一圈时都会改写一次, 即使改写成的值跟原来一样
(这也是为什么一开始将 i 变量的改写拿掉之后效率会变好这么明显的原因)
也就是有部份圈数原本没有变量改写的在改动后有变量改写造成效率降低
所以另一个方向就是我们要再想办法把 sav 这个变量拿掉
可以看到每次运算的结果其实就只是单一值的更新
也就是说这可以看成 新sav=运算[旧sav] 这样的一个函数
对 Mathematica 来说进行函数运算比实际存取变量要好太多了
因此我们可以把这个运算写成一个函数, 然后套用 Nest 进行迭代
(关于 Nest 可参照本版 #1JbkymTC, 那篇也是在讲一个差不多的迭代状况可以参考)
这样这个变量的中间结果就会变成函式迭代的中间过程, 变量本身就不见了
于是把运算写成纯函式之后就变成推文这一条了:
: → biglion: Nest[UnitStep[(1/2-Random[]^2)]+#&,0,10000000] 12/21 00:57
(关于纯函式可参照本版 #1EiPGgzs)
这一条在我的电脑上的执行时间大约只有原来的 3~4% 而已
不过呢, Mathematica 在这里有一个大绝招
还记得我上面提说把高阶 If 变成低阶吧？
Mathematica 有一个函式可以把大部份简单的运算都给变成低阶, 叫做 Compile
用法是 Compile[{变量}, 函数定义]
它会回传一个 CompiledFunction 物件, 可以当做函式使用
喂给这个物件参数就会用比较低阶的方式计算你给的函数
(实际上 Compile 是将函数编译成 Mathematica 内部专用的虚拟机器码
所以会比直接进行高阶运算来的快)
最一开始的程式其实稍做修改就能改成 Compile 版:
calculate1 = Compile[{{iter, _Integer}},
Module[{sav, i},
sav = 0;
For[i = 1, i <= iter, i++, If[Random[]^2 < 0.5, sav = sav + 1;]];
sav
]
]
calculate1[10000000]
很惊人的, 在我的电脑上这个计算的时间就已经是一开始的 4~5% 了!
这就是将运算变成低阶的威力
(事实上, 整个函式里只有 Random 这个函式没有低阶对应而要额外呼叫
全部的时间有不小的部份都是花在这个外部呼叫上面的)
当然上面的改进写进去也有助于计算加速
把推文的那条改成 Compile 版是这样:
calculate2 = Compile[{{iter, _Integer}},
Nest[UnitStep[(0.5 - Random[]^2)] + # &, 0, iter]]
calculate2[10000000]
我的电脑上这一条的计算时间是一开始的 2% 而已
之所以看起来没有差多少的原因就是因为 Random 这个外部呼叫的时间的关系
不过呢, Compile 时有一个重点要记一下
参数如果可以确定是整数, 那参数列上写成像上面范例那样有助于加速
因为对电脑来说整数运算比实数运算要来得快
做个比较, 如果 calculate1 的参数列单纯只写 {iter} 的话
执行时间会多出约四分之一
这是因为 Compile 会假设参数是实数的关系
不过如果算到一半不得不出现实数时, 那写实数会比写分数快
上面的 Compile 版把 1/2 改成 0.5 就是这个原因
因为 Random 的回传值一定是实数
如果那里依然写 1/2 的话计算时间会稍稍多个 10% 左右