Einzelnen Beitrag anzeigen

Benutzerbild von sakura
sakura

Registriert seit: 10. Jun 2002
Ort: München
11.412 Beiträge
 
Delphi 11 Alexandria
 
#4

Re: Dezimalzahlen in Römische Zahlen umwandeln und umgekehrt

  Alt 12. Jul 2003, 22:04
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;
......
Daniel W.
Ich bin nicht zurück, ich tue nur so
  Mit Zitat antworten Zitat