Programm Optimierung
Hi ihr :hi: ,
Ich habe ein Programm zum Herausfiltern von Primzahlen geschrieben :coder: . Allerdings ist dieses recht langsam und ich wollte mal fragen, ob irgendjemand eine Idee hat, wie ich dieses Programm zu Gunsten der Geschwindigkeit verändern bzw. optimieren kann. :?: Hier der Code:
Delphi-Quellcode:
_______________
unit Primzahlen_Generator;
interface uses ExtCtrls, Math, SysUtils, Classes; type TPrimzahlen_Generator = class private A_Zahlen : Array of Integer; Zahlengrenze : Integer; private procedure Filtern (Panel: TPanel; Grenze : Integer); virtual; procedure Loeschen_Aufruecken (Pos: Integer); virtual; procedure Speichern (Speicherort: String); virtual; procedure Werte_Uebernehmen (Grenze: Integer); virtual; public procedure Ausfuehren (Grenze: Integer; Speicherort: String; Anzeigepanel: TPanel); virtual; end; implementation procedure TPrimzahlen_Generator.Filtern (Panel: TPanel;Grenze : Integer); var i, j : Integer; begin for j := 2 to round(power(Grenze+1,1/2)) do begin for i := Length(A_Zahlen)-1 downto j-1 do begin if (A_Zahlen[i] mod j = 0) and (A_Zahlen[i] <> j) then Loeschen_Aufruecken(i); if i mod 100 = 0 then begin Panel.Caption := 'Noch: '+inttostr(round(power(Length(A_Zahlen)-1,1/2)+1)-j); Panel.Update; end; end; end; Panel.Caption := 'Fertig!'; end; procedure TPrimzahlen_Generator.Loeschen_Aufruecken (Pos: Integer); var i : Integer; begin for i := pos to length(A_Zahlen)-2 do begin A_Zahlen[i] := A_Zahlen[i+1]; end; setlength(A_Zahlen,length(A_Zahlen)-1); end; procedure TPrimzahlen_Generator.Speichern (Speicherort: String); var Datei: TextFile; i : Integer; begin AssignFile(Datei, Speicherort + 'Primzahlen von 2 bis '+inttostr(Zahlengrenze)+'.txt'); Rewrite(Datei); try WriteLn(Datei,inttostr(Length(A_Zahlen))); for i := 0 to Length(A_Zahlen)-1 do begin WriteLn(Datei,inttostr(i)+' - '+inttostr(A_Zahlen[i]) ); end; finally CloseFile(Datei); end; end; procedure TPrimzahlen_Generator.Werte_Uebernehmen (Grenze: Integer); var i : Integer; begin setlength(A_Zahlen,Grenze-1); for i := 2 to length(A_Zahlen)-1 do begin A_Zahlen[i-2] := i; end; Zahlengrenze := Grenze; end; procedure TPrimzahlen_Generator.Ausfuehren (Grenze: Integer; Speicherort: String; Anzeigepanel: TPanel); begin Werte_Uebernehmen(Grenze); Filtern(Anzeigepanel,Grenze); Speichern(Speicherort); end; end. Lg Florian :bounce2: |
Re: Programm Optimierung
Ein mathematisches Verfahren zur Primfaktorenzerlegung sollte da deutlich schneller sein
[Edit: Tippfehler entfernt] |
Re: Programm Optimierung
Moin Moin Florian,
wollte mal darauf hinweisen, dass es in den Foren eine SuFu gibt, wo man z. B. auf folgenden Link stößt. Hier kann man sich prima Anregungen hohlen. |
Re: Programm Optimierung
Ich würde sagen: Trenne den Code von der Darstellung.
Du benutzt so was ähnliches wie das Sieb des Eratosthenes - aber warum nur so ähnlich? Du möchtest alle Primzahlen von 0 bis X finden ? Dann erstelle dir ein dyn. Array of Boolean mit der Länge X + 1. Dort setzt du alle Werte erstmal auf true (true heißt später Primzahl, false keine Primzahl) nur den Eintrag 0 und 1 auf false (per Def. keine Primzahl) Dann gehst du das Array durch, und zwar streichst du alle vielfachen der 2 weg, und gehst dann zur nächsten, nicht weggestrichenen Zahl:
Code:
Im Anschluss kannst du dann alle Primzahlen (die, bei denen arr[y] true ist) ausgeben ;)
var
i, j: Integer; for i := 2 to sqrt(X) do // Es gibt eine Fkt. sqrt() statt power(...) begin if not arr[i] then continue; j := i * 2; while j <= X do begin arr[j] := false; j := j + i; end; end; |
Re: Programm Optimierung
Vielen Danke für die schnellen Antworten, ich werde es ausprobieren :thumb:
|
Re: Programm Optimierung
Ich würde das mit einem Bitvektor machen. Der Vorteil: Verringerung des Speicherverbrauchs um den Faktor 32 (oder 8, ich kann mir nie merken, wie Boolean-Arrays jetzt genau aussehen)
|
Re: Programm Optimierung
was ist denn "Bitvektor" ... ich habe mal im inet geguckt und kein tutorial oder ähnliches gefunden.
|
Re: Programm Optimierung
Statt einer Variable nimmt man ein Bit einer variable. Die man dann durch Ausmaskieren abprüfen kann
|
Re: Programm Optimierung
Ich denke er meint einfach nur das er kein Array of Boolean nehmen würde sondern einfach bits setzen damit somit für jede Zahl nur ein bit benötigt.
|
Re: Programm Optimierung
Ja, genau das meine ich. Delphi stellt dafür sogar eine Klasse zur Verfügung: TBits
Also wenn immer man eine große Anzahl an true/false-Werten verwalten sind, sind Bitvektoren eine mögliche, speichersparende Alternative zu Boolean-Arrays mit geringem Mehraufwand an Performance. |
Alle Zeitangaben in WEZ +1. Es ist jetzt 07:39 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz