𝗣𝗿𝗼𝗼𝗳 𝗢𝗳 𝗔 𝗟𝗲𝘀𝘀 𝗘𝗳𝗳𝗶𝗰𝗶𝗲𝗻𝘁 𝗕𝗶𝗻𝗮𝗿𝘆 𝗦𝗲𝗮𝗿𝗰𝗵
Stawiam hipotezę, że biorąc pod uwagę element, w którym wszystkie jego elementy podrzędne są uporządkowane w dokumencie po kolei, najszybszym sposobem powinno być przeszukanie binarne, porównując pozycje elementów w dokumencie. Jednak, jak wprowadzono we wniosku, hipoteza zostaje odrzucona. Im więcej masz elementów, tym większy potencjał wydajności. Na przykład, gdybyś miał 256 elementów, to (optymalnie) musiałbyś sprawdzić tylko 16 z nich! Dla 65536 tylko 256! Wydajność rośnie do potęgi 2! Zobacz więcej liczb / statystyk. Odwiedź Wikipedię
(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);
Następnie sposób, w jaki go używasz, polega na uzyskaniu właściwości „parentIndex” dowolnego elementu. Na przykład sprawdź następujące 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>
Ograniczenia
- Ta implementacja rozwiązania nie będzie działać w IE8 i starszych.
Wyszukiwanie binarne VS liniowe na 200 000 elementów (może spowodować awarię niektórych przeglądarek mobilnych, OSTROŻNIE!):
- W tym teście zobaczymy, jak długo trwa wyszukiwanie liniowe, aby znaleźć środkowy element VS wyszukiwanie binarne. Dlaczego środkowy element? Ponieważ znajduje się w średniej lokalizacji wszystkich innych lokalizacji, więc najlepiej reprezentuje wszystkie możliwe lokalizacje.
Wyszukiwanie binarne
(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>
Wyszukiwanie liniowe wstecz (`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>
Wyszukiwanie liniowe do przodu (`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>
PoprzedniElementSibling Counter Search
Zlicza liczbę PreviousElementSiblings, aby uzyskać 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>
Brak wyszukiwania
Do analizy porównawczej, jaki byłby wynik testu, gdyby przeglądarka zoptymalizowała wyszukiwanie.
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
Jednak po przejrzeniu wyników w Chrome wyniki są odwrotne od oczekiwanych. Głupsze wyszukiwanie liniowe do przodu było zaskakujące o 187 ms, 3850%, szybciej niż wyszukiwanie binarne. Najwyraźniej Chrome w jakiś magiczny sposób przechytrzył console.asserti zoptymalizował go lub (bardziej optymistycznie) Chrome wewnętrznie używa numerycznego systemu indeksowania dla DOM, a ten wewnętrzny system indeksowania jest ujawniany poprzez optymalizacje zastosowane Array.prototype.indexOfna HTMLCollectionobiekcie.
parent.childNodes, a nieparent.children?. Ta ostatnia wymienia tylkoElements, wyłączając poszczególneTextwęzły ... Część odpowiedzi, np. UżywaniepreviousSibling, opiera się na wykorzystaniu wszystkich węzłów potomnych, podczas gdy inne dotyczą tylko dzieci, które sąElement... (!)