search

cheind / py-lapsolver

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

Q: why is py-lapsolver so much faster than its counterparts like scipy.optimize.linear_sum_assignment or sklearn.utils.linear_assignment_? #6

Closed guoyangqin closed 2 years ago

guoyangqin commented 5 years ago

Thanks for this package, it saves me a huge amount of time.

Just wondering why is it so much faster? Is it because of a better algorithm or being based on C. If latter, why didn't scipy.optimize.linear_sum_assignment or sklearn.utils.linearassignment develop based on C? Thanks.

cheind commented 5 years ago

Hard to tell, as I'm not familiar with the details of the scipy implementation. The problem is O(n^x) where x in {3,4} depending on the implementation (see [1]). A genuine C implementation might cure any overhead that stems from looping in interpreted languages.

[1] http://www.assignmentproblems.com/doc/LSAPIntroduction.pdf