Skip to main content

Python module to solve the linear sum assignment problem (LSAP) low memory friendly

Project description

nanolsap

A Python module to solve the linear sum assignment problem (LSAP) efficiently. Extracted from SciPy, and modified to minimal memory cost.

Description

from nanolsap import linear_sum_assignment
Solve the linear sum assignment problem.

Parameters
----------
cost_matrix : array
    The cost matrix of the bipartite graph.
    It should be 2-D ArrayLike object, with nr rows and nc cols.

maximize : bool (default: False)
    Calculates a maximum weight matching if true.

subrows : array (default: None)
    Use sub rows from cost matrix if not None.

subcols : array (default: None)
    Use sub cols from cost matrix if not None.

Returns
-------
row_ind, col_ind : array
    An array of row indices and one of corresponding column indices giving
    the optimal assignment. The cost of the assignment can be computed
    as ``cost_matrix[row_ind, col_ind].sum()``. The row indices will be
    sorted if subrows and subcols are both None; in the case of a square cost
    matrix they will be equal to ``numpy.arange(cost_matrix.shape[0])``.

This module is useful in cases when you need an efficient LSAP solver on very large cost_matrix and limited memory.

For a cost_matrix with dtype float64 has shape of 30000*30000, it needs 30000*30000*8 / 1024**3 = 6.7GB memory to store it. In scipy.optimite.linear_sum_assignment, it will first convert it to float64 contiguous numpy 2-D array, then do a copy, and finally starts the solver. So, the actual memory cost is at least 6.7*2 = 13.4GB. if the origin cost_matrix does not match, for example a float32 2-D array, the first step here will cause one extra copy, increases the actual memory cost to 6.7/2+6.7*2 = 16.75GB.

In this module, When input cost_matrix is a contiguous numpy 2-D array, the solver can run on it directly without any copy. Also, cost_matrix can use small dtype like float32 to half reduce memory, so 3.35GB memory is enough.

Notice: when nr > nc, scipy.optimize.linear_sum_assignment will copy then transpose and rearrange cost matrix so keeps memory access locality, but this module do not do this, so it is about 2x slower in this situation. For nr <= nc, this module has almost no performance drop, so you can manually construct a transposed cost matrix for this module, and manually swap row_ind and col_ind result if nr > nc to get better performance.

The subrows and subcols arguments allow solver run on only a subgroup of row and cols on cost_matrix. The result should be same as scipy.optimize.linear_sum_assignment(cost_matrix[np.ix_(subrows, subcols)]), but it avoids the expensive construct of sub cost_matrix.

License

The code in this repository is licensed under the 3-clause BSD license, except for files including a different license header.

The LSAP solver copied from SciPy is also licensed under the 3-clause BSD license.

Some files copied from minilsap are also licensed under the 3-clause BSD license.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

nanolsap-0.1.4.tar.gz (16.0 kB view details)

Uploaded Source

Built Distributions

nanolsap-0.1.4-cp39-abi3-win_amd64.whl (25.2 kB view details)

Uploaded CPython 3.9+ Windows x86-64

nanolsap-0.1.4-cp39-abi3-win32.whl (21.4 kB view details)

Uploaded CPython 3.9+ Windows x86

nanolsap-0.1.4-cp39-abi3-musllinux_1_2_x86_64.whl (1.0 MB view details)

Uploaded CPython 3.9+ musllinux: musl 1.2+ x86-64

nanolsap-0.1.4-cp39-abi3-musllinux_1_2_i686.whl (1.1 MB view details)

Uploaded CPython 3.9+ musllinux: musl 1.2+ i686

nanolsap-0.1.4-cp39-abi3-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (36.3 kB view details)

Uploaded CPython 3.9+ manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

nanolsap-0.1.4-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl (33.6 kB view details)

Uploaded CPython 3.9+ manylinux: glibc 2.17+ i686 manylinux: glibc 2.5+ i686

nanolsap-0.1.4-cp39-abi3-macosx_10_9_universal2.whl (48.6 kB view details)

Uploaded CPython 3.9+ macOS 10.9+ universal2 (ARM64, x86-64)

File details

Details for the file nanolsap-0.1.4.tar.gz.

File metadata

  • Download URL: nanolsap-0.1.4.tar.gz
  • Upload date:
  • Size: 16.0 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.0 CPython/3.12.4

File hashes

Hashes for nanolsap-0.1.4.tar.gz
Algorithm Hash digest
SHA256 3c651512b37e8db03abbdf910eb0b6dffb739c6105c51cf4e02ed38b3e550610
MD5 237bf8bc678627ac80e06b8c0d27d59a
BLAKE2b-256 69fefd647c3b340afa3a86c6fcf0282e7eb673612ed558eaa745c1c6e4c2d437

See more details on using hashes here.

File details

Details for the file nanolsap-0.1.4-cp39-abi3-win_amd64.whl.

File metadata

  • Download URL: nanolsap-0.1.4-cp39-abi3-win_amd64.whl
  • Upload date:
  • Size: 25.2 kB
  • Tags: CPython 3.9+, Windows x86-64
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.0 CPython/3.12.4

File hashes

Hashes for nanolsap-0.1.4-cp39-abi3-win_amd64.whl
Algorithm Hash digest
SHA256 d4e47d034ccd45dd0113d45129ce71ade787319737a8c0021f6b890be417405d
MD5 41efc6c2576488a2760435e69b80a2f3
BLAKE2b-256 3abf15eda3cabbd6437ac9e22c4bd680f562f00e9bd03a24566dce7f16faa3df

See more details on using hashes here.

File details

Details for the file nanolsap-0.1.4-cp39-abi3-win32.whl.

File metadata

  • Download URL: nanolsap-0.1.4-cp39-abi3-win32.whl
  • Upload date:
  • Size: 21.4 kB
  • Tags: CPython 3.9+, Windows x86
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/5.1.0 CPython/3.12.4

File hashes

Hashes for nanolsap-0.1.4-cp39-abi3-win32.whl
Algorithm Hash digest
SHA256 d1bf5255e800d30befefd540b16ee1541e14039022588a48a8c98a2a22a41a5b
MD5 5b8c4de8b81227d0224c2144b55f7c25
BLAKE2b-256 5b2afb292bf5b5064b520d8cbdf5117ab174e1e0748bc2b9e4957012abe41f2e

See more details on using hashes here.

File details

Details for the file nanolsap-0.1.4-cp39-abi3-musllinux_1_2_x86_64.whl.

File metadata

File hashes

Hashes for nanolsap-0.1.4-cp39-abi3-musllinux_1_2_x86_64.whl
Algorithm Hash digest
SHA256 112387656381be76b451813e8667b9704151d1b46d390bfed2042eb320432778
MD5 14e0c91b2c648bc8ee5f7cbf179e4c99
BLAKE2b-256 307b9f2f7e23a291edb0df820e4689ec93a00d2c27da9de61d0da6001590a030

See more details on using hashes here.

File details

Details for the file nanolsap-0.1.4-cp39-abi3-musllinux_1_2_i686.whl.

File metadata

File hashes

Hashes for nanolsap-0.1.4-cp39-abi3-musllinux_1_2_i686.whl
Algorithm Hash digest
SHA256 b67cf129ef61348e9879339b52112a42d02ed22900c0d0218f1be439f6e3bb9d
MD5 7416d43369547d8421824db8600691f7
BLAKE2b-256 87b7e95b4543f195e60ecade7cbd562236b1d6c795188b62aea7313a2f898dc3

See more details on using hashes here.

File details

Details for the file nanolsap-0.1.4-cp39-abi3-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl.

File metadata

File hashes

Hashes for nanolsap-0.1.4-cp39-abi3-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm Hash digest
SHA256 47c061d6903827ffbc2ab7566249476a6ea9076751f97f60ecfd0f4106e2a102
MD5 4c17f68e9570b5b68909de7b3c25555d
BLAKE2b-256 2e6d141c9fe901a5864bf5a7be6b178932404beab31ff998ee44dd9e97311f83

See more details on using hashes here.

File details

Details for the file nanolsap-0.1.4-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl.

File metadata

File hashes

Hashes for nanolsap-0.1.4-cp39-abi3-manylinux_2_5_i686.manylinux1_i686.manylinux_2_17_i686.manylinux2014_i686.whl
Algorithm Hash digest
SHA256 2fd0c5d660be0b4fa8fc2613d874ebf0557427eb441107aea72135b6d8ca818f
MD5 5634855803fa39e9edadc7614d406b4e
BLAKE2b-256 f9744b8dbeb7a050ce0a264d36d4a50d3a16d5f76a734958f117e5065bdb2af1

See more details on using hashes here.

File details

Details for the file nanolsap-0.1.4-cp39-abi3-macosx_10_9_universal2.whl.

File metadata

File hashes

Hashes for nanolsap-0.1.4-cp39-abi3-macosx_10_9_universal2.whl
Algorithm Hash digest
SHA256 42c8ee1eb5ff77c7910ebafd75ae2bbce5c4afc569924b54b422f13dda20df2d
MD5 9b8a66ec7ea3d04549b869b2069bec46
BLAKE2b-256 8ebac5125b46d4fcb8929f2c96fb4974bf3f7ae10b1856fe3f3a35f890a7bbf6

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page