Comments (7)
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.
Related Issues (20)
- C function return "float" number HOT 2
- Use native generators instead of custom iteration methods HOT 2
- Typescript support HOT 4
- v1.2.x does not work with native Node.js ESM HOT 5
- Please add a changelog
- Wrong combinations HOT 1
- Move to ES6 breaks node compatability HOT 4
- Combination: unexpected behavior when r > n HOT 1
- Deleted
- SyntaxError: Unexpected token 'export' HOT 11
- Question: Unexpected token 'export' using Babel HOT 4
- unexpected token 'export' while using ts-node. HOT 1
- SyntaxError: The requested module 'js-combinatorics' is a CommonJS module HOT 1
- Combination with 2D Array Seed Produces Flatten/Concatenated Output HOT 1
- bitwiseIterator not working for some numbers HOT 2
- SyntaxError: Unexpected token 'export' in NextJS HOT 1
- Doesn't work on esm? HOT 1
- Rollup: Missing Export: 'BaseN' is not exported by "file" HOT 1
- Small bug: BaseN not allocating proper size HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from js-combinatorics.