Knobelaufgabe (April 2022) - Laufzeit XSTRING
13 Beiträge
•
Seite 1 von 1
13 Beiträge
Seite 1 von 1
Beitrag
von black_adept (Top Expert / 4087 / 126 /
940
)
»
Moin allerseits,
ich bin mal wieder über ein Thema gestolpert und habe daraus eine kleine Knobelaufgabe gemacht.
Es geht "einfach" darum, aus einer Tabelle von X-Feldern einen X-String aufzubauen. Und hier ist das Problem. Wenn man den trivialen Ansatz wählt ( siehe Beispielimplementierung ) sieht man ( Screenshot ), dass sich die Laufzeit quadratisch verhält. D.h. bei Verdopplung der Größe der Eingabetabelle vervierfacht sich die Laufzeit ( bei größeren Eingabetabellen ). Der Screenshot stammt aus einem 7.40 EHP 10 System, aber ich habe das analog auch auf einem 7.54 System nachgestellt und dort den gleichen Effekt gehabt.
Und das ist euer Aufgabe:
Die aktuelle Implementierung benötigt für eine Tabelle mit 2^17 = 131.072 Einträgen knapp 2 Minuten, wie man am letzten Eintrag des Screenshots erkennt. Könnt ihr das Ganze irgendwie so beschleunigen, dass mehr machbar ist? Ich fürchte, dass auch andere Lösungen irgendwie quadratisch sein werden - aber vielleicht kann man die Basis so weit drücken, dass hier bessere Ergebnisse erzielt werden können oder gar einen Ansatz mit besserer als quadratischer Laufzeit finden.
ich bin mal wieder über ein Thema gestolpert und habe daraus eine kleine Knobelaufgabe gemacht.
Es geht "einfach" darum, aus einer Tabelle von X-Feldern einen X-String aufzubauen. Und hier ist das Problem. Wenn man den trivialen Ansatz wählt ( siehe Beispielimplementierung ) sieht man ( Screenshot ), dass sich die Laufzeit quadratisch verhält. D.h. bei Verdopplung der Größe der Eingabetabelle vervierfacht sich die Laufzeit ( bei größeren Eingabetabellen ). Der Screenshot stammt aus einem 7.40 EHP 10 System, aber ich habe das analog auch auf einem 7.54 System nachgestellt und dort den gleichen Effekt gehabt.
Und das ist euer Aufgabe:
Die aktuelle Implementierung benötigt für eine Tabelle mit 2^17 = 131.072 Einträgen knapp 2 Minuten, wie man am letzten Eintrag des Screenshots erkennt. Könnt ihr das Ganze irgendwie so beschleunigen, dass mehr machbar ist? Ich fürchte, dass auch andere Lösungen irgendwie quadratisch sein werden - aber vielleicht kann man die Basis so weit drücken, dass hier bessere Ergebnisse erzielt werden können oder gar einen Ansatz mit besserer als quadratischer Laufzeit finden.
Code: Alles auswählen.
REPORT zknobel_xstring.
PARAMETERS: p_seed TYPE i,
p_expon TYPE numc2 OBLIGATORY DEFAULT 23. " Bis 2^23 = 8.388.608 < 10 Millionen
CLASS lcl_knobel DEFINITION FINAL.
PUBLIC SECTION.
TYPES: mtt_x TYPE STANDARD TABLE OF x WITH NON-UNIQUE DEFAULT KEY.
METHODS:
main,
build_problem IMPORTING iv_times TYPE i
RETURNING VALUE(rt_x) TYPE mtt_x,
build_xstring IMPORTING it_x TYPE mtt_x
RETURNING VALUE(rv_x) TYPE xstring.
DATA: mo_random TYPE REF TO cl_abap_random_int.
ENDCLASS.
CLASS lcl_knobel IMPLEMENTATION.
METHOD build_xstring.
**********************************************************************
* Für diese Methode wird die Laufzeit gemessen.
* Hier soll geschaut werden, ob man irgendwie die Laufzeit verberssern kann
* wenn man anstatt des trivialen Ansatzes einen etwas gewiefteren verwendet.
**********************************************************************
LOOP AT it_x ASSIGNING FIELD-SYMBOL(<lv_x>).
rv_x = rv_x && <lv_x>.
ENDLOOP.
ENDMETHOD.
METHOD build_problem.
DATA: lv_i TYPE byte.
FIELD-SYMBOLS: <lv_x> TYPE x.
DO iv_times TIMES.
lv_i = mo_random->get_next( ).
ASSIGN lv_i TO <lv_x> CASTING.
APPEND <lv_x> TO rt_x.
ENDDO.
ENDMETHOD.
METHOD main.
DATA: lv_count TYPE n,
lv_times TYPE i VALUE 1,
lv_runtime_ms type i,
lv_runtime_ms_last type i value 1,
lv_factor type f.
mo_random = cl_abap_random_int=>create( seed = p_seed
min = 0
max = 255
).
*--------------------------------------------------------------------*
* Max. 2^23 < 10 Millionen Einträge. Später wird's ein Speicherproblem
* aber die Aufgabe soll ein Laufzeitproblem sein
*--------------------------------------------------------------------*
IF p_expon > 23.
p_expon = 23.
ENDIF.
DO p_expon TIMES.
* Setup problem
CALL FUNCTION 'SAPGUI_PROGRESS_INDICATOR'
EXPORTING
TEXT = |{ sy-index }|.
DATA(lt_x) = me->build_problem( lv_times ).
* Solve and get runtime
GET RUN TIME FIELD DATA(lv_before).
DATA(lv_x) = me->build_xstring( lt_x ).
GET RUN TIME FIELD DATA(lv_after).
lv_runtime_ms = lv_after - lv_before.
lv_factor = lv_runtime_ms / lv_runtime_ms_last.
* Output runtime and some statistics
WRITE:/ lv_times COLOR 1,
AT 16 'Runtime in ms:' COLOR 2, lv_runtime_ms COLOR 2,
at 50 'Factor' color 3, lv_factor EXPONENT 0 DECIMALS 2 color 3.
IF xstrlen( lv_x ) > 30.
WRITE: lv_x(30) COLOR 7 NO-GAP, '...' COLOR 7.
ELSE.
WRITE lv_x COLOR 7.
ENDIF.
lv_runtime_ms_last = lv_runtime_ms.
lv_times = lv_times * 2.
ENDDO.
ENDMETHOD.
ENDCLASS.
END-OF-SELECTION.
NEW lcl_knobel( )->main( ).Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
gesponsert ⓘ
Stellenangebote auf ABAPforum.com schalten
kostenfrei für Ausbildungsberufe und Werksstudenten
kostenfrei für Ausbildungsberufe und Werksstudenten
Hie die Laufzeiten des Originals auf meinem Testsystem (Exp. 18 - mehr dauert mir zu lange) im Vergleich meiner Version (Exp 21) (ist aber nur ein scheller, unoptimierter proof-of-concept, da geht noch was)
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Beitrag
von black_adept (Top Expert / 4087 / 126 /
940
)
»
Moin whaslbeck,
sehr schöne lineare Lösung. Aber wie das so ist, wenn man was Gutes abliefert kommt dann die Nachforderung ( bitte via PM an mich, damit andere noch ein wenig in den Genuss der Herausforderung kommen ): Was sorgt dafür, dass es so viel schneller ist? Und hättest du das vermutet?
sehr schöne lineare Lösung. Aber wie das so ist, wenn man was Gutes abliefert kommt dann die Nachforderung ( bitte via PM an mich, damit andere noch ein wenig in den Genuss der Herausforderung kommen ): Was sorgt dafür, dass es so viel schneller ist? Und hättest du das vermutet?
Hallo,
endlich mal eine Aufgabe, bei der mir sofort ein Ansatz eingefallen ist (vermutlich der gleiche wie bei whaslbeck). MfG
Thomas R.
Lösung geht Dir per PM zu.
endlich mal eine Aufgabe, bei der mir sofort ein Ansatz eingefallen ist (vermutlich der gleiche wie bei whaslbeck). MfG
Thomas R.
Lösung geht Dir per PM zu.
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Hi,
hier das schnellere Ergebnis auf unserem Testsystem. Das Original kam nicht bis Exp. 23, da ein Dump aufgrund der langen Laufzeit kam ;-)
hier das schnellere Ergebnis auf unserem Testsystem. Das Original kam nicht bis Exp. 23, da ein Dump aufgrund der langen Laufzeit kam ;-)
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Schöne Aufgabe. Hier mein erster Ansatz, vielleicht fällt mir ja noch etwas ein.
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Beitrag
von black_adept (Top Expert / 4087 / 126 /
940
)
»
An alle, die hier eine schöne lineare Lösung gepostet haben noch die Frage, die bitte nur via PM zu beantworten ist, da sonst die Lösung der Knobelaufgabe vorweggenommen wird:
Warum hat die Demolösung der Aufgabenstellung eine quadratische Laufzeit und eure eine lineare?
Warum hat die Demolösung der Aufgabenstellung eine quadratische Laufzeit und eure eine lineare?
Hier meine - ebenfalls 10-Sekunden - Lösung:
Du hast keine ausreichende Berechtigung, um die Dateianhänge dieses Beitrags anzusehen.
Beitrag
von black_adept (Top Expert / 4087 / 126 /
940
)
»
Moin allerseits
da wir ja schon hinreichend viele Antworten haben, kommt heute das Fazit der Aufgabe schon einen Tag später.
Da alle Einsender bzw. die, die hier im Forum ihre Screenshots gepostet haben, eine lineare Laufzeit erreicht haben, ist das Problem definitiv in der quadratischen Laufzeit des Originalpostings zu suchen.
Aber zunächst mal ein paar Lösungen, die ich so erhalten habe ( teilweise mehrfach die mehr oder weniger gleiche Lösung ) und ich gehe davon aus, dass diejenigen von denen ich keine PM bekommen habe eine analoge Lösung haben, insbesondere wenn so was wie "Implementierungsaufwand 10 Sekunden" angegeben wird:
Variante 1:Variante 1 zeigt sehr schön das Problem. Denn das && des Originalpostings ist ja eigentlich nur eine Kurzform des CONCATENATE - Befehls. Und beim Concatenate kann man den Zusatz "IN BYTE MODE" angeben um die X(String)-Verarbeitung zu wählen. Wenn man den Zusatz nicht angibt, wird normale Stringverarbeitung gewählt und da es beim "&&" keinen Zusatz gibt wird hier immer die Stringverareitung ausgeführt. Und das ist auch schon die Erklärung für die schlechte Laufzeit. Das && sorgt dafür, dass der X-String und das X-Feld zunächst in String- oder Charfelder konvertiert werden, danach zusammengefügt und schlussendlich dann wieder in einen X-String zurückgewandelt wird. Und diese Aktion ist um so langsamer, je länger der String ist, was dann zu der quadratischen Laufzeit führt.
Variante 2:
Variante 2 ist dann die noch kürzere (und deutlich schnellere ) Version von Version 1, die genau auf dieses Problem zugeschnitten ist. Offenbar ist SAP beim Befehl CONCATENATE LINES OF in der Lage den benötigten Speicherbereich vorab zu alloziieren und dann die Zeilen der Reihe nach dort einzufügen wohingegen in Variante 1 in jedem Schleifendurchlauf ein neuer String auf dem Heap erzeugt werden muss. Und das kostet tatsächlich so viel Laufzeit, so dass auf meinem System Variante 2 um etwa einen Faktor 10 schneller ist, als die Variante 1.
Variante 3:
Variante 3 ist sehr interessant, denn sie sieht auf den ersten Blick nicht so aus, als ob sie eine lineare Laufzeit erreichen könnte, weil ja das "IN BYTE MODE" nicht verwendet wird. Dass dem trotzdem so ist erklärt sich aus dem Aufbau der FOR-Schleife. In dieser wird jede Zeile der Eingabetabelle (= 1-stelliges X-Feld ) in einen 2-stelligen String umgewandelt. Und danach wird dann intern eine normale Stringverkettung vorgenommen. Da die Verkettung von Strings genau so linear abläuft wie die Verkettung von X-Strings mit dem Zusatz "IN BYTE MODE" ergibt sich für den Aufbau des Strings auch eine lineare Laufzeit und das abschließende, einmalige Umwandeln des langen Strings in einen X-String fällt nicht mehr ins Gewicht.
Fazit für mich:
Ich glaube, dass ich in meiner Laufbahn den Zusatz "IN BYTE MODE" oder die Variante "CONCATENATE LINES OF" noch nie gebraucht habe, so dass ich diese irgendwie verdrängt hatte. Somit hat sich diese Aufgabe allein für mich schon gelohnt, weil mir diese beiden wieder in Erinnerung gebracht wurden.
Das Problem, was mich auf diese Knobelaufgabe gebracht hat, hatte ich selber mit einer Variante 3 ähnlichen Version gelöst. Habe das schon umgeschrieben auf Variante 1 und bin aktuell am Überlegen, ob ich meine Datenbasis irgendwie so umstellen kann, dass ich Variante 2 verwenden kann.
Ich hoffe es hat euch auch Spaß gemacht und auch denjenigen, die hier nur lesend im Forum vorbeischauen, Erkenntnisse verschafft.
da wir ja schon hinreichend viele Antworten haben, kommt heute das Fazit der Aufgabe schon einen Tag später.
Da alle Einsender bzw. die, die hier im Forum ihre Screenshots gepostet haben, eine lineare Laufzeit erreicht haben, ist das Problem definitiv in der quadratischen Laufzeit des Originalpostings zu suchen.
Aber zunächst mal ein paar Lösungen, die ich so erhalten habe ( teilweise mehrfach die mehr oder weniger gleiche Lösung ) und ich gehe davon aus, dass diejenigen von denen ich keine PM bekommen habe eine analoge Lösung haben, insbesondere wenn so was wie "Implementierungsaufwand 10 Sekunden" angegeben wird:
Variante 1:
Code: Alles auswählen.
LOOP AT it_x INTO DATA(x).
CONCATENATE rv_x x INTO rv_x IN BYTE MODE.
ENDLOOP.Variante 2:
Code: Alles auswählen.
CONCATENATE LINES OF it_x[] INTO rv_x IN BYTE MODE.Variante 3:
Code: Alles auswählen.
METHOD build_xstring.
rv_x = Reduce xstring( INIT lv_str = `` FOR lv_x in it_x NEXT lv_str = |{ lv_str }{ lv_x }| ).
ENDMETHOD.Fazit für mich:
Ich glaube, dass ich in meiner Laufbahn den Zusatz "IN BYTE MODE" oder die Variante "CONCATENATE LINES OF" noch nie gebraucht habe, so dass ich diese irgendwie verdrängt hatte. Somit hat sich diese Aufgabe allein für mich schon gelohnt, weil mir diese beiden wieder in Erinnerung gebracht wurden.
Das Problem, was mich auf diese Knobelaufgabe gebracht hat, hatte ich selber mit einer Variante 3 ähnlichen Version gelöst. Habe das schon umgeschrieben auf Variante 1 und bin aktuell am Überlegen, ob ich meine Datenbasis irgendwie so umstellen kann, dass ich Variante 2 verwenden kann.
Ich hoffe es hat euch auch Spaß gemacht und auch denjenigen, die hier nur lesend im Forum vorbeischauen, Erkenntnisse verschafft.
Folgende Benutzer bedankten sich beim Autor black_adept für den Beitrag (Insgesamt 7):
ewx • Thomas R. • Murdock • a-dead-trousers • ST22 • rob_abc • qyurryus
Variante 4?
Code: Alles auswählen.
DATA lv_str type string.
LOOP AT it_x ASSIGNING FIELD-SYMBOL(<lv_x>).
lv_str &&= <lv_x>.
ENDLOOP.
rv_x = lv_str.
Beitrag
von black_adept (Top Expert / 4087 / 126 /
940
)
»
Entspricht de facto Variante 3. Aber diese Version war die Version, die ich zunächst verwendet hatte, bevor ich die anderen Lösungen gesehen hatte.
Seite 1 von 1
Vergleichbare Themen
5
Antw.
Antw.
1819
Views
Views
Knobelaufgabe ( Sommer 2022 ) - Unit Test Coverage
von black_adept » 27.07.2022 12:36 • Verfasst in SAP - Allgemeines
von black_adept » 27.07.2022 12:36 • Verfasst in SAP - Allgemeines
1
Antw.
Antw.
2544
Views
Views
konvertierung von TIF-Xstring to PDF-Xstring
von lino » 11.07.2012 16:38 • Verfasst in ABAP Objects®
von lino » 11.07.2012 16:38 • Verfasst in ABAP Objects®
20
Antw.
Antw.
6248
Views
Views
Erfolgt: Stammtisch ABAP-Forum Süd(west): 05.April 2006
von ereglam » 06.03.2006 10:08 • Verfasst in SAP - Allgemeines
von ereglam » 06.03.2006 10:08 • Verfasst in SAP - Allgemeines
0
Antw.
Antw.
1537
Views
Views
Frage die ABAP Experten
Über diesen Beitrag
Unterstütze die Community und teile den Beitrag für mehr Leser und Austausch
Aktuelle Forenbeiträge
Newsletter Anmeldung
Keine Beiträge verpassen! Wöchentlich versenden wir lesenwerte Beiträge aus unserer Community.Die letzte Ausgabe findest du hier.