std::distance und size()

[happystudent]

Hallo,

angenommen ich will eine Funktion schreiben die unter anderem die Größe eines Containers braucht, etwa eine Mittelwert Funktion. Diese würde ich ungefähr folgendermaßen implementieren:

template <typename iter> auto mean(iter start_, iter end_) -> typename std::remove_reference<decltype(*start_)>::type
{
	typedef typename std::remove_reference<decltype(*start_)>::type T;
	return std::accumulate(start_, end_, T(0))/std::distance(start_, end_);
}

Meine Bedenken bei diesem Code beziehen sich auf das std::distance .

Dieses hat laut Doku nur für Random-Access Iteratoren eine konstante Laufzeit. Wenn ich jetzt also Iteratoren einer std::list übergeben würde, würde ich Performance verschwenden. Denn nach hier hat std::list nur bidirectional Iteratoren, während der .size() Zugriff bei list laut dieser Quelle konstant ist ab C++11.

Das heißt, mit .size() wäre die Funktion wesentlich effizienter als mit std::distance , allerdings kann ich das ja nicht mit Iteratoren verwenden. Die Mittelwert Funktion wäre also nicht für jeden Container optimal, die Abstraktion würde Overhead verursachen.

Wie könnte man das verbessern? Selbst wenn ich einen Container als Template übergeben würde und keine Iteratoren (was an sich schon eine schlechte Lösung wäre), gäbe es das zusätzliche Problem dass kein std::size (in Anlehnung an std::begin ) existiert.

Ein Dilemma?

[icarus2]

An der Laufzeitkomplexität ändert sich natürlich nichts, ist beides $\mathcal{O}(n)$. Aber die Liste muss zwei Mal durchlaufen werden was natürlich einen gewissen Overhead mit sich bringt (wobei man beachten muss dass es - im Gegesatz zu Arrays - onehin grauenhaft langsam ist eine verkettete Liste zu durchlaufen).

Die einfachste Lösung, die mir einfällt, ist auf std::accumulate zu verzichten und selber mit einer for-Schleife und einem counter durchzulafen:

counter = 0;
for ( iter it = start_; it != end_; ++it, ++counter )
{
  // sum up
}

Am Ende der for-Schleife hast du die Anzahl Elemente dann in counter gespeichert und brauchst kein std::distance mehr.

[TNA]

Ich denke wenn du auf ganzen Containern arbeiten willst ist die Übergabe eines Containers ok. Wenn du aber einen Algorithmus erstellen will der auf beliebigen Iteratorpaaren funktioniert, nützt dir der size-Aufruf eh nichts, da es ja z.B. auch nur ein Teil einer Liste sein könnte.

[happystudent]

icarus2 schrieb:

Die einfachste Lösung, die mir einfällt, ist auf std::accumulate zu verzichten und selber mit einer for-Schleife und einem counter durchzulafen:

Hm Ok, dann werd ichs wohl so machen.

Wollte halt std::accumulate verwenden weil das anscheinend noch irgendwelche internen Optimierungen durchführt die sich mir nicht so ganz erschließen (siehe hier). Wäre vielleicht ganz gut wenn die ne Überladung dafür schreiben würden die ne counter-Referenz oder so nimmt...

[TNA]

happystudent schrieb:

Wäre vielleicht ganz gut wenn die ne Überladung dafür schreiben würden die ne counter-Referenz oder so nimmt...

Es gibt eine Überladung die eine "Binary Operation" nimmt. Da könntest du deinen Counter einbauen, aber ob es den Aufwand wert ist weiß ich nicht.

[mean_user]

mean ist kein besonders gutes Beispiel für eine generische Funktion.

std::vector<int> v{1,2};
double m = mean(begin(v), end(v));
assert(m == 1.5); // fail!

Wenn du es doch selber schreibst: www.boost.org/libs/iterator/doc/counting_iterator.html + std::accumulate/boost::accumulate mit Lamba

[icarus2]

mean_user schrieb:

assert(m == 1.5); // fail!

Der grösste Fail ist dieser Vergleich

[happystudent]

mean_user schrieb:

mean ist kein besonders gutes Beispiel für eine generische Funktion.

std::vector<int> v{1,2};
double m = mean(begin(v), end(v));
assert(m == 1.5); // fail!

Ja und, warum soll das jetzt irgendwie schlecht sein?

Ist doch klar dass wenn du ints aufaddierst und dann teilst keinen korrekten double Wert kriegst. Generisch heißt doch nicht dass ein Typ (bzw. Ergebnis) beliebig konvertierbar sein muss.

Meiner Meinung nach ist das ein perfektes Beispiel für eine generische Funktion, da sie sowohl den Typen als auch den Container weg abstrahiert, und zwar automatisch und nicht wie etwa std::accumulate durch einen nervigen extra Parameter.

[Kellerautomat]

Uebergib accumulate halt ne Lambda:

T count = 0;
return accumulate(s, e, T(0), [&](T a, T b){ ++count; return a + b; }) / count;

[icarus2]

*Edit
Hier stand völliger Unsinn.

[UB]

Kellerautomat schrieb:

Uebergib accumulate halt ne Lambda:

T count = 0;
return accumulate(s, e, T(0), [&](T a, T b){ ++count; return a + b; }) / count;

Öhm...

[volkard]

happystudent schrieb:

Wollte halt std::accumulate verwenden weil das anscheinend noch irgendwelche internen Optimierungen durchführt die sich mir nicht so ganz erschließen (siehe hier).

Ha??

Kellerautomat schrieb:

lamda

Keine gute Idee, falls accumulate unerschließliche Optimierungen machen darf.

[Kellerautomat]

UB schrieb:

Kellerautomat schrieb:

Uebergib accumulate halt ne Lambda:

T count = 0;
return accumulate(s, e, T(0), [&](T a, T b){ ++count; return a + b; }) / count;

Öhm...

Speicher es halt in ne Variable und gib dann sum / count zurueck. Kommt doch aufs selbe raus

[icarus2]

Man könnte mal so etwas probieren (habs nicht gross getestet, ist nur so hingeklatscht, um die Idee zu geben):

template <typename Iter>
double mean(Iter first, Iter last)
{
    auto accumulator = [](std::pair<double,size_t> p, double val) { p.first += val; ++p.second; return p; };
    auto acc_pair = std::accumulate(first, last, std::make_pair(0.0, 0), accumulator);
    return acc_pair.first / acc_pair.second;
}

Bringt aber auch einen Overhead mit, den man wahrscheidlich vermeiden möchte.

Bin mir auch nicht ganz sicher ob das wirklich funktioniert mit den Optimierungen, die std::accumulate verwendet. Wenns falsch ist wirds bestimmt gleich gesagt

[overheadprojector]

icarus2 schrieb:

Bringt aber auch einen Overhead mit, den man wahrscheidlich vermeiden möchte.

Und zwar welchen Overhead ausser dem Hardcoden von double?

[happystudent]

volkard schrieb:

Ha??

Naja, das war doch der Konsens des Threads oder? Zumindest hatte ich das so verstanden:

SeppJ schrieb:

Wenn du nun sagst, dass dein Iterator mehr kann, dann merkt das accumulate das und wählt eine entsprechend raffiniertere Implementierung, die dies ausnutzt. Wenn dein Iterator dann aber deine Versprechen nicht halten kann, kommt es zum beobachteten Fehler.

Also irgendeinen Grund muss es ja geben dass std::accumulate den operator< braucht und damit von dieser Referenz-Implementierung dahingehend abweicht.

Das mit dem lambda werd ich mal austesten, bin ich nicht selbst drauf gekommen^^

[Nathan]

volkard schrieb:

Kellerautomat schrieb:

lamda

Keine gute Idee, falls accumulate unerschließliche Optimierungen machen darf.

Darf es nicht (mehr):

§26.7.2 Accumulate schrieb:

Effects:
Computes its result by initializing the accumulator acc
with the initial value init and then modifies it with acc = acc + *i or acc = binary_op(acc, *i) for every iterator i in the range [first,last) in order.

[happystudent]

Nathan schrieb:

Darf es nicht (mehr):

Ok, also auf gut deutsch es würde eh keinen Unterschied machen ob std::accumulate oder selbstgebaute Schleife? Weil dann könnte man sich den Stress ja eh sparen^^