[HaBo]

**bitmuncher** · 11.04.07, 19:41

Zitat:

Original von Elderan
Bei deinem Schleifendurchlauf würde also 30000 mal neuer Speicher reserviert, und das Array würde 30000 mal verschoben werden, was sehr Zeitintensiv ist.

Was auch immer man unter "zeitintensiv" versteht.

Code:

bitmuncher@deepthought:~$ cat test.php
<?
for($i=0; $i<=30000; $i++) {
  $meinarray[$i] = '';
}
?>
bitmuncher@deepthought:~$ time php test.php

real    0m0.093s
user    0m0.080s
sys     0m0.004s

my2$/100 · 12.04.07, 15:18

Zitat:

Original von bitmuncher
Was auch immer man unter "zeitintensiv" versteht.

Vielleicht bedeutet es, dass die Ermittlung der Primzahlen von 1 bis 1 Mio. in PHP schneller geht, als ein ebenso großes Array anzulegen. :O

Code:

my2cent@hover:~$ nice -20 ./prim.php 
Leeres Array bis 1000000 erzeugt: : 2.400700 Sek. (2.400 ?s pro Element) 
Primzahlen bis 1000000 berechnet: : 2.077223 Sek. 
78498 Primzahlen gefunden

PHP-Code:

 
#!/usr/bin/php
<?php
# Anzahl der Arayelemente
$MAX = 1000000;

###### 1. Zeitmessung #######
# Erzeuge ein leeres Array mit MAX Elementen

$zeitmessung1=microtime();

for($i=0; $i<$MAX; $i++)
   $a[$i]='';

$zeitmessung2=microtime();

### ENDE ###

print_stats($zeitmessung1, $zeitmessung2, $MAX, "Leeres Array bis ".$MAX." erzeugt: ");

####### 2. Zeitmessung ########
# Ermittle die Primzahlen bis MAX (Array ist vorhanden)

$zeitmessung1=microtime();

$grenze = sqrt($MAX);
$a[0]=1;
$a[1]=1;

# Produkte als nicht-Primzahlen markieren
for($i=3; $i<=$grenze; $i+=2)
{
   $a[$i] or $j = $i*$i and $step = $i<<1;
   while($j<$MAX)
   {
     $a[$j] = 1;
     $j+=$step;
   }
}

# gerade Zahlen als nicht-Primzahlen markieren
$i=4;
$j=$MAX-2;
while($i<$j)
{
  $a[$i] = 1;
  $a[$j] = 1;
  $i+=2;
  $j-=2;
}

$zeitmessung2=microtime();

### ENDE ###

print_stats($zeitmessung1, $zeitmessung2, -1, "Primzahlen bis ".$MAX." berechnet: ");

count_prim($a, $MAX);

# Funktion gibt Laufzeitinformtionen aus
function print_stats($z1, $z2, $count, $comment)
{
  $temp=explode(" ",$z1);
  $zeit1=$temp[0]+$temp[1];

  $temp=explode(" ",$z2);
  $zeit2=$temp[0]+$temp[1];

  $zeit=$zeit2-$zeit1;
  $ratio=$zeit/$count*1E6;

  $ratio=substr($ratio,0,5);
  $zeit=substr($zeit,0,8);

  if($count>0)
    print("$comment: $zeit Sek. ($ratio ?s pro Element) \n");
  else
    print("$comment: $zeit Sek. \n");
}

# Funktion gibt Anzahl gefundener Primzahlen aus 
function count_prim($a, $MAX)
{
   for($i=3, $c=1; $i<$MAX; $i++)
      $a[$i] or $c++;

   print ("$c Primzahlen gefunden\n");
}
?>

Wenn man sich noch drauf einigt, dass gerade Zahlen (außer der 2) keine Primzahlen sein können und die 2te Schleife weg lässt, geht's nochmal 30% schneller. Hoffentlich sind da keine groben Schnitzer drin - hatte nicht die Zeit 78498 Zahlen zu prüfen.

**Elderan** · 12.04.07, 16:54

Hallo,
mal zum vergleich:
Leeres Array in C# mit 1 Mio. Elementen: Zeitspanne nicht messbar bei höchster Genauigkeit unter Windows (also unter 0,01 Sekunden)

Array mit Zahlen 0 - 1 Mio: 0 Ticks oder 156250 Ticks was ca. 0,015 Sek entspricht*. Genauer gings leider nicht.

* Durch 1000 mal ausführen des Tests kam ich auf 0,013 Sekunden pro Erstellung des Arrays mit Zahlen von 0 - 1 Mio..

Tara · 06.05.07, 22:36

Hi!

@ Indi und andere:

Hat jemand von euch mal so einen 8/30-Eratosthenes implementiert? Das Auslassen der geraden Zahlen ist ja noch einfach (mein Delphi-Sieb schafft damit Primzahlen bis 1 Mio in 7 ms, ich verwende TBits), aber wenn ich versuche, Vielfache von 3 und 5 zu überspringen, gibt es beim Ausstreichen immer Murks oder die Rechnung wird so umständlich, daß das Programm langsamer wird.

Einen hübschen Algo hierzu würde ich gern mal sehen!

**CDW** · 07.05.07, 01:27

hier gibt es was:
[link] Project Euler - Programmieraufgaben
(zusammenzählen aller Primzahlen bis 1Mio mit Erastotheles-Algorithmus: ca. 85ms auf einem alten P4).
Ob diese Umsetzung in der vorhandenen Form Dir was bringt, sei aber dahingestellt

Allerdings, wenn Du den Code postest, könnte man nach dem Fehler suchen

**Elderan** · 07.05.07, 12:28

Hallo,
für das Sieb findest du hier grundlegende Überlegungen, aber hier werden weitere Überlegungen zur Optimierung angestellt.

Wie du am Diagramm ganz unten sehen kannst, dauert das Außlassen von z.B. 2 und 3 länger als alle Zahlen zu verwenden. Erst ab den Zahlen 2-7 bekommst du einen Geschwindigkeitsvorteil, der bei 2-13 maximal ist (zumindest dort).

Indi · 07.05.07, 16:34

@Tara:
Ja, hatte ich implementiert. Allerdings nicht mit einem speziellen Algorithmus. Das Schema wiederholt sich praktisch immer nach allen 30 Zahlen. Einmal ist es die zweitfolgende Zahl die geprüft werden soll, dann die drittfolgende Zahl oder ähnlich. Kann man sich ganz leicht für einen 30er-Block raussuchen, welche Reihenfolge man verwenden muss. Kann man dann in ein Array speichern zb.

Tara · 07.05.07, 17:53

Hi!

Diese Informatikjahr-Seite ist ja wirklich toll, nicht nur zum Thema Eratosthenes. Alles schön genau erklärt, und auch Nicht-Informatiker-kompatibel!

Nur gut daß ich sie zu Beginn meiner Überlegungen noch nicht kannte, das hätte ja jegliches Nachdenken meinerseits abgewürgt!

Mein eigenes Delphi-Programm sieht so aus:

Code

Mit den Infos von dieser Seite versuche ich mal, was besseres draus zu machen. Danke!

@ Indi:
Das Schema ist ja wirklich überichtlich, habe es mir gerade aufgemalt.

edit: Hab noch schnell den Zugriff auf die Zahlen ergänzt, so daß es Euler10 rechnet. Primzahl 2 muß separat behandelt werden.

Anzeige

- Anzeige -

07.05.07, 01:27	#20 (permalink)
CDW Moderator Registriert seit: 20.07.05 Likes: 202	hier gibt es was: [link] Project Euler - Programmieraufgaben (zusammenzählen aller Primzahlen bis 1Mio mit Erastotheles-Algorithmus: ca. 85ms auf einem alten P4). Ob diese Umsetzung in der vorhandenen Form Dir was bringt, sei aber dahingestellt Allerdings, wenn Du den Code postest, könnte man nach dem Fehler suchen __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

07.05.07, 17:53	#23 (permalink)
Tara Registriert seit: 10.04.07 Likes: 0	Hi! Diese Informatikjahr-Seite ist ja wirklich toll, nicht nur zum Thema Eratosthenes. Alles schön genau erklärt, und auch Nicht-Informatiker-kompatibel! Nur gut daß ich sie zu Beginn meiner Überlegungen noch nicht kannte, das hätte ja jegliches Nachdenken meinerseits abgewürgt! Mein eigenes Delphi-Programm sieht so aus: Code Code: const PrimeMax = 1000000; var i, j, n, HalfPrimeMax: Integer; Sum: Int64; IsComposite: TBits; begin HalfPrimeMax := PrimeMax div 2; IsComposite := TBits.Create; IsComposite.Size := HalfPrimeMax+1; for i := 1 to Trunc(Sqrt(HalfPrimeMax)) do if not IsComposite.Bits[i] then begin j := i+i+1; n := jj shr 1; while n <= HalfPrimeMax do begin IsComposite.Bits[n] := True; Inc(n,j) end; end; Sum := 2; for i := 1 to HalfPrimeMax do if not IsComposite.Bits[i] then Inc(Sum,2i+1); end; Mit den Infos von dieser Seite versuche ich mal, was besseres draus zu machen. Danke! @ Indi: Das Schema ist ja wirklich überichtlich, habe es mir gerade aufgemalt. edit: Hab noch schnell den Zugriff auf die Zahlen ergänzt, so daß es Euler10 rechnet. Primzahl 2 muß separat behandelt werden.

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

Ähnliche Themen
Thema	Autor	Forum	Antworten	Letzter Beitrag
Primzahlen	T1G3R	Cryptography & Encryption	3	31.10.08 13:08
[c++] Primzahlengenerator: Ganzzahlige primzahlen	_fux_	Code Kitchen	15	17.09.08 21:47
Script für automatische Tests erstellen??	ecologys	Code Kitchen	0	29.06.04 13:46
2 versch. versionen von md5?	immado	Cryptography & Encryption	5	18.04.04 17:06
Tests von Testreich.com	kressi	Umfragen	12	18.12.03 15:42

12.04.07, 16:54	#18 (permalink)
Elderan Moderator Themenstarter Registriert seit: 30.03.04 Likes: 14	Hallo, mal zum vergleich: Leeres Array in C# mit 1 Mio. Elementen: Zeitspanne nicht messbar bei höchster Genauigkeit unter Windows (also unter 0,01 Sekunden) Array mit Zahlen 0 - 1 Mio: 0 Ticks oder 156250 Ticks was ca. 0,015 Sek entspricht. Genauer gings leider nicht. Durch 1000 mal ausführen des Tests kam ich auf 0,013 Sekunden pro Erstellung des Arrays mit Zahlen von 0 - 1 Mio..

06.05.07, 22:36	#19 (permalink)
Tara Registriert seit: 10.04.07 Likes: 0	Hi! @ Indi und andere: Hat jemand von euch mal so einen 8/30-Eratosthenes implementiert? Das Auslassen der geraden Zahlen ist ja noch einfach (mein Delphi-Sieb schafft damit Primzahlen bis 1 Mio in 7 ms, ich verwende TBits), aber wenn ich versuche, Vielfache von 3 und 5 zu überspringen, gibt es beim Ausstreichen immer Murks oder die Rechnung wird so umständlich, daß das Programm langsamer wird. Einen hübschen Algo hierzu würde ich gern mal sehen!

07.05.07, 12:28	#21 (permalink)
Elderan Moderator Themenstarter Registriert seit: 30.03.04 Likes: 14	Hallo, für das Sieb findest du hier grundlegende Überlegungen, aber hier werden weitere Überlegungen zur Optimierung angestellt. Wie du am Diagramm ganz unten sehen kannst, dauert das Außlassen von z.B. 2 und 3 länger als alle Zahlen zu verwenden. Erst ab den Zahlen 2-7 bekommst du einen Geschwindigkeitsvorteil, der bei 2-13 maximal ist (zumindest dort).

07.05.07, 16:34	#22 (permalink)
Indi Member of Honour Registriert seit: 02.10.01 Likes: 0	@Tara: Ja, hatte ich implementiert. Allerdings nicht mit einem speziellen Algorithmus. Das Schema wiederholt sich praktisch immer nach allen 30 Zahlen. Einmal ist es die zweitfolgende Zahl die geprüft werden soll, dann die drittfolgende Zahl oder ähnlich. Kann man sich ganz leicht für einen 30er-Block raussuchen, welche Reihenfolge man verwenden muss. Kann man dann in ein Array speichern zb.

[HaBo]

Primzahlen mit versch. Tests