¿El DOM tiene una tabla hash de elementos cuyas claves son los identificadores de los elementos?
Quiero saber si document.getElementById busca una tabla hash o atraviesa todo el árbol.
¿Este comportamiento es diferente en todos los navegadores?Javascript getElementById búsquedas: ¿hash map o recursive tree traversal?
Las implementaciones son libres de hacer lo que quieran, pero dado que id se define como un valor único, parece sensato utilizar un mapa hash o un mecanismo de búsqueda similar en lugar de un recorrido transversal. Sin embargo, lo que parece sensato desde el exterior puede no serlo cuando te metes en la plomería de construir un navegador web complejo con muchos imperativos (a veces contradictorios).
Hice una prueba fácil pero muy simplista (ver página al final de la respuesta). Es muy simplista, no menos importante porque no sabemos que los navegadores no almacenan en caché los resultados anteriores.
Chrome 4.1.249.1059 informes:
ID: 0.0082ms per lookup
Tag: 0.0249ms per lookup
Por lo tanto, mucho más rápido por ID de etiqueta con su nombre.
IE7 informes:
ID: 2.4438ms per lookup
Tag: 0.0437ms per lookup
tan dramáticamente más rápido por nombre de la etiqueta de identificación (pero recuerda IE7 tiene una broken concept of getElementById, lo que es fijo en IE8).
IE8 (en una máquinadiferente, no se pueden comparar los absolutos, estamos mirando las diferenciaciones dentro del navegador probado) informes:
ID: 1.1335ms per lookup
Tag: 0.0287ms per lookup
Así casi lo mismo que IE7.
Firefox 3.6.3 informes:
ID: 0.0042ms per lookup
Tag: 0.006ms per lookup
por lo que no importa mucho (en repetidas peticiones; nuevo, puede ser el almacenamiento en caché).
Opera 10.5.1 informes:
ID: 0.006ms per lookup
Tag: 1.467ms per lookup
dramáticamente más rápido por ID de etiqueta con su nombre.
Haga de esos resultados lo que quiera. Sería necesario un caso de prueba más complejo para inferir realmente los mecanismos. Por supuesto, en al menos dos de esos casos (Firefox y Chrome), podemos consultar la fuente. CMS amablemente points us a las implementaciones WebKit y Firefox (y mirándolo, mi sospecha sobre el almacenamiento en caché puede haber sido on the money).
página de prueba:
<!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>
Aquí está el ejemplo en vivo para cualquiera que esté interesado http://jsbin.com/esemi3/ – R0MANARMY
@ROMANARMY: Eso necesita un * lote * más contenido (vea el comentario en línea en el HTML). –
@ T.J.- Buena prueba, traté de agregar el contenido en jsbin, pero parece que tienen un límite de tamaño, lo he subido [aquí] (http://dl.dropbox.com/u/35146/js/tests/getElementById .html). – CMS
No debería ser difícil de probar.
Si está basado en un árbol, entonces hacer un árbol muy muy (a través de Javascript) debería ser un buen caso de prueba.
Por favor, responda la pregunta y no publicar para obtener representante. –
Sí, realice esa prueba, en al menos 3 navegadores principales. – Kobi
@Srinivas: ¿has visto mi representante? Podría importarme menos. –
La implementación específica no está definida en el HTML spec por lo que podría variar fácilmente el navegador al navegador. Por ejemplo IE documentation estados
Devuelve una referencia al primer objeto con el valor especificado del atributo ID o NAME.
así que estaría tentado de decir que hace una búsqueda (o simplemente arroja elementos en casos de colisiones hash).
EDIT También tenga en cuenta que existen otras estructuras de datos (como árboles) que permiten el tiempo de acceso en algún lugar entre constante y lineal.
Recuerde que la implementación de IE, el bit que citó, está rota, completamente en desacuerdo con el comportamiento especificado por el W3C. Lo arreglaron en IE8, por suerte. –
Buen punto. Para ser justos, W3C dice ** ... El comportamiento no está definido si más de un elemento tiene esta ID. ** Técnicamente, IE no puede estar equivocado si no se define el comportamiento correcto. – R0MANARMY
@ROMANARMY: El bit incorrecto es entremezclar 'name' con' id'. Si tiene identificadores duplicados en sus documentos, como usted dice, lo que el navegador quiera hacer (incluso ignorarlos a todos) está perfectamente bien. –
que sé sobre las implementaciones de Firefox y DOM WebKit, tanto de ellos utilizan una tabla hash para buscar los elementos, cavando en la fuente de ellas se puede dar un vistazo a las implementaciones internas :
aplicación WebKit, Document.cpp, utiliza la tabla hash si el id es único, de lo contrario, atraviesa el documento para obtener el primer partido:
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;
}
Implementación de Firefox, nsDocument.cpp
+1 Interesante. Por lo tanto, usar el mismo 'id' dos veces no solo hace que su documento no sea válido, sino que también empeora el rendimiento. – bobince
@CMS, la tabla hash solo se puede usar para el almacenamiento en caché. Solo sabremos si realizamos pruebas en un DOM grande. – sash
respuesta increíble, gracias – foreyez
+1, buena pregunta. –
+1 para una muy buena pregunta. – Kangkan
No estoy muy seguro de que sea una buena pregunta. Una buena pregunta podría ser "¿Cuál es la mejor manera de encontrar un elemento con un ID determinado?", Y es probable que "getElementById" sea la mejor respuesta. ¿Cómo se implementa? Eso es asomarse en una caja negra. Probablemente hay demasiados buscadores para una respuesta definitiva. – Kobi