Fastest way to find the index of a child node in parent

Question

I want to find the index of the child div that has the id 'whereami'.

<div id="parent">
   <div></div>
   <div></div>
   <div id="whereami"></div>
   <div></div>
</div>

Currently I am using this function to find the index of the child.

function findRow(node){
    var i=1;
    while(node.previousSibling){
        node = node.previousSibling;
        if(node.nodeType === 1){
            i++;
        }
    }
    return i; //Returns 3
}

var node = document.getElementById('whereami'); //div node to find
var index = findRow(node);

fiddle: http://jsfiddle.net/grantk/F7JpH/2/

The Problem
When there are a thousands of div nodes, the while loop has to traverse through each div to count them. Which can take a while.

Is there any faster way to tackle this?

*Note that the id will change to different divs node, so it will need to be able to re-calculate.

Answer 1

Year 2020 - A solution if you're using Tables - Clean Vanilla JS approach

Credit goes to: Alain Cruz

Source: https://stackoverflow.com/a/58845058/3626361 (leave him an Up vote if it helped you)

Question: How to return the row and column index of a table cell by clicking?

const cells = document.querySelectorAll('td');
cells.forEach(cell => {
  cell.addEventListener('click', () =>
    console.log("Row index: " + cell.closest('tr').rowIndex + " | Column index: " + cell.cellIndex));
});

<table>
  <tr>
    <td>0:0</td>
    <td>0:1</td>
    <td>0:2</td>
    <td>0:3</td>
  </tr>
  <tr>
    <td>1:0</td>
    <td>1:1</td>
    <td>1:2</td>
    <td>1:3</td>
  </tr>
  <tr>
    <td>2:0</td>
    <td>2:1</td>
    <td>2:2</td>
    <td>2:3</td>
  </tr>
</table>

Cheers! Stefano

Answer 2

I hypothesise that given an element where all of its children are ordered on the document sequentially, the fastest way should be to to do a binary search, comparing the document positions of the elements. However, as introduced in the conclusion the hypothesis is rejected. The more elements you have, the greater the potential for performance. For example, if you had 256 elements, then (optimally) you would only need to check just 16 of them! For 65536, only 256! The performance grows to the power of 2! See more numbers/statistics. Visit Wikipedia

(function(constructor){
   'use strict';
    Object.defineProperty(constructor.prototype, 'parentIndex', {
      get: function() {
        var searchParent = this.parentElement;
        if (!searchParent) return -1;
        var searchArray = searchParent.children,
            thisOffset = this.offsetTop,
            stop = searchArray.length,
            p = 0,
            delta = 0;

        while (searchArray[p] !== this) {
            if (searchArray[p] > this)
                stop = p + 1, p -= delta;
            delta = (stop - p) >>> 1;
            p += delta;
        }

        return p;
      }
    });
})(window.Element || Node);

Then, the way that you use it is by getting the 'parentIndex' property of any element. For example, check out the following demo.

(function(constructor){
   'use strict';
    Object.defineProperty(constructor.prototype, 'parentIndex', {
      get: function() {
        var searchParent = this.parentNode;
        if (searchParent === null) return -1;
        var childElements = searchParent.children,
            lo = -1, mi, hi = childElements.length;
        while (1 + lo !== hi) {
            mi = (hi + lo) >> 1;
            if (!(this.compareDocumentPosition(childElements[mi]) & 0x2)) {
                hi = mi;
                continue;
            }
            lo = mi;
        }
        return childElements[hi] === this ? hi : -1;
      }
    });
})(window.Element || Node);

output.textContent = document.body.parentIndex;
output2.textContent = document.documentElement.parentIndex;

Body parentIndex is <b id="output"></b><br />
documentElements parentIndex is <b id="output2"></b>

Limitations

• This implementation of the solution will not work in IE8 and below.

Binary VS Linear Search On 200 thousand elements (might crash some mobile browsers, BEWARE!):

• In this test, we will see how long it takes for a linear search to find the middle element VS a binary search. Why the middle element? Because it is at the average location of all the other locations, so it best represents all of the possible locations.

Binary Search

(function(constructor){
   'use strict';
    Object.defineProperty(constructor.prototype, 'parentIndexBinarySearch', {
      get: function() {
        var searchParent = this.parentNode;
        if (searchParent === null) return -1;
        var childElements = searchParent.children,
            lo = -1, mi, hi = childElements.length;
        while (1 + lo !== hi) {
            mi = (hi + lo) >> 1;
            if (!(this.compareDocumentPosition(childElements[mi]) & 0x2)) {
                hi = mi;
                continue;
            }
            lo = mi;
        }
        return childElements[hi] === this ? hi : -1;
      }
    });
})(window.Element || Node);
test.innerHTML = '<div> </div> '.repeat(200e+3);
// give it some time to think:
requestAnimationFrame(function(){
  var child=test.children.item(99.9e+3);
  var start=performance.now(), end=Math.round(Math.random());
  for (var i=200 + end; i-- !== end; )
    console.assert( test.children.item(
        Math.round(99.9e+3+i+Math.random())).parentIndexBinarySearch );
  var end=performance.now();
  setTimeout(function(){
    output.textContent = 'It took the binary search ' + ((end-start)*10).toFixed(2) + 'ms to find the 999 thousandth to 101 thousandth children in an element with 200 thousand children.';
    test.remove();
    test = null; // free up reference
  }, 125);
}, 125);

<output id=output> </output><br />
<div id=test style=visibility:hidden;white-space:pre></div>

Backwards (`lastIndexOf`) Linear Search

(function(t){"use strict";var e=Array.prototype.lastIndexOf;Object.defineProperty(t.prototype,"parentIndexLinearSearch",{get:function(){return e.call(t,this)}})})(window.Element||Node);
test.innerHTML = '<div> </div> '.repeat(200e+3);
// give it some time to think:
requestAnimationFrame(function(){
  var child=test.children.item(99e+3);
  var start=performance.now(), end=Math.round(Math.random());
  for (var i=2000 + end; i-- !== end; )
    console.assert( test.children.item(
        Math.round(99e+3+i+Math.random())).parentIndexLinearSearch );
  var end=performance.now();
  setTimeout(function(){
    output.textContent = 'It took the backwards linear search ' + (end-start).toFixed(2) + 'ms to find the 999 thousandth to 101 thousandth children in an element with 200 thousand children.';
    test.remove();
    test = null; // free up reference
  }, 125);
});

<output id=output> </output><br />
<div id=test style=visibility:hidden;white-space:pre></div>

Forwards (`indexOf`) Linear Search

(function(t){"use strict";var e=Array.prototype.indexOf;Object.defineProperty(t.prototype,"parentIndexLinearSearch",{get:function(){return e.call(t,this)}})})(window.Element||Node);
test.innerHTML = '<div> </div> '.repeat(200e+3);
// give it some time to think:
requestAnimationFrame(function(){
  var child=test.children.item(99e+3);
  var start=performance.now(), end=Math.round(Math.random());
  for (var i=2000 + end; i-- !== end; )
    console.assert( test.children.item(
        Math.round(99e+3+i+Math.random())).parentIndexLinearSearch );
  var end=performance.now();
  setTimeout(function(){
    output.textContent = 'It took the forwards linear search ' + (end-start).toFixed(2) + 'ms to find the 999 thousandth to 101 thousandth children in an element with 200 thousand children.';
    test.remove();
    test = null; // free up reference
  }, 125);
});

<output id=output> </output><br />
<div id=test style=visibility:hidden;white-space:pre></div>

PreviousElementSibling Counter Search

Counts the number of PreviousElementSiblings to get the parentIndex.

(function(constructor){
   'use strict';
    Object.defineProperty(constructor.prototype, 'parentIndexSiblingSearch', {
      get: function() {
        var i = 0, cur = this;
        do {
            cur = cur.previousElementSibling;
            ++i;
        } while (cur !== null)
        return i; //Returns 3
      }
    });
})(window.Element || Node);
test.innerHTML = '<div> </div> '.repeat(200e+3);
// give it some time to think:
requestAnimationFrame(function(){
  var child=test.children.item(99.95e+3);
  var start=performance.now(), end=Math.round(Math.random());
  for (var i=100 + end; i-- !== end; )
    console.assert( test.children.item(
        Math.round(99.95e+3+i+Math.random())).parentIndexSiblingSearch );
  var end=performance.now();
  setTimeout(function(){
    output.textContent = 'It took the PreviousElementSibling search ' + ((end-start)*20).toFixed(2) + 'ms to find the 999 thousandth to 101 thousandth children in an element with 200 thousand children.';
    test.remove();
    test = null; // free up reference
  }, 125);
});

<output id=output> </output><br />
<div id=test style=visibility:hidden;white-space:pre></div>

No Search

For benchmarking what the result of the test would be if the browser optimized out the searching.

test.innerHTML = '<div> </div> '.repeat(200e+3);
// give it some time to think:
requestAnimationFrame(function(){
  var start=performance.now(), end=Math.round(Math.random());
  for (var i=2000 + end; i-- !== end; )
    console.assert( true );
  var end=performance.now();
  setTimeout(function(){
    output.textContent = 'It took the no search ' + (end-start).toFixed(2) + 'ms to find the 999 thousandth to 101 thousandth children in an element with 200 thousand children.';
    test.remove();
    test = null; // free up reference
  }, 125);
});

<output id=output> </output><br />
<div id=test style=visibility:hidden></div>

The Conculsion

However, after viewing the results in Chrome, the results are the opposite of what was expected. The dumber forwards linear search was a surprising 187 ms, 3850%, faster than the binary search. Evidently, Chrome somehow magically outsmarted the console.assert and optimized it away, or (more optimistically) Chrome internally uses numerical indexing system for the DOM, and this internal indexing system is exposed through the optimizations applied to Array.prototype.indexOf when used on a HTMLCollection object.

Answer 3

Out of curiosity I ran your code against both jQuery's .index() and my below code:

function findRow3(node)
{
    var i = 1;
    while (node = node.previousSibling) {
        if (node.nodeType === 1) { ++i }
    }
    return i;
}

Jump to jsperf results

It turns out that jQuery is roughly 50% slower than your implementation (on Chrome/Mac) and mine arguably topped it by 1%.

Edit

Couldn't quite let this one go, so I've added two more approaches:

Using Array.indexOf

[].indexOf.call(node.parentNode.children, node);

Improvement on my earlier experimental code, as seen in HBP's answer, the DOMNodeList is treated like an array and it uses Array.indexOf() to determine the position within its .parentNode.children which are all elements. My first attempt was using .parentNode.childNodes but that gives incorrect results due to text nodes.

Using previousElementSibling

Inspired by user1689607's answer, recent browsers have another property besides .previousSibling called .previousElementSibling, which does both original statements in one. IE <= 8 doesn't have this property, but .previousSibling already acts as such, therefore a feature detection would work.

(function() {
    // feature detection
    // use previousElementSibling where available, IE <=8 can safely use previousSibling
    var prop = document.body.previousElementSibling ? 'previousElementSibling' : 'previousSibling';

    getElementIndex = function(node) {
        var i = 1;
        while (node = node[prop]) { ++i }
        return i;
    }

Conclusion

Using Array.indexOf() is not supported on IE <= 8 browsers, and the emulation is simply not fast enough; however, it does give 20% performance improvement.

Using feature detection and .previousElementSibling yields a 7x improvement (on Chrome), I have yet to test it on IE8.

Answer 4

Generally speaking, a small difference in performance has a negligible effect unless the code is run in a loop. Having to run the code once instead of every time will be significantly faster.

Do something like this once:

var par = document.getElementById('parent');
var childs = par.getElementsByTagName('*');
for (var i=0, len = childs.length;i < len;i++){
  childs[i].index = i;
}

Subsequently finding the index is as easy as:

document.getElementById('findme').index

It sounds like whatever you're doing could be benefited by having a cleaner relationship between the DOM and the javascript. Consider learning Backbone.js, a small javascript MVC library which makes web applications much easier to control.

edit: I've removed the jQuery I used. I do normally avoid using it, but there's quite a preference for it on SO, so I assumed it would end up being used anyway. Here you can see the obvious difference: http://jsperf.com/sibling-index/8

Answer 5

I added two tests to the jsPerf test. Both use previousElementSibling, but the second includes compatibility code for IE8 and lower.

Both of them perform extremely well in modern browsers (which is most browsers in use today), but will take a small hit in older browsers.

---

Here's the first one that doesn't include the compatibility fix. It'll work in IE9 and higher, as well as pretty much all of Firefox, Chrome and Safari.

function findRow6(node) {
    var i = 1;
    while (node = node.previousElementSibling)
        ++i;
    return i;
}

---

Here's the version with the compatibility fix.

function findRow7(node) {
    var i = 1,
        prev;
    while (true)
        if (prev = node.previousElementSibling) {
            node = prev;
            ++i;
        } else if (node = node.previousSibling) {
            if (node.nodeType === 1) {
                ++i;
            }
        } else break;
    return i;
}

---

Because it automatically grabs element siblings, there's no test needed for nodeType, and the loop is shorter overall. This explains the large performance increase.

---

I also added one last version that loops the .children, and compares the node to each one.

This isn't quite as fast as the previousElementSibling versions, but is still faster than the others (at least in Firefox).

function findRow8(node) {
    var children = node.parentNode.children,
        i = 0,
        len = children.length;
    for( ; i < len && children[i] !== node; i++)
        ; // <-- empty statement

    return i === len ? -1 : i;
}

---

---

Going back to the previousElementSibling version, here's a tweak that may bump up the performance just a bit.

function findRow9(node) {
    var i = 1,
        prev = node.previousElementSibling;

    if (prev) {
        do ++i;
        while (prev = prev.previousElementSibling);
    } else {
        while (node = node.previousSibling) {
            if (node.nodeType === 1) {
                ++i;
            }
        }
    }
    return i;
}

I haven't tested it in the jsPerf, but breaking it out into two different loops based on the presence of a previouselementSibling would only help I would think.

Maybe I'll add it in a bit.

I went ahead and added it to the test linked at the top of this answer. It does help a little bit, so I think it's probably worth doing.

Answer 6

A little improvement over Jack's solution, 3% improvement. Little weird indeed.

function findRow5(node)
{
    var i = 2;
    while (node = node.previousSibling)
        i += node.nodeType ^ 3;
    return i >> 1;
}

As there are only two possible nodeTypes in this case (and in most cases):

Node.ELEMENT_NODE == 1
Node.TEXT_NODE == 3

So xor 3 with nodeType, will give 2 and 0.

http://jsperf.com/sibling-index/4

Answer 7

Try this:

function findRow(node) {
    var i = 1;
    while ((node = node.previousSibling) != null) {
        if (node.nodeType === 1) i++;
    }
    return i; //Returns 3
}

Answer 8

By co-opting Array indexOf you could use :

  var wmi = document.getElementById ('whereami');
  index = [].indexOf.call (wmi.parentNode.children, wmi);

[Tested on Chrome browser only]

Answer 9

Since you are using jQuery. index should do the trick

jQuery('#whereami').index()

but how are you going to use the index later?