Javascript 在父节点中查找子节点索引的最快方法

Question

提问by gkiely

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

我想找到具有 id 的子 div 的索引'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/

小提琴：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.

问题
当有数千个 div 节点时，while 循环必须遍历每个 div 以计算它们。这可能需要一段时间。

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.

*注意id会变化到不同的divs节点，所以需要重新计算。

Answer 1

回答by Ja?ck

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

出于好奇，我针对 jQuery.index()和下面的代码运行了您的代码：

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

Jump to jsperf results

跳转到 jsperf 结果

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

事实证明，jQuery 比你的实现（在 Chrome/Mac 上）慢了大约 50%，我的可以说比它高 1%。

Edit

编辑

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

不能完全放弃这个，所以我又添加了两种方法：

Using Array.indexOf

使用 Array.indexOf

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

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

改进了我之前的实验代码，如HBP 的回答中所见，它DOMNodeList被视为一个数组，并用于Array.indexOf()确定其内.parentNode.children所有元素的位置。我的第一次尝试是使用，.parentNode.childNodes但由于文本节点而给出了不正确的结果。

Using previousElementSibling

使用 previousElementSibling

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

受user1689607 的回答的启发，最近的浏览器除了.previousSibling称为 . previousElementSibling, 将两个原始语句合二为一。IE <= 8 没有这个属性，但.previousSibling已经这样做了，因此特征检测会起作用。

(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.

Array.indexOf()IE <= 8 浏览器不支持使用，而且仿真速度不够快；但是，它确实提高了 20% 的性能。

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

使用特征检测并.previousElementSibling产生 7 倍的改进（在 Chrome 上），我还没有在 IE8 上测试它。

Answer 2

回答by HBP

By co-opting ArrayindexOfyou could use :

通过选择ArrayindexOf你可以使用：

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

[Tested on Chrome browser only]

[仅在 Chrome 浏览器上测试]

Answer 3

回答by I Hate Lazy

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

我在jsPerf test 中添加了两个测试。两者都使用previousElementSibling，但第二个包含 IE8 及更低版本的兼容性代码。

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.

这是第一个不包括兼容性修复的。它适用于 IE9 及更高版本，以及几乎所有 Firefox、Chrome 和 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.

因为它会自动获取同级元素，所以不需要对进行测试nodeType，并且整个循环更短。这解释了性能的大幅提升。

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

我还添加了一个循环的最后一个版本，.children并将与node每个版本进行比较。

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

这不像previousElementSibling版本那么快，但仍然比其他版本快（至少在 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 previousElementSiblingversion, here's a tweak that may bump up the performance just a bit.

回到previousElementSibling版本，这里有一个调整，可能会稍微提高性能。

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 previouselementSiblingwould only help I would think.

~~我还没有在 jsPerf 中测试过它，但是~~根据 a 的存在previouselementSibling将它分成两个不同的循环只会帮助我认为。

~~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 4

回答by xiaoyi

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

对 Hyman 的解决方案略有改进，提高了 3%。确实有点奇怪。

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):

因为nodeType在这种情况下（并且在大多数情况下）只有两种可能的s：

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

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

所以 xor 3 with nodeType, 将给出2and 0。

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

Answer 5

回答by mowwwalker

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.

听起来您所做的任何事情都可以通过在 DOM 和 javascript 之间建立更清晰的关系而受益。考虑学习 Backbone.js，这是一个小型 javascript MVC 库，它使 Web 应用程序更易于控制。

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

编辑：我已经删除了我使用的 jQuery。我通常会避免使用它，但是在 SO 上非常偏爱它，所以我认为它最终会被使用。在这里你可以看到明显的区别：http: //jsperf.com/sibling-index/8

Answer 6

回答by Hyman Giffin

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

我假设给定一个元素，它的所有子元素都按顺序在文档中排序，最快的方法应该是进行二分查找，比较元素的文档位置。然而，正如结论中所介绍的，假设被拒绝。您拥有的元素越多，性能的潜力就越大。例如，如果您有 256 个元素，那么（最佳情况下）您只需要检查其中的 16 个！对于65536，只有256！性能增长到 2 的幂！查看更多数字/统计数据。访问维基百科

(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.

然后，您使用它的方式是获取任何元素的 'parentIndex' 属性。例如，查看以下演示。

(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.

该解决方案的这种实现不适用于 IE8 及以下版本。

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

二进制 VS 线性搜索 20 万个元素（可能会导致某些移动浏览器崩溃，请注意！）：

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.

在这个测试中，我们将看到线性搜索需要多长时间才能找到中间元素 VS 二进制搜索。为什么是中间元素？因为它处于所有其他位置的平均位置，所以它最好地代表了所有可能的位置。

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

向后（`lastIndexOf`）线性搜索

(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

转发（`indexOf`）线性搜索

(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

PreviousElementSibling 计数器搜索

Counts the number of PreviousElementSiblings to get the parentIndex.

计算 PreviousElementSiblings 的数量以获取 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.assertand 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.indexOfwhen used on a HTMLCollectionobject.

但是，在 Chrome 中查看结果后，结果与预期相反。愚蠢的前向线性搜索惊人的 187 毫秒，3850%，比二分搜索快。显然，Chrome 以某种方式神奇地超越console.assert并优化了它，或者（更乐观地）Chrome 在内部为 DOM 使用数字索引系统，并且这个内部索引系统通过在对象Array.prototype.indexOf上使用时应用的优化来公开HTMLCollection。

Answer 7

回答by pala?н

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 fedmich

Since you are using jQuery. index should do the trick

由于您使用的是 jQuery。索引应该可以解决问题

jQuery('#whereami').index()

but how are you going to use the index later?

但是你以后将如何使用索引？

Javascript 在父节点中查找子节点索引的最快方法

提问by gkiely

回答by Ja?ck

回答by HBP

回答by I Hate Lazy

回答by xiaoyi

回答by mowwwalker

回答by Hyman Giffin

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

二进制 VS 线性搜索 20 万个元素（可能会导致某些移动浏览器崩溃，请注意！）：

Binary Search

二分查找

Backwards (`lastIndexOf`) Linear Search

向后（`lastIndexOf`）线性搜索

Forwards (`indexOf`) Linear Search

转发（`indexOf`）线性搜索

PreviousElementSibling Counter Search

PreviousElementSibling 计数器搜索

No Search

没有搜索

The Conculsion

震荡

回答by pala?н

回答by fedmich

相关推荐

最近更新

标签

Javascript 在父节点中查找子节点索引的最快方法

提问by gkiely

回答by Ja?ck

回答by HBP

回答by I Hate Lazy

回答by xiaoyi

回答by mowwwalker

回答by Hyman Giffin

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

二进制 VS 线性搜索 20 万个元素（可能会导致某些移动浏览器崩溃，请注意！）：

Binary Search

二分查找

Backwards (`lastIndexOf`) Linear Search

向后（`lastIndexOf`）线性搜索

Forwards (`indexOf`) Linear Search

转发（`indexOf`）线性搜索

PreviousElementSibling Counter Search

PreviousElementSibling 计数器搜索

No Search

没有搜索

The Conculsion

震荡

回答by pala?н

回答by fedmich

相关推荐

Javascript 如何使用 jQuery 删除“禁用”属性？

Javascript 使用 HTML5 的画布绘制带有外笔画的文本

Javascript 为数字添加 st、nd、rd 和 th（序数）后缀

Javascript 如何使用JS和提交按钮计算两个输入表单字段并将值放入另一个？

相关推荐

最近更新

标签