Algorithmus der rekursiven Hyperlinksuche verschnellern @ tutorials.de: Tutorials, Forum & Hilfe

NTDY · 03.12.08 22:51

Ich habe ein Skript geschrieben, das auf einer Webseite alle Hyperlinks einsammelt. Leider ist die Perfomance noch nicht gut genug und das Skript beendet sich nach 5 Minuten. Hat jemand eine Idee, wie man diesen Algorithmus verbessern kann?

PHP-Code:


<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">

<head>

<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />

<title>Sucker</title>

<style type="text/css">

*,body{

font-family:"Courier New", Courier, monospace;

font-size:12px;

}

</style>

</head>



<body>

<pre>

<?php

global $linkpuffer;



function suche_komplett_www($url){

    //Seite einlesen

    $zeile=@file_get_contents($url);

    // Pattern für Hyperlinks

    $pattern = '=^(.*)<a(.*)href\="?(\S+)"([^>]*)>(.*)</a>(.*)$=msi';

    //solange ein Hyperlink noch gefunden wird, lesen

    while (preg_match($pattern, $zeile, $txt)){

    

        //txt[3] ist der Hyperlink

        if(preg_match("/http:/",$txt[3])){

        }elseif(preg_match("/Javascript:/i",$txt[3])){

        }elseif(preg_match("/.pdf/i",$txt[3])){

        }else{

            $variable = $txt[3];

            if(substr($variable,0,2)=="./"){

                //echo $variable." (mit ./)<br>";                        

                // nun den Punkt (.) am Anfang loeschen

                $variable = substr($variable,1,strlen($variable)-1); 

                $in_puffer=$url.$variable;

                //echo $variable." (./ entfernen)<br>";

                echo $variable."<br>";                

                if(@array_search($variable,$linkpuffer)!=true){

                    $linkpuffer[] = $variable;

                    suche_komplett_www($in_puffer);                    

                }        

            }elseif(substr($variable,0,1)=="/"){

                //echo $variable." (mit /)<br>";

                $in_puffer=$url.$variable;

                //echo $variable." (/ entfernen)<br>";

                echo $variable."<br>";

                //wenn Wert noch nicht im Array, dann einfügen

                if(@array_search($variable,$linkpuffer)!=true){

                    $linkpuffer[] = $variable;

                    suche_komplett_www($in_puffer);

                }

            }else{

    

                $variable="/".$variable;            

                $in_puffer=$url."/".$variable;            

                echo $variable."<br>";                

                if(@array_search($variable,$linkpuffer)!=true){

                    $linkpuffer[] = $variable;

                    suche_komplett_www($in_puffer);                    

                }        

            }        

        }

      $zeile = $txt[1]." hier war mal ein Link ".$txt[6];    

    }

    return $linkpuffer;

}



$linkpuffer=suche_komplett_www("http://www.tech-island.com/technet/techtalk/rekursiv_programmieren");



echo "<hr>";

echo "<pre>";

print_r($linkpuffer);

echo "</pre>";



?>    

</pre>

</body>

</html>

Enumerator · 03.12.08 22:58

Abend!

Liest nicht die gesamte Datei/Site auf einmal. Arbeite zeilenweise.
Benutze einen anderen Regulären ausdruck, z.B.
Code :
1
/(href|src)="([^"])"/
Filtere die URIs erst nachdem Du sie gesammelt hast

Das für's erste - aber da geht noch mehr...

Greetz
Enum

PS, als Schmankerl: Damit kannst Du URLs validieren, nachdem Du sie gefiltert hast: http://internet.ls-la.net/folklore/url-regexpr.html

Gumbo · 04.12.08 10:49

Der reguläre Ausdruck ist wirklich ungeeignet. Auch würde ich erst die a-Tags heraussuchen und dann die Attribute auswerten.

PHP-Code:


'/<a(\s+[^>]+)>/i'

Enumerator · 04.12.08 11:33

Zitat von Gumbo

Der reguläre Ausdruck ist wirklich ungeeignet. Auch würde ich erst die a-Tags heraussuchen und dann die Attribute auswerten.

Es geht doch um Speed, richtig? Rekursive Hyperlinks? Quasi ein reiner Link-Crawler? Dann ist jede Vereinfachung des 1. regulären Ausdrucks ein Zeitgewinn, der sich mit der Laufzeit potenziert. Und href Attribute sind so ziemlich das einzige, was dann noch interessiert. Die srcs eventuell auch, wenn man Bilder haben möchte - aber war ja nur ein Beispiel.
Ich bin davon überzeugt, dass man die Applikation mehrgleisig fahren muss, wenn man wirklich performant arbeiten will - Threads die Sammeln (mit einfachem RegEx) und Threads die Filtern...

Greetz
Enum

NTDY · 04.12.08 17:47

Hat jemand eine Idee, wie man meinen Algorithmus terminatorieren lassen kann?

Die Funktion sammelt ja alle Links heraus, verwirft bereits welche, die nicht zur Seite gehören und baut dann Links zusammen, die dann wieder in die Funktion gehen.

./ETWAS.HTML
werden zu http://www.seite.de/ETWAS.HTML

/ETWAS.HTML
werden zu http://www.seite.de/ETWAS.HTML
usw.

Ich komme aber nicht auf die Idee, wie man die Rekursion stoppen kann?

PHP-Code:


<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">

<head>

<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />

<title>Sucker</title>

<style type="text/css">

*,body{

font-family:"Courier New", Courier, monospace;

font-size:12px;

}

</style>

</head>



<body>

<pre>

<?php



function suche_komplett_www($url,$pufferarray,$uri="http://www.comicportal.de"){

        $puffer=@file($url);

        foreach($puffer as $zeile){

            $pattern = '=^(.*)<a(.*)href\="?(\S+)"([^>]*)>(.*)</a>(.*)$=msi';    

            //$pattern='/<a(\s+[^>]+)>/i';

            if(preg_match($pattern, $zeile, $txt)==true){

                if(preg_match("/http:/",$txt[3])){

                }elseif(preg_match("/Javascript:/i",$txt[3])){

                }elseif(preg_match("/.pdf/i",$txt[3])){

                }else{

                    $variable = $txt[3];

                    //Link ist ein ./ Link

                    if(substr($variable,0,2)=="./"){

                        $variable = substr($variable,1,strlen($variable)-1);

                        $in_puffer=$uri.$variable;

                        if(in_array($in_puffer,$pufferarray)!=true){

                            $pufferarray[] = $in_puffer;

                            echo "1 ->".$in_puffer."<-\n";                        

                            suche_komplett_www($in_puffer,$pufferarray);                    

                        }                                            

                    }elseif(substr($variable,0,1)=="/"){

                        $in_puffer=$uri.$variable;            

                        //print_r($pufferarray)."..\n";

                        //echo $in_puffer."...\n";                

                        if(in_array($in_puffer,$pufferarray)!=true){

                            $pufferarray[] = $in_puffer;

                            echo "2 ->".$in_puffer."<-\n";                        

                            suche_komplett_www($in_puffer,$pufferarray);                    

                        }                                    

                    }else{

                        $variable="/".$variable;            

                        $in_puffer=$uri.$variable;    

                        if(in_array($in_puffer,$pufferarray)!=true){

                            $pufferarray[] = $in_puffer;

                            echo "3 ->".$in_puffer."<-\n";                        

                            suche_komplett_www($in_puffer,$pufferarray);                    

                        }        

                    }

                }

            }

        }

    return $linkpuffer;

}







$pufferarray = array();

echo "<textarea cols='160' rows='40'>";

$valurl="http://www.comicportal.de";

$linkpuffer=suche_komplett_www($valurl,$pufferarray,$valurl);

echo "</textarea>";    



echo "<hr>";

echo "<pre>";

print_r($linkpuffer);

echo "</pre>";



?>    

</pre>

</body>

</html>

Gumbo · 04.12.08 18:42

Ich würde gar keine Rekursion verwenden, da sonst bei jeder Rekursion der benötigte Speicher (allein durch die Initialisierung der Variablen) immer weiter steigt. Stattdessen würde ich die gesammelten Links sequenziell abarbeiten. Das kannst du rein schematisch wie folgt machen:

PHP-Code:


$unvisited = array('http://localhost/start');
$visited = array();
while ($url = array_shift($unvisited)) {
    if ($content = file_get_contents($url)) {
        // neue URLs werden gesammelt
        // …
    }
    $visited[] = $url;
    foreach ($newUrls as $newUrl) {
        if (!in_array($newUrl, $visited) && !in_array($newUrl, $unvisited)) {
        // nur neue URLs werden aufgenommen
            $unvisited[] = $newUrl;
        }
    }
}

NTDY · 04.12.08 21:01

Hallo Gumbo,
vielen Dank für die Gedankenstütze. Ich habe nun ein fertiges Skript heraus (für alle, die es interessiert).

PHP-Code:


<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
<title>Unbenanntes Dokument</title>
</head>

<body>
<?php
$uri="http://www.intel.com/";
$unvisited = array($uri);
$visited = array();
while ($url = array_shift($unvisited)) {
    $puffer=@file($url);
    foreach($puffer as $zeile){
        $pattern = '=^(.*)<a(.*)href\="?(\S+)"([^>]*)>(.*)</a>(.*)$=msi';
        if(preg_match($pattern, $zeile, $txt)==true){
            $variable = $txt[3];
            if(preg_match("/http:/",$variable)){
            }elseif(preg_match("/Javascript:/i",$variable)){
            }elseif(preg_match("/.pdf/i",$variable)){
            }elseif(substr($variable,0,2)=="./"){
                // "./" wurde entfernt
                $variable = substr($variable,2,strlen($variable)-1);
                $in_puffer=$uri.$variable;
                $newUrls[] = $in_puffer;
                //echo $in_puffer;
            }elseif(substr($variable,0,1)=="/"){
                $variable = substr($variable,1,strlen($variable)-1);
                $in_puffer=$uri.$variable;                
                $newUrls[] = $in_puffer;
//                echo $in_puffer."<br>";            
            }else{
                $in_puffer=$uri.$variable;                    
                $newUrls[] = $in_puffer;
                //echo $in_puffer."<br>";
            }
        }
        // neue URLs werden gesammelt
        // …
    }
    $visited[] = $url;
    foreach ($newUrls as $newUrl) {
        if (!in_array($newUrl, $visited) && !in_array($newUrl, $unvisited)) {
        // nur neue URLs werden aufgenommen
            $unvisited[] = $newUrl;
        }
    }    
}

echo "<pre>";
print_r($visited);
echo "</pre>";
?>
</body>
</html>

DeeJTwoK · 04.12.08 23:09

Hallo,
sorry, dass ich hier noch mal nachhake, aber ich erkenne noch keinen Sinn in diesen Abfragen:

PHP-Code:


if(preg_match("/http:/",$variable)){

}elseif(preg_match("/javascript:/i",$variable)){

}elseif(preg_match("/.pdf/i",$variable)){

}elseif(substr($variable,0,2)=="./"){

Es soll also nur etwas gemacht werden wenn das Ziel mit ./ anfängt. Wenn es dies tut, wird wohl kaum noch ein hhtp: oder ein javascript: vorkommen. Warum machst du es nicht einfach so:

PHP-Code:


if(substr($variable,0,2)=="./" and !preg_match("/.pdf$/i",$variable)){

"WENN der String mit ./ anfängt und nicht auf .pdf endet, DANN..."

Da es hier ja um Performance geht, könnte das helfen, oder?

Grüße und so
DJ

tut orials.de	tut verbinden	tut dir helfen	tut kooperieren
©2000-2012 tutorials.de Alle Rechte vorbehalten	tut informieren » Impressum » Nutzungsregeln » Netiquette » Team » Redaktion	» Tutorials » Videotutorials » Showroom » Events & Contests » Chat » RSS-Feed » Blogs	» der-webdesigner.net » DesignerInAction » Design Nation » Directorforum » Flashhilfe » PHP-Resource » PHPwelt » PSD-Tutorials

Themen-Optionen

Anzeige

Ähnliche Themen

Kombinationen über rekursiven Algorithmus berechnen?

Problem mit dem rekursiven Einlesen von Verzeichnissen

MS SQL Server - Definition einer rekursiven Beziehung (m:n)

Problem mit rekursiven verzeichnis durchlauf

Rendern verschnellern

[PHP][Snippet] Array zu XML konvertieren

PHP: LDAP / Active Directory abfragen

E-Mail:

Abonnieren Abbestellen