CXProduct
Very highspeed, low memory Cartesian crossproduct as a first class object. Naive crossproducts can rapidly consume vast amounts of memory and degrade exponentially in performance. Generator based approaches conserve RAM, but are not performant when nonsequential access is required. CXProduct
supports virtual Cartesian crossproduct creation and use through the use of lazy evaluation, i.e. rows of the crossproduct 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 crossproduct 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 competitorfastcartesion
 For a 6x6 matrix
CXProduct
is more that 20% faster than both generator approaches,@anywhichway/cartesainproduct
andbigcartesian
. The@anywhichway/cartesainproduct
Thenaive
andfastcartesiona
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/cartesianproduct.
Basic  Ops/Sec  +/ 

construct and loop 3x3 naive#  10182  10.80% 
construct and loop 3x3 @anywhichway/cartesianproduct  11987  4.44% 
construct and loop 3x3 CXProduct#  12285  2.77% 
construct and loop 3x3 fastcartesian  11824  9.06% 
construct and loop 3x3 bigcartesian  10593  3.51% 
construct and loop 5x5 naive#  261  1.73% 
construct and loop 5x5 @anywhichway/cartesianproduct  2879  0.49% 
construct and loop 5x5 CXProduct#  8461  2.62% 
construct and loop 5x5 fastcartesian  6451  1.39% 
construct and loop 5x5 bigcartesian  2099  20.63% 
construct and loop 6x6 naive#  Timeout  N/A 
construct and loop 6x6 @anywhichway/cartesianproduct  82  3.60% 
construct and loop 6x6 CXProduct#  1004  0.52% 
construct and loop 6x6 fastcartesian  Timeout  N/A 
construct and loop 6x6 bigcartesian  84  2.86% 
construct and loop 7x7 CXProduct#  132  1.08% 
construct and loop 7x7 @anywhichway/cartesianproduct  Timeout  N/A 
construct and loop 7x7 bigcartesian  Timeout  N/A 
construct and random access 6x6 @anywhichway/cartesianproduct  102  19.86% 
construct and random access 6x6 CXProduct#  5559  2.35% 
construct and random access 6x6 bigcartesian  118  14.72% 
If you want similar performance for intersection, union, or memoizing also see:

https://github.com/anywhichway/nanomemoize
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)
20230427 v2.1.4 Documentation enhancements. Fixed potential bug in asGenerator()
now returns empty iterable if CXProduct
was created with a zero length array.
20230223 v2.1.3 Documentation updates.
20230215 v2.1.2 Documentation updates.
20230213 v2.1.1 Documentation updates.
20230211 v2.1.0 Added asGenerator
and asArrayLike
.
20230211 v2.0.2 Updated documentation.
20230206 v2.0.1 Updated docs. Added @anywhichway/cartesianproduct
as a dev dependency.
20230205 v2.0.0 Switched to module format. Updated performance tests to use benchtest 3.x
. Corrected issue with undocumented method intersection
. Added comparisons to fastcartesian
and bigcartesian
.
20200715 v1.0.0 Finally added unit and performance tests! Added caching. Calling interfaces changed to support caching. Added indexable
.
20200714 v0.0.3 Updated documentation.
20200607 v0.0.2 Updated documentation.
20160330 v0.0.1 First public commit.
License
This software is provided asis under the MIT license.
Credits
Credit to Gavin Kistner for the core code: http://phrogz.net/lazycartesianproduct