JLI Spieleprogrammierung

[HotAcid]

@Lord: weil bei Vector die Iteratoren nur intern benutzt werden. Als Benutzer bekommst du davon nicht viel mit

@LeeDiGer: Das mit der Komplexität stimmt so nicht ganz...

alle Angaben in der Form vector / list

Einfügen und Entfernen:

vorne: O(n) / O(1)
Hinten: O(1) / O(1)
Mitte: O(n) / O(1)

Zugriff:

erstes: O(1) / O(1)
letztes: O(1) / O(1)
mittleres: O(1) / O(n)


Also kann man sagen, dass du list benutzen soltest, wenn du häufig Daten änderst. Wenn du nur auf die Elemente zugreifen willst, wäre ein vector angebracht.

Bei kleinen Datemengen ist das noch ziemlich egal, aber für größere Werte können sich da die Laufzeiten doch schon stark unterscheiden. Ich habe das mal getestet(bzw. als Hausaufgabe machen dürfen , da sollten wir eine Liste mit 13.000 Elementen einmal mit BubleSort (Aufwand: O(n^2) ) und dann mit QuickSort (Aufwand: O(n*log(n) ) ) sortieren. BubbleSort hat etwa eine Minute gebraucht, QuickSort nicht mal eine Sekunde! Übrigens, das war in Java, nicht in C++.

viele Grüße
Felix
_________________
StGB §§ 328 Abs. 2 Pkt 3:
Mit Freiheitsstrafe bis zu fünf Jahren oder mit Geldstrafe wird bestraft, wer eine nukleare Explosion verursacht.

[Kampfhund]

@Acid:

Was heißt das O(..) genau?

[The Lord of Programming]

[xardias]

löschen sollte aber wesentlich langsamer sein als in einer liste.
Ich würde immer listen nehmen, sobald die größe der liste/arrays nicht feststeht, und variable sein muss.

[Kampfhund]

Ich meine, dass das einfügen am ende langsamer sein müsste als bei der liste. Das array müsste nämlich immer neu angelegt werden und das alte array in das neue kopiert werden.
(vileicht erklärt das O(..) aber genau das?)

[Hazel]

[HotAcid]

Wenn eine Operation den Aufwand O(1) hat, bedeutet das, dass diese Operation "in einem Schritt" (bzw in mehreren) gemacht werden können.

O(n) bedeutet, dass diese Operation n Schritte benötigt, wobei n für die Anzahl der Daten(bzw für die Länge) steht.

Das ganze ist stark vereinfacht, es geht dabei nur um die Potenz. Faktoren oder sontige Summanden werden dabei ignoriert. Wenn man den Aufwand einer Methode analysiert und dabei auf die Formel 4*n + 2938 kommt, ist die Aufwandsklasse immer noch O(n).

Häufige Aufwandsklasen sind:
O(1) O(n) O(log(n) ) O(n*log(n)) O(n^2) o(2^n)

viele Grüße
Felix
_________________
StGB §§ 328 Abs. 2 Pkt 3:
Mit Freiheitsstrafe bis zu fünf Jahren oder mit Geldstrafe wird bestraft, wer eine nukleare Explosion verursacht.

[Kampfhund]

Ja, sowas in der Art hate ich mir schon gedacht.

Dann kann man doch aber schlecht vergleichen:

wenn ein vector 10000 elemente hat und man eins hinzufügt ist der (zeit-)aufwand sehr groß. Bei der liste hingegen nicht.

das würde bedeuten Ov(1) = Ol(1) aber Zv >> Zl
(Z = Zeitaufwand, >> = wesentlich größer, v = vector , l = list)

[HotAcid]

bei vector ist der Aufwand auch nur O(1) wenn man hinten anfügt.

Angenommen, Vector und list haben jeweils 10.000 Elemente. Wenn du vorne einfügen willst, bist du bei Ov(10.000) und Ol(1)
das ist schon ein kleiner Unterschied

viele Grüße
Felix
_________________
StGB §§ 328 Abs. 2 Pkt 3:
Mit Freiheitsstrafe bis zu fünf Jahren oder mit Geldstrafe wird bestraft, wer eine nukleare Explosion verursacht.

[Kampfhund]

Aber der _Zeit_ - aufwand ist beim einfügen hinten in den vector doch auch größer als bei der liste. schlißlich muss das gesamte array neu angelegt und alle elemente in das neue array kopiert werden. bei der liste muss nur ein kleiner speicherblock reserviert werden.

[HotAcid]

achso, so meinst du das...

hm... mag sein, dass du sogar Recht hast, da bin ich mit meinem Latein jetzt ein wenig am Ende. Habe die Tabelle aus nem Buch abgeschrieben("Die C++ Standardbibbliothek" von Kuhlins, Schader), die interne Struktur von vector habe ich aber noch nicht gelesen, wenn ich soweit bin kann ich das hier nochmal schreiben.

viele Grüße
Felix
_________________
StGB §§ 328 Abs. 2 Pkt 3:
Mit Freiheitsstrafe bis zu fünf Jahren oder mit Geldstrafe wird bestraft, wer eine nukleare Explosion verursacht.

[Hazel]

HotAcid: Du musst dazu sagen, dass das nicht immer so ist, sondern nur im worst-case.
_________________
*click* Dabuu!?
Twitter: http://twitter.com/Ollie_R

[The Lord of Programming]