search

kevmo314 / canigraduate.uchicago.edu

Automated graduation dependency resolution.
http://canigraduate.uchicago.edu/
MIT License
4 stars 3 forks source link

Publish Hungarian algorithm implementation on npm #25

Open kevmo314 opened 6 years ago

kevmo314 commented 6 years ago

A custom implementation of the Hungarian algorithm is used because the current one published on npm (munkres-js) is too slow.

We should publish the faster one. The code can probably be cleaned up a bit and documented a little better before that and there are probably a few additional small performance improvements to be had.

bebbi commented 6 years ago

have you seen the hungarian-on3 npm package? It's pretty fast

kevmo314 commented 6 years ago

Interesting, no I haven't. It looks like it's substantially more code though and uses a different algorithm (the same one munkres-js uses). My intuition is that it'll be slower because it's not updating via augmenting paths, instead updating locally, however I'll take a look. Thanks for the pointer.

bebbi commented 6 years ago

It would be nice to hear your feedback how it compares with yours speed-wise! hungarian-on3 is way faster than munkres-js.

kevmo314 commented 6 years ago

Just ran a test, it looks like hungarian-on3 is slower for small matrices (smaller than ~100x100) but faster for anything larger:

20 20
canigraduate impl: 1.285ms
hungarian-on3 impl: 1.897ms

200 200
canigraduate impl: 18.053ms
hungarian-on3 impl: 22.275ms

2000 2000
canigraduate impl: 9956.591ms
hungarian-on3 impl: 1976.959ms

Would probably be worth investigating if some of the optimizations can be incorporated in, as the canigraduate implementation wasn't really meant to be optimized, just asymptotically fast.