Skip to content

anywhichway/cxproduct

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

16 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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.

Maintainability

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 competitor fast-cartesion
  • For a 6x6 matrix CXProduct is more that 20% faster than both generator approaches, @anywhichway/cartesain-product and big-cartesian. The @anywhichway/cartesain-product The naive and fast-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:

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

About

Cartesian cross-product as a first class object.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published