Performance of Combination

[hildjj]

I recently wrote the same code against this library's Combinations.of and compared it to very similar code in Python using itertools.combinations. In both cases, I was taking combinations of 200 inputs 3 at a time (a mere 1,313,400 results), iterating over the results with for/of and doing a trivial amount of processing for each combination. The Python itertools version was several orders of magnitude faster for no apparent reason.

input is a list of 200 integers. JS code node 15.3.0:

for (const [x, y, z] of Combination.of(input, 3)) {
}

Python 3.9.0:

for [x, y, z] in itertools.combinations(input, 3):

[N8Brooks]

I'm pretty sure itertools is written in c which is going to be way faster than js

[hildjj]

I think there's something else going on. Compare these two gists:

https://gist.github.com/hildjj/1e5cf863c25a2f75f8a0ff4c1f8e51c0 (199.87s user)

and

https://gist.github.com/hildjj/082bf5104006fc8cf97f92324b2607a8 (0.70s user) (sorry that second one is so long, but I wanted it to be self-contained for you)

You'll see that there is more than two orders of magnitude in difference between the performance of the same loop. This is on node 15.6.0, MacOS 11.1, on a recent-ish Intel Mac Mini.

[N8Brooks]

Oh okay, that seems quite inefficient! Is the second implementation lexicographically ordered?

[hildjj]

I just checked to make sure it wasn't some weird interaction with the esm package by modifying your package.json file to include "type": "module", changing my example to a .mjs, and changing the initial line to import {Combination} from 'js-combinatorics'.

[hildjj]

Yes, I think the second one is supposed to be lexicographically ordered.

[N8Brooks]

It's been a while ... but I found out part of the reason why it is so inefficient. This library bases all of their calculations on the index. All of the classes here have an nth method that returns the nth element. The efficiency of this depends on the specific subclass.

In some ways this is useful. Mostly when you need the nth element.

Unfortunately this is detrimental for efficiency. Unnecessarily inefficient. The nth method for Combination hides away what appears to be an r^3 computation where r is the size of the element. What takes length * r time for itertools take length * r^3 time for js-combinators where length is the number of elements in the entire iterator.

If you, or others, only need efficient iteration of combinatics I'd recommend a module I developed based on Python's itertools package. It's available for npm and deno. The itertools c implementations are only 33% faster than these implementations!

If you need additional calculations like nth, the length, or even some of the random functionality, this library may still be a good option.

[shahata]

This is indeed a big performance issue with this library, sadly even after several years it is not resolved... The performance was much better in version 0.6.1 as demonstrated here: https://github.com/shahata/combinatorics-perfromance

This respository demonstrates a huge performance degradation in js-cobinatorics library. It shows how long it takes to iterate through all of the combinations of selecting 3 items from a 200 items array.

To run the test simply do:

$ git clone git@github.com:shahata/combinatorics-perfromance.git
$ npm install
$ node index.js

The result will be something like:

Combinatorics 0.6.1: 392049900 (891ms)
Combinatorics 2.1.1: 392049900 (71531ms)

It shows how the exact same iteration takes under 1 seconds in version 0.6.1 vs more than a minute in version 2.1.1 Further testing I did shows that this performance issue exists ever since version 1.0.0 was released