Inhaltsverzeichnis |
Hier findest du die Benchmarks verschiedener Codes und ein paar Tipps zum Schreiben eines Siebcodes. Die verschiedenen Quellcodes stammen aus dem Umfeld des berüchtigten PHP-Resource.de Forums und wurden von Hund auf seiner Seite zusammengestellt.
Leider wird der Benchmark nur beim Bearbeiten der Wiki-Seite aktualisiert (muss noch rauskriegen warum). Der Benchmark, der die Ergebnisse auch aktualisiert befindet sich hier
Habe nun die Infos gefunden wie man das Caching komplett deaktivieren kann
<runphp>
$test = 1000;
$dauer = 10;
$diff_arr = $diff_prime = $schleifen = $prim_zahl = 0;
//Hunds Code function init_array_h($zahl){ $anfang = microtime(true); $temp = range(0,$zahl,1); $ende = (int) $zahl/2; unset($temp[0],$temp[1]); for($i=2;$i <= $ende;$i+=1){ unset($temp[$i*2]); } $diff = microtime(true) - $anfang; return array($temp,$diff); } function primes_h($temp,$zahl){
$anfang = microtime(true); $multi = 0;
$ende_abs = (int) sqrt($zahl); while(list($key,$wert) = each($temp)){ if($wert > $ende_abs){ break; } $ende = (int) ($zahl/$wert); $ende += 1; $i = $wert; while($i < $ende){ $multi +=1; unset($temp[$i*$wert]); $i += 2; } } $ende = microtime(true); $diff = round($ende - $anfang,6); return array($temp,$diff,$multi); } $zeit_a = 0; $zeit_r = 0; $multi = 0; $primen = 0; for($i=0;$i<$dauer;$i++){
$fp = init_array_h($test); $zeit_a += $fp[1]; $fp = primes_h($fp[0],$test); $zeit_r += $fp[1]; $multi += $fp[2]; $primen += count($fp[0]);
}
function initArrayN($max){
$anfang = microtime(true);
$data = array();
$data[2] = 2;
$data[3] = 3;
for( $i = 3; $i <=$max; $i += 2 ){
($i % 3) ? $data[$i] = $i : 0;
}
$diff = microtime(true) - $anfang;
return array($data,$diff); }
function primesN($data,$max){
$anfang = microtime(true);
$multi = 0;
$sqrt = ceil( sqrt( count($data) * 3 ) );
$i = 2;
while( true ){
++$i;
if( isset( $data[$i] ) ) {
$t = &$data[$i];
if( $t > $sqrt )
break;
$dt=2*$t;
for ($ii = 3*$t; $ii < $max; $ii+=$dt){
$multi += 1;
unset( $data[$ii] );
}
}
}
$diff = microtime(true) - $anfang;
return array($data,$multi,$diff); } $durchl_N = $zahlen_N = $init_N = $suche_N = 0; for($i=0;$i<$dauer;$i++){
$fp = initArrayN($test);
$init_N += $fp[1]; $fp = primesN($fp[0],$test); $suche_N += $fp[2]; $durchl_N += $fp[1]; $zahlen_N += count($fp[0]); }
function init_array($max){
$anfang = microtime(true);
$data = array();
$data[2] = 2;
$data[3] = 3;
for($i=5;$i<=$max;$i+=2){
($i % 3) ? $data[$i] = $i : 0;
}
$diff = microtime(true) - $anfang;
return array($data,$diff); } function primes($data,$max){
$anfang = microtime(true);
$sqrt = ceil(sqrt($max));
$multi = 0;
$i = 5;
while(true){
if( isset( $data[$i] ) ) {
if($data[$i] >= $sqrt ){
break;
}
$ende = ceil($max/$data[$i]);
for ($ii = $i; $ii<$ende; $ii+=2){
$multi += 1;
unset($data[$ii*$i]);
}
}
$i += 2;
}
$diff = microtime(true) - $anfang;
return array($data,$multi,$diff);
} $durchl = $zahlen = $init = $suche = 0; for($i=0;$i<$dauer;$i+=1){
$fp = init_array($test);
$init += $fp[1]; $fp = primes($fp[0],$test); $suche += $fp[2]; $durchl += $fp[1]; $zahlen += count($fp[0]); }
function initArrayH($max){
$anfang = microtime(true);
$data = array();
$data[2] = 2;
for( $i = 3; $i < $max; $i += 2 ){
$data[$i] = $i;
}
$diff = microtime(true) - $anfang;
return array($data,$diff); }
function primesH($data,$max){
$anfang = microtime(true);
$multi = 0;
$sqrt = ceil( sqrt( count($data) * 2 ) );
$i = 1;
while( true ){
$i+=2;
if( isset( $data[$i] ) ) {
$t = &$data[$i];
if( $t > $sqrt )
break;
for ($ii=pow($t,2); $ii<$max; $ii+=$t ){
$multi += 1;
unset( $data[$ii] );
}
}
}
$diff = microtime(true) - $anfang;
return array($data,$multi,$diff); } $durchl_H = $zahlen_H = $init_H = $suche_H = 0; for($i=0;$i<$dauer;$i++){
$fp = initArrayH($test); $init_H += $fp[1]; $fp = primesH($fp[0],$test); $suche_H += $fp[2]; $durchl_H += $fp[1]; $zahlen_H += count($fp[0]);
} $data = file('../primen/stat.txt'); $hund = array($data[0]+$zeit_a+$zeit_r,$data[1]+1); $tobi = array($data[2]+$init+$suche,$data[3]+1); $hund1 = array($data[4]+$init_H+$suche_H,$data[5]+1); $nzo = array($data[6]+$init_N+$suche_N,$data[7]+1); $fp = fopen('../primen/stat.txt','w'); $str = implode("\r\n",$hund)."\r\n".implode("\r\n",$tobi)."\r\n".implode("\r\n",$hund1)."\r\n".implode("\r\n",$nzo); fwrite($fp,$str); fclose($fp); $b = $tobi[0]/$tobi[1]/$dauer; echo '
| Wert | Benchmark von Siebcodes zur Berechnung von Primzahlen im Bereich von 0 - '.$test.' bei '.$dauer.' Durchläufen pro Benchmark | ||||
| Tobi | NZO | Hund | Unknown | ||
| Zeit Benchmark | '.round(1000*($init+$suche),8).' ms | '.round(1000*($init_N+$suche_N),8).' ms | '.round(1000*($zeit_a+$zeit_r),8).' ms | '.round(1000*($init_H+$suche_H),8).' ms | |
| Ø pro Lauf | '.round(1000*(($init+$suche)/$dauer),8).' ms | '.round(1000*(($init_N+$suche_N)/$dauer),8).' ms | '.round(1000*(($zeit_a+$zeit_r)/$dauer),8).' ms | '.round(1000*(($init_H+$suche_H)/$dauer),8).' ms | |
| Aufbau Zahlenarrays | '.round(1000*$init,8).' ms | '.round(1000*$init_N,8).' ms | '.round(1000*$zeit_a,6).' ms | '.round(1000*$init_H,8).' ms | |
| Ø pro Lauf | '.round(1000*($init/$dauer),8).' ms | '.round(1000*($init_N/$dauer),8).' ms | '.round(1000*($zeit_a/$dauer),8).' ms | '.round(1000*($init_H/$dauer),8).' ms | |
| Zeit Suche | '.round(1000*$suche,8).' ms | '.round(1000*$suche_N,8).' ms | '.round(1000*$zeit_r,8).' ms | '.round(1000*$suche_H,8).' ms | |
| Ø pro Lauf | '.round(1000*($suche/$dauer),8).' ms | '.round(1000*($suche_N/$dauer),8).' ms | '.round(1000*($zeit_r/$dauer),8).' ms | '.round(1000*($suche_H/$dauer),8).' ms | |
| Multiplikationen | '.number_format($durchl,,,"'").' | '.number_format($durchl_N,,,"'").' | '.number_format($multi,,,"'").' | '.number_format($durchl_H,,,"'").' | |
| Ø pro Lauf | '.number_format(round($durchl/$dauer,8),,,"'").' | '.number_format(round($durchl_N/$dauer,8),,,"'").' | '.number_format(round($multi/$dauer,8),,,"'").' | '.number_format(round($durchl_H/$dauer,8),,,"'").' | |
| Primzahlen | '.number_format($zahlen,,,"'").' | '.number_format($zahlen_N,,,"'").' | '.number_format($primen,,,"'").' | '.number_format($zahlen_H,,,"'").' | |
| Ø pro Lauf | '.number_format($zahlen/$dauer,,,"'").' | '.number_format($zahlen_N/$dauer,,,"'").' | '.number_format($primen/$dauer,,,"'").' | '.number_format($zahlen_H/$dauer,,,"'").' | |
| Totale Zeit für '.$tobi[1]*$dauer.' Läufe | '.round($tobi[0],8).' s | '.round($nzo[0],8).' s | '.round($hund[0],8).' s | '.round($hund1[0],8).' s | |
| Ø pro Benchmark | '.round(1000*($tobi[0]/$tobi[1]),8).' ms | '.round(1000*($nzo[0]/$nzo[1]),8).' ms | '.round(1000*($hund[0]/$hund[1]),8).' ms | '.round(1000*($hund1[0]/$hund1[1]),8).' ms | |
| Ø pro Lauf | '.round(1000*($tobi[0]/($tobi[1]*$dauer)),8).' ms | '.round(1000*($nzo[0]/($nzo[1]*$dauer)),8).' ms | '.round(1000*($hund[0]/($hund[1]*$dauer)),8).' ms | '.round(1000*($hund1[0]/($hund1[1]*$dauer)),8).' ms | |
| Multiplikationen bei '.$tobi[1]*$dauer.' Läufen | '.number_format($durchl*$tobi[1]*$dauer,,,"'").' | '.number_format($durchl_N*$tobi[1]*$dauer,,,"'").' | '.number_format($multi*$tobi[1]*$dauer,,,"'").' | '.number_format($durchl_H*$tobi[1]*$dauer,,,"'").' | |
| Performance | ';'.$temp['tobi'][1].'% | '.$temp['nzo'][1].'% | '.$temp['hund'][1].'% | '.$temp['hund1'][1].'% | |
</runphp>
Die verwendeten Quellcodes in diesem Benchmark findet Ihr hier:
Wir sehen also, dass diese beiden Primen Codes optimal sein müssten und der Zeitunterschied von wo anders herkommen muss. Da beide Codes nur 2 Funktionen beinhalten ist der Kandidat schnell gefunden. Die jeweilige Array Initiierungsfunktion muss es sein. Wenn ihr diese beiden Funktionen miteinander vergleicht dann seht ihr die zwei Möglichkeiten diesen Array aufzubauen, die Aufgabe bleibt dieselbe: Damit berechnete Kompositzahlen schnell aus dem Array entfernt werden können muss sichergestellt sein, dass der Wert einer Zahl gleich ihrem Key im Array ist. Sonst muss zum Löschen einer Zahl aus dem Array erst deren Index mittels einer Funktion festgestellt werden.
Obige Aufgabe kann mittels einer range() Funktion automatisch oder mit einer Schleife manuell gemacht werden. Die range-Funktion ist schneller hat jedoch den Nachteil, dass, um obige Bedingung zu erfüllen, das Array komplett von 0 bis Ende aufgebaut werden muss. Dies führt dazu, dass die Array Elemente 0 und 1 und alle Vielfachen von 2 entfernt werden müssen, damit in der inneren for Schleife bei den Vielfachen von 3 und einer Schrittweite von 2 begonnen werden kann. Ein Vorteil der manuellen Methode ist es, dass man den Key eines Elements im Array vorgeben kann. Somit kann man ein Array ungerader Zahlen > 1 aufbauen, welche ja nur Primzahlen sein können und die 2 nach der Berechnung einfach anhängen Ich weigere mich bis heute standhaft 2 als wirklich Prim anzuerkennen ;-) Ein weiterer Vorteil der manuellen Methode ist es, dass man beim Erstellen gleich eine Bedingung prüfen kann und damit weniger Zahlen ins Array schreibt.
<?php /* * Diese drei Code Snippets sollen die unterschiedlichen Ansätze * beim Aufbau des Array mit den zu prüfenden Zahlen zeigen */ //langsam $temp = range(0,$ende,1); $ende = $ende/2; //zuerst müssen 0 und 1 aus dem Array entfernt werden unset($temp[0],$temp[1]); for($i=2;$i<=$ende;$i++){ //hier müssen die Vielfachen von 2 aus dem Array gelöscht werden unset($temp[$i*2]); } //schneller $temp = array(); for($i=3;$i<=ende;$i+=2){ //hier wird einfach ein Array mit ungeraden Werten aufgebaut $temp[3] = 3 $temp[$i] = $i; } //optimal $temp = array(); $temp[2] = 2; $temp[3] = 3; for($i=3;$i<=$zahl;$i+=2){ ($i % 3) ? $temp[$i] = $i : 0; } ?>
Wenn ihr beide Quellcodes miteinander vergleicht, dann werdet ihr keine grossartigen Unterschiede feststellen. V.a die jeweiligen prime()-Funktionen, die sich eigentlich identisch. Dies kommt daher, wie ich hier schon gezeigt habe, dass es für die äussere Schleife keine andere Möglichkeit als eine while-Schleife gibt. Man muss auf den aktuellen Zustand des Arrays zugreifen können, um die Anzahl unnötiger Berechnungen zu minimieren. Zusammen mit each() ist mir in PHP keine Möglichkeit bekannt schneller über einen sich ändernden Array zu iterieren
Als innere Schleife kommt wiederum eigentlich nur eine for-Schleife in Frage, weil diese Schleife x-tausendfach durchlaufen wird. Wenn die for-Schleife pro Durchlauf auch nur eine Milisekunde schneller ist als eine while-Schleife, kommt man schon in Zahlenbereichen > 10'000 zu deutlich messbaren Unterschieden.
Ein absolutes Don't bei häufig durchlaufenen Schleifen sind Bedingungen. Im Falle der Siebscripts betrifft dies v.a. die innere Schleife.Oft hört man die Aussage, dass der Code wohl Schleifen habe, die häufig durchlaufen würden, aber darin keine Bedingungen enthalten seien. Dabei vergisst der Programmierer dann, dass ohne Bedingung keine Schleife existieren kann.
<?php /* * Diese Snippets zeigen deutliche Unterschiede * in den Laufzeiten v.a. bei gross gewähltem $ende */ //langsamer Code $ende = 10000; for($i=2;$i<=$ende/2;$i++){ //anderer Code } //schneller Code $ende = 10000; $ende = $ende/2; for($i=2;$i<=ende;$i++){ //anderer Code } ?>
Bei jedem Durchlauf einer Schleife muss jeweils die Abbruchbedingung gepüft werden. Wenn dann in dieser Abbruchbeddingung noch gerechnet werden muss, dann ist das eine Verlängerung der Laufzeit von ca 50% ! Wenn die richtige Schleifenwahl getroffen wird und die Abbruchbedingungen korrekt gesetzt sind, dann sehen wir, dass bei der Berechnung der Vielfachen nicht mehr Zeit gewonnen werden kann.
Das Gebot keine Bedingungen in Schleifen zu haben muss dahingehend relativiert werden, dass es unter gewissen Umständen doch sinnvoll sein kann eine zusätzliche Bedingung in die Schleife einzubauen, um unnötige Berechnungen zu sparen. Wie folgende Codes demonstrieren sollen:
<?php /* * Mit folgenden zwei Codes möchte ich zeigen, dass Bedingungen in Schleifen * nicht zwangsläfig zu einer längeren Laufzeit führen müssen */ $zahl = 10000; $i = 5; //Anzahl Multiplikationen $multi = 0; $sqrt = ceil(sqrt($zahl)); while(true){ /*Im Gegensatz zur while-Methode mit $elem=each($array) s.u. wird hier eine Bedingung benötigt, die prüft ob die Zahl nicht schon als komposite Zahl gestrichen wurde.*/ if( isset( $temp[$i] ) ) { /*Diese Abbruchbedingung muss bei jedem Siebcode vorhanden sein sonst werden tausendfach Zahlen berechnet, deren Wert schon ausserhalb des Zahlenbereichs liegt*/ if($temp[$i] >= $sqrt ){ break; } /*Hier wird der jeweilig grösste Multiplikator ($ende) berechnet, dessen Produkt mit der zu prüfenden Zahl gerade noch innerhalb des Testbereiches liegt.*/ $ende = ceil($zahl/$temp[$i]); for ($ii = $i; $ii<$ende; $ii+=2){ $multi += 1; unset($temp[$ii*$i]); } } $i += 2; } //dieser Code hat zwei Bedingung weniger und ist trotzdem messbar langsamer ! $zahl = 10000; $i = 5; //Anzahl Multiplikationen $multi = 0; $sqrt = ceil(sqrt($zahl)); while($i<$sqrt){ /*Hier wird der jeweilig grösste Multiplikator ($ende) berechnet, dessen Produkt mit der zu prüfenden Zahl gerade noch innerhalb des Testbereiches liegt.*/ $ende = ceil($zahl/$i); for ($ii = $i; $ii<$ende; $ii+=2){ $multi += 1; unset($temp[$ii*$i]); } $i += 2; } ?>
Die beiden letzten Codebeispiele sollen nochmals verdeutlichen, dass Bedingungen in Schleifen wohl langsamer sind, es aber unter bestimmten Voraussetzungen einen Performance Gewinn bringen kann dies trotzdem zu tun. Der zweite Code hat weniger Bedinungen und macht dadurch deutlich mehr Multiplikationen (z.B. werden Vielfache von 9 berechnet, welche aber ALLE durch die Vielfachen von 3 bereits aus dem Array gelöscht wurden). Diese unnötigen Berechnungen sind wesentlich zeitintensiver als die entsprechenden zusätzlichen Bedingungen zu deren Vermeidung! Man darf nicht vergessen, dass man eigentlich nicht die Primzahlen berechnet, sondern die Kompositzahlen d.h die Anzahl der Kompositzahlen nimmt bei steigender Grösse exponential zu und damit auch die Anzahl dieser unnötigen Berechnungen. In kleinen Zahlenbereichen wiegen diese Fehlberechnungen nicht so sehr, aber bei grossen Bereichen (> 500'000) kommen schnell Unterschiede von mehreren Sekunden in der Laufzeit zusammen.mehr zum Thema
Noch etwas kurzes zu diesem Thema zum Schluss dieses Kapitels:
Objektorientierte Programmierung und Benchmarks (v.a. Sieb Benchmarks) vertragen sich überhaupt nicht. Allein die Initiierung der Klasse oder der reset aller Klassenvariabeln bei jedem Durchlauf des Benchmarks dauern länger als die gesamte Berechnung mittels zwei einfacher Funktionen. Ich behaupte das jetzt mal einfach so, lasse mich aber gerne eines besseren belehren. Wenn also jemand eine PHP Klasse hat, die in so einem Benchmark mithalten kann, dass immer her damit (tobi[*ç%%**""ççAT]tobisworld[%ç*""*ç**DOT]ch)