Schnellere Funktion als StreamWriter

BiedermannS · 5. September 2012, 16:07

Wie lässt du denn die Primzahlen berechnen? also mit welchem Algorithmus?

FritschFisch · 5. September 2012, 16:11

@fire88 das hab ich ja auch versucht, nur um eine collection in ein array umzuwandeln, das braucht ewig ... es ist übrigens eine collection, weil ein array so unflexibel ist
@BiedermannS so:

VB.NET-Quellcode

primes.Clear()
primes.Add(2)
For prime As Integer = 3 max_primes Step 2
teilbar = False
For i As Integer = 2 To Math.Ceiling(prime ^ 0.5)
If prime Mod i = 0 Then
teilbar = True
Exit For
End If
Next
If teilbar = False Then
primes.Add(prime)
End If
Next

max_primes gibt an, bis zu welcher zahl (einschließlich) nach primzahlen gesucht werden soll

jvbsl · 5. September 2012, 16:18

prime ^ 0.5 -> Math.Sqrt(prime)
Und ich denke da gibt es bessere Algorithmen...
en.wikipedia.org/wiki/Sieve_of_Atkin

BiedermannS · 5. September 2012, 16:20

ich lass das ganze gerade in 2 threads laufen.

Das ist Thread Nummer 1. Der berechnet nur und schiebt die Zahlen in eine Queue.

VB.NET-Quellcode

Private Const Zwei As UInt64 = 2
Private Const Vier As UInt64 = 4
Sub start(ByRef callback As Action(Of UInt64), ByRef finished As Action)
_Callback = callback
_finished = finished
Dim t As New Threading.Thread(AddressOf running)
t.Start()
End Sub
Private n As UInt64
Private _Callback As Action(Of UInt64)
Private _finished As Action
Sub running()
_Callback(2)
_Callback(3)
For Me.n = 5 To 100000000 Step 2
Prime()
Next
End Sub
Sub Prime()
If n Mod 2 = 0 OrElse n Mod 3 = 0 OrElse n Mod 7 = 0 OrElse n Mod 5 = 0 Then Exit Sub
Dim r As Double = Math.Sqrt(n), f As UInt64 = 11
If r Mod 1 = 0 Then Exit Sub
While f <= r
If n Mod f = 0 Then Exit Sub
f += Zwei
If n Mod f = 0 Then Exit Sub
f += Vier
End While
_Callback(n)
End Sub

FritschFisch · 5. September 2012, 16:21

@jvbsl ja ich weiß, aber ich bin der meinung irgendwo gelesen zu haben, das der computer "^ 0.5" schneller rechnen kann, als tatsächlich die quadratwurzel zu ziehen

Fire88 · 5. September 2012, 16:23

hm, ich sehe das es wirklich sehr lange dauert bis ca 5mio zahlen in einen string oder array geschriben werden.

habe gerade nur eine symple schleife gemacht 0 to 5000000

und das dauert bei mir 4.3min ca...

FritschFisch · 5. September 2012, 16:25

sorry, dass hört sich jetzt sicher blöd an, aber mir geht es nicht darum wie schnell er die zahlen berechnet, sondern wie schnell er sie abspeichert

(trotzdem danke jvbsl)

Fire88 · 5. September 2012, 16:27

eventuell währe es schneller in php. das speichern alleine sollte eig. nicht so lange dauern. weil wen du es in ein string ladest und am ende writealltext machst, dan schreibt es alles auf einmal. wen du aber nach jedem schleifendurchlauf schreibst... dan muss er die datei zich mal öffnen schreiben schließen.

FritschFisch · 5. September 2012, 16:29

ich kenne php, und weiß wie das gehen würde, nur würde ich das gerne als exe speichern. genauso möchte ich es in vb nur vorschreiben, um es dann später in c++ umzusetzen, da c++ ja doch nocht schneller ist als vb

BiedermannS · 5. September 2012, 16:29

@Fire88: wie erstellst du die Strings bzw. Arrays?

Strings mit stringbuilder.append?

Array mit vordefinierten Grenzen? oder jedes mal neu dimensionieren?

PHP ist eine ScriptSprache für Webanwendungen. O.o

Wenn man es schnell will, dann c++. Und den stream offen lassen und nicht immer neu öffnen.

picoflop · 5. September 2012, 16:32

FritschFisch schrieb:

aber mir geht es nicht darum wie schnell er die zahlen berechnet

Ich bin immer noch der Überzeugung, dass das Schreiben kaum jemals Stunden dauern kann ... (PS: C wäre dann aber auch nicht schneller!)

Zeig doch mal deinen "Speichercode" !

BiedermannS · 5. September 2012, 16:36

ich bin jetzt ca bein n > 64000000

und hab dafür eine halbe stunde gebraucht. Berechnen + Schreiben

FritschFisch · 5. September 2012, 16:37

der steht zwar schon am anfang, aber hier nochmal:

VB.NET-Quellcode

Using sw As New IO.StreamWriter(Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments) & "\primes.txt")
For i As ULong = 1 To primes.Count
sw.WriteLine(primes(i))
Next
End Using
Console.ForegroundColor = ConsoleColor.Green
Console.WriteLine("File """ & Environment.GetFolderPath(Environment.SpecialFolder.MyDocuments) & "\primes.txt"" was successful saved!")
Console.ForegroundColor = ConsoleColor.Gray
My.Computer.Audio.PlaySystemSound(Media.SystemSounds.Asterisk)

der wird aber nur gestartet, wenn man einen Befehl eingibt, also nicht nach jeder primzahl

BiedermannS · 5. September 2012, 16:41

FritschFisch schrieb:

For i As ULong = 1 To primes.Count
sw.WriteLine(primes(i))
Next

Mich wundert dass das nicht abstürzt. Gehört da nicht ein - 1 hin

VB.NET-Quellcode

For i As ULong = 0 To primes.Count - 1
sw.WriteLine(primes(i))
Next

FritschFisch · 5. September 2012, 16:42

Collections sind nicht null-basiert

picoflop · 5. September 2012, 16:50

FritschFisch schrieb:

er wird aber nur gestartet, wenn man einen Befehl eingibt,

Ja clever. JEDESMAL wird eine komplett neue Datei erzeugt ...

FreakJNS · 5. September 2012, 16:55

mal noch eine idee^^ Ich weiß zwar nicht was ein BuffredStream genau macht - ich vermute aber ähnliches:
nicht jede Primzahl einzeln speichern, sondern Blockweise. Ein Block könnte z.B. 1000 Primzahlen lang sein... Rechnen geht eben flott - schreiben langsam.

also immer ca. 1000 (oder noch mehr?) Zahlen in einen Buffer (bytearray) schreiben und erst diesen Buffer per Stream auf die Platte hauen.

Aber vor allem die Zahlen BINÄR abspeichern! BitConverter-Klasse regelt^^
Vergleiche mal: 1234567 als string brauch 7byte speicher - binär als integer aber nur 4byte. Jeder Integer braucht eben nur 4Byte. Ein Double immer 8 Byte.
Vorteil ist außerdem, dass du kein Trennzeichen mehr einzubauen brauchst - du liest blöcke von n-Bytes aus und konvertiertst sie in eine Zahl. Dann kommen die nächsten n-Bytes für die nächste usw

lg

FritschFisch · 5. September 2012, 17:00

okay, das kann ich dann noch mal ausprobieren. danke

BiedermannS · 5. September 2012, 17:06

Zum Thema berechnen ist schneller.

Bei mir laufen gerade, wie bereits erwähnt, zwei threads. Berechnen und Schreiben.

Und die Queue die die beiden verbindet, hatte nie mehr wie ein paar Einträge. Je nach dem wie Groß die Zahl bereits ist.

hier mein Ergebnis:

Finished in 3194279 ms! (53 Min 14,3 Sec)

In Wirklichkeit wären es weniger, da ich zwischendurch immer wieder angehalten habe um zu sehen wie weit ich schon bin.

Das Ergebnis bezieht sich auf das Berechnen aller Primzahlen von 2 bis 100.000.000 und das Schreiben auf die Festplatte. Insgesamt 5761456 Primzahlen.

Hier mein Code:

Spoiler anzeigen

VB.NET-Quellcode

Public q As New Queue(Of UInt64)
Sub callback(ByVal n As UInt64)
q.Enqueue(n)
End Sub
Private running1 As Boolean = False
Private running2 As Boolean = False
Private stp As New Stopwatch
Sub finished1()
running1 = False
End Sub
Function finished2() As Boolean
If Not running1 And q.Count < 1 Then
running2 = False
stp.Stop()
InputBox("LOL", DefaultResponse:="Finished in " & stp.ElapsedMilliseconds & " ms!")
Return True
Else
Return False
End If
End Function
Private Sub Button1_Click(sender As Object, e As System.EventArgs) Handles Button1.Click
stp.Start()
Dim c As New Primes
running1 = True
c.start(AddressOf callback, AddressOf finished1)
Dim w As New writer
running2 = True
w.start(q, AddressOf finished2)
End Sub
Class writer
Private sw As New IO.StreamWriter("c:\primes.txt", False, System.Text.Encoding.Default)
Private _finished As Func(Of Boolean)
Private _q As Queue(Of UInt64)
Sub start(ByRef q As Queue(Of UInt64), ByRef finished As Func(Of Boolean))
_q = q
_finished = finished
Dim t As New Threading.Thread(AddressOf run)
t.Start()
End Sub
Sub run()
Do Until _finished()
If _q.Count > 0 Then
sw.WriteLine(_q.Dequeue)
sw.Flush()
End If
Loop
End Sub
End Class
Class Primes
Private Const Zwei As UInt64 = 2
Private Const Vier As UInt64 = 4
Sub start(ByRef callback As Action(Of UInt64), ByRef finished As Action)
_Callback = callback
_finished = finished
Dim t As New Threading.Thread(AddressOf running)
t.Start()
End Sub
Private n As UInt64
Private _Callback As Action(Of UInt64)
Private _finished As Action
Sub running()
_Callback(2)
_Callback(3)
For Me.n = 5 To 100000000 Step 2
Prime()
Next
_finished()
End Sub
Sub Prime()
If n Mod 2 = 0 OrElse n Mod 3 = 0 OrElse n Mod 7 = 0 OrElse n Mod 5 = 0 Then Exit Sub
Dim r As Double = Math.Sqrt(n), f As UInt64 = 11
If r Mod 1 = 0 Then Exit Sub
While f <= r
If n Mod f = 0 Then Exit Sub
f += Zwei
If n Mod f = 0 Then Exit Sub
f += Vier
End While
_Callback(n)
End Sub
End Class

Ist aber noch nicht zu 100% optimiert.

Edit:
@FreakJNS: Binär speichern würde es noch etwas schneller machen.
und die Klasse für den Writer arbeitet mit einer do loop schleife ohne events, da ließen sich auch noch unnötige aufrufe vermeiden.

FritschFisch · 5. September 2012, 17:24

Okay... LOL, also Queue kannte ich noch gar nicht aber scheint eine gute Lösung zu sein, Danke

EDIT:
Noch eine Frage:
bei mir findet er nur 5761455 Primzahlen, das ist eine weniger als bei dir. weißt du, woran das liegen könnte?

Schnellere Funktion als StreamWriter

VB.NET-Quellcode

VB.NET-Quellcode

FritschFisch schrieb:

VB.NET-Quellcode

FritschFisch schrieb:

VB.NET-Quellcode

FritschFisch schrieb:

VB.NET-Quellcode

Tags

Ähnliche Themen

10 Benutzer haben hier geschrieben