search

cheind / py-lapsolver

Fast linear assignment problem (LAP) solvers for Python based on c-extensions
MIT License
154 stars 24 forks source link

Compare with new Scipy implementation #15

Closed Multihuntr closed 4 years ago

Multihuntr commented 4 years ago

As of v1.4.0 (Dec 2019) [1] [2] Scipy released a new implementation for solving the linear assignment problem.

The release notes under-sell how much of a speed improvement there is. I adapted the python-based tests found in https://github.com/Yay295/AssignmentProblemComparison, to test the speed across versions and found it to be up to 1000x faster than it used to be on random data.

For completeness: here is my test script, and these are my results:

                           |   50x50      250x250   1000x1000
--------------------------------------------------------------
scipy v1.3.4               |  0.009084    0.50559    59.3130
scipy v1.4.1               |  0.000101    0.00198     0.0439

They reference a paper in the source code which implies that this speedup is from a new, effective algorithm, rather than technical implementation improvements.

I think that either the tests should be re-run on scipy >1.4.0, or the README should make note that the latest scipy implementation is much faster than indicated.

jvlmdr commented 4 years ago

Hey, thanks for highlighting this. We updated the figures in commit 2935ababa635e6a066f144b3fa2440d8540877d5. Indeed it makes a huge difference.

Before: Before

After: After

jvlmdr commented 4 years ago

We should perhaps add the version numbers to the legend.

Multihuntr commented 4 years ago

Oh, my bad. I looked at the "README" last updated. I didn't think about the jpg itself. Sorry about that.

Including version number would ensure that it is always unambiguously correct.

But it is correct as-is, so I'll close this as an issue.