Und hier meine Lösung für die Rück-Verwandlung. Diese sind mit
Daniel B abgesprochen und ich hatte mal gerade nichts zu tun. Der Hauptgrund für die Lösung ist, Euch gleichzeitig mal Möglichkeiten für Optimierungen offenzulegen. Erst einmal zum Lösungsansatz.
Idee ist folgende. Jedes Roman-Numeral wird separat entschlüsselt und zwischengespeichert. Anschließend wird es mit dem nächsten verglichen. Ist das nächste größer Numeral vom Wert größer, so muss das letzte von Gesamtergebnis subtrahiert werden, ansonsten wird es addiert. usw.
Hier erst einmal die nicht-optimierte Variante, welche aber leichter verständlich ist.
Delphi-Quellcode:
function RomanToDec3(Roman: String): LongInt;
function Value(Numeral: String): Integer;
const
Romans: Array[1..10] of String = ('I', 'V', 'X', 'L', 'C', 'D', 'M', '(M)',
'[M]', '{M}');
Arabics: Array[1..10] of Integer = (1, 5, 10, 50, 100, 500, 1000, 10000,
100000, 1000000);
var
I: Integer;
begin
Result := 0;
// alle roman numerals durchlaufen und match in "arabisch" zurückgeben
for I := Low(Romans) to High(Romans) do
if Romans[I] = Numeral then
begin
Result := Arabics[I];
Break;
end;
end;
var
Next: String;
Current, This, IPos, Len: Integer;
begin
// endergebnis
Result := 0;
// current hält den letzten ermittelten wert
Current := 0;
// jedes roman testen und verarbeiten
Len := Length(Roman);
IPos := 1;
while IPos <= Len do
begin
// nächstes roman holen
if Roman[IPos] in ['(', '[', '{'] then
begin
// die besonderen sind 3 zeichen lang
Next := Copy(Roman, IPos, 3);
Inc(IPos, 3);
end else begin
// der rest nur eines
Next := Roman[IPos];
Inc(IPos);
end;
// wert in "arabisch" umwandeln
This := Value(Next);
if This = 0 then
// fehleraft, skip
Continue;
if Current > 0 then
begin
// der letzte wert muss berücksichtigt werden
if This > Current then
begin
// der aktuelle wert ist größer als der letzte
// also muss der letzte abgezogen werden
// und der aktuelle hinzuaddiert werden
Result := Result - Current + This;
// der atkuelle wert muss nicht in der nächsten runde berücksichtigt
// werden
Current := 0;
end else begin
// der letzte wert wird addiert
Result := Result + Current;
// der aktuelle wert wird notiert
Current := This;
end;
end else begin
// der aktuelle wert wird notiert
Current := This;
end;
end;
// der letzte nicht berücksichtigte wert wird addiert
Result := Result + Current;
end;
Die folgende Variante ist optimiert und bringt zwischen ca. 80 und 97 Prozent Geschwindigkeitsvorteil und das ohne Assembler.
Es ist lediglich die Rücksichtnahme auf drei Gegebenheiten. Zu beachten ist, das der zugrunde liegende Algorithmus 100% identisch ist.
Der größte der Vorteile wird dadurch erzielt, das die Funktion
Value durch ein
case-Statement ersetzt wird. Einerseits umgehe ich die etwas langsamere Schleife, andererseits den langwierigen Funktionsaufruf. Dieser verbraucht am meisten Zeit.
Der zweite Vorteil liegt in der Verarbeitung des Strings. Anstatt die berechneten Wert aus dem String zu löschen, arbeite ich mit der Variable
IPos, welche den aktuellen Index im String zurückgibt. Mit jedem verarbeiteten Roman-Numeral wird diese entsprechend erhöht.
Der dritte Vorteil ergibt sich aus der Nutzung des zweiten Vorteils. Es wird nicht mehr das überprüfenden Numeral kopiert, sondern lediglich der aktulle Character and das case-Statement (Vorteil 1) geliefert.
Hier nun die optimierte Lösung:
Delphi-Quellcode:
function RomanToDec3Optimized(const Roman: String): LongInt;
var
Current, This, IPos, Len: Integer;
begin
// endergebnis
Result := 0;
// current hält den letzten ermittelten wert
Current := 0;
This := 0;
// jedes roman testen und verarbeiten
// dabei merkt sich der algo, die aktuelle position im string
// das ist schneller, als den string an und für sich zu manipulieren
Len := Length(Roman);
IPos := 1;
while IPos <= Len do
begin
// nächstes roman holen
case Roman[IPos] of
// die sonder-numerals sind 3 char lang, deshalb INC(IPos, 3)
'{': begin
This := 1000000;
Inc(IPos, 3);
end;
'[': begin
This := 100000;
Inc(IPos, 3);
end;
'(': begin
This := 10000;
Inc(IPos, 3);
end;
// die standard-numerals sind 1 char lang
'M': begin
This := 1000;
Inc(IPos);
end;
'D': begin
This := 500;
Inc(IPos);
end;
'C': begin
This := 100;
Inc(IPos);
end;
'L': begin
This := 50;
Inc(IPos);
end;
'X': begin
This := 10;
Inc(IPos);
end;
'V': begin
This := 5;
Inc(IPos);
end;
'I': begin
This := 1;
Inc(IPos);
end;
else
// fehlerhaft, skip
Inc(IPos);
Continue;
end;
if Current > 0 then
begin
// der letzte wert muss berücksichtigt werden
if This > Current then
begin
// der aktuelle wert ist größer als der letzte
// also muss der letzte abgezogen werden
// und der aktuelle hinzuaddiert werden
Result := Result - Current + This;
// der atkuelle wert muss nicht in der nächsten runde berücksichtigt
// werden
Current := 0;
end else begin
// der letzte wert wird addiert
Result := Result + Current;
// der aktuelle wert wird notiert
Current := This;
end;
end else begin
// der aktuelle wert wird notiert
Current := This;
end;
end;
// der letzte nicht berücksichtigte wert wird addiert
Result := Result + Current;
end;
...
...