On Fri, Jun 22, 2012 at 9:42 AM, eat <e.antero.ta...@gmail.com> wrote:
> Hi, > > On Fri, Jun 22, 2012 at 7:51 AM, Gael Varoquaux < > gael.varoqu...@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
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
