34

id を持つ子 div のインデックスを見つけたい'whereami'

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

現在、この関数を使用して子のインデックスを見つけています。

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

フィドル: http://jsfiddle.net/grantk/F7JpH/2/

問題点
何千もの div ノードがある場合、while ループはそれらをカウントするために各 div をトラバースする必要があります。これには時間がかかる場合があります。

これに取り組むより速い方法はありますか?

*id は別の div ノードに変更されるため、再計算できるようにする必要があることに注意してください。

4

9 に答える 9

40

好奇心から、jQuery.index()と以下のコードの両方に対してコードを実行しました。

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

jsperf の結果にジャンプ

jQuery はあなたの実装 (Chrome/Mac 上) よりも約 50% 遅く、間違いなくそれを 1% 上回っていることがわかりました。

編集

これを手放すことはできなかったので、さらに 2 つのアプローチを追加しました。

Array.indexOf の使用

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

HBPの回答に見られるように、私の以前の実験コードの改善はDOMNodeList、配列のように扱われ、すべての要素であるArray.indexOf()その中の位置を決定するために使用されます。.parentNode.children私の最初の試みは使用.parentNode.childNodesでしたが、テキストノードが原因で誤った結果が得られました。

previousElementSibling の使用

user1689607 の answerに触発されて、最近のブラウザーには、.previousSiblingという名前以外の別のプロパティがあります。previousElementSibling、これは両方の元のステートメントを 1 つにまとめます。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;
    }

結論

の使用Array.indexOf()は IE <= 8 ブラウザーではサポートされておらず、エミュレーションは単に十分に高速ではありません。ただし、パフォーマンスが 20% 向上します。

機能検出を使用すると.previousElementSibling、(Chrome で) 7 倍の改善が得られますが、IE8 ではまだテストしていません。

于 2012-12-01T08:05:55.660 に答える
5

共同選択することArray indexOfで、次を使用できます。

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

[Chrome ブラウザのみでテスト済み]

于 2012-12-01T07:39:51.753 に答える
4

jsPerf testに 2 つのテストを追加しました。どちらも を使用previousElementSiblingしていますが、2 番目には IE8 以前の互換性コードが含まれています。

どちらも最新のブラウザー(現在使用されているほとんどのブラウザー)では非常に優れたパフォーマンスを発揮しますが、古いブラウザーでは多少の影響があります。


これは、互換性修正プログラムが含まれていない最初のものです。Firefox、Chrome、Safari のほぼすべてと同様に、IE9 以降で動作します。

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

互換性修正が適用されたバージョンは次のとおりです。

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;
}

要素の兄弟を自動的に取得するため、 for のテストは不要でnodeType、全体的にループが短くなります。これにより、パフォーマンスが大幅に向上します。


また、 をループし.children、 をそれぞれと比較する最後のバージョンを 1 つ追加しましnodeた。

これはバージョンほど高速ではありません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;
}


バージョンに戻ると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;
}

私は jsPerf でテストしていませんが、 a の存在に基づいて 2 つの異なるループに分割すると、previouselementSibling私が考えるのに役立つだけです。

多分私はそれを少し追加します。

私は先に進み、この回答の上部にリンクされているテストに追加しました。少しは効果があるので、やってみる価値はあると思います。

于 2012-12-01T14:51:46.897 に答える
2

ジャックのソリューションよりもわずかに改善され、3% 改善されました。確かに少し奇妙です。

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

nodeTypeこの場合 (そしてほとんどの場合) には 2 つの可能な s しかないため:

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

したがって、 xor 3 と は、とnodeTypeを与えます。20

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

于 2012-12-01T09:04:12.977 に答える
1

jQueryを使用しているため。インデックスはトリックを行う必要があります

jQuery('#whereami').index()

しかし、後でインデックスをどのように使用しますか?

于 2012-12-01T06:56:13.667 に答える
1

一般的に言えば、コードがループで実行されない限り、パフォーマンスのわずかな違いは無視できるほどの影響を及ぼします。毎回ではなく 1 回コードを実行する必要があるため、大幅に高速化されます。

次のようなことを 1 回実行します。

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

その後、インデックスを見つけるのは次のように簡単です。

document.getElementById('findme').index

DOM と JavaScript の関係をより明確にすることで、何をしていても恩恵を受けることができるようです。Backbone.js を学習することを検討してください。Backbone.js は、Web アプリケーションの制御をはるかに容易にする小さな JavaScript MVC ライブラリです。

編集:使用したjQueryを削除しました。私は通常それを使用することを避けますが、SO ではかなりの好みがあるので、とにかく使用されることになると思いました。ここで明らかな違いを見ることができます: http://jsperf.com/sibling-index/8

于 2012-12-01T15:05:07.093 に答える
1

すべての子要素がドキュメント上で順番に並べられている要素がある場合、要素のドキュメント位置を比較して二分探索を行うのが最速の方法であると仮定します。ただし、結論で紹介したように、仮説は棄却されます。要素が多いほど、パフォーマンスの可能性が高くなります。たとえば、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);

次に、それを使用する方法は、任意の要素の「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>

制限事項

  • このソリューションの実装は、IE8 以下では機能しません。

バイナリ VS 線形検索 20 万要素 (一部のモバイル ブラウザはクラッシュする可能性があります。注意してください!):

  • このテストでは、線形検索で中間要素を見つけるのにかかる時間と二分検索にかかる時間を確認します。なぜ真ん中の要素?これは、他のすべての場所の平均的な場所にあるため、考えられるすべての場所を最もよく表しています。

二分探索

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

後方 (`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>

フォワード (`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>

前の要素兄弟カウンター検索

ParentIndex を取得するために、PreviousElementSiblings の数をカウントします。

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

検索なし

ブラウザが検索を最適化した場合にテストの結果がどうなるかをベンチマークするため。

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>

脳震盪

ただし、Chrome で結果を表示すると、結果は予想とは逆になります。ばかげた順方向線形検索は、驚くべきことに 187 ミリ秒 (3850%) で、二分検索よりも高速でした。明らかに、Chrome はどういうわけか魔法のように を裏切ってconsole.assert最適化し、または (より楽観的に) Chrome は DOM の数値インデックス システムを内部的に使用しており、この内部インデックス システムはArray.prototype.indexOf、オブジェクトで使用されたときに適用される最適化を通じて公開されHTMLCollectionます。

于 2017-07-02T22:13:37.407 に答える
1

これを試して:

function findRow(node) {
    var i = 1;
    while ((node = node.previousSibling) != null) {
        if (node.nodeType === 1) i++;
    }
    return i; //Returns 3
}
于 2012-12-01T07:41:51.253 に答える