Il DOM ha una tabella hash di elementi le cui chiavi sono gli id degli elementi?
Voglio sapere se document.getElementById cerca una tabella hash o attraversa l'intero albero.
Questo comportamento è diverso tra i vari browser?Javascript getElementById ricerche - hash map o cross traversal ad albero ricorsivo?
Le implementazioni sono libere di fare quello che vogliono, ma dal momento che id è definito come un valore univoco, sembrerebbe ragionevole utilizzare una mappa hash o un meccanismo di ricerca simile piuttosto che attraversare. Ciò che sembra sensato dall'esterno, tuttavia, potrebbe non essere quando si entra nell'impianto idraulico della costruzione di un browser Web complesso con molti imperativi (talvolta contrastanti).
Ho eseguito un semplice test ma semplicistico (vedere la pagina alla fine della risposta). È semplicemente molto, non ultimo perché non sappiamo che i browser non memorizzano nella cache i risultati precedenti.
Chrome 4.1.249.1059 rapporti:
ID: 0.0082ms per lookup
Tag: 0.0249ms per lookup
Quindi, drammaticamente più veloce per ID di nome del tag.
IE7 rapporti:
ID: 2.4438ms per lookup
Tag: 0.0437ms per lookup
così drammaticamente più veloce per nome tag di ID (ma ricordate IE7 ha un broken concept of getElementById; questo è fissato in IE8).
IE8 (su una macchina differente , non si confronta assoluti, stiamo guardando diff all'interno del browser testato) relazioni:
ID: 1.1335ms per lookup
Tag: 0.0287ms per lookup
Così più o meno come IE7.
Firefox 3.6.3 rapporti:
ID: 0.0042ms per lookup
Tag: 0.006ms per lookup
Quindi non si preoccupa più di tanto (a ripetute richieste; nuovo, può essere caching).
Opera 10.5.1 rapporti:
ID: 0.006ms per lookup
Tag: 1.467ms per lookup
notevolmente più veloce rispetto ID nome del tag.
Fai di quei risultati quello che vuoi. Sarebbe necessario un caso di test più complesso per inferire realmente i meccanismi. Ovviamente, in almeno due di questi casi (Firefox e Chrome), , possiamo dare un'occhiata alla fonte. CMS gentilmente points us alle implementazioni WebKit e Firefox (e guardandolo, il mio sospetto sulla memorizzazione nella cache potrebbe essere stato on the money).
pagina di prova:
<!DOCTYPE HTML>
<html>
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">
<title>Test Page</title>
<style type='text/css'>
body {
font-family: sans-serif;
}
#log p {
margin: 0;
padding: 0;
}
</style>
<script type='text/javascript'>
window.onload = pageInit;
function pageInit() {
document.getElementById('btnGo').onclick = btnGoClick;
}
function btnGoClick() {
log("Testing...");
setTimeout(run, 0);
}
function run() {
var count, time;
try {
// Warm up
testid(10);
testtag(10);
// Test
count = 10000
time = testid(count);
log("ID: " + (time/count) + "ms per lookup");
time = testtag(count);
log("Tag: " + (time/count) + "ms per lookup");
}
catch (e) {
log("Error: " + (e.message ? e.message : String(e)));
}
}
function testid(count) {
var start;
start = new Date().getTime();
while (count-- > 0) {
if (!document.getElementById('fred')) {
throw "ID 'fred' not found";
}
}
return new Date().getTime() - start;
}
function testtag(count) {
var start;
start = new Date().getTime();
while (count-- > 0) {
if (document.getElementsByTagName('em').length == 0) {
throw "Tag 'em' not found";
}
}
return new Date().getTime() - start;
}
function log(msg) {
var log = document.getElementById('log');
log.innerHTML += "<p>" + msg + "<\/p>";
}
</script>
</head>
<body><div>
<input type='button' id='btnGo' value='Go'>
<div id='log'></div>
<hr>
<div>test test<span>test<span>test<span>test<span>test</span></span></span></span></div>
<div>test test<span>test<span>test<span>test<span>test</span></span></span></span></div>
<div>test test<span>test<span>test<span>test<span>test</span></span></span></span></div>
<div>test test<span>test<span>test<span>test<span>test</span></span></span></span></div>
<!-- repeat the above a couple of thousand times; I had about 2,200 -->
<div>test test<span>test<span>test<span>test<span>test</span></span></span></span></div>
<div>test test<span>test<span>test<span>test<em id='fred'>test</em></span></span></span></div>
</div></body>
</html>
Ecco l'esempio dal vivo per chiunque sia interessato http://jsbin.com/esemi3/ – R0MANARMY
@ROMANARMY: Questo ha bisogno di un * lotto * di contenuti in più (vedere il commento inline nell'HTML). –
@ T.J.- Bel test, ho provato ad aggiungere il contenuto su jsbin, ma sembra che abbiano un limite di dimensione, l'ho caricato [qui] (http://dl.dropbox.com/u/35146/js/tests/getElementById .html). – CMS
Non dovrebbe essere difficile da testare.
Se si tratta di una struttura ad albero, la creazione di un albero profondo(tramite Javascript) dovrebbe essere un buon banco di prova.
Si prega di rispondere alla domanda e non pubblicare per ottenere un rappresentante –
Sì, si prega di fare questo test, su almeno 3 principali browser. – Kobi
@ Srinivas: hai visto il mio rappresentante? Potrei interessarmi di meno. –
L'implementazione specifica non è definita nello HTML spec in modo da poter facilmente variare il browser nel browser. Ad esempio IE documentation stati
Restituisce un riferimento al primo oggetto con il valore specificato dell'attributo ID o NOME.
quindi sarei tentato di dire che esegue una ricerca (o semplicemente getta elementi in caso di collisioni di hash).
EDIT Inoltre, tenere presente che ci sono altre strutture di dati (come alberi) che consentono un tempo di accesso tra costante e lineare.
Ricorda che l'implementazione di IE, il bit che hai citato, è rotta, completamente in disaccordo con il comportamento specificato dal W3C. Hanno risolto questo problema in IE8, per fortuna. –
Buon punto. Per essere onesti, W3C dice ** ... Il comportamento non è definito se più di un elemento ha questo ID. ** Tecnicamente IE non può essere sbagliato se il comportamento corretto non è definito. – R0MANARMY
@ROMANARMY: il bit sbagliato sta mescolando 'nome' con' id'. Se hai documenti duplicati nei tuoi documenti, come dici tu, qualunque cosa il browser voglia fare (incluso ignorarli tutti) è perfettamente a posto. –
so circa le implementazioni di Firefox e WebKit DOM, entrambi utilizzano una tabella hash di ricercare gli elementi, scavando nella fonte di essi è possibile dare uno sguardo alle implementazioni interne :
implementazione WebKit, Document.cpp, utilizza la tabella hash se la id è unico, altrimenti si attraversa il documento per ottenere la prima partita:
Element* Document::getElementById(const AtomicString& elementId) const
{
if (elementId.isEmpty())
return 0;
m_elementsById.checkConsistency();
Element* element = m_elementsById.get(elementId.impl());//<-- hastable lookup
if (element)
return element;
if (m_duplicateIds.contains(elementId.impl())) {
// We know there's at least one node with this id,
// but we don't know what the first one is.
for (Node *n = traverseNextNode(); n != 0; n = n->traverseNextNode()) {
if (n->isElementNode()) {
element = static_cast<Element*>(n);
if (element->hasID() &&
element->getAttribute(element->idAttributeName()) == elementId) {
m_duplicateIds.remove(elementId.impl());
m_elementsById.set(elementId.impl(), element);
return element;
}
}
}
ASSERT_NOT_REACHED();
}
return 0;
}
Implementazione di Firefox, nsDocument.cpp
+1 Interessante. Quindi, utilizzando lo stesso 'id' due volte non solo il tuo documento non è valido, ma peggiora anche le prestazioni. – bobince
@CMS l'hashtable potrebbe essere utilizzato solo per la memorizzazione nella cache. Sapremo solo se eseguiremo test su un DOM di grandi dimensioni. – sash
risposta stupenda, grazie – foreyez
+1, buona domanda. –
+1 per un'ottima domanda. – Kangkan
Non sono abbastanza sicuro che sia una buona domanda. Una buona domanda potrebbe essere "Qual è il modo migliore per trovare un elemento con un dato ID", e "getElementById" è probabilmente la risposta migliore. Come viene implementato? Sta sbirciando in una scatola nera. Probabilmente ci sono troppi browser per una risposta definitiva. – Kobi