[js] dynamic option list performance

[Justice]

Ik ben voor mijn werk bezig met een pagina die een selectlist filtered door de hele lijst te doorzoeken op de user-input en alle options die niet overeenkomen te verplaatsen naar een onzichtbare list (en terug) zodat effectief je een instant zoekresultaat krijgt soortgelijk aan google auto-suggest.

Ik heb de code werkend echter de performance in Internet Explorer 6/win is nog onvoldoende, Firefox en Opera zijn 3-5x sneller. Het doorzoeken van delange select-list is de oorzaak, ik wil dus de loop zo snel mogelijk maken. (de pagina komt op een intern netwerk dus andere browsers hoeven nu niet ondersteund te worden).

Echter verder dan het onderstaande kan ik niet komen omdat ik onvoldoende javascript ervaring heb, en geen programmeer achtergrond.

Live test-pagina

JavaScript:

function autoComplete(field, srcSelectId, property, forcematch, dstSelectId) {
    var firstIndex=null;
    //shortcuts
    var srcSelectOpt = document.getElementById(srcSelectId).getElementsByTagName('option');
    var dstSelectOpt = document.getElementById(dstSelectId).getElementsByTagName('option');

    //shortcuts for speedup
    var theInput = field.value.toUpperCase();
    var srcSelectOpt = document.getElementById(srcSelectId).getElementsByTagName('option');
    var dstSelectOpt = document.getElementById(dstSelectId).getElementsByTagName('option');
    var dstLength = dstSelectOpt.length;
    document.getElementById(srcSelectId).style.display = "none";
    //loop through templist
    for(var i = 0;i < dstLength;i++) {

        //IF user input is part of dstSelectId option
        if(dstSelectOpt[i][property].toUpperCase().indexOf(theInput) != -1){
            // move them back to srcSelectId list   
            trash = document.getElementById(dstSelectId).removeChild(dstSelectOpt[i]);
            document.getElementById(srcSelectId).appendChild(trash);
            dstLength = dstSelectOpt.length;
            i--;    
        }
    }
    document.getElementById(srcSelectId).style.display = "block";
    var srcLength = srcSelectOpt.length;    
    
    var srcSelectOpt = document.getElementById(srcSelectId).getElementsByTagName('option');
    var dstSelectOpt = document.getElementById(dstSelectId).getElementsByTagName('option');
    var srcLength = srcSelectOpt.length;
    document.getElementById(srcSelectId).style.display = "none";
    //loop through mainlist
    for(var i = 0;i < srcLength;i++) {

        //IF user input is NOT  part of srcSelectId option
        if(srcSelectOpt[i][property].toUpperCase().indexOf(theInput) == -1){
            // move them to dstSelectId list    
            trash = document.getElementById(srcSelectId).removeChild(srcSelectOpt[i]);
            document.getElementById(dstSelectId).appendChild(trash);
            srcLength = srcSelectOpt.length;
            i--;    
        }
    }
    document.getElementById(srcSelectId).style.display = "block";
    var srcLength = srcSelectOpt.length;    
}

HTML:

<form id="UnitSelect" name="UnitSelect" method="POST">
<select name="temp2" id="temp2" style="display:none"></select>

<strong style="color:#fff">Search list: </strong>
    <input name="input2" value="" onkeyup="autoComplete(this,'D1','text',true,'temp2')" type="text"><span style="color:#fff">or select from the list below (list is affected by input):</span><br>
    <select name="D1" id="D1" size="10" style="width:70%;">
    
    <option value="DE3535|2D Digital Imaging and Animation">2D Digital Imaging and Animation                                                                                        &nbsp;(DE3535)</option>
    
</select><input type="submit"  value=" GO " name="doSubmit2" onClick="UnitScript('UnitSelect','D1');">
</form>

[ Voor 37% gewijzigd door Justice op 14-03-2005 10:30 . Reden: overbodig commentaar verwijderd ]

[André]

Ik zie 2 keer dat je getElementByTagName gebruiken waar je ook gewoon door de childs heen kunt lopen. Je kunt de for lussen ook naar 0 toe laten lopen (dat scheelt ietsje).

Wat misschien beter is is een array bijhouden met alle waardes, die kan veel sneller doorlopen worden op eventuele matches. Je kunt een 2D array maken waar je alle waardes en references naar de options in zet, dan kun je heel makkelijk de juiste options heen en weer gooien.

[ Voor 22% gewijzigd door André op 11-03-2005 12:34 ]

[Justice]

Maar als ik zo'n array gebruik, dan moet ik toch alsnog de DOM doorlopen om opties te verhuizen? Dat zou dan toch juist langzamer zijn ipv sneller?

voor de duidelijkheid, de opties verhuizen is echt het knelpunt, maar ik kan het niet sneller krijgen dan:

JavaScript:

    //shortcuts zodat binnen de loop minder doorlopen hoeft te worden
    var srcSelectOpt = document.getElementById(srcSelectId).getElementsByTagName('option');
    var dstSelectOpt = document.getElementById(dstSelectId).getElementsByTagName('option');
    var srcLength = srcSelectOpt.length;

    for(var i = 0;i < srcLength;i++) {
        //IF user input is NOT  part of srcSelectId option
        if(srcSelectOpt[i][property].toUpperCase().indexOf(theInput) == -1){
            // move them to dstSelectId list    
            trash = document.getElementById(srcSelectId).removeChild(srcSelectOpt[i]);
            document.getElementById(dstSelectId).appendChild(trash);
            srcLength = srcSelectOpt.length;
            i--;    
        }
    }

[ Voor 74% gewijzigd door Justice op 14-03-2005 11:38 . Reden: code toevoeging ]

[André]

Ik ben even met wat bezig geweest maar ik krijg het ook niet sneller. Ipv verplaatsen verwijderd ik alleen de option en plaats hem in een array, vanuit daar kun je hem dan ook weer terugzetten. Maar je bottleneck blijft de indexOf en de removeChild en daar kun je weinig aan doen.

Een andere optie is het onkeyup event te vervangen door een zoekknop, want het is in wezen een zoekveld en geen autocomplete. Een autocomplete zou met substr werken, alleen dat is ook niet sneller dan de indexOf.

[crisp]

Je kan al een heleboel lookups voorkomen door dit te doen:

JavaScript:

var srcSelect = document.getElementById(srcSelectId);
...
trash = srcSelect.removeChild(...);

btw; je hoeft geen DOM remove/appendChild, getElementsByTagName e.d. te gebruiken. Je kan ook gewoon gebruik maken van de options-collection waar je gewoon doorheen kan lopen, kan verwijderen en aan kan toevoegen dmv new Option() - het zou me niets verbazen als dat sneller was.

Last but not least kan ik me ook voorstellen dat het zoeken in een reguliere JS array vele malen sneller is, en dat je wellicht zelfs nog beter na het filteren je hele select leeg kan gooien ( select.options.length = 0; ) en weer kan vullen.

[Verwijderd]

var i = foo.length;while(i--){} loops zijn zowiezo sneller

Maar tenzij je lijst duizenden elementen bevat vraag ik me af in hoeverre je de impact ervan gaat zien. Dit lijken me premature optimizations.