Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

refactoring for additional speed improvements #5

Merged
merged 6 commits into from Mar 22, 2022
Merged

refactoring for additional speed improvements #5

merged 6 commits into from Mar 22, 2022

Conversation

plusk01
Copy link
Member

@plusk01 plusk01 commented Mar 22, 2022

these changes are API breaking

further speed improvements over (#3) are found by improving the use of sparsity (i.e., only populating the upper triangle) and by limiting the amount of data that is copied.

note: this PR leaves matlab bindings broken for now

Sparse and avoiding mat-vec multiplies (#3)

Benchmarking over 20 trials


Benchmarking ρ = 90% [██████████████████████████████████████████████████] 100% [00m:56s]               

+-------+---------+----------------+-------------------+---------------+------------+
| ρ [%] | # assoc |  affinity [ms] | dense clique [ms] | precision [%] | recall [%] |
+-------+---------+----------------+-------------------+---------------+------------+
| 0     | 64      |   0.52  ±  0.9 |      0.07  ±  0.0 | 100           | 89         |
| 0     | 256     |   1.41  ±  0.4 |      0.92  ±  0.2 | 100           | 89         |
| 0     | 512     |   5.30  ±  0.3 |      3.62  ±  0.8 | 100           | 89         |
| 0     | 1024    |  42.30  ±  1.7 |      9.63  ±  1.5 | 100           | 89         |
| 0     | 2048    | 174.11  ±  9.8 |     47.51  ±  9.4 | 100           | 89         |
+-------+---------+----------------+-------------------+---------------+------------+
| 20    | 64      |   0.25  ±  0.0 |      0.24  ±  0.0 | 100           | 89         |
| 20    | 256     |   1.18  ±  0.1 |      3.89  ±  0.8 | 100           | 89         |
| 20    | 512     |   5.10  ±  0.3 |     15.27  ±  2.5 | 99            | 89         |
| 20    | 1024    |  23.18  ±  2.5 |     54.81  ± 11.1 | 99            | 89         |
| 20    | 2048    | 133.73  ± 12.5 |    345.16  ± 77.3 | 99            | 89         |
+-------+---------+----------------+-------------------+---------------+------------+
| 40    | 64      |   5.34  ±  5.6 |      0.25  ±  0.0 | 100           | 89         |
| 40    | 256     |   1.04  ±  0.1 |      3.36  ±  0.7 | 99            | 89         |
| 40    | 512     |   4.22  ±  0.4 |     12.42  ±  1.5 | 100           | 89         |
| 40    | 1024    |  21.38  ±  3.6 |     48.93  ± 11.1 | 99            | 89         |
| 40    | 2048    |  92.75  ±  4.5 |    264.75  ± 55.5 | 99            | 89         |
+-------+---------+----------------+-------------------+---------------+------------+
| 80    | 64      |   0.37  ±  0.6 |      0.16  ±  0.0 | 99            | 91         |
| 80    | 256     |   0.86  ±  0.1 |      1.71  ±  0.2 | 100           | 90         |
| 80    | 512     |   3.46  ±  0.3 |      7.44  ±  1.7 | 99            | 89         |
| 80    | 1024    |  15.76  ±  0.4 |     23.73  ±  3.6 | 99            | 89         |
| 80    | 2048    |  63.44  ±  4.6 |    113.56  ± 28.4 | 99            | 89         |
+-------+---------+----------------+-------------------+---------------+------------+
| 90    | 64      |   0.23  ±  0.0 |      0.17  ±  0.0 | 99            | 91         |
| 90    | 256     |   0.86  ±  0.1 |      1.64  ±  0.2 | 99            | 90         |
| 90    | 512     |   3.22  ±  0.4 |      6.25  ±  1.0 | 99            | 90         |
| 90    | 1024    |  15.01  ±  0.5 |     21.29  ±  2.9 | 99            | 90         |
| 90    | 2048    |  61.48  ±  3.3 |     93.10  ± 13.6 | 99            | 90         |
+-------+---------+----------------+-------------------+---------------+------------+

this version

Benchmarking over 20 trials


Benchmarking ρ = 90% [██████████████████████████████████████████████████] 100% [00m:46s]               

+-------+---------+---------------+-------------------+---------------+------------+
| ρ [%] | # assoc | affinity [ms] | dense clique [ms] | precision [%] | recall [%] |
+-------+---------+---------------+-------------------+---------------+------------+
| 0     | 64      |  0.29  ±  0.3 |      0.07  ±  0.0 | 100           | 89         |
| 0     | 256     |  0.88  ±  0.1 |      0.79  ±  0.2 | 100           | 89         |
| 0     | 512     |  3.42  ±  0.3 |      3.18  ±  1.1 | 100           | 89         |
| 0     | 1024    | 16.52  ±  1.2 |     11.79  ±  4.5 | 100           | 89         |
| 0     | 2048    | 73.97  ±  2.5 |     44.81  ± 20.4 | 100           | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 20    | 64      |  0.81  ±  2.6 |      0.21  ±  0.0 | 100           | 89         |
| 20    | 256     |  0.88  ±  0.1 |      3.15  ±  0.7 | 100           | 89         |
| 20    | 512     |  3.63  ±  0.4 |     13.58  ±  2.3 | 100           | 89         |
| 20    | 1024    | 16.22  ±  0.3 |     40.62  ± 10.0 | 99            | 89         |
| 20    | 2048    | 69.55  ±  4.3 |    235.73  ± 50.8 | 99            | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 40    | 64      |  0.22  ±  0.0 |      0.20  ±  0.0 | 100           | 89         |
| 40    | 256     |  0.86  ±  0.1 |      2.49  ±  0.3 | 99            | 89         |
| 40    | 512     |  3.49  ±  0.4 |     11.55  ±  2.3 | 100           | 89         |
| 40    | 1024    | 15.40  ±  0.4 |     39.22  ±  8.8 | 100           | 89         |
| 40    | 2048    | 57.30  ±  2.6 |    187.87  ± 50.2 | 99            | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 80    | 64      |  0.22  ±  0.0 |      0.14  ±  0.0 | 100           | 91         |
| 80    | 256     |  0.83  ±  0.1 |      1.50  ±  0.2 | 99            | 90         |
| 80    | 512     |  3.10  ±  0.3 |      5.81  ±  1.0 | 99            | 89         |
| 80    | 1024    | 15.39  ±  3.1 |     23.94  ±  6.1 | 99            | 89         |
| 80    | 2048    | 53.72  ±  1.4 |     86.29  ± 20.8 | 99            | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 90    | 64      |  0.22  ±  0.0 |      0.16  ±  0.0 | 100           | 92         |
| 90    | 256     |  0.98  ±  0.8 |      1.48  ±  0.2 | 99            | 89         |
| 90    | 512     |  3.43  ±  1.1 |      5.57  ±  1.0 | 99            | 91         |
| 90    | 1024    | 14.61  ±  1.2 |     21.31  ±  2.4 | 99            | 90         |
| 90    | 2048    | 53.18  ±  1.8 |     83.43  ± 15.7 | 99            | 90         |
+-------+---------+---------------+-------------------+---------------+------------+

@plusk01 plusk01 merged commit 1213acb into main Mar 22, 2022
@plusk01 plusk01 deleted the refactor branch March 22, 2022 04:11
@plusk01 plusk01 mentioned this pull request Apr 21, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

1 participant