[JavaScript] Performancesteigerung für Suchalgorithmus

Dieses Thema im Forum "Webentwicklung" wurde erstellt von Flyde, 7. April 2010 .

Schlagworte:
Status des Themas:
Es sind keine weiteren Antworten möglich.
  1. 7. April 2010
    Performancesteigerung für Suchalgorithmus

    Hi,

    hab mir in JS ne Volltextsuche für Tabellen gebastelt, bei diesem möchte ich gerne die Performance steigern (evtl ist mein algorithmus auch einfach nur fürn ***** Hoffe das ich da n paar tricks in der FH Fach: Algorithmen und Datenstrukturen mir abschauen kann )

    Eine kleine Einleitung damit ihr überhaupt wisst um was es geht, wies funzt etc.


    Mein Script sucht in folgendem
    HTML:
    <table>
<thead>
<tr>
 <td>Titel der Spalte 1</td>
 <td>Titel der Spalte 2</td>
 ...
</tr>
</thead>
<tbody><!-- Hier schaut mein Script rein -->
<tr>
 <td>Datensatz 1</td>
 <td>Mit Inhalt etc.</td>
</tr>
<tr>
 <td>Datensatz 2</td>
 <td>Noch mehr Inhalt</td>
</tr>
...
</tbody><!-- // -->
</table>
    Ablauf meines Algorithmus:
    1. Bei Eingabe in das Suchtextfeld wird mein sogenannter "listener()" - das Script schnappt sich die einzelnen Spalten und haut sie in ein Array
    2. Es setzt alle tr auf style="display: none" (hab ich getestet, geht in allen Browsern mit nem Wimpernschlag bei 5000 Datensätzen)
    3. Es durchläuft alle zeilen der Tabelle (in tbody) und entfernt innerhalb dieser for schleife die HTML-Tags des derzeitigen Feldes
    4. Es vergleicht das Eingegebene mit dem, was in den einzelnen Spalten steht, wenn das ergebnis davon != null ist, wird die zeile angezeigt


    Leider sehe ich in Punkt 4 meinen Schwachpunkt... das Script funzt super bei mehreren 100 Datensätzen.. ich habe in meinem Test 5000 und in IE, FF und Opera brauch er zwischen 15 und 30 Sekunden bei 5000 Datensätzen, nur in Chrome brauch er 2-4 Sekunden was einem als User relativ Human vor kommt

    Punkt 3 habe ich neu hinzugefügt und hat die Sache nicht viel langsamer gemacht, alles gleichbleibend.

    Hier mein JS-Code
    HTML:
    // JavaScript Document
function SearchEngine(tbl, input)
{
 var myTbl = $(tbl).childElements()[1];
 var rows;
 var regExp;
 var myString;

 this.hideEverything = function()
 {
 myTbl.childElements().each( function(node) { node.hide(); } );
 }

 this.searchData = function()
 { 
 var inputText = $F(input);
 var ergebnis;
 
 for(i=0; i<rows; i++)
 { 
 // Inhalt: <tr><td>Spalte1</td><td>Spalte2</td></tr>
 myString = myTbl.childElements()[i].innerHTML; 
 // HTML-Tags entfernen
 myString = myString.replace(/(<([^>]+)>)/ig,""); 
 
 // inputText == Suchfeld
 regExp = new RegExp(inputText, "ig");
 ergebnis = regExp.exec(myString);
 
 // Wenn nicht null - zeige zeile
 if(ergebnis != null)
 { 
 myTbl.childElements()[i].show();
 }
 }
 }
 
 this.listener = function()
 {
 rows = myTbl.childElements().length;
 this.hideEverything(); 
 this.searchData();
 }
}
    Ebenfalls ist ein sehr starkes problem, dass die Browser bis auf Chrome alleins schon probleme haben nur 5000 Datensätze auszugeben, da der Quelltext sich dadurch elendig weit zieht, Firefox z.b. schießt sich komplett ab wenn man die Suche benutzt

    Vorschläge?
    Ist meine aller erste suchfunktion.. wenn sie bockmisst ist... bin für alles offen
     
  3. 7. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    ja das kann durchaus ein wenig dauern. die performance kannst du steigern indem du die funktion "myTbl.childElements()" nur einmal ausführst. die funktion ist nämlich nicht nativ und dauert a weng.

    Code:
    this.searchData = function()
{ 
 var inputText = $F(input);
 var ergebnis;
 var childs = myTbl.childElements();
 
 for(i=0; i<rows; ++i)
 { 
 // Inhalt: <tr><td>Spalte1</td><td>Spalte2</td></tr>
 myString = childs[i].innerHTML; 
 // HTML-Tags entfernen
 myString = myString.replace(/(<([^>]+)>)/ig,""); 
 
 // inputText == Suchfeld
 regExp = new RegExp(inputText, "ig");
 ergebnis = regExp.exec(myString);
 
 // Wenn nicht null - zeige zeile
 if(ergebnis != null)
 { 
 childs[i].show();
 }
 }
}
     
  4. 7. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    Hui, na klar.. kleine feinheit, großer unterschied
    In chrome geht die suche nahezu flüssig (aber hab ja auch grad n starkes testsystem..) und firefox stürzt nicht mehr ab, brauch aber so bei den ersten keywords 7-8 sekunden


    Wäre es sinnvoll noch nen timeout einzubauen? Quasi nach eingabe einer taste gebe dem User 2 sekunden zeit weitere buchstaben einzugeben, so ersparrt man sich das stück für stück suchen...
     
  5. 7. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    du könntest die siche aufteilen und in "timeouts" ausführen, dann blockt der browser nicht, das stimmt ^^

    und vergiss nicht die variable "myTbl" zu nullen, sonst bleibt das objekt im ram liegen und das muss auch ned sein
     
  6. 7. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    Danke, ich lass den Thread noch mal bis morgen auf, evtl fällt ja jemand anderem noch was ein ich find das thema algorithmen echt spannend und interessant
     
  7. 7. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    ich weiß nicht was rows beinhaltet ein array oder einfach nur ne zahl.
    ist auch egal, vielleicht hilft ne each schleife etwas mehr statt ne for schleife.
     
  8. 8. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    perfekte idee! ich weiß nicht was prototype so ultra gut macht aber jetzt funktioniert die suche in Firefox sogar flüssig!

    Ich denke jetzt ist die SuFu praxisbereit
    Müsste nurnoch die Ausgabe der Datensätze schneller rendern.. gibts ja auch einige tricks aber davon weiß ich leider noch zu wenig, whatever


    Wer die SuFu benutzen will:

    HTML:
    // JavaScript Document
function SearchEngine(tbl, input)
{
 var myTbl = $(tbl).childElements()[1];
 var rows;
 var regExp;
 var myString;

 this.hideEverything = function()
 {
 myTbl.childElements().each( function(node) { node.hide(); } );
 }

 this.searchData = function()
 { 
 var inputText = $F(input);
 var ergebnis;
 
 myTbl.childElements().each( function(i)
 { 
 // Inhalt: <tr><td>Spalte1</td><td>Spalte2</td></tr>
 myString = i.innerHTML; 
 // HTML-Tags entfernen
 myString = myString.replace(/(<([^>]+)>)/ig,""); 
 
 // inputText = Suchfeld
 regExp = new RegExp(inputText, "ig");
 ergebnis = regExp.exec(myString);
 
 // Wenn nicht null - zeige zeile
 if(ergebnis != null)
 { 
 i.show();
 }
 });
 }
 
 this.listener = function()
 {
 rows = myTbl.childElements().length;
 this.hideEverything(); 
 this.searchData();
 }
}
    Praxisnahe benutzung:

    HTML:
    <input type="text" onClick="Suche.listener();" id="suchfeld" />
<table id="myTbl">
<thead>
<tr>
 <td>Spalte 1</td>
 <td>Spalte 2</td>
</tr>
</thead>
<tbody>
<tr>
 <td>Inhalt 1</td>
 <td>Inhalt 2</td>
</tr>
<tr>
 <td>Noch mehr Inhalt</td>
 <td>Usw.</td>
</tr>
</tbody>
</table>
<script type="text/javascript">
Suche = new SearchEngine('myTbl', 'suchfeld');
</script>
    Das wars auch schon... kompatibel zu jeder tabelle egal wie verschachtelt die nur den Grundaufbau des thead und tbody einhält...

    Aber mehr möcht ich auch schon garnicht dazu sagen.. bald mach ich eh mal werbung für meinen blog in dem ich dann solche sachen und diverse andere sachen präsentiere

    Danke nochmal an alle, die die suche mitverbessert haben!
    bye
     
  9. 8. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    hab dein script mal überarbeitet

    Code:
    // JavaScript Document
function SearchEngine(tbl, input) {
 function _search() { 
 //muss nicht in die schleife
 var regex = new RegExp($F(input), "gi");
 
 //in modernen browsern nativ und schneller als childElements()
 var rows = $(tbl).select('tbody tr'); 
 
 for(var i = 0, l = rows.length; i < l; ++i)
 //aus zwei schleifen eine gemacht. wenn match->show; wenn nicht->hide
 rows[i][(rows[i].innerHTML.replace(/<[^>]+>/gi, '').match(regex)) ? 'show' : 'hide']();
 }
 
 this.listener = _search;
}
     
  10. 8. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    lol
    copy & paste und es klappt

    Hatte noch von 2 leuten ne PM bekommen (ich hab den thread bisl voreilig geschlossen :S) mit n paar vorschlägen aber mehr oder weniger sind da die ein oder anderen vorschläge schon kombiniert bzw. da die klasse jetzt sowas von klein ist... genial

    Das sind probleme, die einem Programmierer spaß machen, merke das schon

    edit: mir fällt auf, dadurch hast du aber meine theads zerschossen, denn ich hab ja spaltenüberschriften wie "Artikelnummer", "dies und jenes" etc. , die verschwinden bei benutzung deiner klasse, kann man den select auf tbody tr setzen?

    //done - mfg Murdoc
     
  11. 8. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    noch ein wenig optimiert, jetzt reichts aber

    Code:
    // JavaScript Document
function SearchEngine(tbl, input) {
 //"_search" deswegen um die funktion auch ohne klassen-kontext zu verwenden 
 //wenn du das nicht brauchst, kannst du "_search" auch entfernen
 this.listener = function _search() {
 //muss nicht in die schleife
 //mod: "g" nicht nötig. ein fund reicht, matched schneller
 var regex = new RegExp($F(input), "i");
 
 //in modernen browsern nativ und schneller als childElements()
 var rows = $(tbl).select('tbody tr'); 
 
 for(var i = 0, l = rows.length; i < l; ++i)
 //aus zwei schleifen eine gemacht. wenn match->show; wenn nicht->hide
 //mod: "i" im regex nicht nötig
 rows[i][(rows[i].innerHTML.replace(/<[^>]+>/g, '').match(regex)) ? 'show' : 'hide']();
 }
}
    noch schneller bist du in xpath-fähigen (xquery) browsern, das solltest du ggf. ausnutzen.
     
  12. 8. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    mh hab ich grad zum ersten mal gehört, erstmal coole verbesserungen..

    Hab gesehen firefox 3.6 wär da so ein fall für xpath kompatibilität... also kommt mir doch der gedanke: in chrome funktioniert die suche in echtzeit, in firefox z.b. nicht in echtzeit..

    SuFu dann folgendermaßen
    Wenn Browser xyz der xquery unterstüzt
    -> nutze diese funktionen
    andernfalls
    -> nutze standardfunktion

    in etwa so? müsste mir nur mal anschauen wie das alles klappt ... aber man lernt ja nie aus ^^
     
  13. 9. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    Kannst ja Browserweichen bauen das ist ja das geringerte übel. Da ist sich in xpath einarbeiten was schwerer denk ich^^ Wobei es doch eigentlich recht überschaubar ist
     
  14. 9. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    prototype nutzt ja für "select" auch xpath wenn vorhanden, aber das is ein wenig zu komplex. vorallem weißt du ned was der browser alles unterstützt usw.

    ich denk mit der lösung oben bist du gut dabei.
    aja, das script wird immer langsamer umso mehr tr's vorkommen, aber das is klar denk ich?
     
  15. 9. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    klar ist das klar, sonst würd ichs nicht für 5000 datensätze testen sondern nur für 50
     
  16. 10. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    ich weiß nicht wie das bei java script ist, aber könnte man nicht beim anlegen der seite einen b* baum erstellen z.b. für jede spalte.
    so ist es ja auch bei einem dbms.
     
  17. 10. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    nein das wäre schwachsinnig, was willt du denn mit nem b-baum wenn du nur strings hast die du ALLE mit nem regexp testen musst?

    in wie fern hast du dir das vorgestellt?
     
  18. 11. April 2010
    AW: Performancesteigerung für Suchalgorithmus

    ja ist mir danach auch mal eingefallen. geht ja gar nicht.

    eine etwas kleinere optimierung wäre es, wenn man am anfang prüft ob überhaupt irgendein treffer vorhanden ist.
    sollte das nicht sein, so kann man sich das suchen gleich spaaren und einfach alles auf invisible stellen.

    ich weiß nicht mehr genau wie viele datensätze das bei dir waren, aber bei 5k oder mehr würde es sich sicher lohnen die datensätze vor dem vergleichen in 1k pakete zu paken und dann immer prüfen ob im paket etwas gefunden wird.
     
  19. 9. August 2010
    AW: Performancesteigerung für Suchalgorithmus

    hätte ja dann doch noch was, das mir jetzt erst aufgefallen ist...

    Das Ding funktioniert ja mit RegExp, wie kann ich jetzt nach sonderzeichen suchen? Hatte was mit escape() versucht, klappte nicht..

    Beispiel: "Firma x.y.z" man sucht "Firma x" und es kommt der richtige treffer, man sucht "Firma x." und es gibt 0 treffer
     
  20. 9. August 2010
    AW: Performancesteigerung für Suchalgorithmus

    RegExp.quote()
     
  21. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.