Hi,<br><br><div class="gmail_quote">On Fri, Jun 22, 2012 at 7:51 AM, Gael Varoquaux <span dir="ltr"><<a href="mailto:gael.varoquaux@normalesup.org" target="_blank">gael.varoquaux@normalesup.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">On Thu, Jun 21, 2012 at 08:59:09PM -0400, Benjamin Root wrote:<br>
> † † †> munkres seems to be a pure python implementation ;-).<br>
<br>
> † † †Oops! I could have sworn that I once tried one named munkres that used<br>
> † † †numpy. But that was several years ago.<br>
<br>
> † †There is a development branch of sk-learn with an implementation of the<br>
> † †hungarian assignment solver using numpy. It will even do non-square<br>
> † †matrices and matrices with an empty dimension.<br>
<br>
</div>Yes, absolutely, thanks to Ben:<br>
<a href="https://github.com/GaelVaroquaux/scikit-learn/blob/hungarian/sklearn/utils/hungarian.py" target="_blank">https://github.com/GaelVaroquaux/scikit-learn/blob/hungarian/sklearn/utils/hungarian.py</a><br>
I never merged this in the main scikit-learn tree, because munkres is not<br>
used so far. Maybe I should merge it in the main tree, or maybe it should<br>
be added to scipy or numpy.<br></blockquote><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div><br></div><div>Regards,</div><div>-eat</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
GaŽl<br>
<div class="HOEnZb"><div class="h5">_______________________________________________<br>
NumPy-Discussion mailing list<br>
<a href="mailto:NumPy-Discussion@scipy.org">NumPy-Discussion@scipy.org</a><br>
<a href="http://mail.scipy.org/mailman/listinfo/numpy-discussion" target="_blank">http://mail.scipy.org/mailman/listinfo/numpy-discussion</a><br>
</div></div></blockquote></div><br>