Optimierungspotential bei Primzahlsuche

[penizillin]

derhund - ist es ein jobangebot? quatsch...

es reicht ja, wenn ihr count($data) vergleicht. beim letzten script von tbt macht das 1230 stück zwischen 1 und 10.000.

[derHund]

hmm,

hab grad die ersten 10.000 verglichen ... die passen.
der vergleich der ersten 100.000 läuft gerade ...

mal schauen ... ok, die ersten 100.000 stimmen mit http://wikisource.org/wiki/Prime_numbers_(2_-_100.000) überein.

count zu vergleichen ist natürlich irgendwie besser, bei mir sinds zwischen 2 und 10.000 nur 1229 ^^

Primzahlen im Bereich 2 - 100.000
overall: 9592
took 1.5871961116791s

was kommt bei euch raus?

[TBT]

nochmal verbessert, und nun noch weit schneller

$s = explode(' ', microtime());
$start = $s[1] + $s[0];

function remove( &$data, $zahl ) {
    foreach( $data as $key => $value )
        if( $value > $zahl && $value%$zahl == 0 )
            unset( $data[$key] );
}
$data = array();
$data[] = 2;
for( $i=3; $i<100000; $i+=2 )
    $data[] = $i;
$max = ceil( count( $data ) / 2 );
$sqrt = ceil( sqrt( count($data) * 2 ) );
for( $i=1; $i<=$max ; ++$i )
    if( isset( $data[$i] ) ) {
        if( $data[$i] > $sqrt )
            break;
        remove( $data, $data[$i] );
    }
$e = explode(" ", microtime());
$ende = $e[1] + $e[0];
echo implode(', ',$data)."<br><br>";
echo count($data).' Primzahlen<br><br>';
echo number_format(($ende-$start)*1000, 1, ',', '.').' ms'; 

obige Routine

0 - 10.000 in 0,14 sek mit 1229 Primzahlen
0 - 100.000 in 2,6 sek mit 9592 Primzahlen
0 - 200.000 in 6,2 sek mit 17984 Primzahlen
0 - 500.000 in 20,5 sek mit 41538 Primzahlen

die Routine von Happay kommt bei mir auf

0 - 10.000 in 0,39 sek mit 1229 Primzahlen
0 - 100.000 in 13,8 sek mit 9592 Primzahlen
0 - 200.000 länger als 30 Sek => max_execution_time hochgesetzt auf 300
0 - 200.000 in 53,6 sek mit 17984 Primzahlen
0 - 500.000 länger als 300 Sek

[derHund]

hmm,

@TBT:

hatte ich zuerst gedacht, du hängst uns ja ganz schön ab, ... dann hab ich gesehen, daß du die ausgabe nicht mit benchmarkst ... ^^ dann habe ich das bei mir angepaßt, sogar deine zeitrechnung eingebaut, um fehler zu vermeiden ...

• 0 - 10.000: overall: 1229, took: 35,9 ms (tbt: 1229 Primzahlen, 114,9 ms)
• 0 - 100.000: overall: 9592, took: 472,4 ms (tbt: 9592 Primzahlen, 2.474,4 ms)
• 0 - 200.000: overall: 17984, took: 1.046,7 ms (tbt: 17984 Primzahlen, 5.937,2 ms)
• 0 - 500.000: overall: 41538, took: 4.728,1 ms (tbt: 41538 Primzahlen, 19.638,8 ms)
• 0 - 1.000.000: overall: 78498, took: 24.016,7 ms (tbt: 78498 Primzahlen, 49.355,6 ms)

teste mal bitte, ob die wirklich fixer ist ...

  class findPrimes {
    var $min;
    var $max;
    var $maxToGo;
    var $primeHolder = array();
    var $timer;

    function findPrimes($min, $max) {
      $s = explode(' ', microtime());
      $this->timer = $s[1] + $s[0];
      $this->min = $min;
      $this->max = $max;
      $this->maxToGo = ceil(sqrt($max));
      $this->primeHolder[2] = 2;
      for ($i = 3; $i <= $max; $i+=2)
        $this->primeHolder[$i] = $i;
      $this->calc();
    }

    function calc($step = 2) {
      if ($step > $this->maxToGo)
        return;
      for ($i = 2*$step; $i <= $this->max; $i += $step) {
        unset($this->primeHolder[$i]);
      }
      $this->calc($this->get_next_step($step));
    }

    function get_next_step($current) {
      for ($i = $current+1; $i < $this->max; $i++)
        if (isset($this->primeHolder[$i]))
          return $this->primeHolder[$i];
    }

    function out() {
      $e = explode(" ", microtime());
      $ende = $e[1] + $e[0];
      $time = number_format(($ende - $this->timer)*1000, 1, ',', '.').' ms';
      return implode(', ', $this->primeHolder).'<br />overall: '.count($this->primeHolder).'<br />took: '.$time.'<br />';
    }
  }

  $prime = &new findPrimes(0, 1000000);
  echo $prime->out(); 

bitte nicht auf die uneleganz des feldaufbaus achten, bei 2.000.000 stürzt der apache (dadurch) eh wieder ab.

[TBT]

nicht schlecht ....

dann lege ich auch nochmal nach

// Startzeit
$s = explode(' ', microtime());
$start = $s[1] + $s[0];
// max Wert
$max = 500000;
// Datenarray aufbauen
$data = array();
$data[2] = 2;
for( $i = 3; $i < $max; $i += 2 )
    $data[$i] = $i;
// nicht Primzahlen loeschen
$sqrt = ceil( sqrt( count($data) * 2 ) );
$i = 2;
while( true ){
    ++$i;
    if( isset( $data[$i] ) ) {
        $t = &$data[$i];
        if( $t > $sqrt )
            break;
        for ($ii = 2*$t; $ii < $max; $ii+=$t)
            unset( $data[$ii] );
    }
}
// Endzeit
$e = explode(" ", microtime());
$ende = $e[1] + $e[0];
// Ausgabe
echo implode(', ',$data)."<br><br>";
echo count($data).' Primzahlen<br><br>';
echo number_format(($ende-$start)*1000, 1, ',', '.').' ms'; 

Schnitt aus 10 Aufrufen mit Primzahlen bis 500.000

der Hund: 2,97 Sek
TBT : 1,95 Sek

[derHund]

hmm,

besser gehts wohl nicht ...

vielleicht könnte man das ++$i; noch in $ += 2 ändern, bei 1 beginnend ... bringt aber keine (meßbaren) vorteile.

schön

[NROz]

Hi,

hab mir TBTs script ma genauer angesehn und mir sind 2 dinge aufgefallen:

1. die 3er braucht man nicht in $data, und
2. die for-schleife mit $$i sucht auch nach geraden $$i

also schwingt man die finger und hackt:

<?php
// Startzeit
$s = explode(' ', microtime());
$start = $s[1] + $s[0];
// max Wert
$max = 500000;
// Datenarray aufbauen
$data = array();
$data[2] = 2;
$data[3] = 3;
for( $i = 3; $i < $max; $i += 2 )
   ($i % 3) ? $data[$i] = $i : 0;
// nicht Primzahlen loeschen
$sqrt = ceil( sqrt( count($data) * 2 ) );
$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)
            unset( $data[$ii] );
    }
}

// man prüfe die primzahlen
/*
$k = array_keys($data);

$lk = count($k);

for($i = 0; $i<$lk; $i++) {
    $z = ceil(sqrt($i));
    $c = 2;
    while( $c < $z) {
        if($data[$k[$i]] % $c == 0) echo $data[$k[$i]]," teilbar durch $c<br/>";
        $c++;
    }
}
*/

// Endzeit
$e = explode(" ", microtime());
$ende = $e[1] + $e[0];
// Ausgabe
echo implode(', ',$data)."<br><br>";
echo count($data).' Primzahlen<br><br>';
echo number_format(($ende-$start)*1000, 1, ',', '.').' ms';
?>

... soweit so gut dacht ich mir ... bis mir auffiel, dass mein script mehr primzahlen findet als TBT's?! -> man prüfe die Primzahlen.

vielleicht stehe ich nur gottverlassen im wald und hoffe dass ich wenigstens mit meiner for-schleifen version noch n paar millisekunden rausholen konnte, oder euer script verschluckt zahlen.

grüße aus meiner welt

[derHund]

1. die 3er braucht man nicht in $data, und

was meinst du? die vielfachen von 3 braucht man nicht? man braucht auch die vielfachen von 4, 5, 6, 7, 8, .. etc pp. nicht ...
das ist doch das prinzip des siebes ...

2. die for-schleife mit $$i sucht auch nach geraden $$i

da hast recht ... wieder ne microsekunde gespart
eigentlich brauch man doch sowieso erst bei $ii^2 anfangen, weil alle möglichen vorherigen schon vorher ausgesiebt wurden ... ich werds morgen noch mal probieren ... *g

oder euer script verschluckt zahlen.

da TBT und ich unabhängig voneinander, mit eigens geschriebenen algorithmen gleiche anzahl an primzahlen erhielten, eher unwahrscheinlich, imho.

ich hab auch die ersten 100.000 mit einer primzahlen-tabelle verglichen, sie stimmten ...

[TBT]

Vorschläge von Hund aufgenommen

// Startzeit
$s = explode(' ', microtime());
$start = $s[1] + $s[0];
// max Wert
$max = 500000;
// Datenarray aufbauen
$data = array();
$data[2] = 2;
for( $i = 3; $i < $max; $i += 2 )
    $data[$i] = $i;
// nicht Primzahlen loeschen
$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 )
            unset( $data[$ii] );
    }
}
// Endzeit
$e = explode(" ", microtime());
$ende = $e[1] + $e[0];
// Ausgabe
echo implode(', ',$data)."<br><br>";
echo count($data).' Primzahlen<br><br>';
echo number_format(($ende-$start)*1000, 1, ',', '.').' ms'; 

=> 1,85 Sek

ab jetzt dürfte nurnoch Milisekundenhascherei möglich sein?

[derHund]

ab jetzt dürfte nurnoch Milisekundenhascherei möglich sein?

denke ich auch ...

[jahlives]

Erstmal sorry, dass ich so wat altes wieder ausgrabe. Aber ich habe in den letzten zwei Tagen in JS und PHP meine Primzahlenscripte fertig geschrieben. Ich denke v.a. beim PHP Script könnte noch etwas Optimierungspotenzial vorhanden sein.
Zahlenbereich 0-500'000 --> 41538 Primen 1.65 sek
Code (falls es jemanden interessiert)

function primes(){
    $anfang = microtime(true);
    $temp = range(0,$_POST['ende'],1);
    $ende_abs = (int) sqrt($_POST['ende'];
    unset($temp[0],$temp[1]);
    while(list($key,$wert) = each($temp){
        if($wert > $ende_abs){
            break;
        }
        $ende = (int) ($_POST['ende']/$wert);
        $ende += 1;
        $i = $wert;
        while($i < $ende){
            unset($temp[$wert*$i];
            if($wert == 2){
                $i += 1;
            }else{
                $i += 2;
            }
        }
    }
    $ende = microtime(true);
    $diff = $ende - $anfang;
    $ende = count($temp);
    return 'Es wurden '.$ende.' Primzahlen gefunden. Die Suche dauerte '.$diff.' Sekunden.';
} 

Gruss

tobi

EDIT:

---

Kleine Codeanpassung bringt ca 1/10 Sek bei Primen bis 500'000

---

[jahlives]

function primes($zahl){
    $anfang = microtime(true);
    $temp = range(0,$zahl,1);
    unset($temp[0],$temp[1]);
    $ende = (int) $zahl/2;
    for($i=2;$i<=$ende;$i+=1){
        unset($temp[2*$i]):
    }
    $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){
            unset($temp[$wert*$i];
            $i += 2;
        }
    }
    $ende = microtime(true);
    $diff = $ende - $anfang;
    $ende = count($temp);
    return array($temp,$diff);
} 

Primzahlen 0- 100'000 --> 9592 Stücke --> 0.3 sek...

Gruss

tobi

[jahlives]

function primes($zahl){
    $temp = range(0,$zahl,1);
    unset($temp[0],$temp[1]);
    $ende = (int) $zahl/2;
    for($i=2;$i<=$ende;$i+=1){
        unset($temp[2*$i]):
    }
    $anfang = microtime(true);//kleiner Beschiss zum Optimieren ;-)
    $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){
            unset($temp[$wert*$i];
            $i += 2;
        }
    }
    $ende = microtime(true);
    $diff = $ende - $anfang;
    $ende = count($temp);
    return array($temp,$diff);
} 

Mit obigen kleinem "Bschiss" sinkt die Zeit für 0-500'000 auf 0.8 sek. Ich weiss dies ist nicht sauber: Den Zahlenbereich wollte ich ursprünglich mit

$temp = range(3,$zahl,2); 

initialisieren, da, bis auf die 2, keine gerade Zahl eine Prime sein kann. Dies scheitert jedoch daran, dass dann die Indecies im Array nicht mehr dem Wert entsprechen und somit die unsets ins Leere laufen.
Drum habe ich jetzt die Zeitmessung erst nach Erstellung des Arrays in obengenannter(range(3,$zahl,2) Form angeworfen. Das macht gut 500'000 Rechenoperationen weniger wenn die geraden Zahlen bereits beim Erstellen gar nicht berücksichtig werden.

Gruss

tobi

[jahlives]

Letzte Optimierung...

In meiner langen, ereignislosen Nachtschicht, habe ich nochmals den
Code überarbeitet. Das grösste Optimierungspotenzial hatte der
Aufbau des Arrays. Dort habe ich bis anhin am meisten Zeit
liegenlassen. Zuerst mit Range ein Array aufzubauen und dann die
geraden Zahlen rauszuputzen, das dauerte eben doch zu lange.
Nun habe ich den Aufbau des Arrays in eine eigene Fkt ausgelagert
und eine zweite zum Rausstreichen der ungeraden Kompositzahlen.

function init_array($zahl){
    $anfang = microtime(true);
    $temp = array();
    $temp[2] = 2;
    for($i=3;$i<=$zahl;$i+=2){
        $temp[$i] = $i;
    }    
    $diff = round(microtime(true) - $anfang,6);
    return array($temp,$diff);
}
function primes($temp,$zahl){
    $anfang = microtime(true);
    $ende_abs = (int) sqrt($zahl);
    $i = 0;
    while(list($key,$wert) = each($temp)){
        $i += 1;
        if($wert > $ende_abs){
            break;
        }
        $ende = (int) ($zahl/$wert);
        $ende += 1;
        $i = $wert;
        while($i < $ende){
            unset($temp[$i*$wert]);
            $i += 2;
        }
    }
    $diff = round(microtime(true) - $anfang,6);
    return array($temp,$diff);
} 

Auf einem AMD Sempron 2800+ mit Win2k und PHP5 dauert es nun 1.3 sek im Schnitt für die Primen von 0-500'000.

Gruss

tobi