On Sat, Nov 6, 2010 at 3:28 PM, K. Sun <[email protected]> wrote: > Hello, > > I wrote the following code with numpy to implement the Floyd-Wallshall > algorithm to compute the pair-wise shortest path in a undirected weighted > graph. It is really slow when N ~ 10k, while the same implementation in > matlab is much faster. I am sorry I don't want to run it again to > present some accurate comparison. Is there any suggestions to optimize > this code without destroying the elegant coding style of python? > Thank you very much. > > def floyd( dis ): > ''' > dis is the pair-wise distance matrix. > return and update dis as the shortest path matrix w_{ij}.''' > > N = dis.shape[0] > for k in range( N ): > route = np.kron( np.ones( (N, 1) ), dis[k, :] )
I think your kron just does broadcasting, if you use route = dis[k:k+1, :] (I expect) you get the same results, and it would save one intermediary array > dis = np.minimum( dis, route + route.T ) Otherwise, I don't see much that I would speed up (without understanding the algorithm) Josef > > return dis > _______________________________________________ > NumPy-Discussion mailing list > [email protected] > http://mail.scipy.org/mailman/listinfo/numpy-discussion > _______________________________________________ NumPy-Discussion mailing list [email protected] http://mail.scipy.org/mailman/listinfo/numpy-discussion
