11.09.2009

Palindrom-Zahlen

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.

09.09.2009

Stammtisch

Ich war grade bei meinem ersten Piraten-Stammtisch und auf meinem ersten Stammtisch überhaupt. Es waren ca. 40-50 Leute anwesend, was die ganze Sache etwas chaotisch gemacht hat. Nachdem der offizielle Teil vorbei war, fanden sich aber schnell kleinere Gruppen die angeregt diskutierten.
Eigentlich wollte ich mich ja informieren, wie ich die Piratenpartei unterstützen kann, stattdessen fand ich mich sofort im Gespräch mit einem Nicht-Piraten wieder und konnte ihm das ein oder andere Konzept der Piratenpartei näherbringen u.a. Liquid Democracy).
Jedenfalls denke ich jetzt, das man der Piratenpartei am besten hilft in dem man den Leuten von ihr erzählt und ein paar Punkte ihres Programms anschneidet. Also, Spread the word!

Nach knapp 3 Stunden hab ich mich dann auf den Nachhauseweg gemacht, ich schätze aber, dass der Stammtisch noch nicht zuende ist. Alles in allem hat es mir Spaß gemacht und ich werde wohl noch das ein oder andere Mal dort vorbeischauen.

PS: @Alte Parteien: Ihr werdet euch noch wünschen, wir wären Politikverdrossen!

06.09.2009

Recut

Die Meme ist schon älter, aber durch den heutigen Kinobesuch1 bin ich mal wieder draufgestoßen.
Junge, kreative Menschen Internetbewohner nehmen einen Film auseinander und setzen daraus einen neuen Trailer zusammen. Der Clou an der Sache ist, dass das Genre gewechselt wird.
Es folgt eine kleine Auswahl der besseren Trailer dieser Machart:

The Shining - Happy Version

Mrs. Doubtfire - Creepy Version


The Big Lebowski (Drama) - Link
Groundhog Day (Horror) - Link
Crocodile Dundee (Horror) - Link
The Ring (Liebesfilm) - Link
The Blues Brothers - Link

1Final Destination 4 in 3D, woohoo!

02.09.2009

Laptop-Lüfter

Nur eine kleine Erinnerung an alle Laptop-Besitzer:
Es kann nicht schaden die Klappe vom Lüfter von Zeit zu Zeit abzuschrauben und das kleine Schwämmchen aus geschmolzenem Staub zu entfernen.