dfs implicit vs explicit (v2)

Revision 2 of this benchmark created on May 10, 2024

Setup

const Node = (name)=>({name, children:[], push(...args){this.children.push(...args)}});
const root = Node("root");
const a = Node("a");
const b = Node("b");
const c = Node("c");
const d = Node("d");
const e = Node("e");
const f = Node("f");
const g = Node("g");
const h = Node("h");
root.push(a);
root.push(b);
a.push(c);
a.push(d);
d.push(e);
d.push(f);
e.push(g);
b.push(h);

function dfsExplicit(node, func) {
  const stack = [[0,[node]]];
  const NEXT_INDEX = 0;
  const CHILDREN = 1;
  while (stack.length > 0) {
      const lastDepth = stack[stack.length-1];
      const nextIndex = lastDepth[NEXT_INDEX];
      const children = lastDepth[CHILDREN];
      if (nextIndex === children.length) {
          stack.pop();
          continue;
      }
      const currentNode = children[nextIndex];
      func(currentNode);
      if (currentNode.children.length > 0) {
          stack.push([0, currentNode.children]);
      }
      lastDepth[NEXT_INDEX] += 1;
  }
}

function dfsImplicit(node, func) {
    func(node);
    for (let i = 0; i < node.children.length; i++) {
        dfsImplicit(node.children[i], func); 
    }
}


class Stack {
  constructor() {
    this.head = null;
    this.stackSize = 0;
  }

  push(children) {
    const newNode = {
      nextIndex: 0, 
      children,
      next: this.head
    };
    this.head = newNode;
    this.stackSize++;
  }

  pop() {
    const value = this.head;
    this.head = this.head.next;
    this.stackSize--;
    return value;
  }
}

function dfsExplicitStack(node, func, Stack) {
  const stack = new Stack();
  stack.push([node]);

  while (stack.head) {
    const depth = stack.head;
    const nextIndex = depth.nextIndex;
    const children = depth.children;
    if (nextIndex === children.length) {
      stack.pop();
      continue;
    }
    const currentNode = children[nextIndex];
    func(currentNode);
    if (currentNode.children.length > 0) {
      stack.push(currentNode.children);
    }
    depth.nextIndex += 1;
  }
}

Test runner

dfsExplicit(root,()=>{});

dfsImplicit(root,()=>{});

dfsExplicitStack(root, ()=>{}, Stack);

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published on May 10, 2024
• Revision 2: published on May 10, 2024