Mathematica 循环计算效率

这两天帮欧洲的研究小组处理试验数据,就是计算试验数据的 Radial Distribution Funciton (RDF),发现50,000个数据点,用Mathematica处理起来非常吃力。已经开始用C++写程序了,后来尝试另一种方法,找到的计算时间上的差异。

问题定义:列举寻找N个点之间的距离。实现方法有两种,计算复杂度都是 O(N^2)。Mathematica里可以用两种方法实现:(1)利用Subset函数罗列2个点的组合,然后计算距离(Euclidean Distance);(2)利用循环。程序如下:

NumG = 500; Data = RandomReal[1, {NumG, 3}];
(* Method 1: Use Mathematica in-build function *)
DistDistance = {};
Timing[DistDistance = EuclideanDistance @@@ Subsets[Data, {2}];][[1]]
(* Method 2: Use loops *)
DistDistance = {};
Timing[For[i = 2, i <= NumG, i++,
For[j = 1, j <= i - 1, j++, {dx = Norm[Data[[i]] - Data[[j]]]; AppendTo[DistDistance, dx];
}]];][[1]]

测试程序里,都用了500个随机点。前一种是抽象语言,实现时间大概是0.128秒*;而后者属于底端的循环定义,尽然用了44.9秒!而且前者与数据点数量符合O(N^2),后者在1000个点以上就根本无法处理了。

看来以后用Mathematica还是要多使用程序里的函数形式。

 

*硬件环境,MacBook Pro 2014。

[补注] 这个看来是和内存利用相关的。第二种方法采用了AppendTo 函数,在每个循环里都在进行内存的读写。尺寸大的算例里,内存可以用到10G以上。计算程序已经优化。

[补补注] 需要提高计算效率,可以采用几种不同的函数定义方式。上文提到的方法,其中输入函数,并没有确定数据类型。这个其实是Mathematica的优点之一。但是要进行循环计算的时候,就反倒有效率上劣势。其解决方法是换用函数定义方法。下面是几个实测的算例,都是 10^7 次循环。

定义一,函数定义采用 ":=",或者"Function[]",计算时间在70秒左右; 

定义二,采用 Compile[],需要预先定义函数类型,计算时间10秒左右;

定义三,采用 Compile[],类似定义二,但是在最后制定编译类型,CompilationTarget->"C"。计算时间3.5秒。定义入下图。

2 Comments »

  1. 匿名 Said,

    21 4 月, 2015 @ 13:46

    循环怎么这么慢,以前用fortran算rdf,10k颗粒也用不了这么长时间

  2. 杨羽 Said,

    21 4 月, 2015 @ 13:55

    主要原因应该还是内存。和以前的一个例子一样,大尺寸计算时,读写时间在循环中占不少比重。

发表评论