Performance of Combination about js-combinatorics HOT 7 OPEN

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.

from js-combinatorics.

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

from js-combinatorics.

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.

from js-combinatorics.

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

from js-combinatorics.

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'.

from js-combinatorics.

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

from js-combinatorics.

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 [email protected]: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

from js-combinatorics.