Toggle navigation
MeasureThat.net
Create a benchmark
Tools
Feedback
FAQ
Register
Log In
Traverse Elements in DOM tree 3
(version: 0)
What's the fastest way to find all elements of a certain criteria within a DOM tree?
Comparing performance of:
Recursive traversal function vs Queue-based traversal function vs Array-based traversal function
Created:
3 years ago
by:
Guest
Jump to the latest result
HTML Preparation code:
<div id="traversal-root"> <div> <div> <div><div><div><div></div></div></div></div> <div><div><div><div></div></div></div></div> <div><div><div><section></section></div></div></div> </div> <div> <div><section><section><div></div></section></section></div> <div><div><div><div></div></div></div></div> <section><div><div><div></div></div></div></section> </div> <section> <div><div><div><div></div></div></div></div> <div><div><div><div></div></div></div></div> <div><div><div><div></div></div></div></div> </section> <div> <div><div><div><div></div></div></div></div> <div><div><div><div></div></div></div></div> <div><div><div><div></div></div></div></div> </div> </div> <div> <div> <div><div><section><div></div></section></div></div> <div><div><section><div></div></section></div></div> <div><div><div><div></div></div></div></div> </div> <div> <div><div><div><div></div></div></div></div> <div><div><div><div></div></div></div></div> <div><div><div><section></section></div></div></div> </div> <div> <div><div><div><div></div></div></div></div> <div><div><div><div></div></div></div></div> <div><div><div><div></div></div></div></div> </div> <section> <div><div><div><div></div></div></div></div> <div><div><div><div></div></div></div></div> <div><div><div><div></div></div></div></div> </section> </div> <section> <section> <section><section><section><section></section></section></section></section> <div><div><div><section></section></div></div></div> <div><section><div><div></div></div></section></div> </section> <section> <div><div><div><section></section></div></div></div> <div><div><div><section></section></div></div></div> <section><div><section><section></section></section></div></section> </section> <div> <div><div><div><section></section></div></div></div> <div><section><div><div></div></div></section></div> <section><div><div><div></div></div></div></section> </div> <div> <div><section><div><div></div></div></section></div> <div><div><div><section></section></div></div></div> <section><div><section><div></div></section></div></section> </div> </section> </div>
Script Preparation code:
class FastQueue { constructor() { this._array = new Array(16); this._length = 0; this._front = 0; } push(value) { const arr = this._array; if (arr.length === this._length) { arr.length *= 2; arrayMove(arr, this._length, this._front); } arr[(this._front + this._length++) & (arr.length - 1)] = value; } shift() { if (this._length === 0) return; const arr = this._array; const frontIndex = this._front; const ret = arr[frontIndex]; arr[frontIndex] = undefined; this._front = (frontIndex + 1) & (arr.length - 1); this._length -= 1; return ret; } } const arrayMove = (arr, moveBy, len) => { for (let i = 0; i < len; ++i) { arr[i + moveBy] = arr[i]; arr[i] = undefined; } }; window.symbol = Symbol('symbol'); window.traversalRoot = document.getElementById('traversal-root'); for (const el of traversalRoot.getElementsByTagName('section')) { Object.defineProperty(el, window.symbol, { value: {} }); } window.isMatch = function isMatch(element) { return element[symbol] !== undefined; } window.traverse = function traverse(element, callback) { if (isMatch(element)) { callback(element); } else if (element instanceof HTMLSlotElement && element.assignedNodes().length) { for (const child of element.assignedElements()) { traverse(child, callback); } } else { for (const child of element.children) { traverse(child, callback); } } }; window.traverseQueue = function traverseQueue(initialElement, callback) { const queue = new FastQueue(); queue.push(initialElement); let element; while (element = queue.shift()) { if (isMatch(element)) { callback(element); } else if (element instanceof HTMLSlotElement && element.assignedNodes().length) { for (const child of element.assignedElements()) { queue.push(child); } } else { for (const child of element.children) { queue.push(child); } } } }; window.traverseArray = function traverseArray(initialElement, callback) { const queue = []; queue.push(initialElement); let element; while (element = queue.shift()) { if (isMatch(element)) { callback(element); } else if (element instanceof HTMLSlotElement && element.assignedNodes().length) { for (const child of element.assignedElements()) { queue.push(child); } } else { for (const child of element.children) { queue.push(child); } } } };
Tests:
Recursive traversal function
const results = []; traverse(traversalRoot, function callback(element) { for (const child of element.children) { traverse(child, callback); } results.push(element); })
Queue-based traversal function
const results = []; traverseQueue(traversalRoot, function callback(element) { for (const child of element.children) { traverseQueue(child, callback); } results.push(element); })
Array-based traversal function
const results = []; traverseArray(traversalRoot, function callback(element) { for (const child of element.children) { traverseArray(child, callback); } results.push(element); })
Rendered benchmark preparation results:
Suite status:
<idle, ready to run>
Run tests (3)
Previous results
Fork
Test case name
Result
Recursive traversal function
Queue-based traversal function
Array-based traversal function
Fastest:
N/A
Slowest:
N/A
Latest run results:
No previous run results
This benchmark does not have any results yet. Be the first one
to run it!
Autogenerated LLM Summary
(model
llama3.2:3b
, generated one year ago):
I'll do my best to provide a solution. It seems like you have a large HTML document with nested `<div>` elements, and you want to traverse the DOM tree recursively using different algorithms (Recursive Traversal Function, Queue-Based Traversal Function, Array-Based Traversal Function). To solve this problem, I would suggest the following steps: 1. **Write a recursive function** that traverses the DOM tree using recursion. This function will take an element as input and call itself for each of its child elements. 2. **Implement the queue-based traversal function**, which uses a queue data structure to traverse the DOM tree. This function will also take an element as input and add it to the queue, then process all elements in the queue until it's empty. 3. **Implement the array-based traversal function**, which uses an array to store the elements to be traversed. This function will take an element as input, add it to the array, and then traverse all elements in the array using a loop. To write the actual code, I would need more information about the structure of your HTML document and the specific requirements for each traversal algorithm. However, here's some sample code to get you started: ```javascript // Recursive Traversal Function function traverseRecursive(element) { console.log(element); for (const child of element.children) { traverseRecursive(child); } } // Queue-Based Traversal Function function traverseQueue(element) { const queue = [element]; while (queue.length > 0) { const currentElement = queue.shift(); console.log(currentElement); for (const child of currentElement.children) { queue.push(child); } } } // Array-Based Traversal Function function traverseArray(element, array) { array.push(element); for (const child of element.children) { traverseArray(child, array); } } ``` Note that these are simplified examples and may not cover all edge cases. Additionally, the performance of each algorithm will depend on the specific structure of your HTML document. Please let me know if you'd like me to elaborate on any part of this solution or provide more code snippets!
Related benchmarks:
find vs findIndex (Array prototype methods)
find vs findindex with condition test
find vs findIndex (Array prototype methods) object
find vs indexOf (Array prototype methods)
find vs findIndex (Array prototype methods) 123123
Comments
Confirm delete:
Do you really want to delete benchmark?