Cartesian Generator
Produce cartesian product using generator.
Motivation
You can produce cartesian product in a single-line code. such as:
const cartesian = (...args) => args.reduce((acc, cur) => acc.flatMap((x) => cur.map((y) => x.concat([y]))), [[],]);
cartesian([1, 2], [3, 4]) // => [[1,3], [1,4], [2,3], [2,4]]
Although this is concise and easy to copy&paste, this functional-way has some problems.
This way...
- uses so much memory, because cartesian product increase exponentially. This may cause memory leak.
- needs time to produce entire result beforehand.
- causes unnecessary computation, especially you want to find certain tuple(element of cartesian product) that matches your demand. Because this way produces entire result beforehand
That's why I implemented cartesian product
with generator.Generator produces next tuple when it is necessary.
How to use
yarn add cartesian-generator
or simply paste following code.
export function* cartesian(
...args: number[][]
): Generator<number[], void, undefined> {
if (args.length === 0) yield [];
else {
const [head, ...rest] = args;
for (const h of head) {
const restIter = cartesian(...rest);
for (const r of restIter) {
yield [h, ...r];
}
}
}
}
To use:
import { cartesian } from "cartesian-generator";
const prod = cartesian([1, 2], [3, 4]);
for (const p of prod){
console.log(p) // [1,3], [1,4], [2,3], [2,4]
}
Benchmark
function version
vs generator version
(this package).
I tested these two ways with 7 arguments that contains 10 elements, so length of cartesian product is 10^7.You can see code at bench.js
.
version | time(ms) |
---|---|
function | 6862 |
generator | 5950 |
14% faster!!
When I tried bench with more arguments, function version caused memory leak, unlike generator.