Fibonacci

Posted on by Enno Wulff

Related Post

Ein kleines Beispielprogramm um die verschiedenen Arten der Berechnung von Fibonacci-Zahlen und deren Geschwindigkeit zu demonstrieren.

Ursprünglich habe ich das Programm auf Grund eines Beitrags im ABAP-Forum geschrieben (der aber leider gelöscht wurde) und um die verschiedenen Arten der Berechnung zu vergleichen. Hauptsächlich sollte es ein Vergleich sein zwischen der rekursiven und der iterativen Variante. Dazu gekommen ist dann noch eine Lösung, die mit einer internen Tabelle arbeitet. Ausschlaggebend für die Veröffentlichung war dann ein Beispiel von Lars Hvam dafür, wie man nicht programmieren sollte. Wie man an den Ergebnissen sieht, auch im Sinne der schlechten Performance…

Code

REPORT zz_fibonacci.

DATA result_f TYPE f.
DATA start    TYPE i.
DATA stopp    TYPE i.
DATA i        TYPE i.

PARAMETERS p_n       TYPE i.
PARAMETERS p_reku RADIOBUTTON GROUP b USER-COMMAND space.
PARAMETERS p_iter RADIOBUTTON GROUP b.
PARAMETERS p_tabl RADIOBUTTON GROUP b.
PARAMETERS p_hvam RADIOBUTTON GROUP b.
PARAMETERS p_res  TYPE text50 MODIF ID x.
PARAMETERS p_time TYPE i      MODIF ID x.

CLASS lcl_fibonacci DEFINITION.
  PUBLIC SECTION.
    CLASS-METHODS calc_rekursiv IMPORTING n TYPE i RETURNING VALUE(result) TYPE f.
    CLASS-METHODS calc_iterativ IMPORTING n TYPE i RETURNING VALUE(result) TYPE f.
    CLASS-METHODS calc_read_table IMPORTING x TYPE i RETURNING VALUE(result) TYPE f.
    CLASS-METHODS calc_hvam IMPORTING n TYPE i RETURNING VALUE(r) TYPE f.
  PRIVATE SECTION.
    CLASS-METHODS f IMPORTING i TYPE f RETURNING VALUE(f) TYPE f.
ENDCLASS.

CLASS lcl_fibonacci IMPLEMENTATION.

  METHOD calc_iterativ.

    DATA f1 TYPE f VALUE 0.
    DATA f2 TYPE f VALUE 1.
    DATA x  TYPE f VALUE 0.

    IF n <= 0.
      result = 0.
    ELSEIF n = 1.
      result = 1.
    ELSE.
      x = n - 1.
      DO x TIMES.
        result = f1 + f2.
        f1 = f2.
        f2 = result.

      ENDDO.
    ENDIF.

  ENDMETHOD.

  METHOD calc_rekursiv.
    DATA f TYPE f.
    f = n.
    result = f( f ).
  ENDMETHOD.

  METHOD calc_read_table.
    "http://www.abapforum.com/forum/viewtopic.php?f=1&t=21045

    TYPES BEGIN OF ts_fibonacci.        "Strukturtyp
    TYPES n         TYPE i.             "Zählvariable    (Spalte)
    TYPES fib_n     TYPE i.             "Fibonacci-Zahl  (Spalte)
    TYPES rechnung  TYPE string.        "Rechenweg       (Spalte)
    TYPES END OF ts_fibonacci.

    DATA gf_zahl1 TYPE i.
    DATA gf_zahl1_s TYPE string.
    DATA gf_zahl2 TYPE i.
    DATA gf_zahl2_s TYPE string.
    DATA gt_fibzahl TYPE TABLE OF ts_fibonacci.     "Tabelle
    DATA gs_fib TYPE ts_fibonacci.

    DO x TIMES.

      IF sy-index = 1 OR sy-index = 2.
        gs_fib-n = sy-index.
        gs_fib-fib_n = 1.
        gs_fib-rechnung = '-'.

      ELSE.
        READ TABLE gt_fibzahl
        INTO gs_fib
        INDEX sy-index - 1.
        gf_zahl1 = gs_fib-fib_n.

        READ TABLE gt_fibzahl
        INTO gs_fib
        INDEX sy-index - 2.
        gf_zahl2 = gs_fib-fib_n.

        gs_fib-fib_n = gf_zahl1 + gf_zahl2.
        gs_fib-n = sy-index.
        gf_zahl1_s = gf_zahl1.
        gf_zahl2_s = gf_zahl2.
        CONCATENATE gf_zahl1_s '+' gf_zahl2_s INTO gs_fib-rechnung SEPARATED BY space.
      ENDIF.

      APPEND gs_fib TO gt_fibzahl.
      CLEAR gs_fib.

    ENDDO.

    READ TABLE gt_fibzahl INDEX lines( gt_fibzahl ) INTO gs_fib.
    result = gs_fib-fib_n.

  ENDMETHOD.

  METHOD f.
    DATA x TYPE f.
    DATA y TYPE f.

    IF i <= 0.
      f = 0.
    ELSEIF i = 1.
      f = 1.
    ELSE.
      x = i - 2.
      y = i - 1.
      f = f( x ) + f( y ).
    ENDIF.
  ENDMETHOD.

  METHOD calc_hvam.

    "negative example of Lars Hvam for how _NOT_ to code!
    "https://gist.github.com/larshp/cc5326dec8fe413bdc29e4d6b8c64b4f
    DATA n1 TYPE i.
    DATA n2 TYPE i.
    DATA r1 TYPE p.
    DATA r2 TYPE f.

    n2 = n - 1.
    n1 = n2 - 1.
    IF n = 1.
      r = n.
    ELSEIF n := 2.
      r = n - 1.
    ELSE.
      r2 = calc_hvam( n1 ).
      r1 = calc_hvam( n2 ).
    ENDIF.
    r = r + r1 + r2.

  ENDMETHOD.

ENDCLASS.



AT SELECTION-SCREEN OUTPUT.
  LOOP AT SCREEN.
    IF screen-group1 = 'X'.
      screen-input = '0'.
      MODIFY SCREEN.
    ENDIF.
  ENDLOOP.

  GET RUN TIME FIELD start.
  CASE abap_true.
    WHEN p_iter.
      result_f = lcl_fibonacci=>calc_iterativ( p_n ).
    WHEN p_reku.
      result_f = lcl_fibonacci=>calc_rekursiv( p_n ).
    WHEN p_tabl.
      result_f = lcl_fibonacci=>calc_read_table( p_n ).
    WHEN p_hvam.
      result_f = lcl_fibonacci=>calc_hvam( p_n ).
  ENDCASE.

  WRITE result_f TO p_res EXPONENT 0 DECIMALS 0 LEFT-JUSTIFIED.
  GET RUN TIME FIELD stopp.
  p_time = stopp - start.


START-OF-SELECTION.

  DO p_n TIMES.
    i = sy-index.

    GET RUN TIME FIELD start.
    CASE abap_true.
      WHEN p_iter.
        result_f = lcl_fibonacci=>calc_iterativ( i ).
      WHEN p_reku.
        result_f = lcl_fibonacci=>calc_rekursiv( i ).
      WHEN p_tabl.
        result_f = lcl_fibonacci=>calc_read_table( i ).
    ENDCASE.

    WRITE result_f TO p_res EXPONENT 0 DECIMALS 0 LEFT-JUSTIFIED.
    WRITE: / i, p_res.

  ENDDO.

  GET RUN TIME FIELD stopp.
  p_time = stopp - start.

  WRITE: / 'Time:', p_time.

 

Enno Wulff
Letzte Artikel von Enno Wulff (Alle anzeigen)