[Numpy-discussion] Optimize Floyd-Wallshall algorithm with Numpy
josef.pktd@gmai...
josef.pktd@gmai...
Sat Nov 6 15:24:29 CDT 2010
On Sat, Nov 6, 2010 at 4:14 PM, K. Sun <sunk.cs@gmail.com> 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 )
>
> * josef.pktd@gmail.com <josef.pktd@gmail.com> [2010-11-06 15:46:17 -0400]:
>
>>On Sat, Nov 6, 2010 at 3:28 PM, K. Sun <sunk.cs@gmail.com> 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
>>> NumPy-Discussion@scipy.org
>>> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>>>
>>_______________________________________________
>>NumPy-Discussion mailing list
>>NumPy-Discussion@scipy.org
>>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
> NumPy-Discussion@scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>
More information about the NumPy-Discussion
mailing list