Awesome
CXProduct
Very high-speed, low memory Cartesian cross-product as a first class object. Naive cross-products can rapidly consume vast amounts of memory and degrade exponentially in performance. Generator based approaches conserve RAM, but are not performant when non-sequential access is required. CXProduct
supports virtual Cartesian cross-product creation and use through the use of lazy evaluation, i.e. rows of the cross-product are not created until needed by calling functions.
CXPProduct
is between 10% and 10x faster than other libraries, depending on the size of the arrays you are combining.
Install
npm install cxproduct
Usage
import {CXProduct} from "cxproduct";
const cxproduct = new CXProduct([[1,2],[3,4]]); // [1,3],[1,4],[2,3],[2,4]
cxproduct.forEach((row,i) => console.log(i,row));
for(const row of new CXProduct([[1,2],[3,4]]).asGenerator()) {
console.log(row)
}
API
new CXProduct(arrayOfArrays,{cache}={})
- Creates a virtual Cartesian cross-product based on the arrays. A copy of the top level wrapping array is created, which means the contained arrays are not. This way they can be manipulated (added to, deleted from) by code outside the CXProduct
. If cache
is true, then all get
, has
, indexOf
will all cache results. DO NOT modify the arrays with an external program if caching is on unless you call flush()
each time you make a modification.
The following methods are supported:
cxproduct.asGenerator()
- Returns a generator equivalent of the CXProduct so you can use for(item of cxproduct.asGenerator())
. For convenience, the generator also has a length
property so you can use const iterable = cxproduct.asGenerator(); for(let i=0;i<iterable.length;i++)
cxproduct.asArrayLike()
- Returns a Proxy that behaves like an array of the CXProduct so you can use const arrayLike = cxproduct.asGnerator(); for(let i=0;i<arrayLike.length;i++)
cxproduct.add(array,...)
- Adds the array to the collection of arrays already associated with the CXProduct. Invalidates the cache, if any.
cxproduct.push(index,element)
- Adds the element to the array at the index in the collection of arrays associated with the CXProduct. Invalidates the cache, if any.
cxproduct.forEach(callback,{test,cache}={})
- Iterates over the CXProduct and invokes the callback for each row, optionally matching the row against a provided pattern or passing the provided boolean test. The callback takes the signature callback(row,index). The optional test
has the signature test(array)
and should return true or false. It is not recommended to loop through the CXProduct
using get and a counter. The access algorithms are different and the one under forEach
is optimized for forward moving access rather than random access.
cxproduct.get(index:number,{test:function,cache:boolean}={})
- Return row as array at index. Allocates memory for the row. Repeated calls will not return the same object. Unless cache===true
or the CXProduct
was created with the cache=true
option.
cxproduct.has(row:number,{cache:boolean}={})
- Returns true
if row
exists and false
otherwise.
cxproduct.indexOf(row:number,{cache}={})
- Return index where the row exists, returns -1 if row does not exist
cxproduct.intersection(cxproduct:CXProduct)
- Returns a new CXProduct
that is an intersection of the current CXProduct
with the one provided as an argument
cxproduct.verify(index:number,row:array,{cache:boolean}={})
- Verifies that the index still contains the row in case the arrays defining the CXProduct have changed.
Benchmarks
Using a sample size of 100 cycles and a timeout prr cycle of 2000ms:
- For a 3x3 matrix all tested approaches are within each others +/- range and order of results changes with each full run
- For a 5x5 matrix
CXProduct
is consistently more than 20% faster than its nearest competitorfast-cartesion
- For a 6x6 matrix
CXProduct
is more that 20% faster than both generator approaches,@anywhichway/cartesain-product
andbig-cartesian
. The@anywhichway/cartesain-product
Thenaive
andfast-cartesiona
both timeout. - For a 7x7 matrix
CXProduct
is the sole approach that does not timeout when iterating over all combinations. - For time to access a combination at a random location in all possible combinations,
CXProduct
is orders of magnitude faster than other solutions at scale.
Matrix sizes:
- 3x3 27
- 5x5 3,125
- 6x6 46,656
- 7x7 823,543
The naive and generator implementations of Cartesian product are below:
const naiveCartesian = (arrays) => arrays.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))),[]));
function* generatorCartesian([head, ...tail]) {
const remainder = tail.length > 0 ? generatorCartesian(tail) : [[]];
for (let r of remainder) for (let h of head) yield [h, ...r];
}
The generator version, with a slight enhancement to support the length
property, is available as @anywhichway/cartesian-product.
Basic | Ops/Sec | +/- |
---|---|---|
construct and loop 3x3 naive# | 10182 | 10.80% |
construct and loop 3x3 @anywhichway/cartesian-product | 11987 | 4.44% |
construct and loop 3x3 CXProduct# | 12285 | 2.77% |
construct and loop 3x3 fast-cartesian | 11824 | 9.06% |
construct and loop 3x3 big-cartesian | 10593 | 3.51% |
construct and loop 5x5 naive# | 261 | 1.73% |
construct and loop 5x5 @anywhichway/cartesian-product | 2879 | 0.49% |
construct and loop 5x5 CXProduct# | 8461 | 2.62% |
construct and loop 5x5 fast-cartesian | 6451 | 1.39% |
construct and loop 5x5 big-cartesian | 2099 | 20.63% |
construct and loop 6x6 naive# | Timeout | N/A |
construct and loop 6x6 @anywhichway/cartesian-product | 82 | 3.60% |
construct and loop 6x6 CXProduct# | 1004 | 0.52% |
construct and loop 6x6 fast-cartesian | Timeout | N/A |
construct and loop 6x6 big-cartesian | 84 | 2.86% |
construct and loop 7x7 CXProduct# | 132 | 1.08% |
construct and loop 7x7 @anywhichway/cartesian-product | Timeout | N/A |
construct and loop 7x7 big-cartesian | Timeout | N/A |
construct and random access 6x6 @anywhichway/cartesian-product | 102 | 19.86% |
construct and random access 6x6 CXProduct# | 5559 | 2.35% |
construct and random access 6x6 big-cartesian | 118 | 14.72% |
If you want similar performance for intersection, union, or memoizing also see:
-
https://github.com/anywhichway/nano-memoize
For a complete high performance solution to Cartesian product and set operations for Arrays and Sets with a standardized API, plus the addition of the standard map/reduce/find operations to Set see:
Bechmarks Explanation
A naive implementation of Cartesian is O(n) for access to the first combination. It computes the entire set of combinations and then returns the one at the index 0.
Although a generator implementation is fast for access to the first combination since it does not compute all possible combinations, it is O(n) for access to the last combination.
CXProduct
is O(1) for any specific combination when it is accessed by index; whereas generator functions are O(n), where n
is the index. This is useful if statistical sampling of the Cartesian product is required. For iterating over all combinations is CXProduct
is still O(n). However, the function that computes the combination at an index is faster than a generator function, so it still succeeds on a 7x7 matrix with a 2000ms timeout when a generator fails. For small products it seems to be about 10% faster. For large products it seems to be about 10x faster. I think this is because of garbage collection (see below).
Typically there will be higher performance variability with the generator functions. My hypothesis is this is because they are more likely to use RAM internally and the garbage collector may be invoked between the internal calls to .next()
. Since the CXProduct
implementation uses a simple arithmetic function it is unlikely to impact the garbage collector.
Building & Testing
Building, testing and quality assessment are conducted using Mocha, Chai, Istanbul, Benchtest, Code Climate, and Codacity.
Updates (reverse chronological order)
2023-04-27 v2.1.4 Documentation enhancements. Fixed potential bug in asGenerator()
now returns empty iterable if CXProduct
was created with a zero length array.
2023-02-23 v2.1.3 Documentation updates.
2023-02-15 v2.1.2 Documentation updates.
2023-02-13 v2.1.1 Documentation updates.
2023-02-11 v2.1.0 Added asGenerator
and asArrayLike
.
2023-02-11 v2.0.2 Updated documentation.
2023-02-06 v2.0.1 Updated docs. Added @anywhichway/cartesian-product
as a dev dependency.
2023-02-05 v2.0.0 Switched to module format. Updated performance tests to use benchtest 3.x
. Corrected issue with undocumented method intersection
. Added comparisons to fast-cartesian
and big-cartesian
.
2020-07-15 v1.0.0 Finally added unit and performance tests! Added caching. Calling interfaces changed to support caching. Added indexable
.
2020-07-14 v0.0.3 Updated documentation.
2020-06-07 v0.0.2 Updated documentation.
2016-03-30 v0.0.1 First public commit.
License
This software is provided as-is under the MIT license.
Credits
Credit to Gavin Kistner for the core code: http://phrogz.net/lazy-cartesian-product