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

John Salvatier jsalvati@u.washington....
Sat Nov 6 15:37:06 CDT 2010


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,  <josef.pktd@gmail.com> wrote:
> 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
>>
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion@scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>


More information about the NumPy-Discussion mailing list