I love using map and filter on arrays. I think it makes iterating over data, conceptually, a lot simpler. But I am always wanting to know clever tricks to improve performance or reduce memory usage. When I learned that python had lazy evaluation I wanted to know how does the performance compare to javascript’s built-in map-filter-reduce functions.
To spoil the conclusion before the code: My lazy evaluation does not outperform the built-ins that javascript has. That doesn’t mean that these lazy evaluators are useless though. Lazy evaluation has the benefit that it can be used on infinite data! It also (more usefully) can be used on streamed data.
function* lazy_map (func) {
for (const element of this) {
yield func(element)
}
}
function* lazy_filter (func) {
for (const element of this) {
if(func(element)){
yield element;
}
}
}
function collect () {
const arr = [];
for (const element of this){
arr.push(element);
}
return arr;
}
function random_from () {
const index = Math.floor(this.length * Math.random());
return this[index];
}
Object.entries({ lazy_map, lazy_filter, collect, random_from })
.forEach(([key, value]) => {
Array.prototype[key] = value;
Object.getPrototypeOf(function*(){}).prototype[key] = value;
});
const maps = [
x => x + 1,
x => -1 * x,
x => 2 * x,
x => x / 2,
x => x * x,
x => 10 * Math.cos(x),
x => 10 * Math.abs(Math.sin(x)),
x => x / 3,
x => Math.floor(x),
x => parseInt((x.toString().split('.').slice(1)[0] || '').substring(0, 3), 10) || 0
];
const filters = [
x => x !== 0,
x => (x % 2) === 0,
x => (x % 3) === 0,
x => (x % 3) === 1,
x => Math.abs(x) === x,
x => Math.floor(x) === x,
x => x <= 0,
x => x.toString() === x.toString().split('').reverse().join('')
];
function random_number () {
const rand = () => Math.floor(100 * (Math.random() - 0.5));
const numerator = rand() + rand();
const denominator = rand() + rand();
return denominator !== 0 ? (numerator / denominator) : 0
}
function random_operation () {
const min_length = 2;
const max_length = 7;
const random_length = min_length + Math.floor((max_length - min_length + 1) * Math.random());
const random_selection = Math.floor(Math.pow(2, random_length) * Math.random());
const signature = random_selection
.toString(2)
.padStart(random_length, '0');
const random_pattern = signature
.split('')
.map(e => e === '0'
? ['map', maps.random_from()]
: ['filter', filters.random_from()])
return { random_pattern, signature };
}
function perform_test (size) {
const { random_pattern, signature } = random_operation();
const values = new Array(size)
.fill(0)
.map(e => random_number());
// Time the lazy_* functions
const lazy_start = performance.now();
let a = values;
for (const [type, func] of random_pattern) {
a = (type === 'map')
? a.lazy_map(func)
: a.lazy_filter(func);
}
a = a.collect()
const lazy_end = performance.now();
// Time the regular functions
const regular_start = performance.now();
let b = values;
for (const [type, func] of random_pattern) {
b = (type === 'map')
? b.map(func)
: b.filter(func);
}
const regular_end = performance.now();
// Verify arrays are the same
const panic_string = 'Functions didn\'t perform the same!';
if (a.length !== b.length) {
throw new Error(panic_string)
}
for (let i = 0; i < a.length; a++) {
if (a[i] !== b[i]) {
throw new Error(panic_string)
}
}
return {
lazy: lazy_end - lazy_start,
regular: regular_end - regular_start,
signature
}
}
const num_tests = 10000;
const all_test_totals = [];
for (let i = 0; i < num_tests; i++) {
const size = 10000 * (1 + Math.floor(20 * Math.random()));
const results = perform_test(size);
results.size = size;
all_test_totals.push(results);
if (i % 100 === 0) {
console.log(`Completed test ${i}`);
}
}
console.log();
const different_sizes = Array.from(new Set(all_test_totals.map(e => e.size)))
.sort((a, b) => a - b);
for (const size of different_sizes) {
const items = all_test_totals.filter(e => e.size === size);
const final = items
.reduce((acc, e) => {
acc.lazy = acc.lazy + e.lazy;
acc.regular = acc.regular + e.regular;
return acc;
}, {lazy: 0, regular: 0});
const round = x => Math.floor(x * 10000) / 10000;
console.log(`Statistics for size of ${size} (n = ${items.length})`);
console.log(`Final lazy average of ${round(final.lazy / items.length)}`)
console.log(`Final regular average of ${round(final.regular / items.length)}`)
console.log('');
}Statistics for size of 10000 (n = 480)
Final lazy average of 2.1229
Final regular average of 1.5511
Statistics for size of 20000 (n = 550)
Final lazy average of 4.0771
Final regular average of 3.1854
Statistics for size of 30000 (n = 503)
Final lazy average of 6.5147
Final regular average of 5.0976
Statistics for size of 40000 (n = 467)
Final lazy average of 7.6646
Final regular average of 5.8899
Statistics for size of 50000 (n = 505)
Final lazy average of 9.3492
Final regular average of 7.2016
Statistics for size of 60000 (n = 461)
Final lazy average of 13.458
Final regular average of 10.7486
Statistics for size of 70000 (n = 526)
Final lazy average of 15.4366
Final regular average of 12.3929
Statistics for size of 80000 (n = 495)
Final lazy average of 16.4056
Final regular average of 13.2401
Statistics for size of 90000 (n = 477)
Final lazy average of 18.2124
Final regular average of 14.5482
Statistics for size of 100000 (n = 502)
Final lazy average of 20.2959
Final regular average of 16.5047
Statistics for size of 110000 (n = 471)
Final lazy average of 22.8225
Final regular average of 17.947
Statistics for size of 120000 (n = 520)
Final lazy average of 25.6252
Final regular average of 20.3387
Statistics for size of 130000 (n = 511)
Final lazy average of 27.9891
Final regular average of 22.2645
Statistics for size of 140000 (n = 490)
Final lazy average of 28.1774
Final regular average of 22.1686
Statistics for size of 150000 (n = 521)
Final lazy average of 27.8976
Final regular average of 22.5158
Statistics for size of 160000 (n = 486)
Final lazy average of 35.2152
Final regular average of 28.541
Statistics for size of 170000 (n = 489)
Final lazy average of 36.9335
Final regular average of 29.7045
Statistics for size of 180000 (n = 540)
Final lazy average of 36.7676
Final regular average of 29.7667
Statistics for size of 190000 (n = 491)
Final lazy average of 41.1355
Final regular average of 33.8442
Statistics for size of 200000 (n = 515)
Final lazy average of 38.1015
Final regular average of 31.1814