Tau Funktion (+Ressourcensparend; +Erweiterter Sieb von Eratosthenes)

[sx2008]

Sollte man folgenden Codeabschnitt nicht mit einer For-Schleife anstelle des While-Ersatzkonstrukts programmieren?

Delphi-Quellcode:

i := Primes.Min;
while i <= Primes.Max do
begin
  if Primes.PrimeState[i] = psIsPrime then
    ....

  inc( i );
end;

// also vereinfacht so
for i:=Primes.Min to Primes.Max do
begin
  if Primes.PrimeState[i] = psIsPrime then
    ....
end;

Ich sehe da noch weitere While-Schleifen, die sich mit einer For-Schleife ersetzen lassen.

[Aphton]

Das sind Int64 Werte (Min & Max)!
Edit: Int64 Variablen können in Turbo Delphi Explorer (2006) bei der For Schleife nicht verwendet werden.
Danke für die Aufmerksamkeit!

[sx2008]

Zitat von Aphton:

Das sind Int64 Werte (Min & Max)!
Edit: Int64 Variablen können in Turbo Delphi Explorer (2006) bei der For Schleife nicht verwendet werden.
Danke für die Aufmerksamkeit!

Schade. Der Code wird so schwerer zu lesen als nötig.
Wenn der Bereich von Min & Max grössere Dimensionen annimmt, dann müssste man
vielleicht noch TBoolArray als packed array deklarieren.

[Aphton]

Hmmm, wenn du mir bestätigen könntest, dass packed Array die Performance nicht verschlechtert?
Imho gibts bei packed Arrays kein Aligning, was zu nem kleineren Speicherverbrauch führt, jedoch leidet das Zugreifen auf die Werte darunter!

[sx2008]

Natürlich wird der Zugriff etwas langsamer.
Ich kann jetzt nur grob schätzen, dass der Zugriff vielleicht 30% länger dauert und der gesamte Algorithmus ~10% langsamer. wird
Das müsste man testen und ich hab keinen Compiler auf'm Rechner, der Funktionen in Records mag.
Aber wenn die Werte Min & Max schon auf Werte > 2^31 ausgelegt sind, dann muss man Kompromisse eingehen.

[BUG]

Andererseits muss diese Menge an Speicher ja auch verwaltet werden.
Bei einer Array-Größe von 2^32 sind das selbst bei einem packed Array schon 4GB, da stößt du mit Delphi im Moment auf die Grenzen.
Wenn du auf Bitebene arbeiten würdest, könntest du da mit 512MB auskommen.

[Aphton]

@BUG
Danke, du hast recht. a und b sind teilfremd und müssen nicht zwingend Primzahlen sein.
Weiters - die Indices des Arrays werden getestet, ob es sich um eine Primzahl handelt. Deswegen auch Int64. Dabei muss das Array nicht > 2^32 sein.
Man kann ja Min und Max so wählen, dass die Differenz < 2^32 bzw Max Arbeitsspeicher ist.

Deshalb auch Ressourcensparend: die Tau Funktion geht Blockweise bis zu N/2 durch und belegt nie einen Speicher > 1000 Bytes (PrimeTable - Array of Boolean)

[himitsu]

Zitat von Aphton:

Hmmm, wenn du mir bestätigen könntest, dass packed Array die Performance nicht verschlechtert?

Zitat:

Delphi-Quellcode:

TBoolArray = Array of Boolean;
TPoint64 = record
  X, Y: Int64;
end;

exp : Array of TPoint64;

Bei diesen beiden Records macht packed absolut keinen Unterschied.
Also, da sich absolut nix an der Ausrichtung ändert, kann sich auch nichts verbesser/verschlechtern.

Ein Array ist immer packed (es sei denn ein enthaltener Record ist packed und eine Ausrichtung könnte das Array optimieren).
Und bei einem Record greift eine Ausrichtung nur, wenn unterschiedlich große Basistypen im Record verbaut wurden ... also bei gleich großen Basistypen kann packed nichts verändern.

PS: Array of Boolean/Byte/.../ShortInt ist ein Sonderfall, denn hier ist ein Arrayfeld jeweils 1 Byte und es ist somit immer packed, da packed die Ausrichtung temporär auf 1 heruntersetzt.