efficient chain-methods for array (lazy iteration)

_Lazy_Iteration_Chain.md

Efficient chain-methods for array (lazy iteration)

Why I made this

People like to use chain methods like .map, but these are sometimes not efficient. I just made a program that iterates using lazy approach.

• The result array is evaluated only at the end of chains (with .collect method)
• The difference is that the native method creates every single result arrays for each chain process.
• There is no full compatibility with the native methods.

After I took benchmark, I noticed that:

• native .map is more performant when the size of an array is small.
• my .map is more performant when the size of an array is very big.

usage:

import { chain } from 'chain.ts'

chain([-10,200,3,400,-50])
  .map(v=> v*2 - 30)
  .filter(v => v > 0)
  .map(v=>`yaay ${v}`)
  .collect()

You don't need to call .collect() if you call forEach, some, or find at the end of the chain.

chain.ts

export const chain = <I>(list: Array<I>) => {
  const it = list[Symbol.iterator]()
  return new M(() => it.next())
}
class M<O> {
  constructor(public next: () => IteratorResult<O>) {}

  map<T>(f: (value: O) => T): M<T> {
    return new M(() => {
      const result = this.next()
      /* @ts-ignore */
      if (!result.done) result.value = f(result.value)
      return (result as unknown as IteratorResult<T>)
    })
  }
  filter(f: (value: O) => boolean): M<O> {
    return new M(() => {
      while (true) {
        const result = this.next()
        if (result.done) {
          return result
        } else {
          if (f(result.value)) return result
        }
      }
    })
  }
  every(f: (value: O) => unknown): boolean {
    while (true) {
      const { done, value } = this.next()
      if (done) return true
      if (!f(value)) return false
    }
  }
  some(f: (value: O) => unknown): boolean {
    while (true) {
      const { done, value } = this.next()
      if (done) return false
      if (f(value)) return true
    }
  }
  forEach(f: (value: O, index: number) => any) {
    let index = 0
    while (true) {
      const { done, value } = this.next()
      if (done) return
      f(value, index++)
    }
  }
  find(f: (value: O, index: number) => boolean): O | undefined {
    let index = 0
    while (true) {
      const { done, value } = this.next()
      if (done) return
      if (f(value, index)) return value
      index++
    }
  }
  reduce(f: (previousValue: O, currentValue: O) => O, initialValue: O): O {
    let acc = initialValue
    while (true) {
      const { done, value } = this.next()
      if (done) return acc
      acc = f(acc, value)
    }
  }
  collect() {
    return [...this]
  }
  [Symbol.iterator]() {
    return this
  }
}

tbench.ts

import { chain } from 'chain.ts'

const LENGTH_ARRAY = 10**7.5, RANGE = 1000, NUM_TRIAL = 3
const list: number[] = []
const { random } = Math
const { log, error, table } = console

const measure = <T>(task: () => T, trial: number) => {
  const data: {
    time: number,
    result?: T
  } = {
    time: 0,
    result: undefined
  }
  let sum_time = 0
  for (let i = 0; i < trial; i++) {
    const t0 = performance.now()
    data.result ??= task()
    const t1 = performance.now()
    sum_time += t1 - t0
  }
  
  data.time = sum_time / trial
  return data as {
    time: number,
    result: T
  }
}

log("* creating a list of random numbers")
for (let i = 0; i < LENGTH_ARRAY; i++) {
  list.push(((random() * RANGE * 2) | 0) - RANGE)
}
log("...list created")
log("* measuring performance")

const { result: chain_result, time: chain_time } = measure(() =>
  chain(list)
    .filter(i => i > 1)
    .map(i => i * 2)
    .map(i => ({
      name: `ohyo-${i}`,
      age: i
    }))
    .map(i => parseInt(i.name.substring(5)))
    .collect(),
  NUM_TRIAL)
const { result: native_result, time: native_time } = measure(() =>
  list
    .filter(i => i > 1)
    .map(i => i * 2)
    .map(i => ({
      name: `ohyo-${i}`,
      age: i
    }))
    .map(i => parseInt(i.name.substring(5))),
  NUM_TRIAL)

log("* comparing results")

const different_answer = chain_result.find((v, i) => v !== native_result[i])
if (different_answer) error("...found a different answer. your implementation sucks")
else log("...results are the same")

log("* benchmarking")
table({
  "chain": {
    "time (ms)": chain_time,
  },
  "native": {
    "time (ms)": native_time
  }
})