Optimieren, need help

[volkard]

0xdeadbeef schrieb:

template <typename container_t> class container_extension : public container_t {
public:
  void my_new_and_wonderful_method() { ... }
};

...einfach für ne schönere Kapselung. Auf jeden Fall gibt es durchaus Situationen, in denen das Sinn macht.

kann man natürlich ohne sorgen mit allen container_t machen, die nen virtual destruktor haben. ich sehe sowas meist beim versuch, eine bereits hübsche datenstruktur zu vergewaltigen. man coded einem feinen vector eine push_front() dran, statt ins buch zu gucken und rauszufenden, daß die queue hier gefordert wäre.

Was die Verwendung von Bäumen angeht, so macht das vor allem dann Sinn, wenn man hierarchische Strukturen zu verwalten hat, wie etwa Dateisysteme,

selbstredend ist es oft sinnvoll, wenn die rohdaten als baum vorliegen, auch nen baum zu nehmen, der das im code darstellt. da aber nicht mehr ne std::set und auch kein avl-baum, sondern sofort was selber gebautes, oder?

wenn es keine wirklich sinnvolle Möglichkeit gibt, den Schlüssel-Datentyp zu hashen, oder wenn man überhaupt nicht einschätzen kann, wie viele Werte der ADT nachher enthalten soll.

wenn man die anzahl gar nicht einschätzen kann, ist es vermutlich noch recht früh im projekt. klar, am anfang nimmt man irgendwas, selbst wenn es ein vector mal ist, der aufgaben einer map übernimmt. genau auswählen kann man ja später noch, ohne was umzuschmeißen. oo ist toll.

und manchmal kann man nicht sinnvoll hashen. da hab ich mal gehofft, du bemerkst es nicht. hast recht, man kommt nicht immer ohne bäume aus. es ist gut, die std::set und vor allem die std::map so einfach zur verfügung zu haben.

der hauptgrund für die stl ist aber ein ganz anderer: die verbreitung. ob jetzt standardisiert wie die stl oder noch nicht wie boost, die sachen aus diesen libs kennt man und wenn man coded, soll man die bevorzugt nehmen und nur was eigenes machen, wenn der speedvortiel oder die bessere wartbarkeit signifikant sind. und es muß die kosten erheblicher dokumentation wert sein. nicht bloß ein paar kommentare in den code schmieren, sondern hübsch beschreiben, was die vorteile sind und dafür sorgen (z.B. mit einem mini-tutorial), daß die kollegen damit arbeiten können.

den ganzen ärger spart man sich, wenn man sich auf die stl (und boost) beschränkt. alle kollegen sind damit vertraut.

[0xdeadbeef]

volkard schrieb:

kann man natürlich ohne sorgen mit allen container_t machen, die nen virtual destruktor haben. ich sehe sowas meist beim versuch, eine bereits hübsche datenstruktur zu vergewaltigen. man coded einem feinen vector eine push_front() dran, statt ins buch zu gucken und rauszufenden, daß die queue hier gefordert wäre.

Ich hab dabei eigentlich mehr an GUI-Frameworks gedacht - Windows sind ja im weitesten Sinn auch so was wie Container.

volkard schrieb:

selbstredend ist es oft sinnvoll, wenn die rohdaten als baum vorliegen, auch nen baum zu nehmen, der das im code darstellt. da aber nicht mehr ne std::set und auch kein avl-baum, sondern sofort was selber gebautes, oder?

Bei hierarchischen Strukturen nimmst du keine map, das ist wahr, aber es gibt Bäumen allgemein eine Existenzberechtigung - du schienst Bäumen doch sehr...verschlossen...gegenüber zu stehen, deswegen hielt ich das für erwähnenswert.

volkard schrieb:

wenn man die anzahl gar nicht einschätzen kann, ist es vermutlich noch recht früh im projekt.

Ich bin schon öfter in Projekte gelaufen, die, was die Anzahl der zu verwaltenden Objekte anbetraf, sehr flexibel sein mussten, so im Bereich von ein paar hundert bis ein paar hundert tausend Einträgen. Zugegeben, meistens kann man das zumindest ungefähr abschätzen (will sagen, auf etwa eine Größenordnung), aber gerade, wenn du irgendwo im Frontend sitzt, kannst du dir nie sicher sein, wie viele Einträge du kriegst.

volkard schrieb:

klar, am anfang nimmt man irgendwas, selbst wenn es ein vector mal ist, der aufgaben einer map übernimmt. genau auswählen kann man ja später noch, ohne was umzuschmeißen. oo ist toll.

Hm. Eigentlich ist das nun grad mehr ein Merkmal der generischen Programmierung. Gut, wenn dus richtig anfängst, musst du auch in einem OO-Programm nur ein paar typedefs umhängen, aber...
Naja, da kommt es wirklich auf den Anwendungsbereich an.

volkard schrieb:

der hauptgrund für die stl ist aber ein ganz anderer: die verbreitung. ob jetzt standardisiert wie die stl oder noch nicht wie boost, die sachen aus diesen libs kennt man und wenn man coded, soll man die bevorzugt nehmen und nur was eigenes machen, wenn der speedvortiel oder die bessere wartbarkeit signifikant sind. und es muß die kosten erheblicher dokumentation wert sein. nicht bloß ein paar kommentare in den code schmieren, sondern hübsch beschreiben, was die vorteile sind und dafür sorgen (z.B. mit einem mini-tutorial), daß die kollegen damit arbeiten können.

Das ist richtig. Und es senkt die Entwicklungszeit doch deutlich - vielleicht kannst du ja wirklich nen perfekt angepassten RB-Baum in 5 Minuten schreiben, aber dann muss ich mich neidlos verbeugen, aber in aller Regel sitzt man an so was doch ein bisschen länger - und in der Zeit, in der man seine Container schreibt, kommt man mit dem Rest des Programms nicht voran. Plus, du hast nachher mehr zu debuggen - die gängigen STL-Implementierungen sind inzwischen doch recht gut getestet und relativ bugarm. (Bis auf die von Microsoft vielleicht... *hust*)

[Walli]

Hast du auch mal bedacht, dass eine angemessene Datenstruktur nachher auch Entwicklungszeit sparen könnte?

[der_held]

0xdeadbeef schrieb:

volkard schrieb:

klar, am anfang nimmt man irgendwas, selbst wenn es ein vector mal ist, der aufgaben einer map übernimmt. genau auswählen kann man ja später noch, ohne was umzuschmeißen. oo ist toll.

Hm. Eigentlich ist das nun grad mehr ein Merkmal der generischen Programmierung. Gut, wenn dus richtig anfängst, musst du auch in einem OO-Programm nur ein paar typedefs umhängen, aber...
Naja, da kommt es wirklich auf den Anwendungsbereich an.

Quark. Das mit dem Wegkapseln und somit einfach ändern zu können ohne den Rest anzupassen ist OO. Generische Programmierung ist wenn Code generiert wird und hat hiermit garnichts zu tun!

[0xdeadbeef]

Aber mitnichten. Das einfache drop-in-replacement irgendwelcher Kernbauteile ist generisch durch und durch - darum macht man ja diesen ganzen Aufriss mit den Konzepten. Du erwartest nicht mal mehr eine bestimmte Art Datentyp, sondern einfach ein bestimmtes Interface (sog. "Konzept"), und was dir nachher konkret untergejubelt wird, ist dir ziemlich egal.

Der Unterschied zur OOP ist, dass du nachher flexibler bist - im generischen kannst du nachher da, wo du den Kram benutzt, entscheiden, was du benutzen willst. In der OOP musst du das zentral in der Klasse festlegen.

@Mastah: Meiner Erfahrung nach ist das eher selten der Fall, vor allem, wenn du die Datenstrukturen genau auf ein Problem anpasst, so dass du sie nachher für so gut wie nichts anderes benutzen kannst. Das heißt aber natürlich nicht, dass das für alle Leute so gilt wie für mich.

[Helium]

class Foo {
public:
   void showContent()
   {
      copy (container.begin(), container.end(), ostream_iterator<int>(cout, " "));
   }
   ...
private:
   vector<int> container;
};

int main ()
{
   Foo foo;
   .. // ein par methoden (die nicht gezeigt wurden), damit auch inhalt da ist

   foo.showContent();
}

und jetzt merke ich, dass vector kacke ist.

class Foo {
public:
   void showContent()
   {
      copy (container.begin(), container.end(), ostream_iterator<int>(cout, " "));
   }
   ...
private:
   list<int> container;
};

main kann unverändert bleiben, auf Grund der Kapselung[b]. [b]Kapselung ist ein Teil der OOP. Generizität hatte damit nichts zu tun.

Du erwartest nicht mal mehr eine bestimmte Art Datentyp, sondern einfach ein bestimmtes Interface (sog. "Konzept"), und was dir nachher konkret untergejubelt wird, ist dir ziemlich egal.

Schon mal in einer nicht statisch typisierten OO-Spracheprogrammiert? Genau das kannste da machen. Du beschreibst also die OOP und behauptest dann das sei Generizität?

[otze]

ich glaub, er meinte was mit templates

[0xdeadbeef]

*Seufz*.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>

template <typename val_t = int,
          template<typename v_t> class container_t = std::list>
class Foo {
public:
  typedef val_t value_type;
  typedef container_t<val_t> container_type;

  void showContent()
  {
    std::copy(container.begin(),
              container.end(),
              std::ostream_iterator<value_type>(std::cout, " "));
  }

  //...

private:
  container_type container;
};

int main ()
{
  Foo<double, std::vector> foo;

  //...

  foo.showContent();
}

See what I mean?

[Helium]

Das ist die dämlichste Idee, die ich seit langem gesehen habe. Du rennst total am Problem vorbei. Natürlich kann man das machen, was du da zeigst, man kann sich aber auch ein Loch ins Knie boren und warme Milch reinkippen.

Ich will nicht wählen müssen, welcher Container verwendet wird. ICh will das das feststeht.

Ich will einfach schreiben

Foo foo;

foo. neMethode ();

Ich will niemals mit verschiedenen Containern arbeiten. Foo hat eine einzige ganz bestimmte Aufgabe. Am Anfang war mir allerdings noch nicht klar, ob std::vector der richtige Container zum lösen des Problems innerhalb von Foo war. Trotzdem habe ich einfach mal einen std::vector verwendet.
Nun kann ich und alle meine Kollegen Foo bereits verwenden, da es ja schon läuft. Dann beim ausbauen, refaktorisieren, optimieren oder sonstwas fällt mir auf, dass std::vector eine schlechte Wahl war und ersetze ihn durch std::list und passe gegebenen falls ein paar der Methoden von Foo an.

Bei deinem Vorschlag müsste ich und alle meine Kollegen den gesammten Code überarbeiten überall, wo bisher Foo stand muss jetzt Foo<int, std::list> hin. Das ist unmengen unnütze Arbeit und zudem total hässlich und unübersichtlich.

[Jester]

@Helium: Schonmal std::stack angeschaut?

MfG Jester

[Helium]

stack ist ein Container, wie quque auch. Er kann mit einem anderen Container parametrisiert werden.

Das ist eine ganz andere Situation. Bei stack geht es um eine allgemeine Struktur, die ich an die jeweilige Situation anpassen möchte. Bei meinem "Foo" geht es um ein Teil des Projekts, der in der Form überall im Projekt Verwendung findet.
Wenn ich nun merke, das die Struktur in der Form viel zu langsam oder viel zu speicherraubend ist, dann will ich sie einfach ändern können. Dadurch ist mein Projekt dann dementsprechend schneller oder weniger speichrraubend. Und ich will nur eine stelle ändern müssen, nicht das ganze Projekt.

[0xdeadbeef]

Wenn du mal genau hinkuckst, du musst nicht wählen, welchen Container du benutzen willst, du kannst auch einfach den Default-Wert (in diesem Fall std::list) nehmen.

[Jester]

Helium schrieb:

Bei meinem "Foo" geht es um ein Teil des Projekts, der in der Form überall im Projekt Verwendung findet.

Wußte ich nicht. Dachte immer Foo sei "hier beliebiges hindenken".

[volkard]

es ist eh selten eine gute idee. vorher einen ganz unpassenden container zu wählen. am besten ist, man wählt vorher einen, der schon recht genau passt. einen, dessen schnittstellen paßt.
und den kann man später austauschen, weil man von anfang an damit rechnete, ihn auszutauschen. insbesondere meine ich damit, daß man zwar ne std::map mal benutzt, weil's gerade so einfach ist, aber von der eigenschaft, daß sie beim durchiterieren ihre keys sortiert darbringt, keinen gebrauch macht.
und schwupps, hat man die möglichkeit, viele andere datenstrukturen zu nehmen. hashtables natürlich. skip-lists. und vor allem die ganen kombinationen, damit beginnt der spaß ja erst richtig.

[0xdeadbeef]

Ja, ja, schon klar - aber wenn man den Kram nicht konkretisieren will, gibts ja noch den Default-Wert. Aber es kann schon sinnvoll sein, den Datentyp zu parametrisieren - je nach Gelegenheit kann ein ganz anderer Datentyp vorteilhaft sein. Stell dir vor, du brauchst Foo an zwei Stellen des Programms. Das eine mal kannst du vorher feststellen, wie viele Werte du kriegst, das andere Mal hast du nicht die geringste Ahnung. Das eine Mal hättest du gerne nen Vektor, das andere mal nen Baum (auch wenn volkard mich dafür jetzt wahrscheinlich wieder verbal verprügeln wird ). Und da bist du mit reiner OOP ziemlich aufgeschmissen.

[Helium]

Solche Datenstrukturen wirst du aber selten anfinden, es sei denn es geht gerade (wie bei std::stack und den anderen STL-Containern) darum ganz allgemein zu sein.

class Base {
public:
   virtual void add (Foo const & foo) = 0;
};

class Impl1 : public Base {
public:
   void add (Foo const & foo)
   {
      container.push_back (foo);
   }
private:
   std::vector<Foo> container;
};

class Impl2 : public Base {
public:
   void add (Foo const & foo)
   {
      container.insert (foo);
   }
private:
   std::set<Foo> container;
};

Du siehst, reine OO. und dennnoch kann ich in verschiedenen Situationen verschiedene Ddatenstrukturen verwenden. Und ich habe dieses bekloppte Beispiel nur geschreiben, um dich zu ärgern. :p

[volkard]

0xdeadbeef schrieb:

Das eine mal kannst du vorher feststellen, wie viele Werte du kriegst, das andere Mal hast du nicht die geringste Ahnung. Das eine Mal hättest du gerne nen Vektor, das andere mal nen Baum (auch wenn volkard mich dafür jetzt wahrscheinlich wieder verbal verprügeln wird ). Und da bist du mit reiner OOP ziemlich aufgeschmissen.

erstmal die verlanten prügel: *patsch*

kann nicht nachvollziehen, warum die anzahl den wunsch nach baum erzeugt. ne hashtable kann genauso wachsen wie ein baum. die mit verkettung im überlaufbereich (also die inzwischen normalen) können auch in grenzen recht nett schrumpfen.

ich halte nix davon, fette universalschnittstellen zu bauen, wo mal ein baum, mal ne hashtable, mal ein array und mal ne liste drunterliegen und alle strukturen bietet sort, find, remove, insert und iteratoren an. hätte man sowas, könnte man natürlich fein drauflosprogrammieren und erst am ende vor der haustür des kunden noch schnell entscheiden, welche datenstruturen man nimmt. aber vielleicht könnt ihr mich ja auch her von eurem modernen stil überzeugen.

[0xdeadbeef]

Warst du nicht derjenige, der meinte, man sollte sich je nach Problem eigene Datenstrukturen bauen, um die Performance zu steigern? Hier hast du die perfekte Möglichkeit, dir je nach Problem eine auszusuchen und die Interfaces quasi vom Speichermanagement abzukapseln - und das alles ohne overhead. Ravioli-Code par excellence.

@Helium: Ich finde das ziemlich umständlich, und vom Laufzeitverhalten her ist es grausam. virtual void ad...bah. Nehmen wir (um dem Beispiel mal ein bisschen Sinn einzuhauchen) an, std::set hätte tatsächlich keine push_back-Methode, dann schreib ich trotzdem immer noch lieber

template <template<typename t> class container_t> class Foo {
private:
  cointainer_t<Bar> container;

public:
  inline void add(const Bar &bar) { container.push_back(bar); }
};

template<> void Foo<std::set>::add(Bar &bar) { container.insert(bar); }