Gestern bin ich auf eine kleine
Herausforderung für den Entwickler in mir gestoßen. Delphi.about.com sucht einen Algorithmus der für einen Zahlenbereich (z.B. 1 bis 10.000.000) die Anzahl der vorhandenen Palindromzahlen findet.
Eine Palindromzahl ist eine Zahl, die von vorne und hinten gelesen den gleichen Wert hat. Z.B. 121, 3663 oder 98789.
Da in Delphi String-Vergleiche bzw. die Umwandlungen von Integer zu String unglaublich langsam sind (zumindest für n > 1 Million), kann man soetwas wie das folgende komplett vergessen:
function IsPalindrome(aNumber : integer) : boolean;
begin
result := IntToStr(aNumber) = ReverseString(IntToStr(aNumber));
end;
Stattdessen sollte man lieber die Integer direkt vergleichen. Hierfür braucht man eine Funktion, die einen Integer umdrehen kann:
function ReverseInteger(aNumber : integer) : integer;
begin
result := 0;
while aNumber > 0 do
begin
result := 10 * result + aNumber mod 10;
aNumber := aNumber div 10;
end;
end;
Modulo und Integer-Divisionen sind aber auch nicht ohne. Von daher wäre es doch praktisch, wenn man die Umwandlungen und Divisionen weglassen könnte und stattdessen direkt die Ziffern vergleicht. Um auf die Ziffern zuzugreifen können muss man den Integer in einen Array laden.
Type TByteArray = array of byte;
function IntToByteArray(aNumber : integer) : TByteArray;
var
i : integer;
begin
SetLength(result,8); // 8 Stellen, das reicht für 10.000.000
for i := 0 to 7 do // Array mit Nullen initialisieren
begin
result[i] := 0;
end;
i := 0;
while aNumber > 0 do
begin
result[i] := aNumber mod 10;
aNumber := aNumber div 10;
inc(i);
end;
end;
Danach finden sich die Einer im Index 0, die Zehner im Index 1, die Hunderter im Index 2, usw. Diesen array kann man nun ganz einfach auf Palindrome überprüfen.
function IsPalindrom(aNumber : TByteArray; aDigits : byte) : boolean;
var
a, b : integer;
begin
result := true;
a := 0;
b := aDigits-1;
while (a < b) and result do
begin
result := result and (aNumber[a] = aNumber[b]);
inc(a);
dec(b);
end;
end;
Wenn man jetzt versucht den Zahlenbereich mit einer Schleife abzuarbeiten hat man noch nicht viel gewonnen, da man bei der Umwandlung von Integer nach Array wieder jede Menge Modulo und Integer-Divisionen hat. Also muss man die Zahl direkt im Array erhöhen.
procedure IncArray(aArray : TByteArray; aDigit : byte);
begin
if aDigit <= 7 then // Unser Array ist auf 8 Stellen (Index 0-7) beschränkt
begin
inc(aArray[aDigit]); // Feld erhöhen
if (aArray[aDigit] mod 10 = 0) then // bei überlauf
begin
aArray[digit] := 0; // Feld auf 0 setzen
if aDigit < 7 then incArray(aDigit+1); // und nächstes Feld erhöhen (Rekursion!)
end;
end;
end;
Das Erhöhen in einem Array ist natürlich komplizierter als eine Zahl zu erhöhen. Man hat zwar mehr Additionen, aber keine Modulo-Operation oder Integer-Division mehr. Dadurhc spart man wertvolle Taktzyklen ein, da eine CPU wesentlich schneller addieren als teilen kann.
Das fertige Projekt kann man
hier herunterladen. Den Sourcecode gibt es
hier.
Im fertigen Projekt kann man schließlich noch die Anzahl der Threads wählen, die auf die Suche nach Palindromzahlen gehen sollen. Damit kam ich auf einem Intel Core 2 Duo T5750 auf durchschnittlich 0,16 Sekunden mit 5 Threads. (Minimum: 0,13 Sekunden)
Mein Mitbewohner hat das Verfahren optimiert während Ich das Ganze implementiert habe.
