✔ Algorithmus der rekursiven Hyperlinksuche verschnellern

N

NTDY

Erfahrenes Mitglied
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: 
<!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>
 
Abend!

  • Liest nicht die gesamte Datei/Site auf einmal. Arbeite zeilenweise.
  • Benutze einen anderen Regulären ausdruck, z.B.
Code: 
/(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
 
Zuletzt bearbeitet:
Der reguläre Ausdruck ist wirklich ungeeignet. Auch würde ich erst die a-Tags heraussuchen und dann die Attribute auswerten.
PHP: 
'/<a(\s+[^>]+)>/i'
 
Gumbo hat gesagt.:
Der reguläre Ausdruck ist wirklich ungeeignet. Auch würde ich erst die a-Tags heraussuchen und dann die Attribute auswerten.
Zum Vergrößern anklicken....
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
 
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: 
<!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>
 
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: 
$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;
		}
	}
}
 
Zuletzt bearbeitet:
Hallo Gumbo,
vielen Dank für die Gedankenstütze. Ich habe nun ein fertiges Skript heraus (für alle, die es interessiert).

PHP: 
<!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>
 
Zuletzt bearbeitet:
Hallo,
sorry, dass ich hier noch mal nachhake, aber ich erkenne noch keinen Sinn in diesen Abfragen:
PHP: 
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: 
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
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück