The difference is that dis[k,:] eliminates the first dimension since you are using a single number as an index, but dis[k:k+1,:] does not eliminate that dimension.
On Sat, Nov 6, 2010 at 1:24 PM, <[email protected]> wrote: > On Sat, Nov 6, 2010 at 4:14 PM, K. Sun <[email protected]> wrote: >> Thanks a lot. It works! I modify the code as follows and it runs >> at fast as matlab. By numpy's convention, the input and output >> are all ndarrays. 'route' has to be a (1xN) matrix to produce a >> square matrix in 'route + route.T'. > > If you read my small print, > > route = dis[k:k+1, :] should create (1,N) array or alternatively > dis[k, :][:,None] > > I don't like mixing matrices with arrays because it gets confusing and > matrices are (sometimes, often?) slower. > > glad to hear it got faster. > > Josef > >> >> def floyd( dis ): >> '''Floyd-Wallshall algorithm for shortest path >> >> 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.mat( dis[k, :] ) >> dis = np.minimum( dis, route + route.T ) >> >> return np.array( dis ) >> >> * [email protected] <[email protected]> [2010-11-06 15:46:17 -0400]: >> >>>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 >> >> -- >> Ke Sun, Research Assistant >> Viper Group, Computer Vision and Multimedia Lab >> University of Geneva, Switzerland >> Tel: +41 (0)22 379 0176 Fax: +41 (0)22 379 0250 >> _______________________________________________ >> 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 > _______________________________________________ NumPy-Discussion mailing list [email protected] http://mail.scipy.org/mailman/listinfo/numpy-discussion
