[Numpy-discussion] Optimize Floyd-Wallshall algorithm with Numpy

[josef.pktd at gmail.com]

On Sat, Nov 6, 2010 at 4:14 PM, K. Sun <sunk.cs at 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 at gmail.com <josef.pktd at gmail.com> [2010-11-06 15:46:17 -0400]:
>
>>On Sat, Nov 6, 2010 at 3:28 PM, K. Sun <sunk.cs at 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 at scipy.org
>>> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>>>
>>_______________________________________________
>>NumPy-Discussion mailing list
>>NumPy-Discussion at 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 at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>