[Contest] Primzahlen Contest

Page 2 of 2 1 2
03/07/2013 15:56 Lawliet#16
Quote:
Originally Posted by butter123 View Post
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:

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.
03/07/2013 15:59 butter123#17
meine messungen haben auch um ca 5ms geschwankt und ich hab nur grob übers auge gemittelt, aber die 20ms mittlerweile solltens schon sein^^
03/07/2013 16:05 lolkop#18
Quote:
Originally Posted by butter123 View Post
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...
03/07/2013 16:12 butter123#19
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
03/07/2013 16:15 lolkop#20
Quote:
Originally Posted by butter123 View Post
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 =)
03/07/2013 16:31 -STORM-#21
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.
03/07/2013 16:40 butter123#22
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.
03/07/2013 16:45 -STORM-#23
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.
03/07/2013 16:57 lolkop#24
Quote:
Originally Posted by -STORM- View Post
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:
Code:
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.
03/07/2013 17:45 butter123#25
auch da kannste wieder if durch switch ersetzen^^ wieder 10 ms


hatte sowas auch schonmal getestet:
Switch schneller Select schneller If
03/07/2013 18:22 lolkop#26
Quote:
Originally Posted by butter123 View Post
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...
03/07/2013 20:43 Lawliet#27
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.
03/07/2013 21:09 lolkop#28
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
03/07/2013 21:51 Lawliet#29
alles klar :)
#closed
Page 2 of 2 1 2