[Contest] Primzahlen Contest

[Lawliet]

Originally Posted by butter123

das problem was ich bei wettbewerben zu so bekannten verfahren sehe ist, dass man das als wissenschaftlich am schnellsten annerkannte verfahren implementiert und fertig. und das alle das skript benutzen und es noch irgendwie tweaken.

ich konnte lolkops skript um ca 10 ms verbessern^^
1. sqrt($limit) vorher angeben und nicht bei jedem durchlauf neu berechnen
2. beim streichen der zahlen nicht bei 2*$a anfangen sondern bei $a*$a
3. $p nicht mit 0 füllen (glaube macht kein unterschied, passiert sowieso)

hier das skript:

 Spoiler

PHP Code:

#include <array.au3>
$z =  TimerInit()
getPrimesTo(100000)
$x = TimerDiff($z)
ClipPut($x)


Func getPrimesTo($limit)
    Local $t[$limit+1], $p[$limit+1]
    Local $c = Sqrt($limit)
    For $a = 2 To $limit
        If $t[$a] <> 1 Then
            If $a <= $c Then
                For $b = $a*$a To $limit Step $a
                    $t[$b] = 1
                Next
            EndIf
            $p[0]+=1
            $p[$p[0]]=$a
        EndIf
    Next
    ReDim $p[$p[0]+1]
    Return $p
EndFunc 


edit: zu atkin: soweit ich das bei wiki verstanden habe setzt man vorraus, dass man weiß, 2,3,5 sind prim. wäre ja auch eig geschummelt sonst könnte man bei lolkop glaub ich auch alle geraden durch ein step 2 rausschmeißen.

10 ms sind 10ms
Ich habe heute morgen den Pseudocode aus Wikipedia in C# implementiert und konnte ihn, bei einem Limit von 1.000.000 auf einen kaum messbaren Bereich optimieren (Messung schwankt zwischen 0 und 15ms). Mal sehen wie es hier weitergeht.

[butter123]

meine messungen haben auch um ca 5ms geschwankt und ich hab nur grob übers auge gemittelt, aber die 20ms mittlerweile solltens schon sein^^

[lolkop]

Originally Posted by butter123

ich konnte lolkops skript um ca 20 ms verbessern^^
1. sqrt($limit) vorher angeben und nicht bei jedem durchlauf neu berechnen
2. beim streichen der zahlen nicht bei 2*$a anfangen sondern bei $a*$a
3. $p nicht mit 0 füllen (glaube macht kein unterschied, passiert sowieso)
4. erste If abfrage durch switch ersetzt. bei der 2. konnte ich kein zeitunterschied erkennen.

bis auf punkt 1 und 2 bringt hier nichts einen vorteil, sondern ändert nur geringfügig die syntax.

aus der definition des siebes wird mir nicht erkenntlich, warum es reicht mit $a^2 zu beginnen, und nicht bei 2*$a. aus der ergebnismenge scheint sich aber zu ergeben, das es mit $a^2 genauso funktioniert.

dennoch ist das ganze denke ich wie bereits gesagt als wettbewerb wohl kaum geeignet...

[butter123]

Es genügt dabei, mit dem Quadrat der Primzahl zu beginnen, da alle kleineren Vielfachen bereits markiert sind. Sobald das Quadrat der Primzahl größer als die Schranke S ist, sind alle Primzahlen kleiner oder gleich S bestimmt: Es sind die nicht markierten Zahlen.

zitat Sieb des Eratosthenes ? Wikipedia ^^

bspw bei 3² ist 3*2 schon durch die 2 gestrichen, da die 3 erst nach der 2 abgefragt wird

[lolkop]

Originally Posted by butter123

Es genügt dabei, mit dem Quadrat der Primzahl zu beginnen, da alle kleineren Vielfachen bereits markiert sind

das steht dort ja... dennoch ist mir nicht klar, warum das der fall ist. wie dem auch sei... offensichtlich ist das sieb definitiv die bestmögliche lösung der aufgabenstellung.

Edit:
ah ja dank deinem beispiel ist mir nun klar, warum bei $a^2 begonnen werden kann =)

[-STORM-]

 Spoiler

Originally Posted by lolkop

meines wissens nach ist doch das immernoch die effizienteste methode primzahlen in einem gewissen intervall zu ermitteln...

umsetzen kann man das ganze relativ simpel so:

#include <array.au3>
$p = getPrimesTo(100000)
_ArrayDisplay($p)

Func getPrimesTo($limit)
	Local $t[$limit+1], $p[$limit+1] = [0]
	For $a = 2 To $limit
		If $t[$a] <> 1 Then
			If $a <= Sqrt($limit) Then
				For $b = 2*$a To $limit Step $a
					$t[$b] = 1
				Next
			EndIf
			$p[0]+=1
			$p[$p[0]]=$a
		EndIf
	Next
	ReDim $p[$p[0]+1]
	Return $p
EndFunc

Edit:
zurückgegeben wird ein array, in welchem der index 0 die anzahl der primzahlen enthält... die restlichen einträge sind die primzahlen selbst.

Nicht dass es für den gesamten Algorithmus viel ausmachen würde, aber statt dem Vergleichen von $a mit sqrt($limit) wäre das Vergleichen von $a*$a mit $limit deutlich effizienter.

Edit, noch ne Kleinigkeit gefunden:
Statt "For $b = 2*a" reicht es, "For $b = $a*$a" zu nehmen, da alle Produkte k*a mit k<a schon als Vielfache von k gestrichen wurden.
In dem Fall würde sich die Wurzel bzw. die Überprüfung von $a*$a komplett erübrigen, da die For-Schleife erst gar nicht durchlaufen wird, wenn $a*$a kleiner als $limit ist.
Macht aber natürlich auch kaum etwas aus.

[butter123]

aus den schwankungen heraus konnte ich bei meinem aktuellen skript keine veränderung sehen ( höchstens 1 ms). liegt daran, dass die wurzel am anfang berechnet wurde, also höchstens einmal ein paar takte mehr benutzt wurden. dafür muss danach aber jedes mal $a² berechnet werden, was mehr takte brauch als direkt $a zu vergleichen.

[-STORM-]

Meinst du, AutoIt ist so optimiert, dass es nicht bei jedem Druchlaufen der For-Schleife die Wurzel neu berechnet, weil die Variable sich in der Schleife nicht ändert?
In dem Fall wäre dein Weg tatsächlich schneller, das Sprachfeature war mir noch nicht bekannt.

Edit: Hab den vorherigen Post jetzt gelesen. Die Wurzel zu Beginn zu speichern, geht natürlich auch.
Du hast ja sogar noch ein bisschen mehr verbessern können als ich.^^
Warum der Switch bei nur einem Case schneller als ein If ist, erschließt sich mir aber nicht. Vielleicht wurde da irgendwas in AutoIt einfach nicht so gut umgesetzt.

[lolkop]

Originally Posted by -STORM-

Meinst du, AutoIt ist so optimiert, dass es nicht bei jedem Druchlaufen der For-Schleife die Wurzel neu berechnet, weil die Variable sich in der Schleife nicht ändert?
In dem Fall wäre dein Weg tatsächlich schneller, das Sprachfeature war mir noch nicht bekannt.

die effizienteste lösung zur problemstellung, sieht dementsprechend so aus:

Func getPrimesTo($limit)
	Local $t[$limit+1],$p[Ceiling($limit/2)+1]=[1,2],$w=Sqrt($limit)
	For $a=3 To $limit Step 2
		If $t[$a]<>1 Then
			If $a<=$w Then
				For $b=$a^2 To $limit Step $a
					$t[$b]=1
				Next
			EndIf
			$p[0]+=1
			$p[$p[0]+1]=$a
		EndIf
	Next
	ReDim $p[$p[0]+1]
	Return $p
EndFunc

noch effizienter geht es nur, wenn man auf ein ergebnis-array verzichtet und direkt das markierungsarray ausgiebt (enthält ja letztendlich auch alle primzahlen)...

die schnellste lösung wäre das ergebnis entsprechend nach einmaliger ausführung zu speichern und direkt auszugeben...
auf diesem wege, wäre das problem wie gesagt immer in unter 1ms lösbar...

sobald man einen festen wertebereich für sein programm vorgegeben hat, ist selbstverständlich immer variante 2 zu bevorzugen, da sämtliche einmalig nötigen berechnungen schon als lösung im script hinterlegt wären.

[butter123]

auch da kannste wieder if durch switch ersetzen^^ wieder 10 ms


hatte sowas auch schonmal getestet:

 Spoiler

PHP Code:

$a = 0
$b = 0
$c = 0

For $i = 0 To 10
    $stamp = TimerInit()
    While TimerDiff($stamp) < 1000
        If Mod($stamp,2) = 0 Then
            $a = $a + 1
        EndIf

    WEnd

    $stamp = TimerInit()
    While TimerDiff($stamp) < 1000
        Select
            Case Mod($stamp,2) = 0
            $b = $b + 1
        EndSelect
    WEnd

    $stamp = TimerInit()
    While TimerDiff($stamp) < 1000
        Switch  Mod($stamp,2)
            Case 0
            $c = $c + 1
        EndSwitch
    WEnd
Next

MsgBox(0,"Result","If: " & $a &" Select: " &$b &" Switch: " &$c) 


Switch schneller Select schneller If

[lolkop]

Originally Posted by butter123

auch da kannste wieder if durch switch ersetzen^^ wieder 10 ms

es gibt dinge, die mache ich aus prinziep schon nicht, weil sie syntaktischer nonsense sind... das von dir angesprochene problem ist ein autoit performance problem und hat nichts mit genereller logik oder übersichtlichkeit zu tun.

switch und select sind für den einsatz in sehr komplexen/verschachtelten abragen gedacht. aus meiner sicht, hat keine der beiden alternativen, hier etwas verloren...

wenn wir hier an einem punkt angekommen sind, welcher sich faktisch nichteinmal mehr wirklich messen lässt, wird das ganze langsam lächerlich...

abgesehen davon sind wettbewerbe wie dieser nur dann sinnvoll, wenn ergebnisse nicht öffentlich gepostet werden, sondern per pn an den te gehen müssen.
letztendlich kann jeder das script von anderen nehmen und eventuell durch einfache syntax spielerein das ganze in punkto performance/übersichtlichkeit/verständlichkeit modifizieren...

das interessante an coding/scripting wettbewerben sollte es aber eigentlich sein, das in der regel JEDES ergebnis sich sehr von den anderen unterscheidet. selbst bei bekannten algorithmen wie diesem, gibt es millionen verschiedene wege der implementierung...

[Lawliet]

Ich fand die Diskussion jedenfalls interessant Leider weiß ich nicht an wen ich jetzt e*Gold schicken ^^
Wenn ihr darauf verzichtet, einfach anmerken, dann überleg ich mir einen neuen Contest mit weniger vorhandenem Input.

[lolkop]

Ich denke niemand hier ist auf die Belohnung angewiesen und alle würden sich über einen neuen, etwas "geheimeren" Wettbewerb freuen :-)

Ergo keine öffentlichen Ergebnisse mehr, sondern nurnoch per pn an dich

[Lawliet]

alles klar
#closed