js factorial benchmark

JSFB.js

function factorialByLoop(number) {
  let num = 1n;
  for (let i = 0; i < number; i++) {
    num *= BigInt(number - i);
  }
  return num;
}

function factorialByReversedArray(number) {
  const arr = new Array();
  for (let i = number; i >= 0; i--) arr.push(BigInt(i == 0 ? 1 : i));
  while (arr.length > 1) {
    arr.push(arr.pop() * arr.pop());
  }
  return arr.pop();
}

function factorialByArray(number) {
  const arr = new Array();
  for (let i = 0; i <= number; i++) arr.push(BigInt(i == 0 ? 1 : i));
  while (arr.length > 1) {
    arr.push(arr.pop() * arr.pop());
  }
  return arr.pop();
}

function factorialByMinHeap(number) {
  const heap = new MinHeap();
  for (let i = 0; i <= number; i++) heap.insert(BigInt(i == 0 ? 1 : i));
  while (heap.heap.length > 1) {
    heap.insert(heap.remove() * heap.remove());
  }
  return heap.remove();
}

function factorialByMaxHeap(number) {
  const heap = new MaxHeap();
  for (let i = 0; i <= number; i++) heap.insert(BigInt(i == 0 ? 1 : i));
  while (heap.heap.length > 1) {
    heap.insert(heap.remove() * heap.remove());
  }
  return heap.remove();
}

function factorialByLoopWithOptionalBigInt(number) {
  let num = 1;
  for (let i = 1; i <= number; i++) {
    num =
      typeof num === "bigint"
        ? num * BigInt(i)
        : num * i < Math.MAX_SAFE_INTEGER
        ? num * i
        : BigInt(num) * BigInt(i);
  }
  return num;
}

function factorialByReversedArrayWithOptionalBigInt(number) {
  const arr = new Array();
  for (let i = number; i > 0; i--) arr.push(i);
  arr.push(1);
  while (arr.length > 1) {
    const a = arr.pop();
    const b = arr.pop();
    const a1 = typeof a === "bigint" || typeof b !== "bigint" ? a : BigInt(a);
    const b1 = typeof b === "bigint" || typeof a !== "bigint" ? b : BigInt(b);
    const res = a1 * b1;

    if (typeof res == "bigint") arr.push(res);
    else if (res < Number.MAX_SAFE_INTEGER) arr.push(res);
    else arr.push(BigInt(a1) * BigInt(b1));
  }
  return arr.pop();
}

function factorialByArrayWithOptionalBigInt(number) {
  const arr = new Array();
  arr.push(1);
  for (let i = 0; i <= number; i++) arr.push(i);
  while (arr.length > 1) {
    const a = arr.pop();
    const b = arr.pop();
    const a1 = typeof a === "bigint" || typeof b !== "bigint" ? a : BigInt(a);
    const b1 = typeof b === "bigint" || typeof a !== "bigint" ? b : BigInt(b);
    const res = a1 * b1;

    if (typeof res == "bigint") arr.push(res);
    else if (res < Number.MAX_SAFE_INTEGER) arr.push(res);
    else arr.push(BigInt(a1) * BigInt(b1));
  }
  return arr.pop();
}
function factorialByMinHeapWithOptionalBigInt(number) {
  const heap = new MinHeap();
  heap.insert(1);
  for (let i = 1; i <= number; i++) heap.insert(i);
  while (heap.heap.length > 1) {
    const a = heap.remove();
    const b = heap.remove();
    const a1 = typeof a === "bigint" || typeof b !== "bigint" ? a : BigInt(a);
    const b1 = typeof b === "bigint" || typeof a !== "bigint" ? b : BigInt(b);
    const res = a1 * b1;

    if (typeof res == "bigint") heap.insert(res);
    else if (res < Number.MAX_SAFE_INTEGER) heap.insert(res);
    else heap.insert(BigInt(a1) * BigInt(b1));
  }
  return heap.remove();
}

function factorialByMaxHeapWithOptionalBigInt(number) {
  const heap = new MaxHeap();
  heap.insert(1);
  for (let i = 1; i <= number; i++) heap.insert(i);
  while (heap.heap.length > 1) {
    const a = heap.remove();
    const b = heap.remove();
    const a1 = typeof a === "bigint" || typeof b !== "bigint" ? a : BigInt(a);
    const b1 = typeof b === "bigint" || typeof a !== "bigint" ? b : BigInt(b);

    const res = a1 * b1;
    if (typeof res == "bigint") heap.insert(res);
    else if (res < Number.MAX_SAFE_INTEGER) heap.insert(res);
    else heap.insert(BigInt(a1) * BigInt(b1));
  }
  return heap.remove();
}

class MinHeap {
  /** @type Array<{ data: number }> */
  heap = [];

  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

  peek = () => this.heap[0];

  insert = (data) => {
    const node = { data };
    this.heap.push(node);
    this.heapifyUp(); // 배열에 가장 끝에 넣고, 다시 min heap 의 형태를 갖추도록 한다.
  };

  // 최근에 삽입된 노드가 제 자리를 찾아갈 수 있도록 하는 메소드
  heapifyUp = () => {
    let index = this.heap.length - 1; // 계속해서 변하는 index 값
    const lastInsertedNode = this.heap[index];

    // 루트노드가 되기 전까지
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);

      // 부모 노드의 data 값이 마지막에 삽입된 노드의 키 값 보다 크다면
      // 부모의 자리를 계속해서 아래로 내린다.
      if (this.heap[parentIndex].data > lastInsertedNode.data) {
        this.heap[index] = this.heap[parentIndex];
        index = parentIndex;
      } else break;
    }

    // break 를 만나서 자신의 자리를 찾은 상황
    // 마지막에 찾아진 곳이 가장 나중에 들어온 노드가 들어갈 자리다.
    this.heap[index] = lastInsertedNode;
  };

  remove = () => {
    const count = this.heap.length;
    const rootNode = this.heap[0];

    if (count <= 0) return undefined;
    if (count === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop(); // 끝에 있는 노드를 부모로 만들고
      this.heapifyDown(); // 다시 min heap 의 형태를 갖추도록 한다.
    }

    return rootNode.data;
  };

  // 변경된 루트노드가 제 자리를 찾아가도록 하는 메소드
  heapifyDown = () => {
    let index = 0;
    const count = this.heap.length;
    const rootNode = this.heap[index];

    // 계속해서 left child 가 있을 때 까지 검사한다.
    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      // 왼쪽, 오른쪽 중에 더 작은 노드를 찾는다
      // rightChild 가 있다면 data의 값을 비교해서 더 작은 값을 찾는다.
      // 없다면 leftChild 가 더 작은 값을 가지는 인덱스가 된다.
      const smallerChildIndex =
        rightChildIndex < count &&
        this.heap[rightChildIndex].data < this.heap[leftChildIndex].data
          ? rightChildIndex
          : leftChildIndex;

      // 자식 노드의 키 값이 루트노드보다 작다면 위로 끌어올린다.
      if (this.heap[smallerChildIndex].data <= rootNode.data) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
      } else break;
    }

    this.heap[index] = rootNode;
  };
}

class MaxHeap {
  /** @type Array<{ data: number }> */
  heap = [];

  getLeftChildIndex = (parentIndex) => parentIndex * 2 + 1;
  getRightChildIndex = (parentIndex) => parentIndex * 2 + 2;
  getParentIndex = (childIndex) => Math.floor((childIndex - 1) / 2);

  peek = () => this.heap[0];

  insert = (data) => {
    const node = { data };
    this.heap.push(node);
    this.heapifyUp(); // 배열에 가장 끝에 넣고, 다시 max heap 의 형태를 갖추도록 한다.
  };

  // 최근에 삽입된 노드가 제 자리를 찾아갈 수 있도록 하는 메소드
  heapifyUp = () => {
    let index = this.heap.length - 1; // 계속해서 변하는 index 값
    const lastInsertedNode = this.heap[index];

    // 루트노드가 되기 전까지
    while (index > 0) {
      const parentIndex = this.getParentIndex(index);

      // 부모 노드의 data 값이 마지막에 삽입된 노드의 키 값 보다 작다면
      // 부모의 자리를 계속해서 아래로 내린다.
      if (this.heap[parentIndex].data < lastInsertedNode.data) {
        this.heap[index] = this.heap[parentIndex];
        index = parentIndex;
      } else break;
    }

    // break 를 만나서 자신의 자리를 찾은 상황
    // 마지막에 찾아진 곳이 가장 나중에 들어온 노드가 들어갈 자리다.
    this.heap[index] = lastInsertedNode;
  };

  remove = () => {
    const count = this.heap.length;
    const rootNode = this.heap[0];

    if (count <= 0) return undefined;
    if (count === 1) this.heap = [];
    else {
      this.heap[0] = this.heap.pop(); // 끝에 있는 노드를 부모로 만들고
      this.heapifyDown(); // 다시 max heap 의 형태를 갖추도록 한다.
    }

    return rootNode.data;
  };

  // 변경된 루트노드가 제 자리를 찾아가도록 하는 메소드
  heapifyDown = () => {
    let index = 0;
    const count = this.heap.length;
    const rootNode = this.heap[index];

    // 계속해서 left child 가 있을 때 까지 검사한다.
    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index);
      const rightChildIndex = this.getRightChildIndex(index);

      // 왼쪽, 오른쪽 중에 더 큰 노드를 찾는다
      // rightChild 가 있다면 data의 값을 비교해서 더 큰 값을 찾는다.
      // 없다면 leftChild 가 더 큰 값을 가지는 인덱스가 된다.
      const smallerChildIndex =
        rightChildIndex < count &&
        this.heap[rightChildIndex].data > this.heap[leftChildIndex].data
          ? rightChildIndex
          : leftChildIndex;

      // 자식 노드의 키 값이 루트노드보다 크다면 위로 끌어올린다.
      if (this.heap[smallerChildIndex].data >= rootNode.data) {
        this.heap[index] = this.heap[smallerChildIndex];
        index = smallerChildIndex;
      } else break;
    }

    this.heap[index] = rootNode;
  };
}

function test(N) {
  console.log(`\n\ntesting with N = ${N}`);
  console.time("factorialByLoop done");
  factorialByLoop(N);
  console.timeEnd("factorialByLoop done");
  console.time("factorialByArray done");
  factorialByArray(N);
  console.timeEnd("factorialByArray done");
  console.time("factorialByReversedArray done");
  factorialByReversedArray(N);
  console.timeEnd("factorialByReversedArray done");
  console.time("factorialByMinHeap done");
  factorialByMinHeap(N);
  console.timeEnd("factorialByMinHeap done");
  console.time("factorialByMaxHeap done");
  factorialByMaxHeap(N);
  console.timeEnd("factorialByMaxHeap done");
}

function optionalBigIntTest(N) {
  console.log(`\n\ntesting with N = ${N}`);
  console.time("factorialByLoopWithOptionalBigInt done");
  factorialByLoopWithOptionalBigInt(N);
  console.timeEnd("factorialByLoopWithOptionalBigInt done");
  console.time("factorialByArrayWithOptionalBigInt done");
  factorialByArrayWithOptionalBigInt(N);
  console.timeEnd("factorialByArrayWithOptionalBigInt done");
  console.time("factorialByReversedArrayWithOptionalBigInt done");
  factorialByReversedArrayWithOptionalBigInt(N);
  console.timeEnd("factorialByReversedArrayWithOptionalBigInt done");
  console.time("factorialByMinHeapWithOptionalBigInt done");
  factorialByMinHeapWithOptionalBigInt(N);
  console.timeEnd("factorialByMinHeapWithOptionalBigInt done");
  console.time("factorialByMaxHeapWithOptionalBigInt done");
  factorialByMaxHeapWithOptionalBigInt(N);
  console.timeEnd("factorialByMaxHeapWithOptionalBigInt done");
}

function mixTest(N) {
  console.time(`testing with N = ${N} ...done`);
  factorialMix(N);
  console.timeEnd(`testing with N = ${N} ...done`);
}

const lut = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800];
function factorialMix(number) {
  if (number <= 10) return lut[number];
  else if (number < 500) return factorialByLoopWithOptionalBigInt(number);
  else if (number < 1000) return factorialByReversedArray(number);
  else if (number < 10000)
    return factorialByReversedArrayWithOptionalBigInt(number);
  else return factorialByMinHeapWithOptionalBigInt(number);
}

for (let i = 0; i < 5; i++) {
  mixTest(Math.pow(10, i));
}

for (let i = 2; i <= 10; i++) {
  mixTest(i * 10000);
}