[Numpy-discussion] Good way to develop numpy as popular choice!

[Benjamin Root]

On Fri, Jun 22, 2012 at 9:42 AM, eat <e.antero.tammi at gmail.com> wrote:

> Hi,
>
> On Fri, Jun 22, 2012 at 7:51 AM, Gael Varoquaux <
> gael.varoquaux at normalesup.org> wrote:
>
>> On Thu, Jun 21, 2012 at 08:59:09PM -0400, Benjamin Root wrote:
>> >      > munkres seems to be a pure python implementation ;-).
>>
>> >      Oops! I could have sworn that I once tried one named munkres that
>> used
>> >      numpy. But that was several years ago.
>>
>> >    There is a development branch of sk-learn with an implementation of
>> the
>> >    hungarian assignment solver using numpy. It will even do non-square
>> >    matrices and matrices with an empty dimension.
>>
>> Yes, absolutely, thanks to Ben:
>>
>> https://github.com/GaelVaroquaux/scikit-learn/blob/hungarian/sklearn/utils/hungarian.py
>> I never merged this in the main scikit-learn tree, because munkres is not
>> used so far. Maybe I should merge it in the main tree, or maybe it should
>> be added to scipy or numpy.
>>
> I made some simple timing comparisons (see attached picture) between numpy
> based hungarian and pure python shortest path based hungarian_sp. It seems
> that pure python based implementation outperforms numpy based
> implementation. Timings are averaged over five runs.
>
> The difference cannot totally be explained by different algorithms
> (although shortest path based seem to scale better).  Rather the heavy
> access to rows and columns seem to favor list of lists. So this type of
> algorithms may indeed be real challenges for numpy.
>
>
eat,

Thanks for that analysis.  Personally, I never needed high-performance so I
never bothered to optimize it.  However, it does appear that there is an
order-of-magnitude difference between the two, and so it might be worth it
to see what can be done to fix that.

Ben Root
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20120622/33eb5961/attachment.html>