Performance verbessern (Listen...)

  • Performance verbessern (Listen...)

    Wie in einem anderen Thread schon erwähnt, wollte ich ein kleines Tool schreiben, was mir ein paar interessante Statistiken zu meinen WhatsApp verläufen ausspuckt.
    Das funktioniert bis jetzt soweit auch ganz gut. ;)

    Für die Emoji Statistik (wer hat welches Emoji wie oft verwendet usw.) sammelt mein Programm zunächst einmal alle Emojis in einer Liste (liegen als png-Dateien in einem Ordner bei) arbeitet dann für jede Nachricht die gesamte Liste ab, ob ein passendes Emoji drin ist.
    Das funktioniert, habe es mit einem kleinen Auszug aus dem Chatverlauf getestet, das zählen scheint richtig zu funktionieren.
    Nur braucht er für längere Chats echt mega lange.
    Ich habe hier bspw. einen Chatverlauf mit 36000 Nachrichten.
    Dafür braucht er ca. 15 Minuten.
    Klar, denn für jede Nachricht muss er auch über 2000 Emojis testen...

    Irgenwie muss man das doch noch optimieren können und zwar deutlich.
    Nur habe ich gerade keine Idee, wie man die Sache sinnvoller gestalten könnte.
    Hat evtl. einer von euch einen Rat? :)

    Btw: Für die Wort-Analyse (wer schreibt welche Wörter wie oft) braucht er um alle 36000 Nachrichten durch zu zählen ca. 70 Sekunden.
    Das wäre eine Zeit, mit der ich mich anfreunen könnte, auch wenn das vielleicht auch noch schneller geht :D

  • Ohne Code oder Funktionsweise zu kennen kann man da natürlich wenig zu sagen. Aber ein Ansatzpunkt wäre sicher der Suchalgorithmus. Falls du das ganze Iterativ angehst kann man es noch deutlich optimieren. Ich denke da an baumstrukturen und der gleichen. Auch solltest du bedenken das große Listen sehr langsam sind. Du kannst also auchnoch beim Zwischenspeicher optimieren
    132 little bugs in the code. 132 little bugs. Fix a few, set the compiler to stew, 172 little bugs in the code... :vogel:

  • Das klingt so, als ob dir eine Lauflängenkodierung helfen könnte. Das verkürzt deine Liste dann auf:

    Quellcode

    1. 60x :) 1x ;) 20x :) 4x B) 1x ;) 1x :) //usw

    out now: KNOSSOS auf itch.io
    ancient-pixel.com <<< ich freue mich über einen Besuch! ^^

  • Ok, hier mal mein Code. Ich hoffe, es ist soweit verständlich, habe versucht, möglichst alles zu kommentieren.
    Dieser Code wird für Jede Nachricht durchgeführt.

    GML-Quellcode

    1. var str, name, pos, emoji, emoji_l, i, one, zero, stelle, value, index;
    3. //arg0 = Die Nachricht
    4. //arg1 = Der Absender
    5. str = argument0;
    6. name = argument1;
    8. //Gehe alle Emojis aus der Liste durch
    9. //Werte der Liste im Format: LLIIIIEEE... (LL = Länge des Emojis (Anzahl Zeichen), IIII = Index des Emojis in der Emoji-Liste der Bilder, EEE... Das Emoji (Zeichen)
    10. for(i = 0; i < ds_list_size(list_emoji_codes); i += 1)
    11. {
    12. //Speichere zunächst alle Werte in Variablen
    13. value = ds_list_find_value(list_emoji_codes,i);
    14. emoji = string_copy(value,3+global.nr_stellen,string_length(value)-3-global.nr_stellen);
    15. index = real(string_copy(value,3,global.nr_stellen));
    16. emoji_l = string_length(emoji);
    17. emoji_sprite = ds_list_find_value(list_emoji_sprites,index);
    19. //Wurde das Emoji in der Nachricht gefunden?
    20. if(string_pos(emoji,str) > 0)
    21. {
    22. //Überprüfe, ob das Emoji schon einmal vorkam (dann wurde es in den String "emojilist" gespeichert)
    23. pos = string_pos("|"+emoji+"|",emojilist);
    24. //Falls nein, dann füge es neu in die Liste ein
    25. if(pos == 0)
    26. {
    27. stelle = convert_nr(ds_list_size(list_all),global.nr_stellen); //convert_nr(nr,anz) macht aus der Zahl "nr" einen String mit "anz" Stellen (also ggf. mit führenden Nullen) convert(2,5) wird zu "00002"
    28. one = convert_nr(1,global.nr_stellen);
    29. zero = convert_nr(0,global.nr_stellen);
    30. emojilist += "|"+emoji+"|"+stelle+"|";
    32. ds_list_add(list_all,one+"|"+stelle+"|"+string(emoji_sprite));
    34. //Je nachdem, von wem die Nachricht ist, füge das Emoji in die entsprechende Liste ein
    35. if(name == obj_load_txt.chatter_name[1])
    36. {
    37. ds_list_add(list_chatter1,one+"|"+string(emoji_sprite));
    38. ds_list_add(list_chatter2,zero+"|"+string(emoji_sprite));
    39. }
    40. else
    41. {
    42. ds_list_add(list_chatter1,zero+"|"+string(emoji_sprite));
    43. ds_list_add(list_chatter2,one+"|"+string(emoji_sprite));
    44. }
    45. }
    46. //Kam das Emoji schon einmal vor, dann update den entsprechenden Wert in der Liste
    47. else
    48. {
    49. index = real(string_digits(string_copy(emojilist,pos+emoji_l+2,10)));
    50. anz = real(string_digits(string_copy(ds_list_find_value(list_all,index),1,global.nr_stellen)));
    51. ds_list_replace(list_all,index,convert_nr(anz+1,global.nr_stellen)+"|"+convert_nr(index,global.nr_stellen)+"|"+string(emoji_sprite));
    53. //Je nach dem, von wem die Nachricht ist, update den enstprechenden Wert in der entsprechenden Liste
    54. if(name == obj_load_txt.chatter_name[1])
    55. {
    56. anz = real(string_digits(string_copy(ds_list_find_value(list_chatter1,index),1,global.nr_stellen)));
    57. ds_list_replace(list_chatter1,index,convert_nr(anz+1,global.nr_stellen)+"|"+string(emoji_sprite));
    58. }
    59. else
    60. {
    61. anz = real(string_digits(string_copy(ds_list_find_value(list_chatter2,index),1,global.nr_stellen)));
    62. ds_list_replace(list_chatter2,index,convert_nr(anz+1,global.nr_stellen)+"|"+string(emoji_sprite));
    63. }
    64. }
    67. //Entferne das Emoji aus dem String und setze i = i-1, damit der String noch einmal nach diesem Emoji durchsucht werden kann
    68. str = string_replace(str,emoji,"");
    69. i = i-1;
    70. }
    71. }
    Alles anzeigen


    Das mit der Lauflängenkodierung habe ich nicht so recht verstanden. Also das Prinzip ist mir grob klar, aber ich wüsste jetzt nicht, wie ich das auf mein Problem anwenden könnte... ?(

  • Hi, Basti!

    Ich kann mir gut vorstellen das dein Code sehr langsam ist.

    1. Du benötigst doch nicht unbedingt 2 Listen.
    ->list_emoji_codes / list_emoji_sprites -> wird z.B. zu list_emoji

    Deine Sprites musst du doch nicht noch extra per "index" finden.

    Deine Platzhalter-Struktur in der Liste: list_emoji_codes könnte doch gleich den "sprite_index" enthalten.
    (LL hier sprite EEE)

    2. Lauflängenkodierung würde ja so aussehen: LLIIIIEEELLIIIIEEE ->2,4,3#2,4,3 oder L2I4E3L2I4E3

    Das bringt dir aber hier doch gar nichts, weil deine Zahlen/Zeichen in der Liste ja fest vorgegeben sind.

    3. Schau dir auf jeden mal verschiedene Suchalgorithmen an.
    Irgend wie müsstest du die Logik optimieren. (Frag mich jetzt aber noch nicht wie)

    Man könnte ja die Whats-App-Textdatei als Art Matrix (z.B. Tile-Map) ansehen (jedes Zeichen ein Tile) und jetzt wäre nur noch interessant wie z.B. 9000 Tiles in Sekundenschnelle ersetzt werden können. Was ist das Geheimnis so eines Algorithmus ?

    Das wäre herauszufinden.

    4. Wenn du z.B C/C++ oder eine ähnlich gute Programmiersprache beherrscht könntest du deinen Algo versuchen in dieser Sprache zuschreiben und daraus eine DLL erstellen.
    Diese müsste der Gamemaker nur noch aufrufen.

    Ich hoffe du bekommst noch mehr Feedback.

    Viel Glück beim optimieren.

  • Wow, vielen Dank für deine ausführliche Antwort!!! :)
    Stimmt, eine zweite Liste mit den Sprites müsste gar nicht sein... da hast du Recht. Das kann ich in jedem Fall schonmal ändern.

    Ich kann ein bisschen C/C++, aber wirklch nur Grundlagen. Habe noch nie ein DLL geschrieben und da würde ich mich jetzt wohl auch erstmal nicht ran wagen.

    Vielleicht hat ja noch wer andere Optimierungsideen! :)

  • Weis nicht! Ich dachte du nutzt Studio.

    ​z.B. Memory-Schreiben
    ​
    buffer_poke
    Add data to a buffer at a specific position.

    Syntax: buffer_poke(buffer, offset, type, value);

    With the buffer_write function, you can write data to the given buffer at the current "seek" position, with each piece of data advancing this position by the bytes being written or read. However, it may be necessary for you to change a given piece of data without wanting to change the current seek position, and that's when you would use this function. You simply supply the function with a buffer index, and then the offset position from the buffer start (in bytes) within that buffer to write to, as well as the data type and the value to be written.


    ​Du arbeitest bei "Buffer" mit Memory-Adressen auf denen du direkt schreiben und lesen kannst.

    ​Hab mich unter Gamemaker damit aber auch noch nicht beschäftigt.

    ​Ähnlichen Memoryzugriff kenn ich aber von C++.

  • Ja, wenn ich nur was für den PC mache, dann nutze ich noch lieber GM 8 ;)
    Und da gibt es solche Funktionen wohl nicht...

    Krass, ich konnte es jetzt schon auf 2:30 Minuten kürzen!!! O.O
    Ich habe nur folgende zwei Befehle in die if-Abfrage gepackt:

    GML-Quellcode

    1. emoji_l = string_length(emoji);
    2. emoji_sprite = ds_list_find_value(list_emoji_sprites,index);


    Na so kommen wir der Sache ja schon viel näher!!! :)


    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von Basti ()

  • //Mmmh man kann nicht einfach string_replace gegen string_replace_all ersetzen, weil es dient ja nur dem löschen.
    //Ein anderes Ersetzen würde ja die Positionsfindung unmöglich machen.

    ...erste Kommentare bitte nicht weiter beachten.

    //Speichere zunächst alle Werte in Variablen
    value = ds_list_find_value(list_emoji_codes,i);
    emoji = string_copy(value,3+global.nr_stellen,string_length(value)-3-global.nr_stellen);
    index = real(string_copy(value,3,global.nr_stellen));
    emoji_l = string_length(emoji);
    emoji_sprite = ds_list_find_value(list_emoji_sprites,index);


    Das würde ich sowie aus der For-Schleife auslagern.
    Die benötigten Einzelwerte der Liste könnten an anderer Stelle z.B. als Array geschrieben werden.
    ....

    Deine Liste als Buffer wäre (denke ich) trotzdem besser.
    Buffer kann man auch irgend wie asynchron verwenden.

    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von Weihnachtswichtel ()

  • Was ich hinzufügen kann ist dass es sein kann dass die Veränderung eines Strings immer mit dem allokieren und dealokieren des gesamten Strings im Ram verbunden ist.

    Beispiel:

    Quellcode

    1. var text= "1234";
    2. text = text+"5";//text wird kopiert, 5 wird drangehängt und in einem neuen Bereich im Ram gespeichert.


    Ich habe selbst mal einen eigenartigen bottleneck gehabt wo mit der Zeit das spiel immer langsamer wurde. Ich kam dann drauf dass einer der Scripte der über mehrere Steps verteilt einen Buffer in einen string umgewandelt hat (um diesen über HTTP an einen webserver senden zu können) die Ursache war.
    Je größer der String wurde, desto länger dauerten operationen wie eben text=text+character.
    (Das wurde so schlimm dass die Framerate auf den einstelligen Bereich runter viel.)


    Ich habe k.a. wie der GM Strings intern handhabt, aber ich kann mir vorstellen dass (falls Strings intern einfache char arrays sind) String operationen die auf irgendwelche art und weise die größe des Strings verändern eine allokation und deallokation des strings durchführen. (Wenn du an einen text einen weiteren text dranhängst, muss dieser im Ram genügend raum haben um die neue datenmenge speichern zu können. Um das zu gewährleisten wird ein neuer Speicherbereich vom Betriebssystem angefordert der mindestens die länge des neuen Strings hat. Der alte speicher wird gleichzeitig freigegeben.)
    Dies würde erklären wieso die performanceeinbrüche solcher Operationen proportional zu der größe des strings steigt.

    Ich würde das aber in deinem fall noch performancetests machen um zu schauen ob dies bei dir auch wirklich der Fall ist.
    (vor allem funktionen wie string_replace)

    Um sowas zu verhindern würde ich versuchen das ganze mit buffern umzusetzen. Du hättest da die volle kontrolle über wann/was/wie verändert/allokiert/deallokiert wird

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von LEWA ()

  • Ich will nicht den Miesepeter spielen, aber arrays sind tatsächlich schneller als buffer, sie brauchen nur mehr memory. Das wurde schon mehrfach getestet. Also kann sich der TE die Arbeit denke ich spaaren.
    132 little bugs in the code. 132 little bugs. Fix a few, set the compiler to stew, 172 little bugs in the code... :vogel:

  • Weihnachtswichtel schrieb:



    //Speichere zunächst alle Werte in Variablen
    value = ds_list_find_value(list_emoji_codes,i);
    emoji = string_copy(value,3+global.nr_stellen,string_length(value)-3-global.nr_stellen);
    index = real(string_copy(value,3,global.nr_stellen));
    emoji_l = string_length(emoji);
    emoji_sprite = ds_list_find_value(list_emoji_sprites,index);


    Das würde ich sowie aus der For-Schleife auslagern.
    Die benötigten Einzelwerte der Liste könnten an anderer Stelle z.B. als Array geschrieben werden.

    Wie soll ich das denn aus der For-Schleife auslagern?
    Im Endeffekt bezieht sich doch alles auf "value", was ja den Listenwert an der Stelle i ausliest...

    Rhazul schrieb:

    Ich will nicht den Miesepeter spielen, aber arrays sind tatsächlich schneller als buffer, sie brauchen nur mehr memory. Das wurde schon mehrfach getestet. Also kann sich der TE die Arbeit denke ich spaaren.

    Okay, mit Array kenn ich mich wiederum aus. :D
    Also Buffer habe ich wie gesagt bis jetzt noch nie gehört. Und kommt ja auch nicht in Frage, so lange ich bei GM 8 bleibe mit diesem Projekt.

    Aber wie würde das ganze denn aussehen, wenn ich es mit Arrays machen würde? Einfach statt der Liste ein Array oder meinst du das anders?