Gathering of Tweakers

Quicksearch

bookmark offline Geplaatst op zondag 03 april 2005 23:43

Acties: [view][quote]

Door: crisp Devver / Moderator WEB
Papa van Jeremy \o/
Berichten: 30.172
Reg. datum: 24 februari 2000
In het kader 'handig' dacht ik eens een topicje te openen speciaal voor de search, maar ook met wat diepere achtergrondinformatie ter leering ende vermaeck. Dit is dus niet puur bedoelt als een soort codebase-achtig topic maar omvat meer dan dat.

Ik moest voor een script bepaalde elementen uit de DOM tree op basis van classes kunnen selecteren, en dus was het idee om een getElementsByClassName method te schrijven geboren. In het verleden heb ik al diverse malen dergelijke scripts geschreven, en uit ervaring wist ik ongeveer ook wel wat efficient zou zijn. In dit geval wou ik echter mijn eigen implementatie eens toetsen en was dus vervolgens ook maar eens op zoek gegaan naar soortgelijke implementaties op het internet. Dat bracht me al gauw op deze pagina waar wat veelbelovende, en ook goed doordachte, scriptlets stonden. Ik ben daarmee dus ook aan het stoeien geweest en heb ook in diverse browsers eens wat benchmarks gedraait. De bevindingen zijn opmerkelijk te noemen.

Laten we eens met de meest simpele manier beginnen, gebaseerd op getElementsByTagName('*'), wat een erg 'dure' methode lijkt te zijn, maar wel het meest compacte script oplevert:


JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
document.getElementsByClassName = function (needle)
{
    var s = document.getElementsByTagName('*'), i = s.length, r = [], e, c;
    needle = ' ' + needle + ' ';

    while (i--)
    {
        e = s.item(i);

        if (e.className)
        {
            c = ' ' + e.className + ' ';
            if (c.indexOf(needle) != -1) r.push(e);
        }
    }

    return r;
}


Dit is een ietwat meer geoptimaliseerde versie van de functie op bovengenoemde pagina. De methode om ook een bepaalde class in een class-attribuut met meerdere classes te kunnen vinden vond ik op zich wel vindingrijk hoewel mijn voorkeur uitgaat naar een reguliere expressie (die zal ik straks laten zien).
Ik heb dit script (en alle volgende scripts) losgelaten op een gesaved topic van GoT met 50 messages en heb 'm laten zoeken naar elementen met als class 'message', op deze manier:


JavaScript:
1
2
3
4
5
6
7
8
9
10
11
var tc;
function bench()
{
    var st = new Date().getTime();
    tc = 0;

    var r = document.getElementsByClassName('message');

    var et = new Date().getTime();
    alert (r.length + ' items found in ' + (et-st) + ' milliseconds; ' + tc + ' elements total');
}


De tc variabele heb ik in de getElementsByClassName ook het totaal aantal elementen laten tellen om er zeker van te zijn dat alle implementaties ook daadwerkelijk alle elementen in de pagina af zijn gegaan. Niets meer dan een controle getal dus, dus doet verder ook weinig ter zake. Er zaten in het opgeslagen document trouwens in totaal 5310 elementen, waarvan 50 elementen met de 'message'-class. Overigens hadden deze elementen naast de message class ook nog een class 'altmsg1' of 'altmsg2', zeg maar in deze vorm:


HTML:
1
<div class="message altmsg1">


Je kan dus niet puur op e.className == needle checken; dat zou te beperkt zijn en niet het gewenste resultaat opleveren.

Hoe snel was dat script nou eigenlijk? Ik merkte net al op dat getElementsByTagName('*') erg duur lijkt te zijn, maar dat lijkt helemaal aan de gebruikte browser te liggen. Ik heb me beperkt tot recente versies van de meestgebruikte browsers; het testteam bestond uit:

1) Firefox 1.01 (nog geen tijd gehad 1.02 te installeren :P )
2) IE6.0 met alle beschikbare patches voor mijn platform (te weten windows 2000)
3) Opera 7.54

Dat alles op een AMD XP2000+ (niet echt meer een krachtmonster dus hedentendage)

Genoeg gelult, hier zijn de resultaten voor de eerste poging tot een snelle getElementsByClassName method:

Firefox: 340 milliseconden
IE: 15400 milliseconden
Opera: 19300 milliseconden


Conclusie: getElementsByTagName('*') is inderdaad een hele dure method, behalve voor Firefox. De laatste zal daar waarschijnlijk intern een bepaalde optimalisatie voor hebben ingebouwd, wat in dit geval goed van pas komt, maar aan de andere kant nutteloos is omdat de snelheid in andere browsers dusdanig bedroefend is dat het in de praktijk geen nut heeft deze constructie te gebruiken.

De volgende methode (ook van eerdergenoemde pagina) leek me dan ook een stuk veelbelovender:


JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
document.getElementsByClassName = function (needle)
{
    function _GetElementsByClass(r, e, needle)
    {
        while (e)
        {
            if (e.nodeType == 1)
            {
                if (e.className)
                {
                    c = ' ' + e.className + ' ';
                    if (c.indexOf(needle) != -1) r.push(e);
                }

                _GetElementsByClass(r, seed.e, needle)
            }

            e = e.nextSibling;
        }
    }

    needle = ' ' + needle + ' ';
    var r = [], c;
    _GetElementsByClass(r, document.documentElement, needle);

    return r;
}


(wederom ietwat aangepast naar mijn eigen smaak en style en met wat kleine performance verbeteringen)
Deze methode gebruikt recursie om door de DOM heen te lopen en daar alle elementen uit te vissen. De vraag is echter of dat inderdaad sneller is dan het gebruik van getElementsByTagName('*'). Mijn eerste gedacht zou zijn: nee, aangezien je in feite precies hetzelfde doet, maar dan op een eigen manier. Ik zou dus zelfs eerder verwachten dat het langzamer is, maar laten we de benchmarks maar voor zich spreken:

Firefox: 340 milliseconden
IE: 15400 milliseconden
Opera: 19300 milliseconden


Kortom: geen enkel verschil! Kan het dan gewoon niet sneller? En nog belangrijker: kan het voornamelijk in non-Firefox browsers dan niet sneller?
De pagina waar ik deze scripts vandaan heb noemde nog 2 alternatieven; 1 gebaseerd op XPath die in dit geval onbruikbaar was omdat hij geen elementen kan selecteren waarvan het class-attribuut meerdere classes bevat (puur gebaseerd op equality), en 1 met behulp van een TreeWalker die volgens de genoemde site Gecko-only is (dus sowieso al niet bruikbaar om die reden), maar die in Firefox gewoonweg niet eens werkte.

Toen was het tijd om mijn eigen probeersel maar eens te testen. De meeste DOM-walers die ik in het verleden heb gebruikt waren stack-based, en dankzij de recursie-based versie hierboven heb ik die zelfs nog wat weten te verbeteren.

Het script:


JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
document.getElementsByClassName = function (needle)
{
    var s = [], r = [], c, undefined;
    var e = document.documentElement || document.body;
    needle = ' ' + needle + ' ';

    while (e !== undefined)
    {
        while (e)
        {
            if (e.nodeType == 1)
            {
                if (e.className)
                {
                    c = ' ' + e.className + ' ';
                    if (c.indexOf(needle) != -1) r.push(e);
                }

                s.push(e.firstChild);
            }

            e = e.nextSibling;
        }

        e = s.pop();
    }

    return r;
}


In feite doet dit script niets anders als de recursieve variant, behalve dan dat het elementen die nader onderzocht moeten worden op een stack zet, en vervolgens de stack wordt afgelezen totdat 'ie leeg is. Je zou denken dat dit qua instructies meer overhead oplevert (tegenover minder memory gebruik), maar dit blijkt toch een winner qua performance:

Firefox: 550 milliseconden
IE: 280 milliseconden
Opera: 120 milliseconden


... in de non-Firefox-browsers that is ;) Op z'n minst opmerkelijk dus, en zelfs 550 milliseconden in Firefox is nog wel overheen te komen op zo'n relatief grote lap HTML, hoewel het heel vreemd is dat het juist in Firefox trager is, maar in de andere browsers zo ontzettend veel sneller...


Tot nog toe heb ik de truuk met spaties gebruikt om in een lijst van (eventueel) spatie-gescheiden classes naar een bepaalde class te zoeken. Ik noemde in het begin al dat een reguliere expressie hierin toch mijn voorkeur zou hebben. Dit omdat het a) minder code oplevert, en b) misschien zelfs wel sneller is aangezien een reguliere expressie, indien vooraf geinstantieerd, een soortement van compiled object is en daarom misschien zelfs wel sneller zou kunnen zijn. Dit is de reguliere expressie die ik hiervoor gemaakt heb:


JavaScript:
1
var re = new RegExp('(^|\\s)' + needle + '(\\s|$)');


En de laatst genoemde methode zou er met het gebruik van deze expressie zo uitzien:


JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
document.getElementsByClassName = function (needle)
{
    var s = [], r = [], undefined;
    var e = document.documentElement || document.body;
    var re = new RegExp('(^|\\s)' + needle + '(\\s|$)');

    while (e !== undefined)
    {
        while (e)
        {
            if (e.nodeType == 1)
            {
                if (e.className && re.test(e.className)) r.push(e);

                s.push(e.firstChild);
            }

            e = e.nextSibling;
        }

        e = s.pop();
    }

    return r;
}


En natuurlijk de benchmarks:

Firefox: 550 milliseconden
IE: 270 milliseconden
Opera: <100 milliseconden


In Firefox dus (helaas) geen verschil, in IE weer een kleine performancewinst, en in Opera zelfs nog meer performancewinst.

Ok, we hebben dus een getElementsByClassName method die in elke browser voor grote documenten bruikbaar is qua performance. Jammer genoeg blijft Firefox qua performance achterlopen bij het gebruik van een stack-based treewalker, maar ook daar is het resultaat nog wel acceptabel.
Verder illustreren deze scripts wel de grote kracht van de DOM, en het feit dat dit soort scripts in bijna elke moderne browser werken zonder enige vorm van browsersniffing is een goed teken*

*Als laatste moet ik hierbij een voetnoot plaatsen met betrekking tot IE5.0 die niet op het gebied van DOM, maar wel op het gebied van javascript tekort schiet. Deze browser kent namelijk niet de push() en pop() methodes voor het Array-object. Javascript laat ons deze echter makkelijk toevoegen door middel van prototyping:


JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
if (typeof Array.prototype.push == 'undefined')
{
    Array.prototype.push = function()
    {
        var l = this.length, i = 0, j = arguments.length;
        while (i < j) this[l++] = arguments[i++];
        return l;
    }
}

if (typeof Array.prototype.pop == 'undefined')
{
    Array.prototype.pop = function()
    {
        var l = this.length, r;
        if (l)
        {
            r = this[--l];
            this.length = l;
        }

        return r;        
    }
}


Uiteraard kan je binnen je code ook het gebruik van push en pop omzeilen door zelf array-pointers bij te houden; op zich kost dat geen tot weinig extra performance, en je script werkt ook zonder prototyping in IE5.0:


JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
document.getElementsByClassName = function (needle)
{
    var s = [document.documentElement || document.body], i = 0, r = [], l = 0, e;
    var re = new RegExp('(^|\\s)' + needle + '(\\s|$)');

    do
    {
        e = s[i];

        while (e)
        {
            if (e.nodeType == 1)
            {
                if (e.className && re.test(e.className)) r[l++] = e;

                s[i++] = e.firstChild;
            }

            e = e.nextSibling;
        }
    }
    while (i--);

    return r;
}

crisp wijzigde dit bericht 04-04-2005 10:58 (3%)

Crisp's blog minitracker:
18-06 X-UA-InCompatible
31-05 IE6 fucking up BASE (again)?

bookmark offline Geplaatst op zondag 03 april 2005 23:49

Acties: [view][quote]

Door: mophor
zie 23648
Berichten: 5411
Reg. datum: 27 juli 2000
leuk, ik heb 'm ook wel eens gemaakt, alleen nooit zo uitgebreid getest. Wat ik alleen anders had is de functie aan het element object gehangen, zodat je 'm ook voor een substuk van je document kan aanroepen, functie roept dan recursief zichzelf aan.

Wat ik ook wel eens gebruikt heb was een getElementsByAttribute(att, needle);, ook wel handig

die dingen werken dus op ongeveer dezelfde manier


JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Element.prototype.getElementsByAttribute = function(att,val) { 
   var nodes = []; 
   var node; 
   for(var i = 0; i < this.childNodes.length; i++) { 
      node = this.childNodes[i]; 
      if(node[att] == val) nodes.push(node) 
      if(node.hasChildNodes()) { 
         nodes = nodes.concat(node.getElementsByAttribute(att,val)) 
      } 
   }   
   return nodes; 
}

Element.prototype.getElementsByNodeType = function(type) { 
   var nodes = []; 
   var node; 
   for(var i = 0; i < this.childNodes.length; i++) { 
      node = this.childNodes[i]; 
      if(node.nodeType == type) nodes.push(node) 
      if(node.hasChildNodes()) { 
         nodes = nodes.concat(node.getElementsByNodeType(type)) 
      } 
   }   
   return nodes; 
}

Element.prototype.getElementsByClassName = function(className) { 
   var nodes = []; 
   var node; 
   for(var i = 0; i < this.childNodes.length; i++) { 
      node = this.childNodes[i]; 
      if(node.className == className) nodes.push(node) 
      if(node.hasChildNodes()) { 
         nodes = nodes.concat(node.getElementsByClassName(className)) 
      } 
   }   
   return nodes; 
}



misschien kan je die laatste eens door je benchmark gooien? ben wel benieuwd eigenlijk (ik zal wel verliezen :P)

bedenk me ook net dat het misschien wel handig is om juist als argument een regex mee te geven, dan is ie helemaal flexibel

mophor wijzigde dit bericht 04-04-2005 00:12 (85%)

var _ = {_: 'unreadable code detected!'};
alert(_._);

bookmark offline Geplaatst op maandag 04 april 2005 00:12

Acties: [view][quote]

Door: crisp Devver / Moderator WEB
Papa van Jeremy \o/
Berichten: 30.172
Reg. datum: 24 februari 2000
mophor: sowieso is het geen oplossing aangezien het niet werkt in IE of Opera. Daarbij is je manier om classes te vinden flawed omdat je geen rekening houd met class-attributen die meerdere classes bevatten, en je method kan op zich nog wel wat efficienter (volgorde is niet echt een issue, en elke iteratie een length property uitvragen kost je ook extra).
Uiteindelijk heb ik je method herschreven naar dit:


JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Element.prototype.getElementsByClassName = function(className)
{ 
    var nodes = [], node;
    var re = new RegExp('(^|\\s)' + className + '(\\s|$)');
    var i = this.childNodes.length;

    while (i--)
    {
        node = this.childNodes[i]; 
        if (node.className && re.test(node.className)) nodes.push(node) 
        if (node.hasChildNodes())
        {
            nodes = nodes.concat(node.getElementsByClassName(className)) 
        }
    }

    return nodes; 
}


met als resultaat een benchmark van 800 milliseconden op mijn testdocument (toch nog vrij netjes) :)

En in feite zijn mijn methods ook eenvoudig aan te passen om te werken op een sub-element van je document.

crisp wijzigde dit bericht 04-04-2005 00:17 (11%)

Crisp's blog minitracker:
18-06 X-UA-InCompatible
31-05 IE6 fucking up BASE (again)?

bookmark offline Geplaatst op maandag 04 april 2005 00:50

Acties: [view][quote]

Door: crisp Devver / Moderator WEB
Papa van Jeremy \o/
Berichten: 30.172
Reg. datum: 24 februari 2000
En de volgende wonderbaarlijke ontdekking:
JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
document.getElementsByClassName = function (needle)
{
    var s = document.getElementsByTagName('*'), i = s.length, e, r = [];
    var re = new RegExp('(^|\\s)' + needle + '(\\s|$)');

    while (i--)
    {
        e = s[i];
        if (e.className && re.test(e.className)) r.push(e);
    }

    return r;
}


let op hoe ik hier e = s[i] gebruik in plaats van e = s.item(i)

benchmarks:
Firefox: 250 milliseconden
IE: 80 milliseconden
Opera: 4150 milliseconden


mixed approach lijkt hier dus toch de beste oplossing:

JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
document.getElementsByClassName = function (needle)
{
    var s, i, r = [], l = 0, e;
    var re = new RegExp('(^|\\s)' + needle + '(\\s|$)');

    if (navigator.userAgent.indexOf('Opera') > -1)
    {
        s = [document.documentElement || document.body], i = 0;

        do
        {
            e = s[i];

            while (e)
            {
                if (e.nodeType == 1)
                {
                    if (e.className && re.test(e.className)) r[l++] = e;

                    s[i++] = e.firstChild;
                }

                e = e.nextSibling;
            }
        }
        while (i--);
    }
    else
    {
        s = document.getElementsByTagName('*'), i = s.length;

        while (i--)
        {
            e = s[i];
            if (e.className && re.test(e.className)) r[l++] = e;
        }
    }

    return r;
}

crisp wijzigde dit bericht 04-04-2005 01:04 (43%)

Crisp's blog minitracker:
18-06 X-UA-InCompatible
31-05 IE6 fucking up BASE (again)?

bookmark offline Geplaatst op maandag 04 april 2005 02:01

Acties: [view][quote]

Door: Anne
CSS1Compat
Berichten: 1638
Reg. datum: 21 november 2003
Ooit: http://whatwg.org/specs/web-apps/current-work/#selecting

(Ik heb ook een e-mail gestuurd naar www-style voor getElementsBySelector() wat er wellicht ook ooit komt, maar ik gok later.)

"Standards suck"

bookmark offline Geplaatst op maandag 04 april 2005 07:28

Acties: [view][quote]

Door: Blues
Blast-off for Kicksville!
Berichten: 2714
Reg. datum: 08 februari 2000
Nice work, crisp.
quote:
Anne schreef op maandag 04 april 2005 @ 02:01:
(Ik heb ook een e-mail gestuurd naar www-style voor getElementsBySelector() wat er wellicht ook ooit komt, maar ik gok later.)
Dean Edwards heeft ooit een cssQuery functie geschreven die ongeveer doet wat jij bedoelt, denk ik...
http://dean.edwards.name/my/#cssQuery.js

Take a life of responsibility, the inability to make right choices, add to it ignorance and indifference and top it off with a desire for escapism and kicks.

bookmark offline Geplaatst op maandag 04 april 2005 10:05

Acties: [view][quote]

Door: mophor
zie 23648
Berichten: 5411
Reg. datum: 27 juli 2000
ideetje:
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

document.getElementsByAttributeRegex = function (att,re)
{
    var s = [], r = [], undefined;
    var e = document.documentElement || document.body;

    while (e !== undefined)
    {
        while (e)
        {
            if (e.nodeType == 1)
            {
                if (e[att]&& re.test(e[att])) r.push(e);

                s.push(e.firstChild);
            }

            e = e.nextSibling;
        }

        e = s.pop();
    }

    return r;
}

en dan dus:
code:
1

document.getElementsByAttributeRegex('className',/^|\smessage\s|$/); //of
document.getElementsByAttributeRegex('nodeName',/h[1-6]/);

mophor wijzigde dit bericht 04-04-2005 10:05 (4%)

var _ = {_: 'unreadable code detected!'};
alert(_._);

bookmark offline Geplaatst op maandag 04 april 2005 10:14

Acties: [view][quote]

Door: crisp Devver / Moderator WEB
Papa van Jeremy \o/
Berichten: 30.172
Reg. datum: 24 februari 2000
quote:
Anne schreef op maandag 04 april 2005 @ 02:01:
Ooit: http://whatwg.org/specs/web-apps/current-work/#selecting

(Ik heb ook een e-mail gestuurd naar www-style voor getElementsBySelector() wat er wellicht ook ooit komt, maar ik gok later.)

Ziet er veelbelovend uit. Je kan dus zelfs meerdere classes opgeven; ik zal eens kijken hoe dat het efficientst te doen is in mijn implementatie - met een simpele regexp zal dat niet meer lukken...

Het is echter opvallend dat juist in Opera de native DOM method getElementsByTagName zo traag is, en dat zelf de DOM tree doorlopen sneller is...

Crisp's blog minitracker:
18-06 X-UA-InCompatible
31-05 IE6 fucking up BASE (again)?

bookmark offline Geplaatst op maandag 04 april 2005 10:49

Acties: [view][quote]

Door: Blues
Blast-off for Kicksville!
Berichten: 2714
Reg. datum: 08 februari 2000
Wie is de eerste met een oElement.getElementsByXPath( sXPath )? ;)

Take a life of responsibility, the inability to make right choices, add to it ignorance and indifference and top it off with a desire for escapism and kicks.

bookmark offline Geplaatst op maandag 04 april 2005 11:10

Acties: [view][quote]

Door: crisp Devver / Moderator WEB
Papa van Jeremy \o/
Berichten: 30.172
Reg. datum: 24 februari 2000
quote:
crisp schreef op maandag 04 april 2005 @ 10:14:
[...]
Het is echter opvallend dat juist in Opera de native DOM method getElementsByTagName zo traag is, en dat zelf de DOM tree doorlopen sneller is...
En net getest in Opera 8.0 (beta 3) waar de getElementsByTagName('*') versie wel sneller is met benchmarktijden <100ms

Crisp's blog minitracker:
18-06 X-UA-InCompatible
31-05 IE6 fucking up BASE (again)?

bookmark offline Geplaatst op maandag 04 april 2005 12:29

Acties: [view][quote]

Door: Genoil
zie .sig
Berichten: 2604
Reg. datum: 17 maart 2000
hah relaxed man crisp, zo'n functie heb ik net nodig vandaag, thx! :)

__w__
a | s | d

bookmark offline Geplaatst op donderdag 07 april 2005 14:10

Acties: [view][quote]

Door: Kayshin
Bl@@T @@P!!!
Berichten: 962
Reg. datum: 22 juni 2004
LOL, ben net bezig met een dergelijke functie te zoeken.

My personal videoteek: -Clique-; -NMe- is een snol!

© 1998-2008 Tweakers.net BV - Based on React - Hosted by True - Served by Adrastos

© 1998-2008 Tweakers.net BV - Based on React - Hosted by True - Served by Adrastos

[RSS][XML]

Update Tracker

Active Topics
Active Topics
Frontpage Nieuws
Frontpage Nieuws