Performancemythen?

[Phoemuex]

Jester schrieb:

Auch die konstante Laufzeit von list::size halte ich für ein Gerücht. Oder magst Du kurz erklären, wie man das zusammen mit konstantem interlist-splice hinkriegt?

http://www.cplusplus.com/reference/stl/list/size.html

Unter Complexity

Wieso sollte er denn jedesmal nachzaehlen? Man kann die Groesse doch eifnach speichern und immer, wenn sie sich veraendert die Groesse updaten...

Felix

EDIT: Das P.S. war im falschen Film

[CStoll]

Jester schrieb:

Erstens ruft diese Schleife size() nur ein einziges Mal auf. Und zweitens ist eine Implementierung, bei der list::size() jedes Mal neu nachzählen muß, bestimmt nicht standardkonform (der ANSI-Standard definiert nicht nur Schnittstellen, sondern auch Komplexitätsbeschränkungen - und list::size() hat konstante Laufzeit).

Woher soll der Compiler wissen, dass sich size nicht zwischendrin ändert? Und sei es durch Multithreading? Nene, dem bleibt garnichts anderes übrig als size jedesmal auszuwerten.

Schau dir die Schleife nochmal ganz genau an, dann siehst du den Unterschied:

for(
  size_t a=0,Size=list.size();  // Schleifeninitialisierung
  a<Size;                       // Abbruchbedingung
  ++a                           // Iteration
)
  ...

list.size() wird genau EINMAL aufgerufen - während der Schleifeninitialisierung. Für die Abbruchbedingung wird der aktuelle Index mit dem zwischengespeicherten Wert verglichen.

Auch die konstante Laufzeit von list::size halte ich für ein Gerücht. Oder magst Du kurz erklären, wie man das zusammen mit konstantem interlist-splice hinkriegt?

Sorry, wenn ich das jetzt nicht aus dem Kopf zitieren kann, ich habe den Standard nicht vorliegen. Aber ich werde mich bemühen, das nachzuholen.

[Jester]

Phoemuex schrieb:

http://www.cplusplus.com/reference/stl/list/size.html

Unter Complexity

Oha, danke. Interlist-Splice hat also garkeine konstante Laufzeit. std::list ist also noch unbrauchbarer als ich eh schon dachte.

[Mr. N]

Jester schrieb:

Phoemuex schrieb:

http://www.cplusplus.com/reference/stl/list/size.html

Unter Complexity

Oha, danke. Interlist-Splice hat also garkeine konstante Laufzeit. std::list ist also noch unbrauchbarer als ich eh schon dachte.

Du glaubst wirklich cplusplus.com? Tatsächlich ist es so, dass list<>::size() auch O(N) haben darf.

Und so implementiert es die libstdc++:

/**  Returns the number of elements in the %list.  */
      size_type
      size() const
      { return std::distance(begin(), end()); }

Also O(N).

Es ist ja nicht so, als ob du der einzige wärst, der splice kennt.

[Jester]

Womit dann wieder meine ursprüngliche Aussage richtig wäre...
Wie ist das denn nun festgelegt? Oder darf gar beides O(n) Laufzeit haben? -- Wäre ja doof. Beides zusammen konstant dürfte sich jedenfalls nicht machen lassen.

[Mr. N]

Jester schrieb:

Womit dann wieder meine ursprüngliche Aussage richtig wäre...
Wie ist das denn nun festgelegt? Oder darf gar beides O(n) Laufzeit haben? -- Wäre ja doof. Beides zusammen konstant dürfte sich jedenfalls nicht machen lassen.

Es ist nicht festgelegt. libstdc++ hat denke ich konstantes Splice und nicht-konstantes size(), und so sollte das auch sein. Ne andere Möglichkeit, wäre einen size-Cache zu haben, der bei splice invalidiert, sonst aber geupdatet wird. So oder so, ich hab ja nicht behauptet, dass std::list total praktisch wäre.

[Jester]

Mr. N schrieb:

Es ist nicht festgelegt.

Oh, das ist aber häßlich. Das heißt ich kann keine vernünftigen Laufzeitgarantien geben.

libstdc++ hat denke ich konstantes Splice und nicht-konstantes size(), und so sollte das auch sein.

Ja, sehe ich auch so.

Ne andere Möglichkeit, wäre einen size-Cache zu haben, der bei splice invalidiert, sonst aber geupdatet wird.

Das würde denke ich nicht funktionieren. Wie willst Du das implementieren? Du müßtest ja dem list-Objekt bescheid sagen, wenn was rein/rausgesplicet wird (das läuft doch nur über die Iteratoren). Damit das geht müßte jedes listen-element wissen in welcher list es gerade drin ist. Um das aber aktuell zu halten müßte man die Daten beim splicen updaten... was wiederum nicht in konstanter Zeit geht.

Ich denke auf einer Seite muß man in den sauren Apfel beißen und O(N) bezahlen.

[CStoll]

Jester schrieb:

Das würde denke ich nicht funktionieren. Wie willst Du das implementieren? Du müßtest ja dem list-Objekt bescheid sagen, wenn was rein/rausgesplicet wird (das läuft doch nur über die Iteratoren). Damit das geht müßte jedes listen-element wissen in welcher list es gerade drin ist. Um das aber aktuell zu halten müßte man die Daten beim splicen updaten... was wiederum nicht in konstanter Zeit geht.

Was meinst du, warum man bei splice() auch die Quell-Liste mit angeben muß?

[Jester]

CStoll schrieb:

Was meinst du, warum man bei splice() auch die Quell-Liste mit angeben muß?

Das weiß ich nicht. (Abgesehen davon, dass das imho eine weitere Einschränkung der Nutzbarkeit von list ist). Aber inwiefern hilft das die Zielliste upzudaten?

[kleine Bemerkung]

Hallo

OOP frißt ebensowenig Performance im Vergleich zu C wie ein Makroassembler
Performance frißt im Vergleich zu Maschinencode.

Es sei denn, man legt es darauf an.

Wenn man jedes einzelne Zeichen als Objekt behandeln würde und einen String dann als Liste von Zeichen-Objekten, dann kostet das Performance.
Aber deshalb hat man ja in C++ auch noch alle Low-Level-Strukturen von C
(Arrays usw.), die man im Zweifelsfall einsetzen kann.

Für Performace-unkritische Anwendungen wäre die bessere Wartbarkeit dank OOP
selbst einen gewissen Performance-Verlust wert.

Gruß

[rüdiger]

kleine Bemerkung schrieb:

Wenn man jedes einzelne Zeichen als Objekt behandeln würde und einen String dann als Liste von Zeichen-Objekten, dann kostet das Performance.

Quatsch.

[CStoll]

Jester schrieb:

CStoll schrieb:

Was meinst du, warum man bei splice() auch die Quell-Liste mit angeben muß?

Das weiß ich nicht. (Abgesehen davon, dass das imho eine weitere Einschränkung der Nutzbarkeit von list ist). Aber inwiefern hilft das die Zielliste upzudaten?

Ganz einfach: Du brauchst in den Iteratoren nicht zu speichern, welcher Liste sie gehören. Stattdessen hast du beide betroffenen Listen vor Ort (die Quelle als Parameter, das Ziel steckt hinter this) und kannst direkt deren Größenwerte anpassen (oder wenn du willst, auch nur für ungültig erklären).

[Jester]

Ohje, das heißt man muß Quell und Ziel-Liste kennen... und nicht nur Iteratoren dorthin. Naja, dann ist mir zumindest klar wie die Implementierung funktioniert. Wozu man's dann allerdings noch gebrauchen kann ist mir schleierhaft.

[CStoll]

Ja, du brauchst für Splice beide Listen (und Konstruktionen wie l1.splice(p,l2,l3.begin()); sind auch undefiniert). Das hat halt den Vorteil, daß du sehr schnell Elemente zwischen verschiedenen Listen umhängen kannst.

(Z.B. ein Scheduler schiebt ständig Threads zwischen aktiv, suspended, etc. hin und her).

PS: Ich hab mal die Implementation aus MSVC rausgesucht:

template<...>
class list
{
  ...
public:
  size_type size() const
  { return _Size; }

  void splice(iterator pos, _Myt& other)
  {
    if (!other.empty())
    {
      _Splice(pos, other, other.begin(), other.end());
      _Size += other._Size;
      other._Size = 0;
    }
  }

  void splice(iterator pos, _Myt& other, iterator src)
  {
    iterator _L = src;
    if (pos != src && pos != ++_L)
    {
      _Splice(pos, other, src, _L);
      ++_Size;
      --_X._Size;
    }
  }

  void splice(iterator pos, _Myt& other, iterator first, iterator last)
  {
    if (_F != _L)
    {
      if (&other != this)
      {
        difference_type _N = 0;
        _Distance(first, last, _N);
        _Size += _N;
        other._Size -= _N;
      }
      _Splice(pos, other, first, last);
    }
  }
...
};

(_Size merkt sich die aktuelle Größe und _Splice() verbiegt die Zeiger, um die Elemente umzuordnen)

[Jester]

CStoll schrieb:

Ja, du brauchst für Splice beide Listen (und Konstruktionen wie l1.splice(p,l2,l3.begin()); sind auch undefiniert). Das hat halt den Vorteil, daß du sehr schnell Elemente zwischen verschiedenen Listen umhängen kannst.

Das könnte man aber auch, wenn man nur Iteratoren hätte ohne zu wissen in welchen Listen die Dinger konkret rumhängen. Ich hätte gern ein freies splice:

// hängt die Liste [start, end) vor pos in die Liste ein, in der sich pos befindet.
void splice(Iterator start, Iterator end, Iterator pos);

Ich finde das so wie's standardisiert ist eine unnötige Einschränkung, die einige Anwendungsfälle erheblich stört oder gar verhindert.

Das Splice das Du da jetzt gepostet hat, hat aber lineare Laufzeit... es berechnet die Größe ja gleich mit.

[CStoll]

Jester schrieb:

CStoll schrieb:

Ja, du brauchst für Splice beide Listen (und Konstruktionen wie l1.splice(p,l2,l3.begin()); sind auch undefiniert). Das hat halt den Vorteil, daß du sehr schnell Elemente zwischen verschiedenen Listen umhängen kannst.

Das könnte man aber auch, wenn man nur Iteratoren hätte ohne zu wissen in welchen Listen die Dinger konkret rumhängen. Ich hätte gern ein freies splice:

// hängt die Liste [start, end) vor pos in die Liste ein, in der sich pos befindet.
void splice(Iterator start, Iterator end, Iterator pos);
Ich finde das so wie's standardisiert ist eine unnötige Einschränkung, die einige Anwendungsfälle erheblich stört oder gar verhindert.

Das war wohl eine Entscheidung zwischen Aufwand und einfacher Umsetzung.

(außerdem: Ein Iterator kann normalerweise nicht in die zugeordnete Datenstruktur eingreifen, das ist eine Angelegenheit des Containers - du hast ja auch kein globales void insert(Iterator pos, Iterator::value_type val); , sondern nur entsprechende Methoden der Container)

Das Splice das Du da jetzt gepostet hat, hat aber lineare Laufzeit... es berechnet die Größe ja gleich mit.

Stimmt, das hat lineare Laufzeit. Aber irgendeine Einschränkung hast du immer.

[Jester]

CStoll schrieb:

Stimmt, das hat lineare Laufzeit. Aber irgendeine Einschränkung hast du immer.

ja und imho die falsche. Wen interessiert schon die Größe einer Liste?

Vielleicht hab ich mich auch unklar ausgedrückt: mir ist schon klar wofür man eine liste gebrauchen kann (und in welchen Situationen). Aber ich sehe nicht, dass std::list diese Anforderungen erfüllen kann, weil es eben heftige Einschränkungen im Interface macht, die die Klasse für die spannenden Fälle nutzlos machen.

[CStoll]

Jester schrieb:

CStoll schrieb:

Stimmt, das hat lineare Laufzeit. Aber irgendeine Einschränkung hast du immer.

ja und imho die falsche. Wen interessiert schon die Größe einer Liste?

dich anscheinend nicht.

Vielleicht hab ich mich auch unklar ausgedrückt: mir ist schon klar wofür man eine liste gebrauchen kann (und in welchen Situationen). Aber ich sehe nicht, dass std::list diese Anforderungen erfüllen kann, weil es eben heftige Einschränkungen im Interface macht, die die Klasse für die spannenden Fälle nutzlos machen.

Wenn du mit der vorhandenen std::list<> unzufrieden bist, kannst du dir gerne eine eigene Listenklasse aufbauen, die genau deine Wünsche erfüllt Und das Gute daran ist, daß du die vorhandenen STL-Algorithmen problemlos mit deiner Liste zusammenarbeiten lassen kannst.

[Jester]

CStoll schrieb:

Wenn du mit der vorhandenen std::list<> unzufrieden bist, kannst du dir gerne eine eigene Listenklasse aufbauen, die genau deine Wünsche erfüllt Und das Gute daran ist, daß du die vorhandenen STL-Algorithmen problemlos mit deiner Liste zusammenarbeiten lassen kannst.

ich klinke mich dann mal aus der folgenden C++-Werbesendung aus... Es ist echt unglaublich.

Aber eine Frage sei mir noch gestattet: wieviele Listen hast Du schon als Hilfsdatenstrukturen eingesetzt?

Und nebenbei bemerkt: die MSVC-Implementierung würde einem meiner Algorithmen von linearer zu quadratischer Laufzeit verhelfen... richtig tolles Ding.

[CStoll]

Jester schrieb:

ich klinke mich dann mal aus der folgenden C++-Werbesendung aus... Es ist echt unglaublich.

Mach doch, was du denkst.

Aber eine Frage sei mir noch gestattet: wieviele Listen hast Du schon als Hilfsdatenstrukturen eingesetzt?

Bislang noch nicht viele - das liegt aber daran, daß ich meistens andere Anforderungen an meine Hilfsstrukturen habe (z.B. direkter Indexzugriff (vector) oder Sortierung (set/map)).

Und nebenbei bemerkt: die MSVC-Implementierung würde einem meiner Algorithmen von linearer zu quadratischer Laufzeit verhelfen... richtig tolles Ding.

Nur aus Interesse: Was ist denn das für ein Algorithmus?