Wieso Iteratoren statt Zeigern oder statt Indizes?

ipsec

Dann verknüpfst du halt die Range mit einem Strided-Flag. Ist m.E. auch intuitiv.
Zumindest ist es intuitiv genug, dass man beim ersten Blick erahnen kann, was passiert und es nach dem zweiten Blick in die Doku nicht mehr vergisst. Das ist m.E. ausreichend.

Eisflamme

Hm... nach der Definition könnte man viel Unsinn treiben, glaube ich. Aber ich schweige dazu stille, bis ich bessere Argumente habe oder vollends überzeugt bin.

volkard

Tachyon schrieb:

Ich finde die Pipe-Idee jetzt nicht so verwerflich.

Man hat sich dran gewöhnt. Ist halt typisch boost. Verspielte Lösung mit vielen neuen nur für diese eine sub-lib benötigten Begriffen und kaum Mehrwert. Hier möglicherweise sogar mal Null Mehrwert, also ich kann mich geade nicht daran erinnern, daß ich mal jeden zweiten Wert gebraucht hätte.

Tachyon

volkard schrieb:

Tachyon schrieb:

Ich finde die Pipe-Idee jetzt nicht so verwerflich.

Man hat sich dran gewöhnt. Ist halt typisch boost. Verspielte Lösung mit vielen neuen nur für diese eine sub-lib benötigten Begriffen und kaum Mehrwert. Hier möglicherweise sogar mal Null Mehrwert, also ich kann mich geade nicht daran erinnern, daß ich mal jeden zweiten Wert gebraucht hätte.

Ich brauche es ständig. Sogar an Stellen, an denen es schnell gehen muss. So unterschiedlich können die Bedürfnisse sein. Man glaubt es kaum.

volkard

Tachyon schrieb:

volkard schrieb:

Tachyon schrieb:

Ich finde die Pipe-Idee jetzt nicht so verwerflich.

Man hat sich dran gewöhnt. Ist halt typisch boost. Verspielte Lösung mit vielen neuen nur für diese eine sub-lib benötigten Begriffen und kaum Mehrwert. Hier möglicherweise sogar mal Null Mehrwert, also ich kann mich geade nicht daran erinnern, daß ich mal jeden zweiten Wert gebraucht hätte.

Ich brauche es ständig. Sogar an Stellen, an denen es schnell gehen muss. So unterschiedlich können die Bedürfnisse sein. Man glaubt es kaum.

Speicherst Du key/value-Paare in Arrays mit keys an gerade-zahligen Indizes und values an den ungeraden?

Tachyon

volkard schrieb:

Speicherst Du key/value-Paare in Arrays mit keys an gerade-zahligen Indizes und values an den ungeraden?

Nein. Ich multipliziere jeden n-ten Wert mit einem passenden Koeffizienten, um ein ganzzahliges Upsampling zu erreichen. Nur so als Beispiel.

volkard

Tachyon schrieb:

Nein. Ich multipliziere jeden n-ten Wert mit einem passenden Koeffizienten, um ein ganzzahliges Upsampling zu erreichen. Nur so als Beispiel.

Verstehe ich nicht.
Wenn ich http://de.wikipedia.org/wiki/Upsampling anschaue, wo nehmen die jeden n-ten Wert?
Wie sähe so ein Upsampling wie auf Wikipedia gezeigt, mit den Boost-Pipes aus?

Tachyon

volkard schrieb:

Wenn ich http://de.wikipedia.org/wiki/Upsampling anschaue, wo nehmen die jeden n-ten Wert?

Ich stimmte Dir zu. Der Mehrwert der Multplikationen mit Null ist gigantisch. Ich ändere mal und mutlipliziere doch jeden Wert. Den Code für die Range basierte Faltung packe ich jetzt nicht hier ins Forum. Aber ich bin zuversichtlich, dass Du das auch selbst hinbekommst.

volkard

Tachyon schrieb:

Ich stimmte Dir zu. Der Mehrwert der Multplikationen mit Null ist gigantisch. Ich ändere mal und mutlipliziere doch jeden Wert.

Aha!
Statt erst std::copy und dann std::transform kann man mit Expression Templates beide verbinden und nur einmal laufen, was gut für die lahmen Ram-Zugriffe ist. Der Vorteil liegt nicht in der seltsamen Syntax, sondern sie ist Folge des Bemühens umd mehr Compilzeitlogik. Sag das doch gleich.

Tachyon

volkard schrieb:

Tachyon schrieb:

Ich stimmte Dir zu. Der Mehrwert der Multplikationen mit Null ist gigantisch. Ich ändere mal und mutlipliziere doch jeden Wert.

Aha!
Statt erst std::copy und dann std::transform kann man mit Expression Templates beide verbinden und nur einmal laufen, was gut für die lahmen Ram-Zugriffe ist. Der Vorteil liegt nicht in der seltsamen Syntax, sondern sie ist Folge des Bemühens umd mehr Compilzeitlogik. Sag das doch gleich.

Naja, man spart sich Mutliplikationen und Dereferenzierungen. Zusätzliches Kopieren ist auch ziemlich übeflüssig, weil man das in einem Rutsch machen kann. Würdest Du wirklich echt nullen einfügen? Ehrlich jetzt?

volkard

Tachyon schrieb:

Würdest Du wirklich echt nullen einfügen? Ehrlich jetzt?

Ich kenne die Aufgabe nicht. Wenn sich Nullen-Einfügen lahm anfühlt, würde ich es wohl nicht machen.

Tachyon

volkard schrieb:

Tachyon schrieb:

Würdest Du wirklich echt nullen einfügen? Ehrlich jetzt?

Ich kenne die Aufgabe nicht. Wenn sich Nullen-Einfügen lahm anfühlt, würde ich es wohl nicht machen.

Es ist genau das Upsampling wie bei Wikepedia beschrieben. Nur muss man es nicht auf die Brute-Force-Methode implementieren. Man bekommt das deutlich besser hin, ohne die vorhandene Flexibilität zu verlieren.
Anstatt n Nullen enzufügen kannst Du auch jeden n-ten Koeffizienten multiplizieren und die resultierende Summe gleich in den Zielvektor schreiben. Das spart tatsächlich erstaunlich viel Zeit. Du sparst Dir nicht nur Kopiererei sondern auch Dereferenzierungen und Multiplikationen, wie gesagt.

volkard

Tachyon schrieb:

volkard schrieb:

Tachyon schrieb:

Würdest Du wirklich echt nullen einfügen? Ehrlich jetzt?

Ich kenne die Aufgabe nicht. Wenn sich Nullen-Einfügen lahm anfühlt, würde ich es wohl nicht machen.

Es ist genau das Upsampling wie bei Wikepedia beschrieben. Nur muss man es nicht auf die Brute-Force-Methode implementieren. Man bekommt das deutlich besser hin, ohne die vorhandene Flexibilität zu verlieren.
Anstatt n Nullen enzufügen kannst Du auch jeden n-ten Koeffizienten multiplizieren und die resultierende Summe gleich in den Zielvektor schreiben. Das spart tatsächlich erstaunlich viel Zeit. Du sparst Dir nicht nur Kopiererei sondern auch Dereferenzierungen und Multiplikationen, wie gesagt.

Das sagt mir leider gar nichts. Bin weiter neugierig, wie das mit den Pipes aussieht. Falls es mir tatsächlich gelingen sollte, den Code zu verstehen, würde ich mir überlegen können, ob er sich ohne Pipes auch hübsch anfühlen würde.

Ich würde wohl keine Nullen einfügen, um sie gleich darauf wieder durch richtige Werte zu ersetzen. Nur weiß ich gar nicht, wie man die richtigen Werte berechnet.

edit: Alles zurück. Hast recht. Für Signalverarbeitung würde ich auch so vorgehen.

Tachyon

Ich bin mir nicht so sicher, ob es eine gute Idee ist, den Code hier zu posten, da es für meinen Arbeitgeber ist. Der ist normalerweise nicht so glücklich, wenn man irgendwelche Produktivcode ins Netz packt. Das hat nichtmal was damit zu tun, dass das nun so großartig speziell ist. Ist es nicht.
Grundsätzlich geht es so, dass Du jeden n-ten Koeffizienten pro Faltung multiplizierst. Der Index für den Datenvektor (also das, was hochgetastet werden soll) geht alle n Faltungen eins weiter, wobei n die Anzahl der virtuell eingefügten Nullen ist. Innerhalb Deiner Koeffizienten hast Du außerdem noch einen Offset, der von der Position der aktuell indizierten virtuellen Null abhängig ist. Mit mit den slice- und stride Adaptoren kann man sich dann die passenden Koeffizienten rauspicken. Geht natürlich auch ohne von Hand, aber mit den Adaptoren ist das relativ einfach.
Mal es Dir vielleicht einfach mal auf ein Blatt Papier (mit echten Nullen) und schiebe ein Filter an den Daten vorbei. Dabei begucke Dir, welche Koeffizienten mit Werten ungleich null multipliziert werden. Dabei sollte das Prinzip theoretisch klar werden.

krümelkacker

Tachyon schrieb:

Naja, im Prinzip hast Du das doch mit boost.range . Inzwischen gibt es da sogar die Adaptoren (seit 1.44, glaube ich) mit denen man ein paar zusätzliche nette Konzepte bekommt:
[...]

Ich muss gestehen, dass ich mich bisher nicht allzu intensiv mit Boost.Range auseinander gesetzt habe. Mir ist nur der Unterschied aufgefallen, dass das Boost-Konzept einer "Range" keine Kopiersemantik beinhaltet. Auf der einen Seite ist das praktisch, da man so die Grenzen zwischen Iterator-artigen Ranges (Referenzsemantik) und Container-artigen Ranges (Wertesemantik) vermischen kann. Auf der anderen Seite ist das natürlich auch ein Nachteill -- würd eich zumindest vermuten. Da find ich Andreis Ansatz schon okay (Referenzsemantik so wie bei Iteratoren).

Ich könnte mir aber auch vorstellen, dass es Spezialisierungen des Range-Konzepts gibt bzgl Kopiersemantik, die man dann per traits-Klasse abfragen kann. Müsste ich mal wieder Reingucken, in die Doku...

Gruß,
kk

krümelkacker

krümelkacker schrieb:

Tachyon schrieb:

Naja, im Prinzip hast Du das doch mit boost.range . Inzwischen gibt es da sogar die Adaptoren (seit 1.44, glaube ich) mit denen man ein paar zusätzliche nette Konzepte bekommt:
[...]

Ich muss gestehen, dass ich mich bisher nicht allzu intensiv mit Boost.Range auseinander gesetzt habe. Mir ist nur der Unterschied aufgefallen, dass das Boost-Konzept einer "Range" keine Kopiersemantik beinhaltet.
...

Ah, und natürlich gibt es beim Boost-Range-Konzepr wieder Iteratoren. Andrei's Ansatz verzichtet auf Iteratoren (daher auch "iterators must go" als Titel seiner Präsentation). Und das hat die Sache IMHO interessant gemacht.

ipsec

krümelkacker schrieb:

Ah, und natürlich gibt es beim Boost-Range-Konzepr wieder Iteratoren. Andrei's Ansatz verzichtet auf Iteratoren (daher auch "iterators must go" als Titel seiner Präsentation). Und das hat die Sache IMHO interessant gemacht.

Du hast Recht, das ist eine sehr interessante Sache mit sehr interessanten Beispielen. Wie ich das sehe, sind diese Ranges aber nicht in der Lage, Iteratoren vollständig oder vollständig elegant zu ersetzen. Nämlich immer dann, wenn ich mit Iteratoren nicht einen Bereich, sondern nur eine Position angeben will.

Das Beispiel mit find hat Andrei schon benutzt. Hier hat er fix den Rückgabewert von Iterator auf gefundenes Element zu Range von gefundenen Element bis Ende geändert. Das mag in den meisten Anwendungen ausreichend oder genau richtig sein, ist aber schon irgendwie willkürlich. Nehmen wir an, ich wöllte die Range vom Beginn bis zum gefundenen Element. Mit Iteratoren einfach, ich merke mir den Anfangs-Iterator. Auch mit Boost.Range einfach, das kapselt ja auch nur Iteratoren. Aber bei Andrei? Ich sehe jetzt nicht, wie man unter der Voraussetzung find einfach implementieren könnte, die Ranges sind hier einfach zu starr.

Nehmen wir unique . Hier wäre es es wirklich sinnvoll, eine Range von Beginn bis gefundenen Iterator zu haben, damit ich darauf weiter arbeiten kann. Das geht also schonmal nicht. Aber nehmen wir die Implementeirung von unique an sich. Fällt dir spontan ein, wie man die recht einfache Impementierung von http://www.cplusplus.com/reference/algorithm/unique/ auf Ranges übertragen könnte? Ich hänge mich da gerade am result -Iterator auf. Oder hast du stattdessen eine ähnlich einfache rangespezifische Implementierung?
Edit: Ok, man kann am Anfang die Range kopieren und dann mit beiden Ranges arbeiten. Zwar etwas erhöhter Speicherbedarf, aber akzeptabel. Vergiss also den Punkt.

Betrachten wir die Conatiner-Funktion erase . Die könnte man mit Ranges so formulieren, dass sie den zu löschenden Bereich übernimmt. Dadurch spart man sich sogar beide Overloads. Nun möchte ich aber das zweite Element löschen. Wie bekomme ich schnell und einfach eine Range, die nur das zweite Element enthält? Bei Iteratoren müsste ich nur den Beginn-Iterator inkrementieren.

Noch schlimmer wirds bei insert . Ich brauche einen Iterarator für die Einfügeposition. Wie soll man das logisch durch eine Range darstellen? Alles, was mir jetzt so einfiehle (z.B. Range von Einfügeposition bis irgendwohin) ist pure Willkür.

Außerdem sind Ranges, wenn man sie denn mal hat, toll, aber beim Erstellen sind sie zu unflexibel. Ich möchte z.B. mal angenommen aus einer Range eine kleinere Range "ausschneiden", erhalte also 2 Ranges, die vor bzw. hinter der ausgeschnittenen Range liegen. Mit Iteratoren kein Problem und praktisch kostenlos, egal welcher Iteratortyp. Aber mit Ranges? Und ich bin sicher, ähnliche Beispiele lassen sich manche finden. Die Container müssten dafür alle eigene Funktionen anbieten, weil nur sie Zugriff auf die rangeinternen Beginn- und End-Zeiger bzw. -Iteratoren haben und alle generischen Algorithmen nicht. Denn da sind wir auch schon beim letzten Punkt. Bei der compilerspezifischen Rangeimplementierung braucht man wieder Iteratoren, die Anfang und Ende der Range markieren. Das können auch Zeiger sein, man muss sie z.B. nicht inkrementieren können, aber eigentlich ist es das Gleiche. Und wenn das so ist, brauch man diese auch nicht in der Range zu verstecken und das Konzept als genial neu verkaufen, sondern kann sie gleich öffentlich machen und erschenkt sich damit sehr viel Flexibilität.

Zusammengefasst finde ich die Ranges sehr interessant, ich befürworte auch sehr, statt 2 Iteratoren nur noch eine Range haben zu müssen. Am Ende sind die Ranges aber zu unfexibel, wenn man nicht doch wieder Iteratoren benutzt. Deshalb finde ich Ansätze wie Boost.Range bessser.

krümelkacker

Tja, keine Ahnung. Angeblich hätte er all die Funktionalitäten der C++ STL mit "seinen Ranges" nachgebaut.

Ich könnte mir vorstellen, dass er dazu auch Operationen anbietet, die aus zwei Ranges, die eine gemeinsame Grenze haben, eine neue erzeugt. Beispiel:

|-range1-----------|
                |-range2-|
-->
      |-range3--|

("XOR")

Dann könntest Du in deinem find-Beispiel schreiben

auto range3 = allof(numbers) ^ find(allof(numbers),42);

unique könnte man ja ähnlich wie in C++ implementieren:

template<class ForwardRange>
ForwardRange unique(ForwardRange rng)
{
  if (rng.empty()) return rng;
  ForwardRange result = rng;
  for (;;) {
    rng.pop_front();
    if (rng.empty()) break;
    if (!(rng.front()==result.front())) {
      result.pop_front();
      result.front() = rng.front();
    }
  }
  result.pop_front();
  return result;
}

Falls ich da jetzt keine Fehler gemacht habe, liefert unique eine Range für die Elemente zurück, die man dann direkt per container.erase(...) löschen kann, also

vector<int> numbers = ...;
sort( allof(numbers) );
numbers.erase( unique(allof(numbers)) );

Mit der xor-Funktion kann man sich aber auch eine andere range basteln:

vector<int> numbers = ...;
sort( allof(numbers) );
show( allof(numbers) ^ unique(allof(numbers)) );

(entsprechende Funktionen erase,sort,show vorausgesetzt)

insert fügt in C++ ja das Element vor dem Element ein, auf das der Iterator zeigt. Das lässt sich genauso übertragen. container.insert(range,42) würde dann die 42 vor der range einfügen. So gesehen ist ein Iterator nur ein Spezialfall einer Range mit einem oder keinem Element. Der Unterschied: Ein Iterator weiß nicht, ob er gültig ist (oder der end-Iterator ist), wobei eine Range weiß, ob sie leer ist. Aus Sicherheitsgründen kann man Ranges auch nur verkleinern (pop_front, pop_back). Und trotzdem scheint man alles damit machen zu können. Wie so etwas ohne so ein Range-XOR gehen soll, weiß ich allerdings auch nicht. Ich schätze, dass das schon notwendig ist.

Mal überlegen, ob ich die Zahl der Operationen auf Ranges möglichst klein kriege, ohne dass sie damit weniger mächtig werden als Iteratoren:

Signatur                                  Bedingung(en)
------------------------------------------------------------------------
allof : container c --> range r
empty : range x --> bool b
pop_front : range x --> range y           !empty(x)
pop_back : bidi_range x --> bidi_range y  !empty(x)
front : range x --> T&                    !empty(x)
back : bidi_range x --> T&                !empty(x)
size : range x --> int i                  x ist "endlich"
at : (ra_range x, index i) --> T&         0 <= i,
                                          x ist unendlich oder i<size(x)

xor : (range x, range y) --> range z      x und y haben eine gemeinsame Grenze
  (liefert eine dritte Range z, die die Elemente umfasst,
   welche nur entweder in x oder in y enthalten sind.)

Kommt man damit aus?

Leider finde ich die D-Implementierung seiner Container/Range Bibliothek nicht auf Anhieb.

volkard

krümelkacker schrieb:

Ich könnte mir vorstellen, dass er dazu auch Operationen anbietet, die aus zwei Ranges, die eine gemeinsame Grenze haben, eine neue erzeugt.

Nette Idee. Ich habe zusätzlich zu den Ranges wieder Iteratoren zugelassen, weil ich zu oft Sachen wie einen Dateipuffer hatte, mit begin/readpos/end, und beide Ranges werden irgendwo gebraucht. Wichtiger als der Operator wäre überhaupt die BorderSharingDoubleRange. Gegen andere Grenzen bin ich noch nicht gestoßen, wenn ich mich recht erinnere.
Und was passiert mit Quicksort, wo wir vier Iteratoren und drei Ranges mit zwei gemeinsamen Grenzen haben? Vielleicht auch so eine Klasse machen und mal schauen, wie es sich anfühlt.

krümelkacker

volkard schrieb:

krümelkacker schrieb:

Ich könnte mir vorstellen, dass er dazu auch Operationen anbietet, die aus zwei Ranges, die eine gemeinsame Grenze haben, eine neue erzeugt.

...
Und was passiert mit Quicksort, wo wir vier Iteratoren und drei Ranges mit zwei gemeinsamen Grenzen haben?

Soweit habe ich noch nicht gedacht. Ich würde als erstes versuchen, partition zu implementieren:

template<class BidiRange, class Predicate>
BidiRange partition(BidiRange r, Predicate p);

und dann Quicksort

template<class BidiRange>
void quicksort(BidiRange r)
{
  if (r.empty() || r.size()==1) return;
  auto pivotelement = r.front();
  BidiRange t = partition(r, ...x<pivotelement... );
  quicksort(t);
  quicksort(t^r);
}

Es ist zugegebenermaßen ein Umdenken. Ich befürchte, dass man nicht drum herum kommt, einige Ranges als Iteratoren zu missbrauchen. Bei partition bräuchte ich zwei Ranges, statt zwei Iteratoren:

template<class BidiRange, class Predicate>
BidiRange partition(BidiRange r, Predicate p)
{
  BidiRange u = r; // u = "unchecked"
  // Invarianten:
  //   |----r----|
  //       |--u--|
  //   u ist in r enthalten (teilen sich ein gemeinsames Ende)
  //   r "schrumpft rechts" (die rechte Grenze wird verschoben)
  //   u "schrumpft beisdeitig"
  //   p(x) für alle x aus r^u
  for (;;) {
    while (!u.empty() &&  p(u.front()) {
      u.pop_front();
    }
    while (!u.empty() && !p(u.back()) {
      u.pop_back();
      r.pop_back();
    }
    if (!u.empty()) {
      swap( u.front(), u.back() );
      u.pop_front();
      u.pop_back();
      r.pop_back();
    } else {
      break;
    }
  }
  return r; // erste Haelfte
}

(alles ungetestet)