34

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.

11
  • Why are you traversing the node tree for a child that has an id... that you use getElementById on anyway... this has to be a massively simplified example. Dec 1, 2012 at 6:16
  • I am trying to find the count, not the node.
    – gkiely
    Dec 1, 2012 at 6:19
  • Are you saying you want the index position of the node? Also, your code is a little messed up. You should have .nodeType === 1 instead of .nodeType !== 1. Dec 1, 2012 at 6:20
  • When you say you want to find the count, dont you mean the index?
    – Ravi Y
    Dec 1, 2012 at 6:29
  • 4
    Always happy to see good code beat jQuery to shit in performance.
    – xiaoyi
    Dec 1, 2012 at 15:10

9 Answers 9

41

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.

4
  • just made it a little faster.
    – xiaoyi
    Dec 1, 2012 at 9:05
  • @xiaoyi definitely looks interesting, though it didn't make much difference in my setup :)
    – Ja͢ck
    Dec 1, 2012 at 14:13
  • Array.indexOf() can work with really well IE8 if you use polyfill.
    – thednp
    Apr 24, 2015 at 18:46
  • 1
    @thednp Yeah, I've mentioned that in the second last paragraph :)
    – Ja͢ck
    Apr 25, 2015 at 0:16
5

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]

4
  • Tried that too, but it counts text nodes too and is 25% slower :)
    – Ja͢ck
    Dec 1, 2012 at 13:18
  • @Jack: This doesn't count text nodes. The .children property contains only elements (except in IE8 and lower, where it will wrongly include comment nodes). Dec 1, 2012 at 18:19
  • Ah, children != childNodes :)
    – Ja͢ck
    Dec 1, 2012 at 23:38
  • +1. If it wasn't for IE8, this would be a pretty decent solution; I've added this improvement in my jsperf test as well.
    – Ja͢ck
    Dec 2, 2012 at 4:31
4

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.

1
  • +1. Thanks for the inspiration; I've added a version of this to my answer that puts the condition outside using feature detection of document.body.
    – Ja͢ck
    Dec 2, 2012 at 4:30
2

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

1

Since you are using jQuery. index should do the trick

jQuery('#whereami').index()

but how are you going to use the index later?

1
  • I would prefer to use native js. I have removed the jquery tag. I did take a look at the index() method. Thanks.
    – gkiely
    Dec 1, 2012 at 6:59
1

Try this:

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

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

7
  • Your optimization failed to meet the requirement: Note that the id will change to different divs node, so it will need to be able to re-calculate.
    – xiaoyi
    Dec 1, 2012 at 15:07
  • "Having to run the code once instead of every time will be significantly faster." I'm betting that even with the .data() pre-populated, it'll be slower. jQuery's .data() has been notoriously slow. But I'll add it to the test, and will eat my words if I'm wrong. ;-) Dec 1, 2012 at 15:43
  • Well, it actually did a little better than I expected in Firefox, but overall it's not terribly fast and slower than some other solutions. And you still have the static nature of the indices. jsperf.com/sibling-index/7 Dec 1, 2012 at 15:54
  • ...actually did very well in Opera. Dec 1, 2012 at 16:00
  • @user1689607, I wasn't aware that jQuery data was THAT slow. I used it because it's a recognizable api and allows me to give a more concise answer that expresses a point rather than giving the final solution.
    – mowwwalker
    Dec 1, 2012 at 18:04
1

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.