(Array vs. List vs. Map) und (Array 2D vs. Grid)

    Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

    • (Array vs. List vs. Map) und (Array 2D vs. Grid)

      Array vs. List vs. Map
      Spoiler anzeigen

      Ich habe mir gerade kleine Performance-Test für meiner Projekt gemacht. Da es so schön geworden ist, habe ich mich nun entschieden habe, das mit euch mitzuteilen. Einige von euch müsste ja schon bereits kennen.:


      GML-Quellcode

      1. ==============================Create/Addition==============================
      3. --------------------------------------
      4. for(i = 0; i < 99999; i++){
      5. array[i] = 1; <---- too... slow... (Array)
      6. }
      7. Delay: 2705 ms
      8. --------------------------------------
      9. for(i = 99999; i >= 0; i--){
      10. array[i] = 1; <---- Best (Array)
      11. }
      12. Delay: 21 ms
      13. --------------------------------------
      14. list = ds_list_create();
      15. for(i = 0; i < 99999; i++){
      16. ds_list_add(list, 1); <---- Best (List)
      17. }
      18. Delay: 26 ms
      19. --------------------------------------
      20. list = ds_list_create();
      21. for(i = 0; i < 99999; i++){
      22. list[| i] = 1; <---- Slow.... Lol? (List)
      23. }
      24. Delay: 1868 ms
      25. --------------------------------------
      26. map = ds_map_create();
      27. for(i = 0; i < 99999; i++){
      28. ds_map_add(map, i, 1); <---- so-so (Map)
      29. }
      30. Delay: 127 ms
      31. --------------------------------------
      32. map = ds_map_create();
      33. for(i = 0; i < 99999; i++){
      34. map[? i] = 1; <---- so-so (Map)
      35. }
      36. Delay: 135 ms
      37. --------------------------------------
      38. list = ds_list_create();
      39. repeat(99999){
      40. ds_list_add(list, 1); <---- Best (List) (small bonus with repeat)
      41. }
      42. Delay: 16 ms
      43. --------------------------------------
      45. ==============================Replacing==============================
      47. --------------------------------------
      48. for(i = 0; i < 99999; i++){
      49. array[i] = 2; <--- Best (Array)
      50. }
      51. Delay: 20 ms
      52. --------------------------------------
      53. for(i = 99999; i >= 0; i--){
      54. array[i] = 2; <--- Best (Array)
      55. }
      56. Delay: 21 ms
      57. --------------------------------------
      58. for(i = 0; i < 99999; i++){
      59. ds_list_replace(list, i, 2); <--- Very Good (List)
      60. }
      61. Delay: 25 ms
      62. --------------------------------------
      63. for(i = 0; i < 99999; i++){
      64. list[| i] = 2; <--- Very Good (List)
      65. }
      66. Delay: 24 ms
      67. --------------------------------------
      68. for(i = 0; i < 99999; i++){
      69. ds_map_replace(map, i, 2); <--- so-so (map)
      70. }
      71. Delay: 93 ms
      72. --------------------------------------
      73. for(i = 0; i < 99999; i++){
      74. map[? i] = 2; <--- so-so (map)
      75. }
      76. Delay: 124 ms
      77. --------------------------------------
      79. ==============================Access==============================
      81. --------------------------------------
      82. for(i = 0; i < 99999; i++){
      83. a = array[i]; <---- Best(Array)
      84. }
      85. Delay: 21 ms
      86. --------------------------------------
      87. for(i = 99999; i >= 0; i--){
      88. a = array[i]; <---- Best(Array)
      89. }
      90. Delay: 21 ms
      91. --------------------------------------
      92. for(i = 0; i < 99999; i++){
      93. a = ds_list_find_value(list, i); <--- Very Good (List)
      94. }
      95. Delay: 24 ms
      96. --------------------------------------
      97. for(i = 99999; i >= 0; i--){
      98. a = list[| i]; <--- Very Good (List)
      99. }
      100. Delay: 24 ms;
      101. --------------------------------------
      102. for(i = 0; i < 99999; i++){
      103. a = ds_map_find_value(map, i); <--- so-so (Map)
      104. }
      105. Delay: 86 ms
      106. --------------------------------------
      107. for(i = 0; i < 99999; i++){
      108. a = map[? i]; <--- so-so (Map)
      109. }
      110. Delay: 93 ms;
      111. --------------------------------------
      Alles anzeigen



      Ganz im Herz kann ich euch List und Array (wenn man ihn auch richtig benutzt.) empfehlen.
      Wobei ich List doch viel mehr empfehle aufgrund der erweiterte funktionen.

      Viel Spaß damit.

      [Edit:]

      Blöde Forum, der hat meine Textabstand runiert. :wacko:



      Array 2D vs. Grid
      Spoiler anzeigen

      Ich kann "99999" x "99999" nicht nehmen, da Array Limit an 32000x32000 begrenzt ist und bei ds_grid wird dann mein Arbeitsspeicher voll.

      Nur ein kleiner Test:

      Array konnte ich problemlos 10000x10000 erstellen. (bei 30000x30000 kam "Out of Memory").
      bei DS-Grid habe ich problem bei 10000x10000 (Out of Memory)

      Ich habe erstmal ein Test mit "1000x1000" gemacht, damit es auf beiden geht.
      Wie ich sehe, ist Array wesentlich schneller. Wenn man aber die spezielle Funktion von ds_grid benutzt, ist dann ds_grid schneller, viel schneller als array.

      Spoiler anzeigen

      GML-Quellcode

      1. //---2D-Array---
      2. //Create/Edition
      4. for(i = 1000; i >= 0; i--)
      5. {
      6. for(j = 1000; j >= 0; j--)
      7. {
      8. array[i,j] = 1;
      9. }
      10. }
      12. Delay: 291 ms
      14. //Replacing
      15. for(i = 1000; i >= 0; i--)
      16. {
      17. for(j = 1000; j >= 0; j--)
      18. {
      19. array[i,j] = 2;
      20. }
      21. }
      23. Delay: 283 ms
      25. //Access
      26. for(i = 1000; i >= 0; i--)
      27. {
      28. for(j = 1000; j >= 0; j--)
      29. {
      30. a = array[i,j];
      31. }
      32. }
      34. Delay: 287 ms
      36. //---ds_grid---
      37. //Create/Edition
      39. grid=ds_grid_create(1000, 1000);
      40. for(i = 1000; i >= 0; i--)
      41. {
      42. for(j = 1000; j >= 0; j--)
      43. {
      44. ds_grid_set(grid, i, j, 1);
      45. }
      46. }
      47. Delay: 376 ms
      49. //Replacing
      50. for(i = 1000; i >= 0; i--)
      51. {
      52. for(j = 1000; j >= 0; j--)
      53. {
      54. ds_grid_set(grid, i, j, 2);
      55. }
      56. }
      58. Delay: 395 ms
      60. //Access
      61. for(i = 1000; i >= 0; i--)
      62. {
      63. for(j = 1000; j >= 0; j--)
      64. {
      65. a = ds_grid_get(grid, i, j);
      66. }
      67. }
      69. Delay: 304 ms
      71. /// Bonus für Grid
      73. //Access (Summiere den gesamte Grid, ds_grid_get_sum)
      74. sum = ds_grid_get_sum(grid, 0, 0, 1000, 1000);
      76. Delay: 7 ms
      78. //Creation (ds_grid_set_region)
      79. grid=ds_grid_create(1000, 1000);
      80. ds_grid_set_region(grid, 0, 0, 1000, 1000, 2);
      82. Delay: 25 ms
      84. //Replacing (ds_grid_set_region)
      85. ds_grid_set_region(grid, 0, 0, 1000, 1000, 3);
      87. Delay: 15 ms
      Alles anzeigen



      Ihr könnt selber die Performance testen, indem ihr dieser Skript benutzt:

      GML-Quellcode

      1. var time, a, map;
      2. time = current_time;
      4. /// <--- Da kommen die Funktionen rein, um Performance zu testen.
      6. time = current_time - time;
      8. show_debug_message("|-----------------------------");
      9. show_debug_message("| Delay: " + string(time) + " ms");
      10. show_debug_message("|-----------------------------");


      Ihr stinkt.

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von Chinafreak ()

    • Gut zu wissen.

      Was noch fehlt ist ds_grid, das ds equivalent zu 2d-arrays.

      Als ich mal für ein eigenes messagebox system recherchiert habe, ob arrays oder grids performanter im GM sind, hab ich in einem Forenpost von einem Yoyo-Staffmember gelesen, dass grids performanter sind, nicht nur in den speziellen grid-funktionen sondern auch beim schreiben und lesen. Selber nachgeprüft hab ich diese Aussage allerdings nicht und einfach grids statt arrays verwendet.

      EDIT: Das mit dem Array rückwärts initialisieren gilt übrigens nicht für HTML5 und andere Javascript Exporte (Tizen, Windows 8), da empfiehlt Yoyo das "normale" vorwärts initialisieren.

    • Da du ja schon ein Framework für die Zeitmessung hast, würdest du noch die Aussage von Yoyo, dass Grids schneller als Arrays sind verifizieren?
      Ich persönlich finde es ja seltsam, dass ein komplexerer Datentyp wie ds_grid, der vermutlich einen gewissen Overhead mitbringt performanter sein soll, als ein grundlegender Basisdatentyp wie ein Array.

      Hab dir den Code schonmal angepasst:
      Spoiler anzeigen

      GML-Quellcode

      1. //---2D-Array---
      3. //Create/Edition
      5. for(i = 99999; i >= 0; i--)
      6. {
      7. for(j = 99999; j >= 0; j--)
      8. {
      9. array[i,j] = 1;
      10. }
      11. }
      13. //Replacing
      15. for(i = 99999; i >= 0; i--)
      16. {
      17. for(j = 99999; j >= 0; j--)
      18. {
      19. array[i,j] = 2;
      20. }
      21. }
      23. //Access
      25. for(i = 99999; i >= 0; i--)
      26. {
      27. for(j = 99999; j >= 0; j--)
      28. {
      29. a = array[i,j];
      30. }
      31. }
      33. //---ds_grid---
      35. //Create/Edition
      37. grid=ds_grid_create(99999, 99999);
      39. for(i = 99999; i >= 0; i--)
      40. {
      41. for(j = 99999; j >= 0; j--)
      42. {
      43. ds_grid_set(grid, i, j, 1);
      44. }
      45. }
      47. //Replacing
      49. for(i = 99999; i >= 0; i--)
      50. {
      51. for(j = 99999; j >= 0; j--)
      52. {
      53. ds_grid_set(grid, i, j, 2);
      54. }
      55. }
      57. //Access
      59. for(i = 99999; i >= 0; i--)
      60. {
      61. for(j = 99999; j >= 0; j--)
      62. {
      63. a = ds_grid_get(grid, i, j);
      64. }
      65. }
      Alles anzeigen



      EDIT:
      Auch interessant ist, wie viel schneller die ds_grid spezifischen Funktionen sind:
      Spoiler anzeigen

      GML-Quellcode

      1. //Replacing
      2. ds_grid_set_region(grid, 0, 0, 99999, 99999, 3);
      4. //Access
      5. sum=ds_grid_get_sum(grid, 0, 0, 99999, 99999);
      6. //Nur um mal zu gucken ob diese funktion schneller alle werte auslesen kann, als die for-schleife (und dabei zusätzlich alle Werte addieren)

    • Ich kann "99999" x "99999" nicht nehmen, da Array Limit an 32000x32000 begrenzt ist und bei ds_grid wird dann mein Arbeitsspeicher voll.

      Nur ein kleiner Test:

      Array konnte ich problemlos 10000x10000 erstellen. (bei 30000x30000 kam "Out of Memory").
      bei DS-Grid habe ich problem bei 10000x10000 (Out of Memory)

      Ich habe erstmal ein Test mit "1000x1000" gemacht, damit es auf beiden geht.
      Wie ich sehe, ist Array wesentlich schneller. Wenn man aber die spezielle Funktion von ds_grid benutzt, ist dann ds_grid schneller, viel schneller als array.

      Spoiler anzeigen

      GML-Quellcode

      1. //---2D-Array---
      2. //Create/Edition
      4. for(i = 1000; i >= 0; i--)
      5. {
      6. for(j = 1000; j >= 0; j--)
      7. {
      8. array[i,j] = 1;
      9. }
      10. }
      12. Delay: 291 ms
      14. //Replacing
      15. for(i = 1000; i >= 0; i--)
      16. {
      17. for(j = 1000; j >= 0; j--)
      18. {
      19. array[i,j] = 2;
      20. }
      21. }
      23. Delay: 283 ms
      25. //Access
      26. for(i = 1000; i >= 0; i--)
      27. {
      28. for(j = 1000; j >= 0; j--)
      29. {
      30. a = array[i,j];
      31. }
      32. }
      34. Delay: 287 ms
      36. //---ds_grid---
      37. //Create/Edition
      39. grid=ds_grid_create(1000, 1000);
      40. for(i = 1000; i >= 0; i--)
      41. {
      42. for(j = 1000; j >= 0; j--)
      43. {
      44. ds_grid_set(grid, i, j, 1);
      45. }
      46. }
      47. Delay: 376 ms
      49. //Replacing
      50. for(i = 1000; i >= 0; i--)
      51. {
      52. for(j = 1000; j >= 0; j--)
      53. {
      54. ds_grid_set(grid, i, j, 2);
      55. }
      56. }
      58. Delay: 395 ms
      60. //Access
      61. for(i = 1000; i >= 0; i--)
      62. {
      63. for(j = 1000; j >= 0; j--)
      64. {
      65. a = ds_grid_get(grid, i, j);
      66. }
      67. }
      69. Delay: 304 ms
      71. /// Bonus für Grid
      73. //Access (Summiere den gesamte Grid, ds_grid_get_sum)
      74. sum = ds_grid_get_sum(grid, 0, 0, 1000, 1000);
      76. Delay: 7 ms
      78. //Creation (ds_grid_set_region)
      79. grid=ds_grid_create(1000, 1000);
      80. ds_grid_set_region(grid, 0, 0, 1000, 1000, 2);
      82. Delay: 25 ms
      84. //Replacing (ds_grid_set_region)
      85. ds_grid_set_region(grid, 0, 0, 1000, 1000, 3);
      87. Delay: 15 ms
      Alles anzeigen




      Ihr könnt selber die Performance testen, indem ihr dieser Skript benutzt:

      GML-Quellcode

      1. var time;
      2. time = current_time;
      4. /// <--- Da kommen die Funktionen rein, um Performance zu testen.
      6. time = current_time - time;
      8. show_debug_message("|-----------------------------");
      9. show_debug_message("| Delay: " + string(time) + " ms");
      10. show_debug_message("|-----------------------------");

      Ihr stinkt.

    • Das die ds_grid spezifischen Funktionen wesentlich schneller sind, als eigene Scripte hab ich mir schon gedacht.

      Aber wie es aussieht lag der YoYo-Mitarbeiter falsch mit seiner Aussage, dass grids auch beim einfachen auslesen und schreiben von Werten schneller sind als Arrays.
      Da lag ich wohl mit meinem Bauchgefühl richtig, dass dies unlogisch ist und lerne daraus Aussagen von Yoyo-Leute nicht blind zu glauben.^^

      Kann beim nächsten mal also beruhigt auf 2D-Arrays zurückgreifen, wenn ich bloß Daten in/aus "Tabellen" schreiben und auslesen will.

    • Ich finde es immer wieder lustig, in gmc.yoyogames.com zu lesen, das Array immer so lahm ist und die ds_*-Funktionen immer superschnell sind/empfehlt. xD

      Ich fand heraus, das 1D-Array keine 32000 Limit hat... Ich habe mal eben getestet, das es sogar 10000000 Stück gehen sollte.
      Ich glaube, das der Limit von 1D-Array (nehmen wir mal die Limit von 2D-Array 32000 mal 32000) wäre 1024000000 Stück.
      Und das tolle an Array ist, ich kann bei Arrays viel mehr Werte befüllen, ohne gleich "Out of Memory" zu kriegen. Bei ds list dagegen schon.

      @TrunX gib mir mal den Forum-Thread, wo der YoYo-Staff das gesagt hat. Ich werde es ihm zeigen. xD

      Ich glaube, dieser Thread kann ruhig angepinnt werden. Das würde viele Nutzer echt helfen.
      Außerdem überlege ich gerade, ob ich den Thread nach "Optimierung Tipps/Performance Verbesserung" überarbeiten sollte. Ich kenne da viele gute Optimierung. ^^
      Ihr stinkt.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von Chinafreak ()

    • Hier mal zwei Aussagen von Mike Dailly, die ich auf die schnelle ergoogelt habe:
      gmc.yoyogames.com/index.php?showtopic=662361#entry4794670
      gmc.yoyogames.com/index.php?showtopic=574475#entry4246155

      Bin mir aber relativ sicher damals eine ähnliche Aussage von einem anderen Staff-Member gelesen zu haben, hab da ein grobes Avatarbild vor Augen.^^

    • Dann benutzt Arrays doch. Du kannst dir auch eigene Funktionen machen (wie ich es mache). Nur dieser Funktionen solltest du lieber nicht bei extremer großer Arrays öfters benutzen. ^^

      Oder du rufst die Funktion einmal in Ladebildschirm an und fertig ist es. (Sofern du die nur einmal benutzen musst.)

      Sonst macht die Unterschied zwischen eigene Funktionen und ds-funktionen kaum was, solange man es nicht übertreibt.
      Ihr stinkt.

    • Chinafreak schrieb:

      Sonst macht die Unterschied zwischen eigene Funktionen und ds-funktionen kaum was, solange man es nicht übertreibt.

      Als die Grids für mich neu waren und ich von Arrays darauf umgestellt hatte, war ich jedenfalls ziemlich überrascht wie sehr sich die Performance verbessert hat,
      ich muss dazu aber auch sagen, dass die Dinger in meinem Projekt riesig ausfallen: 3330x48 im Schnitt, und das 32 mal.
      Trotzdem beträgt die Ladezeit einer größeren Map (inklusive Erstellung und Befüllung der Grids) ohne YYC ca. 1 Sekunde. Mit YYC merke ich vom Laden fast nichts.
      Aber solange man solche Dimensionen nicht braucht sind Arrays sicher auch gut geeignet.

      Finde aber interressant, dass Arrays in einigen Fällen doch schneller sind. Ich habe dem Yoyo-Typen im Forum das auch ohne zu hinterfragen abgekauft, dass Grids immer schneller sind.^^


    • Stimmt, wo du gerade sagst... Vielleicht sieht die Geschwindigkeitsdifferenz unter YYC komplett anders aus. Ich werde das mal später testen. Falls es unterschied gibt, dann werde ich auch hier hinstellen.

      Aber @RLP soweit ich weiß, war Arrays früher deutlich langsamer. Dank der neue Update ist Arrays viel schneller geworden. Vielleicht ist das der Grund, warum YoYo-Staff das sagen, das DS-Kram schneller ist.
      Ihr stinkt.

    • Was bei 1D Arrays noch zu beachten ist, ist der Memory Cache auf der CPU (y vor x bei 2D array in einem 1D array),

      GML-Quellcode

      1. // Schneller
      2. var width = 4200, height = 4200;
      3. for (var _y = 0; _y < height; _y++)
      4. for (var _x = 0; _x < width; _x++)
      5. myArray[_y * width + _x] = 1;
      7. // Langsamer
      8. for (var _x = 0; _x < width; _x++)
      9. for (var _y = 0; _y < height; _y++)
      10. myArray[_y * width + _x] = 1;

      Hier mal eine genaue beschreibung: Array Cache
      :saint:

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von Tice ()

    • GML-Quellcode

      1. i = 99999;
      2. repeat(100000) {
      3. array3[i] = 1;
      4. i -= 1;
      5. }

      War bei mir um ein paar ms sogar noch schneller. Aber das mit dem rückwärts initialisieren ist mir ein Rätsel - zumal es keinen Unterschied zu machen scheint, ob man vorher bereits das Array an der Stelle 99999 initialisiert oder nicht (intuitiv hätte ich gedacht, dass es etwas mit dem schrittweisen allozieren zu tun hat...).

      Außerdem war die Repeat-Schleife bei Listen bei mir im Schnitt knapp langsamer als die For-Schleife. :D

    • @ghost

      Ich kann mir logisch vorstellen, das rückwärts initialisieren schneller ist.
      Meine Theorie (kA ob es so wirklich ist.)

      Normal initialisieren:

      GML-Quellcode

      1. //Hier muss der Arrays jedesmal neu vergrößern
      2. //erstelle array und vergrößere array zu 1
      3. array[0] = 1;
      4. //vergrößere array zu 2
      5. array[1] = 1;
      6. //vergrößere array zu 3
      7. array[2] = 1;
      8. //vergrößere array zu 4
      9. array[3] = 1;
      10. //vergrößere array zu 5
      11. array[4] = 1
      Alles anzeigen


      Rückwärts initialisieren:

      GML-Quellcode

      1. //erstelle array und vergrößere array zu 5
      2. array[4] = 1;
      3. //vergrößerung ist nicht notwendig
      4. array[3] = 1;
      5. //vergrößerung ist nicht notwendig
      6. array[2] = 1;
      7. //vergrößerung ist nicht notwendig
      8. array[1] = 1;
      9. //vergrößerung ist nicht notwendig
      10. array[0] = 1;



      Und somit läuft rückwärts schneller als fortwärts. Da jedes mal vergrößern mehr zeit benötigt wird als es bereit exisitert.
      Nur wie @TrunX es gesagt hat, funktioniert das unter JavaScript-Exporte nicht (HTML5, Windows 8 JavaScript, Tizen etc.). Da muss man schon fortwärts erstellen.

      [EDIT:]
      Beispiel besser ausgedrückt.
      Ihr stinkt.

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

    • Wie schon erwähnt verwirrt mich es trotzdem - diese Art der Vergrößerung ist ziemlich unüblich, normalerweise wird der allozierte Speicher in so einem Fall verdoppelt (wie zum Beispiel in std::vector in C++) - und in der Tat stimmt deine Theorie auch nicht ganz. Die magische Zahl scheint hierbei die Größe 32000 zu sein, welche auch in der Hilfe bei

      GML-Quellcode

      1. array_length_1d(arr)

      genannt wird.

      Andernfalls müsste folgender Code ja genauso schnell sein - ist er aber nicht:

      GML-Quellcode

      1. array[99999] = 1;
      2. for(var i = 0; i < 99999; i++){
      3. array[i] = 1;
      4. }

      (Einen Umstand, den ich bereits im vorherigen Post erwähnt habe... :whistling: )

      Folgender Code IST aber schnell:

      GML-Quellcode

      1. array[31999] = 1;
      2. for(var i = 0; i < 31999; i++){
      3. array[i] = 1;
      4. }


      Woraus folgt, dass der Game Maker ab der Größe 32000 Arrays anders behandelt - aber vergrößern tut er scheinbar tatsächlich auch unter 32000 in 1er Schritten beim vorwärts initialisieren. Was er genau rückwärts bei größeren Größen macht, habe ich noch nicht ausprobiert. Das Problem dabei ist auch, dass die array_length_1d Funktion nur bis zur Größe 32000 funktioniert.