Wieso Iteratoren statt Zeigern oder statt Indizes?

[Tachyon]

Eisflamme schrieb:

Wie war das mit Operatoren nur intuitiv überladen?

Wenn man Pipes kennt, ist das sehr intuitiv.

[Eisflamme]

Mach mich nur fertig. ^^

Aber ist | in C++ standardmäßig als Pipe-Operator gedacht? Es geht doch um die Intuitivität eines C++-Operators in dem, was man darunter normalerweise versteht. Und | ist für mich XOR oder Flags verknüpfen.

[Tachyon]

Eisflamme schrieb:

Mach mich nur fertig. ^^

Aber ist | in C++ standardmäßig als Pipe-Operator gedacht? Es geht doch um die Intuitivität eines C++-Operators in dem, was man darunter normalerweise versteht. Und | ist für mich XOR oder Flags verknüpfen.

Nein, standardmäßig nicht. Aber auch nicht als XOR. Trotzdem finde ich das jetzt nicht sonderlich unübersichtlich. Vielleicht hätte man da operator>> nehmen sollen. Aber wie gesagt: Ich finde die Pipe-Idee jetzt nicht so verwerflich.

[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.