Minimum und Maximum finden

wob

Hallo,

ich möchte gerne in einem std::vector<MyClass> das Minimum und Maximum finden. Der vector enthält Elemente einer eigenen Klasse MyClass und ich möchte min und max der Funktion calulateValue finden. Dabei ist calulateValue nicht trivial, also kein getter, sondern schon eine Funktion mit etwas Rechenwaufwand. Und da ich in einer Schleife häufig min und max finden muss, summiert sich die Rechenzeit durch unnötige Berechnungen doch schon etwas.

Also, zur Frage: wie gehe ich am besten vor? Aktuell habe ich eine eigene Schleife (in eine Funktion gewrappt):

std::vector<MyClass> v;
...
assert(!v.empty());
auto min = v[0].calulateValue();
auto max = min;
for (size_t i = 1; i < v.size(); ++i) {
  auto val = v[i].calulateValue();
  if (val > max) max = val;
  if (val < min) min = val;
}

Das würde ich eigentlich gern durch std::minmax_element ersetzen. Aber in dem Fall müsste ich in der Vergleichsfunktion jeweils 2 x calculateValue aufrufen und am Ende, wenn ich die Iteratoren zurückbekommen, nochmal. D.h. doppelt so oft wie in der eigenen Loop.

Andere Alternative: neuen vector<double> erzeugen und mit std::transform die calculateValue-Werte da reinschreiben. Aber da frage ich mich: wozu erst einen vector erzeugen?

Wie macht man sowas "in schön"? Oder bleibt mir nichts anderes übrig, als einen neuen Algorithmus zu erstellen? Sowas wie:

template<typename It, typename F>
auto minmax_value(It beg, It end, F f) {
  auto min = f(*beg);
  auto max = min;
  while (++beg != end) {
    auto val = f(*beg);
    if (val > max) max = val;
    if (val < min) min = val; 
  }
  return std::make_pair(min, max);
}

Edit: Bonusfragen:
a) was soll man machen, wenn beg==end? assert(beg!=end) ? Oder (NAN, NAN) zurückgeben? Nur dann würde man sich ja auf den return-Type pair<double,double> festlegen.

b) Wie behandle ich hier sinnvoll NANs oder eher: sollte ich mich überhaupt um NANs kümmern? Sobald ich davon ausgehe, dass es NANs gibt, ist das ja nicht mehr 100% generisch. Oder alternativ eine zusätzliche Funktion minmax_value_ignore_nan ?

Kann man sich das Ergebnis der Berechnung merken?

class MyClass
{
  std::optional<double> myValue;

public:
  double calulateValue()
  {
     if(!myValue.has_value()) myValue = really_calulateValue();
     return myValue.value();
  }

Finnegan

Eine Möglichkeit wäre, dafür zu sorgen dass sich der Anwender von MyClass "per Default" keinen Kopf darum machen muss, ob er nun eine kostspielige Funktion aufruft, oder nicht:

class MyClass
{

    public:
        ...

        void setSomething(...);
        {
            ...
            needs_recalculation = true;
        }

        void calculateValue()
        {
            ...
            needs_recalculation = false;
        }

        double getValue()
        {
            if (needs_recalculation)
                calculateValue();
            return calculated_value;
        }

    private:
        bool needs_recalculation;
        double calculated_value;
}

Schliesslich weiss MyClass , bzw. deren Autor am besten, was "unter der Haube" in den Methoden passiert. Für die nicht-Standardfälle kann man calculateValue() eben öffentlich machen, so dass der Anwender bei Bedarf gezielt eine Berechnung anstossen kann. Es ist sicher nicht verkehrt so einen Algorithmus wie den von dir vorgeschlagenen in der Sammlung zu haben, allerdings benötigt man so eine intimere Kenntnis der Klasse und das Wissen um diesen Algorithmus um effizienten Code zu schreiben - das Zwischenspeichern ist automatisch effizient (wenn auch nur für wirklich teure Berechnungen sinnvoll).

Edit: Hehe, da hatten wir wohl den selben Gedanken. std::optional<> find ich gut, nicht so viele Variablen.

wob

Hm...

MyClass ist in diesem Falls ThridPartyLibraryClass , sodass ich das Verhalten ungern ändern würden.

Und wozu Tausende von Werten cachen? Nur einen Cache einzubauen, weil man einmal das Maximum bestimmen will, halte ich für nicht zielführend. Die Funktion ist selbst auch nur mäßig teuer, sie wird erst in Verbindung mit richtig vielen Aufrufen spürbar.

Ich möchte nicht proaktiv jede Funktion, für die ich irgendwann vielleicht mal ein Maximum berechnen möchte, cachen müssen, nur damit ein "dummer" Algorithmus damit klarkommt.

Wie macht man sowas "in schön"? Oder bleibt mir nichts anderes übrig, als einen neuen Algorithmus zu erstellen? Sowas wie:

Ist ok. Allerdings sollte aus dem Namen der Funktion hervorgehen, dass die Funktion eine Transformation der Werte vornimmt, das versteht sich nicht von selbst. Geht im Prinzip natürlich auch mit std::minmax_element und einem transformierenden Iterator. Ist das eleganter? Eher nicht.

wob schrieb:

b) Wie behandle ich hier sinnvoll NANs oder eher: sollte ich mich überhaupt um NANs kümmern? Sobald ich davon ausgehe, dass es NANs gibt, ist das ja nicht mehr 100% generisch. Oder alternativ eine zusätzliche Funktion minmax_value_ignore_nan ?

Wüsste nicht, warum du dich darum kümmern solltest. NaN hat in Datensätzen erst einmal nichts zu suchen. Anders sähe es vielleicht aus, wenn du mit unvollständigen, sehr löchrigen Datensätzen arbeitest. Aber dann brauchst du gleich einen ganzen Satz neuer Algorithmen, denn std::accumulate usw. scheren sich auch nicht um NaN.
Aber eine Spezialbehandlungen für Fließkommazahlen ist davon abgesehen natürlich immer möglich. Altmodisch mit Templatespezialisierungen, neumodisch mit if constexpr.

DNKpp

Imo ist es doch eher ungewöhnlich eine teure public Funktion zu haben, die gar keine Parameter erwartet. In diesem Fall wäre es wahrscheinlich wirklich das beste zu cachen. Andererseits möchtest du das verhalten der Klasse ja nicht ändern. In solchen Fällen greife ich dann eigentlich immer auf ein transform zurück. Das ganze ist trivial, so lange es sich um einen sequenziellen container handelt. Für map und set wird das natürlich etwas aufwändiger (itr/value oder key/value pairs).