Script sehr langsam - wie optimieren?

[Philipp.]

Hi,

ich bastel gerade an einem Script für eine Suchmaschine, das zwar an und für sich gut funktioniert, jedoch recht langsam ist. Gibts vielleicht eine Möglichkeit, da was zu optimieren?

Was das Script macht: gibt der Besucher als Suchbegriff mehrere Wörter ein zu denen nichts gefunden wird, soll mit der Levenshteinfunktion eine Alternative vorgeschlagen werden. Im Moment gehe ich davon aus, dass die eingegebenen Wörter direkt hintereinander stehen (also quasi eine Suche in Anführungszeichen "wort1 wort2"). Damit nur direkt hintereinander stehende Wörter gefunden werden können, lese ich die Datei, die bei der Suche durchsucht wird ein, und erzeuge immer 2-er Gruppen der darin enthaltenen Wörter (bzw. entsprechend längere Gruppen, wenn mehr Wörter eingegeben wurde).

Bspw. steht in der Datei: "Heute ist ein schöner Tag." Daraus mache ich: "Heute ist", "ist ein", "ein schöner", "schöner Tag".

Diese Gruppen lassen sich ja nun sehr einfach mit dem eingegebenen Suchbegriff vergleichen. Doch diese Gruppenerzeugung ist wohl die Bremse, pro zusätzlichem eingebenen Wort steigt die Ladezeit der Seite um ca. 0.65 sec. (eine Suche mit einem einzigen Begriff ohne diese Gruppen dauert ca. 0.2 sec.).

Ich dachte schon zu Beginn, dass das vermutlich sehr rechenintensiv würde, aber eine Alternative fällt mir eigentlich nicht ein. Hat vielleicht jemand eine Idee, was man da ändern könnte (Google kriegts doch auch hin ;))?

Hier das Script (nicht lachen ;-)):

<?php  
  
$searchexp = $_GET['searchexp'];                            #Variable mit Suchbegriffen  
$anz_searchexp = count($searchexp);                         #Anzahl der Suchbegriffe ermitteln  
$words = array();                                           #Array in dem am Ende die relevanten Alternativen stehen  
$gruppe_liste = array();                                    #Array in dem alle Gruppen gespeichert werden  
  
$datei = "data.txt";                                        #Datei die durchsucht wird, öffnen und einlesen  
$zeilen = file($datei);  
$anz_zeilen = sizeof($zeilen);                              #Zeilenanzahl ermitteln  
  
if($anz_searchexp >1)                                       #Prüfen ob der Suchbegriff aus mehreren Wörtern besteht  
{  
  for($i=0; $i<$anz_zeilen; $i++)                           #Schleife durchlaufen bis letzte Zeile erreicht  
  {  
  list (, , , , $inhalt) = split("\\|", chop($zeilen[$i])); #Split um unnötigen Text nicht einzulesen  
  
  $inhalt = trim($inhalt);  
  
  $liste = preg_split('/[\s,.]+/i', $inhalt);               #Array mit Wörtern erzeugen, split bei Leerzeichen , .  
  $anz_liste = count($liste);                               #Anzahl der Wörter ermitteln  
  
  for($j=0; $j < ($anz_liste - ($anz_searchexp - 1)); $j++) #Schleife durchlaufen, bis die letzte mögliche Gruppe erzeugt ist  
  {  
    $k = 1;  
    $arr_grppe = array();                                   #Array in dem die Wörter pro Gruppe gespeichert werden / Zurücksetzen von der letzten Gruppe  
    foreach($liste as $word)                                #Schleife durchlaufen bis die Gruppe so viele Wörter enthält wie der Suchbegriff  
    {  
      if($k <= $anz_searchexp)  
      {  
        array_push($arr_gruppe,$word);  
        $k++;  
      }  
    }  
    $gruppe_searchexp = implode(".-.",$arr_gruppe);         #Suchbegriffe zu String zusammenfügen, .-. als Platzhalter um die Wörter später trennen zu können  
    array_push($gruppe_liste,$gruppe_searchexp)             #Array in dem alle Gruppen gespeichert werden  
    unset($liste[$j]);                                      #Erstes Wort aus dem Array löschen, nächste Gruppe beginnt bei Wort $liste[$j+1]  
  }  
}  
  
...  
..  
.  
?>

Vielleicht sagt ja jemand "Das geht doch viiiiieeeeel einfacher" :)
Danke schon mal an alle, die sich die Mühe machen das alles zu lesen.

[Sven Rautenberg]

Moin!

Was das Script macht: gibt der Besucher als Suchbegriff mehrere Wörter ein zu denen nichts gefunden wird, soll mit der Levenshteinfunktion eine Alternative vorgeschlagen werden.

Und genau das ist vermutlich die langwierige Operation, die du optimieren müßtest.

Diese Gruppen lassen sich ja nun sehr einfach mit dem eingegebenen Suchbegriff vergleichen. Doch diese Gruppenerzeugung ist wohl die Bremse, pro zusätzlichem eingebenen Wort steigt die Ladezeit der Seite um ca. 0.65 sec. (eine Suche mit einem einzigen Begriff ohne diese Gruppen dauert ca. 0.2 sec.).

Hast du durch Zeitmessungen nachgeprüft, welche Skriptteile wieviel Zeit verbrauchen.

Ich dachte schon zu Beginn, dass das vermutlich sehr rechenintensiv würde, aber eine Alternative fällt mir eigentlich nicht ein. Hat vielleicht jemand eine Idee, was man da ändern könnte (Google kriegts doch auch hin ;))?

Google hat Millionen Rechner stehen und arbeitet massiv parallel, du nur einen einzigen.

Hier das Script (nicht lachen ;-)):

Das hat mindestens einen Syntax- sowie einen kräftigen Logikfehler und kann daher nicht das Original sein. Abgesehen davon fehlt Levenshtein.

- Sven Rautenberg

[Philipp.]

Das hat mindestens einen Syntax- sowie einen kräftigen Logikfehler und kann daher nicht das Original sein. Abgesehen davon fehlt Levenshtein.

Hi,

darf ich fragen, welche Fehler du meinst? Kann sein, dass ich mich bei den zig Variablennamen verfranst habe.

Der Levenshteinvergleich kommt direkt danach, bremst das Script aber nicht aus, das habe ich mit einem Script, dass die Ladezeit berechnet, getestet; mit nur einem Suchbegriff läuft das Script ja wie gesagt einwandfrei.

[Sven Rautenberg]

Moin!

Das hat mindestens einen Syntax- sowie einen kräftigen Logikfehler und kann daher nicht das Original sein. Abgesehen davon fehlt Levenshtein.

Hi,

darf ich fragen, welche Fehler du meinst? Kann sein, dass ich mich bei den zig Variablennamen verfranst habe.

Es fehlt eine schließende geschweifte Klammer, und es erscheint mir unlogisch, count() auf einen String anzuwenden.

Der Levenshteinvergleich kommt direkt danach, bremst das Script aber nicht aus, das habe ich mit einem Script, dass die Ladezeit berechnet, getestet; mit nur einem Suchbegriff läuft das Script ja wie gesagt einwandfrei.

DU mußt levenshtein() aber doch auf alle Kombinationen von gesuchtem Wort und gefundener Alternative anwenden. Das soll nicht aufwendig sein?

- Sven Rautenberg

[Philipp.]

Okay, du hattest wohl recht - hab das Script für die Laufzeit falsch platziert ...

Der oben gepostete Code dauert immer relativ gleich lange, levenshtein bremst dann.

Der entsprechende Code sieht so aus:

<?php  
}                                 #Die Klammer, die oben fehlt  
  
foreach ($gruppe_liste as $gruppe_searchexp)  
{  
  $prozent = (1-levenshtein(strtolower($arr_searchexp), strtolower($gruppe_searchexp))/max(strlen($arr_searchexp), strlen($gruppe_searchexp))); #Zu wieviel % stimmt die jeweilige Gruppe ($gruppe_searchexp) mit dem eingegebenen Suchbegriff ($arr_searchexp) überein  
  
  if((levenshtein(strtolower($arr_searchexp),strtolower($gruppe_searchexp)) <= $focus) && $prozent >= 0.5) #Der lev.-Wert muss kleiner sein als ein vom Suchbegriff abhäniger Wert ($focus = strlen($suchbegriff ...), die Gruppe muss zu 50% mit dem Suchbegriff übereinstimmen  
  
  {  
    if(!array_key_exists($gruppe_searchexp,$words)) #Prüfen, ob das Wort schon exisitert  
    {  
      $word = str_replace('.-.',' ',$gruppe_searchexp);  
      $words[$word] = $prozent;  
    }  
  }  
}  
?>

$word sind dann meine Alternativen.

Was ließe sich da vielleicht verbessern?

Und wegen dem count(). Dachte, dass das so in Ordnung ist; laut php.net: "count — Zählt die Elemente einer Variable oder Attribute eines Objekts"

[Sven Rautenberg]

Moin!

<?php

foreach ($gruppe_liste as $gruppe_searchexp)
{
  $prozent = (1-levenshtein(strtolower($arr_searchexp), strtolower($gruppe_searchexp))/max(strlen($arr_searchexp), strlen($gruppe_searchexp))); #Zu wieviel % stimmt die jeweilige Gruppe ($gruppe_searchexp) mit dem eingegebenen Suchbegriff ($arr_searchexp) überein

if((levenshtein(strtolower($arr_searchexp),strtolower($gruppe_searchexp)) <= $focus) && $prozent >= 0.5) #Der lev.-Wert muss kleiner sein als ein vom Suchbegriff abhäniger Wert ($focus = strlen($suchbegriff ...), die Gruppe muss zu 50% mit dem Suchbegriff übereinstimmen

{
    if(!array_key_exists($gruppe_searchexp,$words)) #Prüfen, ob das Wort schon exisitert
    {
      $word = str_replace('.-.',' ',$gruppe_searchexp);
      $words[$word] = $prozent;
    }
  }
}
?>

>   
> `$word`{:.language-php} sind dann meine Alternativen.  
>   
> Was ließe sich da vielleicht verbessern?  
  
Du kannst die Laufzeit vermutlich halbieren, indem du die levenshtein-Funktion pro Parametersatz nur einmal aufrufst und deren Ergebnis speicherst.  
  
Ansonsten kannst du die Laufzeit dieser Funktion nur verbessern, wenn du PHP verläßt.  
  
Eine Alternative dazu wäre, die Ergebnisse der Funktion in Abhängigkeit von den Eingabeparametern zwischenzuspeichern, und diesen Zwischenspeicher zuerst zu durchsuchen. Das könnte möglicherweise schneller sein, als der Funktionsaufruf selbst, erfordert aber logischerweise entsprechend viel Speicherplatz.  
  

> Und wegen dem count(). Dachte, dass das so in Ordnung ist; laut php.net: "count — Zählt die Elemente einer Variable oder Attribute eines Objekts"  
  
Bei einem String kommt da immer 1 raus. count() ist nur sinnvoll für Arrays. Oder für Objekte in PHP 5, die das Interface "Countable" implementieren.  
  
 - Sven Rautenberg

-- 
"Love your nation - respect the others."

[C-Bra]

Und wegen dem count(). Dachte, dass das so in Ordnung ist; laut php.net: "count — Zählt die Elemente einer Variable oder Attribute eines Objekts"

Bei einem String kommt da immer 1 raus. count() ist nur sinnvoll für Arrays. Oder für Objekte in PHP 5, die das Interface "Countable" implementieren.

• Sven Rautenberg

Nein, es kommt nicht immer 1 raus.
Es "kann" einem die tatsächliche Anzahl der Zeichen geben.

http://at.php.net/manual/de/function.strlen.php#13102
Note that PHP does not need to traverse the string to know its length with strlen(). The length is an attribute of the array used to store the characters. Do not count on strings being terminated by a NULL character.

[Sven Rautenberg]

Moin!

Und wegen dem count(). Dachte, dass das so in Ordnung ist; laut php.net: "count — Zählt die Elemente einer Variable oder Attribute eines Objekts"

Bei einem String kommt da immer 1 raus. count() ist nur sinnvoll für Arrays. Oder für Objekte in PHP 5, die das Interface "Countable" implementieren.

• Sven Rautenberg

Nein, es kommt nicht immer 1 raus.
Es "kann" einem die tatsächliche Anzahl der Zeichen geben.

Die Ziehung der Lottozahlen "kann" einem auch die tatsächliche Anzahl der Zeichen geben.

Sofern die Anzahl der Zeichen im String 1 ist, hast du Recht. Und count() liefert für eine Variable, die NULL enthält, auch den Wert 0 zurück. Trotzdem besteht grundsätzlich zwischen der Länge eines Strings und dem Rückgabewert von count() kein Zusammenhang.

http://at.php.net/manual/de/function.strlen.php#13102
Note that PHP does not need to traverse the string to know its length with strlen(). The length is an attribute of the array used to store the characters. Do not count on strings being terminated by a NULL character.

Du vergleichst offenbar Äpfel und Birnen - also count() und strlen().
Was hat der Kommentar zur Funktion strlen() mit der Funktion count() zu tun?

- Sven Rautenberg

[C-Bra]

Die Ziehung der Lottozahlen "kann" einem auch die tatsächliche Anzahl der Zeichen geben.

Sofern die Anzahl der Zeichen im String 1 ist, hast du Recht. Und count() liefert für eine Variable, die NULL enthält, auch den Wert 0 zurück. Trotzdem besteht grundsätzlich zwischen der Länge eines Strings und dem Rückgabewert von count() kein Zusammenhang.

http://at.php.net/manual/de/function.strlen.php#13102
Note that PHP does not need to traverse the string to know its length with strlen(). The length is an attribute of the array used to store the characters. Do not count on strings being terminated by a NULL character.

Du vergleichst offenbar Äpfel und Birnen - also count() und strlen().
Was hat der Kommentar zur Funktion strlen() mit der Funktion count() zu tun?

• Sven Rautenberg

Hach,
das gibt's fast nicht das das nicht funktioniert.
Ich war mir 100%ig sicher das es funktioniert, aber du hast mich eines besseren belehrt.

Das Augenmerk liegt auf dem Satz:
»The length is an attribute of the array used to store the characters
Also wäre count() durchaus möglich gewesen.
Jedoch funktioniert die Sache nicht.

Gruß,
Daniel

[Philipp.]

Du kannst die Laufzeit vermutlich halbieren, indem du die levenshtein-Funktion pro Parametersatz nur einmal aufrufst und deren Ergebnis speicherst.

Sehr gute Idee - so viel bringt das aber leider gar nicht :(

Bei einem String kommt da immer 1 raus. count() ist nur sinnvoll für Arrays.

Gibts denn alternativen?

[Sven Rautenberg]

Moin!

Du kannst die Laufzeit vermutlich halbieren, indem du die levenshtein-Funktion pro Parametersatz nur einmal aufrufst und deren Ergebnis speicherst.

Sehr gute Idee - so viel bringt das aber leider gar nicht :(

Hast du gemessen, oder nur gefühlt? Die Zeitmessung ist hoffentlich noch drin im Skript, ohne kannst du nämlich nicht optimieren, weil du nicht siehst, ob eine Änderung die Ausführungszeit positiv, negativ oder gar nicht beeinflußt hat.

Bei einem String kommt da immer 1 raus. count() ist nur sinnvoll für Arrays.

Gibts denn alternativen?

Zu was?

Was soll count() denn überhaupt tun?

- Sven Rautenberg

[Philipp.]

• Gemessen, der Unterschied ist fast unabhängig von der Wortanzahl konstant (0.2-0.3 sec).

-Das count() soll mir die anzahl an Wörtern in $liste ermitteln - was es bisher auch erfolgreich tut.

[Sven Rautenberg]

Moin!

• Gemessen, der Unterschied ist fast unabhängig von der Wortanzahl konstant (0.2-0.3 sec).

-Das count() soll mir die anzahl an Wörtern in $liste ermitteln - was es bisher auch erfolgreich tut.

Von $liste rede ich doch gar nicht.

Das hier ists:

$searchexp = $_GET['searchexp'];     #Variable mit Suchbegriffen  
$anz_searchexp = count($searchexp);                 #Anzahl der Suchbegriffe ermitteln

- Sven Rautenberg

[Philipp.]

Achso :)

Das soll mir ermitteln, aus wievielen Wörtern der Suchbegriff besteht, damit ich je nachdem (= 1 || > 1) so oder so weitermachen kann.

[Philipp.]

Wie siehts mit str_word_count(); aus?

[Sven Rautenberg]

Moin!

Achso :)

Das soll mir ermitteln, aus wievielen Wörtern der Suchbegriff besteht, damit ich je nachdem (= 1 || > 1) so oder so weitermachen kann.

Und du hast dich nie gewundert oder nie nachgeprüft, ob deine Annahme, count() könnte auch Werte größer 1 liefern, stimmt?

Und dich nie gewundert, warum deine Schleife nie ausgeführt wird?

- Sven Rautenberg

[Philipp.]

Hi,

das (= 1 || > 1) steht nicht so im Script, das hab ich nur hier geschrieben ;)

Da heißts natürlich

<?php  
  
if($anz_searchexp == 1)  
{ ... }  
else  
{ ... }  
  
?>

Wäre denn str_word_count(); anstelle count(); korrekt?

[Ingo Turski]

Hi,

Vielleicht sagt ja jemand "Das geht doch viiiiieeeeel einfacher" :)

Ich frage mich, was diese Aufsplittung in Zeilen und Wortgruppen überhaupt soll?
Warum nicht den ganzen Dateiinhalt in eine Variable einlesen?
Und warum nicht einfach strpos() hierauf anwenden? Entweder mit dem exakten Suchstring oder für jedes Wort einzeln. Vorher noch beide Strings in Kleinbuchstaben umwandeln und fertig ist der Dreizeiler...

Und wenn Du Wortgrenzen mit berücksichtigen willst, könntest Du das ebenso in einem Rutsch - etwas langsamer - mit einer RegEx machen.

freundliche Grüße
Ingo

[Philipp.]

Warum nicht den ganzen Dateiinhalt in eine Variable einlesen?
Und warum nicht einfach strpos() hierauf anwenden?

Das geschieht ja auch, nur stellt sich mir die Frage wie ich es schaffe, das x. Wort und y direkt nachfolgende Wörter zu prüfen. Danach das x+1. Wort und y nachfolgende. Deswegen habe ich immer diese Gruppen gebildet.

[Ingo Turski]

Hi,

Warum nicht den ganzen Dateiinhalt in eine Variable einlesen?
Und warum nicht einfach strpos() hierauf anwenden?

Das geschieht ja auch, nur stellt sich mir die Frage wie ich es schaffe, das x. Wort und y direkt nachfolgende Wörter zu prüfen. Danach das x+1. Wort und y nachfolgende.

wo denn?
Für die Levenshteinfunktion muss das natürlich anders ablaufen, aber die vorrangige Suche nach einer exakten Übereinstimmung ist doch wirklich so einfach zu realisieren. Entweder
strpos(strtolower(file_get_contents('data.txt')), strtolower($_GET['searchexp']))
oder eben mehrere Durchläufe mit einzelen Worten oder Wortkombinationen.

freundliche Grüße
Ingo

[Philipp.]

Für die Levenshteinfunktion muss das natürlich anders ablaufen, aber die vorrangige Suche nach einer exakten Übereinstimmung ist doch wirklich so einfach zu realisieren.

Die genaue Übereinstimmung interessiert mich gar nicht, da dies schon geschieht. Ich will nur das bestehende Suchscript (welches nicht von mir stammt) dahingehend erweitern, dass bei erfolgloser Suche eben Vorschläge gemacht werden. Ich programmiere leider viel zu selten, dass mir sowas nicht so leicht von der Hand geht.

Wenn also die Suche 0 Treffer liefert, schaltet sich mein Script ein.

[Philipp.]

Für die Levenshteinfunktion muss das natürlich anders ablaufen

Wenn jemand weiß wie das geht, wäre ich für nen Tipp dankbar. strpos ist da ja wenig hilfreich.