nicht angemeldet
"Drossel" in Schleife einbauen?
Hallo,
ich habe ein Script, welches mit recht komplexen regulären Ausdrücken eine Seite nach Glossarbegriffen durchsucht und gefundene Begriffe durch DFN-Nodes ersetzt.
Das funktioniert an sich mittlerweile tadellos.
Leider habe ich das Ganze während der Entwicklung nur mit 5, 6 Glossarbegriffen getestet. Jetzt mußte ich aber bei einem Probelauf mit der kompletten Glossarliste (80 Begriffe) feststellen, daß meine Anwendung den Browser und den kompletten Rechner bei umfangreicheren Seiten für 1 Minute und mehr komplett auslastet und damit lahmlegt.
Ich habe den Eindruck, daß die Gesamtzeit etwas kürzer ist, d.h. die Performance etwas besser, wenn ich zwischendurch Test-Alerts ausgebe und damit das Script immer wieder unterbreche.
Frage 1 dazu: haltet Ihr das für plausibel, oder bilde ich mir das ein?
Nun bin ich auf den Gedanken gekommen, eine Art "Drossel" in meine Glossarfunktion einzubauen, die - wie die Test-Alerts - die Programmausführung bzw. die Schleifendurchläufe ein wenig bremst.
Mit setTimeout() und setInterval() komme ich nicht weiter, da es sich um eine rekursive Funktion handelt, die noch dazu ein Objekt als Parameter erwartet.
Grundsätzlich in aller Kürze Folgendes zu meinem Ansatz:
Mein Script basiert hauptsächlich auf einer rekursiven Funktion, die sich, beginnend bei einem bestimmten Knoten (einem DIV mit der id "content"), durch dessen Unterelemente hangelt und jeden Textknoten in einer for-Schleife, die über einen Array mit den Glossarbegriffen iteriert, nach den Glossarbegriffen durchsucht (mittels exec()).
Vermutlich stoße ich mit diesem Script schlicht und einfach an die Grenzen der Leistungsfähigkeit von Browsern.
Aber vielleicht habt Ihr ja Anregungen?
Thanx und ciao,
Andreas
-
Hi,
ich habe ein Script, welches mit recht komplexen regulären Ausdrücken eine Seite nach Glossarbegriffen durchsucht und gefundene Begriffe durch DFN-Nodes ersetzt.
Was auch immer DFN-Nodes sein mögen. Aber egal: "komplexen reguläre Ausdrücke" sind teuer. Jedes Wort in einer Seite damit abzuklappern ist noch teurer. Diese Kombination in Javascript skaliert auch nur mehr schlecht als recht -- um es mal ganz vorsichtig auszudrücken.
Das funktioniert an sich mittlerweile tadellos.
Leider habe ich das Ganze während der Entwicklung nur mit 5, 6 Glossarbegriffen getestet. Jetzt mußte ich aber bei einem Probelauf mit der kompletten Glossarliste (80 Begriffe) feststellen, daß meine Anwendung den Browser und den kompletten Rechner bei umfangreicheren Seiten für 1 Minute und mehr komplett auslastet und damit lahmlegt.Schon bei 80? Dann stimmt höchstwahrscheinlich der Algorithmus nicht oder die Maschine ist nur ein 486er.
Ich habe den Eindruck, daß die Gesamtzeit etwas kürzer ist, d.h. die Performance etwas besser, wenn ich zwischendurch Test-Alerts ausgebe und damit das Script immer wieder unterbreche.
Frage 1 dazu: haltet Ihr das für plausibel, oder bilde ich mir das ein?Das ist Einbildung. Kann ich aber nachvollziehen, geht mir manchmal genauso. Messungen ergeben aber, das es natürlich mit der Alert-Ausgabe länger dauert.
Grundsätzlich in aller Kürze Folgendes zu meinem Ansatz:
Mein Script basiert hauptsächlich auf einer rekursiven Funktion, die sich, beginnend bei einem bestimmten Knoten (einem DIV mit der id "content"), durch dessen Unterelemente hangelt und jeden Textknoten in einer for-Schleife, die über einen Array mit den Glossarbegriffen iteriert, nach den Glossarbegriffen durchsucht (mittels exec()).Aha, ich habe schon so meine Vermutungen:
Zum einen: wofür sind die Regexe genau? Normalerweise brauchst Du für den beschriebenen Zweck keine.Durchsuchst Du das Array linear oder hast Du ein assoziatives Array gebastelt?
Ich hätte das so gelöst:
glossar = new Array();
glossar["wort1"] = "Definition für Wort 1";
glossar["wort2"] = "Definition für Wort 2";
glossar["wort3"] = "Definition für Wort 3";
...text = textknoten.split(" ");
for(var i = 0;i < text.length;i++){
if(glossar[ text[i] ] != 'undefined')
makeDFNNode(text[i]);
}Das sollte so halbwegs skalieren und ist vielleicht auch noch anderweitig optimierbar. Weniger Text z.B. Nein, ernstgemeint: besser mehr Seiten mit weniger Text als einige zu große. Das JS extern halten, dann wird das schonmal gecached (aber trotzdem jedesmal neu geparsed, leider) und nur der Text wird ausgetauscht.
Vermutlich stoße ich mit diesem Script schlicht und einfach an die Grenzen der Leistungsfähigkeit von Browsern.
Nein, am Browser/Compiler/Interpreter liegt's eher selten >;->
so short
Christoph Zurnieden
-
Hallo,
Dann stimmt höchstwahrscheinlich der Algorithmus nicht oder die Maschine ist nur ein 486er.
Ich nehme an, Andreas meint einen Algorithmus wie in </archiv/2004/9/t88864/#m530093> ff. (DOM oder innerHTML und RegExps). Vielleicht sollte er seinen Ansatz einmal in Codeform vorstellen. Ich glaube nicht, dass sich am grundlegenden Vorgehen viel optimieren lässt und glaube durchaus, dass solches Gefummel am Knotenbaum dermaßen lahm ist. Clientseitiges Scripting ist ein denkbar ungeeignetes Mittel für diese Aufgabe.
Durchsuchst Du das Array linear oder hast Du ein assoziatives Array gebastelt?
(Es gibt keine assoziativen Arrays in JavaScript.)
Ich hätte das so gelöst:
glossar = new Array();
(new Object())
glossar["wort1"] = "Definition für Wort 1";
glossar["wort2"] = "Definition für Wort 2";
glossar["wort3"] = "Definition für Wort 3";
...text = textknoten.split(" ");
An sich performant, aber man muss bedenken, dass man beim Erstellen der neuen Knoten eigentlich drei Strings für drei Textknoten braucht: Der String vom Anfang des Textknotens bis zum Wort, das Wort selbst, der String vom Wort bis zum Ende des Textknotens. Daraus wird dann ein Textknoten, ein Elementknoten mit dem Wort als Textknoten und ein weiterer Textknoten.
[a b c d e]
Wenn »c« ersetzt wird:
[a b ]-(DFN)-[ d e]
|
[c]Wenn der Textknoten »a b c d e« aufgespalten wird, jedes Wort mit dem Glossar verglichen wird, ist beim Finden eines Treffers vor allem die Position des Wortes im String interessant, damit der String dreigeteilt werden kann. Beim Durchlaufen des text-Arrays müsste man z.B. durch das Addieren der Teilstringlängen also eine gegenwärtige Position im String ausrechnen.
Wenn makeDFNNode nun direkt Änderungen am Knotenbaum vornimmt (siehe oben), kann zwar weiter mit dem text-Array gearbeitet werdne, es muss beachtet werden, dass der Anfang des Strings nun bei » d e« liegt. Wenn »d« im Glossar steht, müsste entsprechend herauskommen:
[a b ]-(DFN)-[ ]-(DFN)-[ e]
| |
[c] [d]
usw.Leider wird dieser Ansatz prinzipiell schlecht funktionieren. Ein Text ist keine Liste von Lemmata, die durch Leerzeichen getrennt sind. Daher müssen wahrscheinlich doch reguläre Ausdrücke herhalten, um erst einmal die Worte zu finden. Und selbst die können schwer direkt mit Glossareinträgen verglichen werden (Stichwort Flexion).
for(var i = 0;i < text.length;i++){
if(glossar[ text[i] ] != 'undefined')Soll das JavaScript sein? Nicht existente Objekte kann man nicht mit dem String "undefined" vergleichen, das wird einen Fehler erzeugen. Es gibt das Keyword undefined, das ist aber eine ganz andere Geschichte, denn das bezieht sich auf absichtlich als undefined initialisierte Variablen (var bla;, nicht übergebene, aber in der Parameterliste aufgeführte Funktionsparameter). Dann gibt es den typeof-Operator, der unter anderem auch den String "undefined" zurückgeben kann. Der wäre hier wohl am sinnvollsten.
Mathias
-
Hi,
Clientseitiges Scripting ist ein denkbar ungeeignetes Mittel für diese Aufgabe.
Und für viele andere Aufgaben auch. Aber mitunter läßt es sich leider nicht umgehen.
Allerdings: das Script soll ein S&R vollziehen. Das könnte man eigentlich auch schon vorher machen, oder? Leider sind ja rein gar keine Details vorhanden.Durchsuchst Du das Array linear oder hast Du ein assoziatives Array gebastelt?
(Es gibt keine assoziativen Arrays in JavaScript.)
Ja, aber ich hatte keine Lust auf lange Erklärungen.
Die darf ich ja _jetzt_ auch getrost Dir überlassen ;-)Ich hätte das so gelöst:
glossar = new Array();
(new Object())
Da im Grunde fast das gleiche dient es hier der Lesbarkeit.
An sich performant, aber man muss bedenken, dass man beim Erstellen der neuen Knoten eigentlich drei Strings für drei Textknoten braucht: Der String vom Anfang des Textknotens bis zum Wort, das Wort selbst, der String vom Wort bis zum Ende des Textknotens. Daraus wird dann ein Textknoten, ein Elementknoten mit dem Wort als Textknoten und ein weiterer Textknoten.
Ja, das ist natürlich korrekt, darunter geht's nicht.
[a b c d e]
Wenn »c« ersetzt wird:
[a b ]-(DFN)-[ d e]
|
[c]Wenn der Textknoten »a b c d e« aufgespalten wird, jedes Wort mit dem Glossar verglichen wird, ist beim Finden eines Treffers vor allem die Position des Wortes im String interessant, damit der String dreigeteilt werden kann. Beim Durchlaufen des text-Arrays müsste man z.B. durch das Addieren der Teilstringlängen also eine gegenwärtige Position im String ausrechnen.
Hier würde ich brutal verfahren und einfach das Textarray teilen, den DFN-Knoten einbauen und weiterfahren. Jeder weitere Fund wäre dann einmal der Anfangsabschnitt vom Textarray ab DFN-Knoten, der ist direkter Verwandter vom DFN bzw mit etwas Vorsorge lastChild vom Parent, dann der neue DFN-Knoten, dann der Rest vom Textarray falls vorhanden. Ad finitum. Längenzählung ist hierbei nicht nötig, da an "Sollbruchstellen" geteilt wird.
Macht es aber auch nicht gerade signifikant schneller, zugegeben ;-)
Leider wird dieser Ansatz prinzipiell schlecht funktionieren. Ein Text ist keine Liste von Lemmata, die durch Leerzeichen getrennt sind.
Das weiß man nicht, dazu fehlen die Informationen.
Aber dürfte wohl normaler Text sein, nehme ich auch an.Daher müssen wahrscheinlich doch reguläre Ausdrücke herhalten, um erst einmal die Worte zu finden. Und selbst die können schwer direkt mit Glossareinträgen verglichen werden (Stichwort Flexion).
Tja, Stemming in Javascript wäre doch mal eine interessante Aufgabe ;-)
Aber stimmt schon: mein Vorschlag setzt natürlich voraus, das alle Daten im Vornherein bekannt sind.
Ich tendiere aber auch, wie bereits angedeutet, dazu Dir zuzustimmen: das ganze ist keine gute Idee, das sollte der Kollege anders lösen. Oder zumindest Einzelheiten verraten, damit man hier nicht so im Trübem fischen muß.
for(var i = 0;i < text.length;i++){
if(glossar[ text[i] ] != 'undefined')Soll das JavaScript sein? Nicht existente Objekte kann man nicht mit dem String "undefined" vergleichen,
Hä?
Argh! Jaja, so geht's *sigh*
Der hier:war auf jeden Fall noch drin, als ich es ausprobiert hatte:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><title>Test</title></head><body>
<script type="text/javascript">
<!--
var glossar = new Array();
glossar["nix"]="definition nix";
glossar["Weg"]="Korrekt!";var Satz = "Wer nicht vom rechten Weg abkommt bleibt auf der Strecke";
var Woerter = Satz.split(" ");
document.write("Ein Satz mit " + Woerter.length + " Wörtern.<br>");
document.write("typeof glossar[ bla ] = " + (typeof glossar['bla']) );
//-->
</script></body></html>(Na? Kommt's bekannt vor? ;-)
Ja sowas _peinliches_ aber auch!
so short
Christoph Zurnieden
-
An sich performant, aber man muss bedenken, dass man beim Erstellen der neuen Knoten eigentlich drei Strings für drei Textknoten braucht: Der String vom Anfang des Textknotens bis zum Wort, das Wort selbst, der String vom Wort bis zum Ende des Textknotens. Daraus wird dann ein Textknoten, ein Elementknoten mit dem Wort als Textknoten und ein weiterer Textknoten.
Genau so funktioniert mein Script. Und genau darum (und wegen des Problems der Flexion und der Komposita) komme ich nicht um reguläre Ausdrücke herum.
Noch zur Erläuterung: ich hatte nicht vor, solch ein Script in die produktive Website einzubauen. Mein "Glossar-Assistent" sollte meine Kollegen bei der Arbeit unterstützen, die für Inhalte und damit auch für die Auszeichnung von Glossarbegriffen zuständig sind.
Ursprünglich hatte ich einen serverseitigen Ansatz mit PHP - allerdings muß man dort mit weitaus komplexeren regulären Ausdrücken anrücken, da PHP an sich ja erst einmal nicht von DOM weiß.
An anderer Stelle in diesem Thread wurde aber auf ein DOM-Modul bzw- eine solche Bibliothek für PHP hingewiesen. Ich denke, ich werde mir das einmal ansehen. Der browserbasiert Ansatz scheint mir jedenfalls eine Sackgasse zu sein. Ich sehe da keine Optimierungsmöglichkeiten mehr.Danke an alle hier für die Diskussion und die Anregungen!
Andreas
-
-
-
Sup!
Es ist unwahrscheinlich, dass es schneller geht, wenn Du klickst - es kommst Dir wahrscheinlich nur so vor. Vielleicht kannst Du eine "Prozentanzeige" implementieren, damit die leute beim Warten etwas unterhalten werden - das beschleunigt die Sache psychologisch.
Gruesse,
Bio
--
Keep your friends close, but your enemies closer!-
Vielleicht kannst Du eine "Prozentanzeige" implementieren, damit die leute beim Warten etwas unterhalten werden - das beschleunigt die Sache psychologisch.
Gruesse,
Bio:)
Jau - gute Idee....
-
-
Hallo,
ich habe ein Script, welches mit recht komplexen regulären Ausdrücken eine Seite nach Glossarbegriffen durchsucht und gefundene Begriffe durch DFN-Nodes ersetzt.
Man könnte sich wohl eine Woche hinsetzen und groß angelegte Tests verschiedener Algorithmen machen, die den Knotenbaum vollkommen auf den Kopf stellen. Ich bezweifle aber ernsthaft, dass dabei eine brauchbare und halbwegs performante Lösung herauskommt, die zudem in genügend Browsern zuverlässig funktioniert. Man kann sicher mathematisch berechnen, wieviele Stringvergleiche beim Durchlaufen eines gewissen Textes mit gewissen Wortvorkommen notwendig sind. Pi mal Daumen sind es bei einer so großen Anzahl von Begriffen soviele, dass indexOf() oder RegExp einen Flaschenhals bilden werden.
Ich sehe keine Hoffnung darin, diese Aufgabe mit JavaScript lösen zu können. Wenn du einen halbwegs ausgegorenen Algorithmus schon hast, kannst du dein Konzept ändern und diese Ersetzungen serverseitig vornehmen. Zum Beispiel mit dem DOM-Modul von PHP 5 zusammen mit dessen RegExp-Engine.Mein Script basiert hauptsächlich auf einer rekursiven Funktion, die sich, beginnend bei einem bestimmten Knoten (einem DIV mit der id "content"), durch dessen Unterelemente hangelt und jeden Textknoten in einer for-Schleife, die über einen Array mit den Glossarbegriffen iteriert, nach den Glossarbegriffen durchsucht (mittels exec()).
Das Script würde mich interessieren, im anderen Posting habe ich ein ähnliches einfaches verlinkt.
Mathias
-