größtmögliche Effizienz / vector? / boost

windschief

du hast recht, Referenzen dürften nicht akzeptiert werden, sondern pointer...
eine list ist immer sortiert oder?
bei mir darf die sortierung aber nur zu bestimmten situationen kommen..

Vielen Dank für die Übersicht und dem Tipp mit der deque, ich werde es mal vergleichen und euch berichten.

Ich kann den Code leider nicht öffentlich machen *gr*
Welche Profiler benutzt ihr so? Ich habe mir mal vor einiger Zeit valgrind angeschaut, könnte das helfen? (ich programmiere unter linux)

unskilled

"eine list ist immer sortiert?"
wäre mir neu... man kann sie jederzeit sortieren, ja - aber imho nicht gerade effektiv...

"bei mir darf die sortierung aber nur zu bestimmten situationen kommen.."
hm?
Es gibt doch ein std::sort und std::stable_sort und so gar std::heap_sort - da wird ja wohl einer passen, um bei Bedarf zu sortieren!?

Falls die Größe bekannt ist: boost::circular_buffer sollte dann ne tolle Wahl sein - wenn du boost nicht nutzen darfst, kannst du dir ja seblst nen Ringpuffer schreiben.
Wenn dir das zu viel Arbeit ist oder die max. Größe nicht gegeben, oder abgeschätzt werden kann, ist wohl std::deque nicht die allerschlechteste Wahl...
Evtl. lohnt sich auch ein nicht-linearer Container(set / map / hash_map / ...)

Mach am besten nen typedef auf deinen Container am Anfang des Codes und dann guck mal, wie sich die Laufzeit mit verschiedenen Containern ändert.

"Ich kann den Code leider nicht öffentlich machen"
Dann gib uns doch wenigsten mal nen Stichwort, was du da mit dem Programm simulieren/... willst - dann findet sich bestimmt irgend jemand, der weiß, dass man da auch Algorithmus xyz nehmen könnte und nicht nur am Container Zeit einsparen könnte...

PS: Du compilierst aber im Release-Mode, ja?

bb

SeppJ

Listen sind unsortiert, bringen aber ihren eigenen sehr effizienten Sortieralgorithmus mit.

Der übliche Profiler unter Linux ist der eingebaute Profiler vom gcc (gprof).

unskilled

SeppJ schrieb:

Listen sind unsortiert, bringen aber ihren eigenen sehr effizienten Sortieralgorithmus mit.

Oh - da hatte ich mich wohl in der Komplexität geirrt - dachte, die wäre sehr viel höher gewesen, aber auf cplusplus.com steht(gerad kein standard hier) N*log N (Vergleich: std::sort idR N*log N aber im worst case so gar N*N).

Damit ist zumindest das entfernen und sortieren bei der liste am schnellsten - wäre noch zu klären, wie das beim hinzufügen ist (hier könnte aber ein eigener allokator sinnvoll sein, damit man nicht mehr für jedes hinzufügen ein new hat)

bb

windschief

unskilled schrieb:

Mach am besten nen typedef auf deinen Container am Anfang des Codes und dann guck mal, wie sich die Laufzeit mit verschiedenen Containern ändert.

PS: Du compilierst aber im Release-Mode, ja?

kannst du mir ein kurzes Bsp geben für typedef?

hmm release mode habe ich nur mal bei eclipse gehört... ich benutze kdevelop 4.
ich habe -02 eingeschaltet, kann ich sonst noch was tunen?

unskilled schrieb:

(hier könnte aber ein eigener allokator sinnvoll sein, damit man nicht mehr für jedes hinzufügen ein new hat)

kannst du mir das auch nochmal erklären

Mir scheint es gibt noch viele Möglichkeiten..

Zum Algorithmus.. ist ist eine Art A*-Algorithmus..

drakon

typedef :

typedef std::vector<std::vector> > vector2d;

unskilled

bsp.:

#include <deque>
#include <list>
#include <vector>

struct foo{};

typedef std::list<foo> foo_container;
//typedef std::deque<foo> foo_container;
//typedef std::vector<foo> foo_container;

int main()
{
  //mach was mit foo_container
}

Nur beim sort musst du halt unterscheiden, ob es eine Liste ist oder nicht(das sollte anhand von typename iterator_traits<foo_container::iterator>::category gehen - oder mittels einer extra Überladung für deine sort-Funktion für die Liste:

template<typename CONTAINER, typename COMPARER>
void sort(CONTAINER& me, const COMPARER& cmp = std::less<typename CONTAINER::value_type>())
{
  std::sort(me.begin(), me.end(), cmp);
}

template<typename VALUE_TYPE, typename ALLOCATOR, typename COMPARER>
void sort(std::list<VALUE_TYPE, ALLOCATOR>& me, const COMPARER& cmp = std::less<VALUE_TYPE>())
{
  me.sort(cmp);
}

/* 1
typedef std::list<foo> foo_container;
*/

/* 2
typedef std::deque<foo> foo_container;
*/

/* 3
typedef std::vector<foo> foo_container;
*/

int main()
{
  foo_container x;

//  x.push_back(foo());

  sort(x);
}

Vll sollte man die sort-Funktion in dem Fall auch inplace_sort nennen, weil man nicht erwartet, dass auf es das Argument verändert, aber da hab ich jz keine lust, das noch zu ändern^^
Aber so in etwa sollte das funktionieren...

Man muss eben nur noch das typedef ändern und den Rest kann man halt so lassen - unheimlich praktisch, um immermal zu testen, welcher Container optimale Ergebnisse liefert...

bb

windschief

Das Object das ich speichere speichere besteht aus ca. 5 verschiedenen Werten und einem Array.

Ich habe das jetzt mit einem struct gelöst, bringt das Vorteile gegenüber einer eigenen Klasse? Bei ca. 50.000 Objekten, kann das einen Unterschied machen?

Habe momentan folgendes: (wenn ein ptr eines Obj der liste/enqueue/vector hinzugefügt wird)

struct foo{ // 5 Werte + Array
};
foo* ptrFoo = NULL;

// hinzufügen
foo tmp = {bla blub};
ptrFoo = &tmp;
foo_container.push_back(prtFoo);

Gehts noch besser/schlauer?

Thanks!!!!!

windschief

noch eine zusätzliche Frage:
wenn ich ptrFoo lösche, muss ich dann auch das struct löschen bzw. wie kann ich das machen?

Bei einer klasse geht es ja mit

delete *ptrFoo

...

unskilled

struct = class - macht also keinen unterschied

das hinzufügen an sich ist schon doof, weil es definitiv was anderes macht, als du denkst...

mach es doch einfach erst mal so, wie man es normalerweise machen würde... danach kannst du es noch immer kaputt-optimieren...

bb

windschief

Oh was meinst du jetzt..?
So wird es nicht funktionieren?
Ich dachte so kann ich meine Objekte als Pointer speichern... wie denn dann?
Hatte sie vorher als Kopie, wollte das jetzt ändern - bzw bin gerade dabei.
Muss ich sie als Kopien lassen?

struct foo{ // 5 Werte + Array
};
foo* ptrFoo = NULL;

// hinzufügen
foo tmp = {bla blub};
ptrFoo = &tmp;
foo_container.push_back(prtFoo);

unskilled

struct foo
{
 /*...*/
};

int main()
{
  foo to_add;
  foo_container.push_back(&to_add);

  ;
}

so würde das aussehen - aber da musst du halt vor allem gucken, dass du to_add nicht vorher irgendwie zerstörst...

bsp., wie man es _nciht_ macht:

void add(Tfoo_container &foo_container)
{
  foo to_add;
  foo_container.push_back(&to_add);
}

int main()
{
  Tfoo_container foo_container;
  add(foo_container);
}

bb

DocShoe

Überleg dir mal, wie lange das Objekt lebt, dessen Adresse du speicherst. Und was passiert beim Zugriff auf diese Adresse, wenn das Objekt nicht mehr existiert?

windschief

Ja das verstehe ich, dass in dem Beispiel das Objekt nicht mehr existiert, ich glaube das dürfte bei mir auch nicht passieren...

Ich habe gerade mal vector und deque gegeneinander getestet, der Unterschied ist ziemlich groß!!!! Vielen vielen Dank für den Tipp Ich probiere später nochmal std::list.

Aber wenn ich nur Zeiger anstatt Objekte speichere müßte das auch nochmal sehr viel ausmachen oder was denkt ihr?

Nexus

windschief schrieb:

Aber wenn ich nur Zeiger anstatt Objekte speichere müßte das auch nochmal sehr viel ausmachen oder was denkt ihr?

Was ausmachen? Was erhoffst du dir davon?

Blue-Tiger

windschief schrieb:

Ja das verstehe ich, dass in dem Beispiel das Objekt nicht mehr existiert, ich glaube das dürfte bei mir auch nicht passieren...

Ich habe gerade mal vector und deque gegeneinander getestet, der Unterschied ist ziemlich groß!!!! Vielen vielen Dank für den Tipp Ich probiere später nochmal std::list.

Aber wenn ich nur Zeiger anstatt Objekte speichere müßte das auch nochmal sehr viel ausmachen oder was denkt ihr?

Kommt drauf an. Wenn du die Zeiger jedesmal mit new erstellst und mit delete loescht, dann: ja, wird viel ausmachen, wird naemlich viel langsamer sein. Wenn du die Pointer vorher schon alle hast und erst am Ende loescht: ja, wird vermutlich schneller sein, als dauerndes hin/her kopieren.

windschief

hmm, ich glaube ich habe nicht ganz verstanden was du meinst..

ich habe folgendes:
ich erstelle ein objekt, das muss in eine "liste" hinten dran gespeichert werden (momentan deque), dann nehme ich ein neues objekt aus der "liste" von vorne (und lösche es aus der liste) verändere es und stecke es vielleicht wieder rein, bzw vielleicht auch mehrere veränderungen von dem objekt oder es wird ganz verworfen.

Jetzt ist meine Frage, ob es schneller gehen würde von der performance, wenn ich statt dem objekt selbst nur den pointer auf das objekt speichere.. das objekt muss ich ja so oder so erstellen.

Ich hoffe man kann ungefähr verstehen was der algo macht, wie gesagt, eine art A*..

Nexus

Das kommt wohl auf das Objekt an. Ist es eher klein, lohnen sich Zeiger wahrscheinlich nicht. Wenn du hingegen viel Kopieraufwand sparen kannst, wäre der Ansatz schon eine Überlegung wert. Jedoch müsstest du selbst Speicher verwalten, und das kann (abgesehen von der Mühseligkeit) z.B. bei std::deque wie erwähnt auch langsamer sein. Ich würde am besten weiterhin std::deque oder std::list benutzen, es sei denn, du hast wirklich ein Performance-Problem. In diesem Fall misst du am besten die Zeit in beiden Fällen. Aber nur aufgrund vager Vermutungen würde ich mir keine zusätzliche Mühe machen.

windschief

wie schon gesagt, mein objekt (struct) besteht aus 5 elementen und einem array/vector. Ist das eher klein?

Mein du mit Speicher selbst verwalten new and delete?

Hierzu habe ich noch meine Frage:

wie kann ich wenn ich den pointer habe das struct dahinter löschen?
bsp:

struct foo
{
 /*...*/
};

int main()
{
  foo to_add;
  foo_container.push_back(&to_add);
  foo* ptr = foo_container[0];
  foo_container.pop_front();
  delete *ptr; // so? funktioniert das auch bei einem struct?
  ..;
}

Die Performance ist wie gesagt alles, muss schneller als anderes Programm (anderer algo) sein und muss noch ein bisschen was rausholen...

Nexus

Bevor du dich an solche Optimierungen machst, solltest du vielleicht schon die Grundkonzepte der Sprache verstehen. Manuelle Speicherverwaltung und Zeiger gehören definitiv dazu. Hast du kein C++-Buch, in dem diese Dinge erklärt werden?

Könnte der Compiler deinen Code kompilieren, dann würdest du undefiniertes Verhalten hervorrufen, weil du delete auf ein Objekt anwendest, das nicht mit new angefordert wurde.