求Floyd算法在Mathematica下的改进方法

luyuwuli

我写了个算最短路径矩阵的Floyd算法，但是在计算307*307矩阵的时候速度太慢了，要等十分钟左右。（输给了MATLAB，不甘心啊~~）请大家看看这段代码怎么在mathematica下面改进一下啊。因为我基本上是按照C语言的习惯写的，没有考虑到mathematica的函数式编程的特点。

1. 
   
2. floyd[x_] :=
   
3.   Module[{n, i, j, k, d},
   
4.    n = Length[x];
   
5.    d = x;
   
6.    For[k = 1, k <= n, k++,
   
7.     For[i = 1, i <= n, i++,
   
8.       For[j = 1, j <= n, j++,
   
9.         If[d[[i, j]] > d[[i, k]] + d[[k, j]],
   
10.           d[[i, j]] = d[[i, k]] + d[[k, j]]];
    
11.         ];
    
12.       ];
    
13.     ];
    
14.    d
    
15.    ];
    

复制代码

为简单起见，上面的代码没有算路径矩阵。
另外，请问大家：在用mathematica编程的时候和其他的语言最大的不同在什么地方呢？
大家都是如何适应函数式编程语言的呢？要避免哪些先入为主的编程习惯，写出高效率的代码呢？

chyanog

可以用Do代替For

FreddyMusic

用 Dijkstra(迪杰斯特拉)算法 O(n^2) + 动态规划.
http://baike.baidu.com/view/14495.html

Floyd算法效率太低了O(n^3) ,这和 Mathematica 没有关系.

luyuwuli

3# FreddyMusic
可是，我同学在MATLAB下面用同样的算法，速度却比我的快很多。我在想是不是能用比如递归调用之类的方法避免For循环。

FreddyMusic

你测试这个 算法的代码是什么？或者说你评价这个算法的代码是什么？
贴出来，我看看，可以教你一招半式，你拿回去可以打败，你那个Matlab的同学。

FreddyMusic

你测试这个算法的代码是什么？或者说你评价这个算法的代码是什么？
贴出来，我看看，可以教你一招半式，你拿回去可以打败，你那个Matlab的同学。

chyanog

Mathematica里面For很灵活，不过效率通常不高（相对于Do和Table，While速度也慢。例子很容易找，真不行我下面贴上），可以将楼主的代码转换为Do循环去做，不妨一试

FreddyMusic

Mathematica里面For很灵活，不过效率通常不高（相对于Do和Table，While速度也慢。例子很容易找，真不行我下面贴上），可以将楼主的代码转换为Do循环去做，不妨一试
chyanog 发表于 2010-8-29 01:16

我觉得 Do 和 For 基本上差不多，你有实例能显示Do的效率比For 高？能显示的更具体些？

luyuwuli

好的谢谢版主：

1. {dltemp} = Import[FileNameJoin[{NotebookDirectory[], "coordinate.xls"}]]; {drtemp} = Import[FileNameJoin[{NotebookDirectory[], "relation.xls"}]]; lend = Length[dltemp]; lenr = Length[drtemp]; dtemp = Table[If[i == j, 0, \[Infinity]], {i, 1, lend}, {j, 1, lend}]; For[j = 1, j <= lenr, j++, dtemp[[drtemp[[j, 1]], drtemp[[j, 2]]]] = dtemp[[drtemp[[j, 2]], drtemp[[j, 1]]]] = \[Sqrt]((dltemp[[drtemp[[j, 1]], 1]] - dltemp[[drtemp[[j, 2]], 1]])^2 + (dltemp[[drtemp[[j, 1]], 2]] - dltemp[[drtemp[[j, 2]], 2]])^2); ]; floyd[x_] := Module[{n, i, j, k, d, r, result}, n = Length[x]; r = Table[j, {i, 1, n}, {j, 1, n}]; d = x; For[k = 1, k <= n, k++, For[i = 1, i <= n, i++, For[j = 1, j <= n, j++, If[d[[i, j]] > d[[i, k]] + d[[k, j]], d[[i, j]] = d[[i, k]] + d[[k, j]]; r[[i, j]] = k]; ]; ]; ]; result = {d, r} ]; Export[FileNameJoin[{NotebookDirectory[], "distanceread1-2.txt"}], d]

复制代码

relation.xls存的是相邻点的编号，coordinate.xls存的是每个编号点的坐标。三个源文件见附件



由于没办法直接上传xls文件，我把coordinate.xls和relation.xls改了后缀名，麻烦用的时候再改回~

FreddyMusic

我好好看看，可能需要点时间，来完成我的想法。

下次上传Text 或 xls 文件，可以压缩一下变成Zip文件后上传。

luyuwuli

本来代码贴上去好好的，但是转换成高级回复就变乱了，还是看源文件吧~~

luyuwuli

10# FreddyMusic
好的，竟然忘了还能上传压缩文件，呵呵~~

luyuwuli

7# chyanog

我试过了，但是用Do循环速度也不快啊,我的机器上用了510.953秒，只比For循环的596.657秒快了86秒左右，应该是这样写吗？
Do循环的Floyd算法（无路径矩阵）：

1. 
   
2. 
   
3. floyd[x_] :=
   
4.   Module[{n, i, j, k, d},
   
5.    n = Length[x];
   
6.    d = x;
   
7.    Do[If[d[[i, j]] > d[[i, k]] + d[[k, j]],
   
8.      d[[i, j]] = d[[i, k]] + d[[k, j]]], {k, 1, n}, {i, 1, n}, {j, 1,
   
9.      n}];
   
10.    d
    
11.    ];
    
12. 
    

复制代码

chyanog

8# FreddyMusic 估计版主这方面没有在意，就举一个循环累加的简单例子吧：

1. Module[{sum = 0, i},
   
2.   For[i = 1, i <= 10^6, i++,   
   
3. sum += i ];
   
4. sum] // AbsoluteTiming

复制代码

{4.7656250, 500000500000}

1. 
   
2. Module[{sum = 0},
   
3. Do[sum += i,  
   
4. {i, 10^6}];  
   
5. sum] // AbsoluteTiming

复制代码

{2.1093750, 500000500000}

1. Module[{sum = 0},
   
2. Table[sum += i, {i, 10^6}];
   
3. sum] // AbsoluteTiming

复制代码

{2.2187500, 500000500000}


其实，楼主也已经用Do改写过了，这也说明了Do的确明显比For快，尽管同一个数量级。不过由于同样的算法，不大可能从质上提高效率，那只有从算法上来改进了。

FreddyMusic

解释一下这两个要求计算的点（绿点）分别是什么含义？具体说明？

另外，你那个Matlab 同学用了多长时间？

哥找到了一个红点。

gyc_cn

mathematica 里面有这个函数功能呀，不用自己编写的
图论里面的GraphPath函数可以解决
相关函数请查看Needs["GraphUtilities`"];工具包

算法主要有  "BellmanFord", "Dijkstra", "FloydWarshall", and "Johnson".可以用Method->opt选定

chyanog

luyuwuli 发表于 2010-8-29 10:54
7# chyanog  

我试过了，但是用Do循环速度也不快啊,我的机器上用了510.953秒，只比For循环的596.657秒快 ...

以前不知道用Compile函数，今天试了下，在我的电脑上500×500的8s就行了（旧笔记本）
如果没有C编译器的话，速度会慢一些

1. cfloyd = Compile[{{d0, _Real, 2}},
   
2.    Module[{n, d},
   
3.     n = Length[d0];
   
4.     d = d0;
   
5.     Do[
   
6.      If[d[[i, j]] > d[[i, k]] + d[[k, j]],
   
7.       d[[i, j]] = d[[i, k]] + d[[k, j]]],
   
8.      {k, 1, n}, {i, 1, n}, {j, 1, n}];
   
9.     d
   
10.     ], RuntimeOptions -> "Speed", CompilationTarget -> "C"
    
11.    ];
    
12. 
    
13. data = RandomReal[10, {500, 500}];
    
14. cfloyd[data]; // AbsoluteTiming

复制代码

luyuwuli

chyanog 发表于 2013-4-27 23:06
以前不知道用Compile函数，今天试了下，在我的电脑上500×500的8s就行了（旧笔记本）
如果没有C编译器的 ...

恩，好久以前问的帖子了。后来我也发现用Compile之后速度飞快。时间久了就忘了。不过有一个问题就是对于需要用到side-effect的算法，似乎用函数式编程会比较痛苦。