Listen oder Objektpools?

Übersicht BlitzMax, BlitzMax NG Allgemein

Gehe zu Seite 1, 2  Weiter

Neue Antwort erstellen

M0rgenstern

Betreff: Listen oder Objektpools?

BeitragMo, Nov 01, 2010 13:46
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo Leute.
Ich wollte hier mal eine kleine Diskussion anregen.
Und zwar habe ich mich in letzter Zeit ein wenig mit C# beschäftigt und da war so der allgemeine Tenor, dass die meisten zum Verwalten von Klasseninstanzen Objektpools, also Arrays benutzen.
Ich denke aber, dass die meisten hier im Forum bei BMax mit Listen hantieren (so wie ich es bisher auch gemacht habe).

Jetzt würde mich mal interessieren: Was haltet ihr von der Sache? Also, arbeitet ihr eher mit Listen oder eher mit Pools.

Lg, M0rgenstern

Thunder

BeitragMo, Nov 01, 2010 13:50
Antworten mit Zitat
Benutzer-Profile anzeigen
Kommt darauf an, ob die Anzahl meiner Elemente variabel ist oder nicht. Wenn variabel, dann Listen, ansonsten meistens Arrays. Eine Ausnahme wäre, wenn ich die Methoden von TList verwenden will.

mfg Thunder
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

M0rgenstern

BeitragMo, Nov 01, 2010 13:53
Antworten mit Zitat
Benutzer-Profile anzeigen
Thunder, wie meinst du das mit Variabel?
Denn mit dem Argument hab ich eigentlich in dem anderen Forum auch FÜR Listen argumentiert, aber dann wurde mir gesagt, dass das mit Objektpools genauso geht, dass jede Klasse einfach ein Attribut mehr braucht, z.b. IsInUse:int.
Über das könnte man dann einfach überprüfen, ob ein Objekt bearbeitet werden muss oder nicht.
UNd da kam auch das Argument auf: Man weiß ja etwa wie viele Instanzen von jeder Klasse im Spiel genutzt werden. Also kann man die vorher alle erstellen und einfach den oben genannten Flag setzen.

Lg, M0rgenstern

Thunder

BeitragMo, Nov 01, 2010 13:57
Antworten mit Zitat
Benutzer-Profile anzeigen
Hahaha, typisch Speicherverschwender. Stell die maximale Zahl an Objekten ein, die vorkommen kann.

Ich wollte sagen, dass es darauf ankommt, ob ich eine feste Anzahl an Instanzen habe, z.B. ein Spielfeld das X Mal Y Tiles hat, oder eine nicht feste Anzahl, bei einer Ingame-GUI die Anzahl der Fenster. Bei ersterem verwende ich Arrays, bei letzerem Listen.

mfg Thunder
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

M0rgenstern

BeitragMo, Nov 01, 2010 14:00
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich bin auch eher für Listen.
Aber die sollen seeeehr langsam sein mit wachsender Größe und Arrays halt nicht. Da wurde dann auch gesagt, dass der Speicherplatz ja nicht so groß wäre der dafür gebraucht wird.
Wie gesagt, ich weiß inzwischen nicht mehr wo ich stehe und wollte überhaupt mal hören wie das hier so gesehen wird, weil ich mir sowas schon dachte.

Lg, M0rgenstern

Thunder

BeitragMo, Nov 01, 2010 14:13
Antworten mit Zitat
Benutzer-Profile anzeigen
Naja, die Listen müssen schon um die 100.000 Elemente enthalten, dass man einen Unterschied merkt. Daher nehme ich meistens Listen, aber ich würde auf keinen Fall ein Array mit einer Maximalgröße vordefinieren.
Man kann ja in BlitzMax auch die Arraygröße ändern. Wenn man sich also eine Array-Verwaltung selbst schreibt, ist das schneller, aber der Aufwand wäre meistens zu hoch. Da nehme ich einfach Listen.

mfg Thunder
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

Xeres

Moderator

BeitragMo, Nov 01, 2010 14:16
Antworten mit Zitat
Benutzer-Profile anzeigen
Nimm das, womit du arbeiten kannst und was sich Strukturell am sinnvollsten umsetzen lässt. Diese ganzen Geschwindigkeits und Speicherplatz Argumentationen halte ich immer für leicht überzogen - beides greift erst ab mehreren hundert Objekten und lässt sich nicht so verallgemeinern...
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

hamZta

Administrator

BeitragMo, Nov 01, 2010 14:27
Antworten mit Zitat
Benutzer-Profile anzeigen
M0rgenstern hat Folgendes geschrieben:
Aber die sollen seeeehr langsam sein mit wachsender Größe und Arrays halt nicht


Welche Listen-Operation wird denn langsam bei großen Listen?

Iterieren: Einmal durch die Liste/das Array iterieren läuft in O(n)
Anfügen: Bei einer Liste klares O(1), bei einem Array ebenfalls, allerdings muss gegebenenfalls neuer Speicher angefordert werden und das kostet Zeit
Löschen eines bestimmten Eintrages: Ist Bei Listen und bei Arrays O(1) (kommt bei letzterem aber auf die Implementierung drauf an)
Ein bestimmtes Element suchen: Eine richtige Suche ist bei beiden Datenstrukturen O(n), beide müssen durchiterieren
Einen bestimmten Index ansprechen: Arrays O(1), Listen müssen iterieren.

Wie man sieht, gibts keinen wirklichen Geschwindigkeitsunterschied bei den Standardoperationen. Und ich muss Xeres zustimmen: Den Unterschied wirst du ohnehin nicht merken.

Außerdem ist "Premature Optimization" (also optimieren bevor's überhaupt Sinn macht) ohnehin verschwendete Zeit Wink

hamZta
Blog.

M0rgenstern

BeitragMo, Nov 01, 2010 16:11
Antworten mit Zitat
Benutzer-Profile anzeigen
Zitat:
Eine richtige Suche ist bei beiden Datenstrukturen O(n), beide müssen durchiterieren


So nicht ganz richtig: Siehe binäre Suche in einem sortieren Array. O(log n).
Aber das nur nebenbei, im Grund weiß ich was du meinst.

Ich seh das eigentlich auch eher wie ihr, also dass der Unterschied eigentlich nicht auffällt.
Das einzige wos mir mal aufgefallen ist: Partikel. Die hatte ich in einer Liste und da hats wirklich geruckelt. Weiß nicht ob das mit einem Array besser gewesen wäre.

Was hier vielleicht noch ganz interessant bei der Diskussion ist: In dem anderen Forum wurde bemerkt, dass Listen im Prinzip auch nur Arrays wären die dann intern halt vergrößert und verkleinert werden sobald man Objekte hinzufügt bzw entfernt.
Das ganze kommt mir aber spanisch vor. Wir haben im Info Unterricht mal ne Liste Programmiert und das waren KEINE Arrays. Da hatten wir kein einziges Array. Wie soll ich das also verstehen?


Nebenbei:
Zitat:
Anfügen: Bei einer Liste klares O(1)

Wie kommst du darauf? ein Voranfügen wäre O(1) aber ein Anfügen ist bei mir O(n) weil er bis ans Ende der Liste laufen muss, vorausgesetzt nur der Kopf ist extern angegeben und nicht auch noch das letzte Element.

Lg, M0rgenstern

mpmxyz

BeitragMo, Nov 01, 2010 16:27
Antworten mit Zitat
Benutzer-Profile anzeigen
M0rgenstern, bitte verfange dich nicht in irgendwelchen Implementierungsdetails! Wink
Ich denke, dass hamZta bei typischen doppelt verketteten Listen ist.
Der Begriff Liste ist eher abstrakt.
Das heißt, dass man sowohl eine Liste mit einem Array, eine doppelt verkettete Liste oder einen Binärbaum daraus machen kann.
Er schreibt nur vor, was für Operationen von der Datenstruktur beherrscht werden müssen.
mfG
mpmxyz
PS: M0rgenstern, man kann sogar eine doppelt verkettete Liste über ein Array implementieren!
Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

M0rgenstern

BeitragMo, Nov 01, 2010 16:34
Antworten mit Zitat
Benutzer-Profile anzeigen
mpmxyz:
Ist mir schon klar deswegen wars ja nur ein nebenbei^^

Aber mal ganz ehrlich. Eine Liste über ein Array zu implementieren ist doch viel langsamer sobald es darum geht Objekte anzuhängen oder rauszulöschen oder hab ich grade nen Denkfehler drin?
Denn normalerweise müsste man doch das Array jedesmal vergrößern/verkleinern was ja wohl viel länger dauert als eine neue Klasseninstanz zu erstellen.

Lg, M0rgenstern

mpmxyz

BeitragMo, Nov 01, 2010 16:47
Antworten mit Zitat
Benutzer-Profile anzeigen
Man kann das Array in größeren Blöcken vergrößern und verkleinern.
Beim Hinzufügen eines Eintrages wird dieser einfach am Ende hinzugefügt. (O(1), wenn das Array nicht vergrößert werden muss)
Beim Entfernen eines Objektes wird der Eintrag des entfernten Objektes durch das letzte Objekt im Array ersetzt und der letzte Eintrag frei gemacht. (immer O(1), wenn das Array nicht verkleinert wird)
mfG
mpmxyz
Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer
 

Macintosh

BeitragMo, Nov 01, 2010 16:55
Antworten mit Zitat
Benutzer-Profile anzeigen
man würde aber normalerweise listen nicht über array implimentieren. sonder über pointer ;D aber.... bmax ist in sachen pointern ja sehr beschränkt eswegen die variante der linked list in bmax wohl wegfällt :/

mpmxyz

BeitragMo, Nov 01, 2010 17:00
Antworten mit Zitat
Benutzer-Profile anzeigen
Wo ist denn BlitzMax bei den Pointern eingeschränkt? (von pointern auf Objektvariablen mal abgesehen)
Was für eine Art von verketteten Listen meinst du denn?
mfG
mpmxyz
Edit: DaysShadow, du liegst schon richtig.
Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer
  • Zuletzt bearbeitet von mpmxyz am Mo, Nov 01, 2010 17:02, insgesamt einmal bearbeitet

DaysShadow

BeitragMo, Nov 01, 2010 17:01
Antworten mit Zitat
Benutzer-Profile anzeigen
Macintosh, du weißt schon, dass die List in Bmax eine Linked List ist?
Die Liste besteht aus TLinks, welche jeweils einen Pointer zum nächsten und zum vorherigen TLink haben.
Zudem hat jeder Link einen Pointer auf sein Value.

Es steht halt nur nicht da NextLink:TLink Ptr sondern nur NextLink:TLink.

Trotzdem ist es, wenn ich das ganze nicht vollkommen falsch sehe, nur ein Pointer und keine Kopie des jeweiligen Links.
Blessed is the mind too small for doubt
 

Macintosh

BeitragMo, Nov 01, 2010 17:29
Antworten mit Zitat
Benutzer-Profile anzeigen
eben. object pointer.
Mir ist durchaus bewusst, dass eine TList im grunde eine linked lsit ist.
ich meine nur, das man sich solch eine klasse in BMax nicht selbst bauen kann.
 

n-Halbleiter

BeitragMo, Nov 01, 2010 17:32
Antworten mit Zitat
Benutzer-Profile anzeigen
Eine Linked List kann man sich in BMax ohne Probleme bauen; Wie sonst könnte es die Klasse TList geben? :O

Und genau genommen sind es in BMax Referenzen.
mfg, Calvin
Maschine: Intel Core2 Duo E6750, 4GB DDR2-Ram, ATI Radeon HD4850, Win 7 x64 und Ubuntu 12.04 64-Bit
Ploing!
Blog

"Die Seele einer jeden Ordnung ist ein großer Papierkorb." - Kurt Tucholsky (09.01.1890 - 21.12.1935)
 

Macintosh

BeitragMo, Nov 01, 2010 17:35
Antworten mit Zitat
Benutzer-Profile anzeigen
Ach?! und wie baut man die sich? code bitte.
Viel spass, bei den versuchen aus einem BytePtr wieder ein object zu bekommen :D ^^
Du kannst in bmax auch keine operatoren überladen, aber der String kanns.
 

n-Halbleiter

BeitragMo, Nov 01, 2010 17:36
Antworten mit Zitat
Benutzer-Profile anzeigen
Schaue dazu einfach in den Source von BRL.LinkedList.
mfg, Calvin
Maschine: Intel Core2 Duo E6750, 4GB DDR2-Ram, ATI Radeon HD4850, Win 7 x64 und Ubuntu 12.04 64-Bit
Ploing!
Blog

"Die Seele einer jeden Ordnung ist ein großer Papierkorb." - Kurt Tucholsky (09.01.1890 - 21.12.1935)

BladeRunner

Moderator

BeitragMo, Nov 01, 2010 17:38
Antworten mit Zitat
Benutzer-Profile anzeigen
Und ob man das kann, Macintosch, Denn TLink als auch TList sind ja in BMax geschrieben Wink
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI

Stolzer Gewinner des BAC#48, #52 & #92

Gehe zu Seite 1, 2  Weiter

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Allgemein

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group