Effizienter Weg, um den Durchschnittswert über getrennte Teilbereiche der STL-Karte zu berechnen

Question

Ich konvertiere einen Algorithmus von C# nach C++. Ein kleiner Teil des Algorithmus besteht darin, Durchschnittswerte für bestimmte Bereiche in einem Wörterbuch zu berechnen.

Die Daten im Wörterbuch sind folgendermaßen gespeichert:

Index     Wert
1         10
3         28
290       78
1110      90

Ich muss den Durchschnittswert aller Werte mit einem Index berechnen, der kleiner als eine bestimmte Zahl ist, und aller Indexwerte, die größer als eine bestimmte Zahl sind. In C# mache ich es folgendermaßen:

if (dictionary.Where(x => x.Key < areaWidth).Count() > 0)
{
    avgValue = (int) dictionary.Where(x => x.Key < areaWidth).Average(
        x => x.Value);
}

for (var i = 0; i < line.Length; i++)
{
    if (i == areaWidth)
    {
        avgValue = -1;
        i = line.Length - areaWidth;
        var rightBorder = i - areaWidth;

        if (dictionary.Where(x => x.Key > (rightBorder)).Count() > 0)
        {
            avgValue = (int) dictionary.Where(
                x => x.Key > (rightBorder)).Average(
                                x => x.Value);
        }
    }

    if (line[i] < avgValue * 0.8)
    {
        reallyImportantValue += (avgValue - line[i]);
    }
}

Ich weiß, dass das nicht sehr effizient ist und ziemlich schlechter Code, aber ich wusste, dass ich diesen Teil des Algorithmus sowieso komplett in C++ neu schreiben müsste, also habe ich mich entschieden, es schnell und schmutzig zu implementieren.

Wie auch immer, ich portiere das jetzt nach C++ und weil es auf einer mobilen Plattform laufen wird, ist die Leistung sehr wichtig. Mit meinem begrenzten C++/STL-Wissen könnte ich die Aufgabe wahrscheinlich erledigen, aber das Ergebnis wäre wahrscheinlich viel schlechter als der C#-Code.

Also, wenn du einen guten und effizienten Weg kennst, diese Aufgabe in C++ zu erledigen, sag mir bitte Bescheid.

---

EDIT: Vielen Dank für all eure Antworten. Wie ich in meinem Post erwähnt habe, ist mein STL-Wissen begrenzt, so dass es für mich wirklich schwer ist, eine Lösung auszuwählen, besonders da es viele verschiedene Meinungen gibt. Es wäre großartig, wenn mir jemand bei der Entscheidung helfen könnte, indem er die hier geposteten Lösungen vergleicht. Um dir etwas mehr Hintergrundinformationen zu geben:

Die Funktion wird ungefähr 500 Mal mit 1000 Werten in der Map aufgerufen. Der wichtigste Aspekt ist Stabilität, Leistung ist der zweitwichtigste.

Answer 1

Angenommen, Sie verwenden eine Karte, ist die einfachste Lösung, die sortierte Natur der Schlüssel auszunutzen, wie es auch andere getan haben. Gehen Sie zunächst durch den ersten Teil der Liste, aktualisieren Sie den Akkumulator und die Anzahl. Gehen Sie dann durch den zweiten Teil der Liste und tun Sie dasselbe. Zwei Schleifen nacheinander, und Sie können die Länge des zweiten Teils aus der Länge des ersten Teils ableiten.

Sehr geradliniger Code, der bereits auf den ersten Blick klar sein sollte und keine temporären Container erstellt. Ich würde persönlich diesen Ansatz bevorzugen, aus diesen Gründen. Tatsächlich ist dies genau der Code, den ich schreiben würde, wenn ich dies selbst mit dieser Datenstruktur machen würde.

int schlüssel = ;

std::map::const_iterator it = map.begin(), end = map.end();

size_t num1 = 0;
long insgesamt1 = 0;

while (it != end && it->first < schlüssel) {
    insgesamt1 += it->second;
    ++num1;
    ++it;
}

size_t num2 = map.size() - num1;
long insgesamt2 = 0;

while (it != end) {
    insgesamt2 += it->second;
    ++it;
}

int durchschnitt_weniger = num1 > 0 ? insgesamt1 / num1 : 0;
int durchschnitt_größer_gleich = num2 > 0 ? insgesamt2 / num2 : 0;

Ich sehe keinen Sinn darin, den Enditerator für den ersten Abschnitt mit std::lower_bound zu finden, bevor Sie beginnen. Sie werden so oder so durch die Karte gehen, also könnten Sie genauso gut währenddessen überprüfen. Die Karteniteration ist nicht kostenlos und springt möglicherweise etwas im Speicher herum - im Vergleich dazu sollte der zusätzliche Vergleich bei jeder Iteration nicht spürbar sein.

(Natürlich bin ich verpflichtet zu sagen, dass Sie dies messen sollten, wenn Sie es sicher herausfinden möchten, weil Sie es sollten. Dies ist nur mein fundierter Rat zum Verhalten des optimierten Builds.)

Answer 2

Ok, hier ist mein Outline für diejenigen, die gerne accumulate verwenden, um es etwas weniger schmerzhaft zu machen. Lassen Sie uns eine Klasse namens StatsCollector erstellen. Es ist mir eigentlich egal, was darin ist, außer dass wir davon ausgehen werden, dass dies eine Klasse ist, die Sie an verschiedenen Stellen in Ihrem Code verwenden werden, um Kollektionen von Zahlen zu sammeln und Ihnen Informationen zu geben. Lassen Sie uns es locker definieren. Ich gehe davon aus, dass es Doubles als Werte annimmt, aber Sie können es auch auf Werttyp template.

class StatsCollector
{
public:
   StatsCollector();

   void add(double val);

 // einige Statistiken, die Sie vielleicht wollen
   size_t count() const;
   double mean() const;
   double variance() const;
   double skewness() const;
   double kurtosis() const;
};

Der Zweck des oben Genannten ist die Berechnung statistischer Momente aus den übergebenen Daten. Es handelt sich um eine Klasse, die nützlich sein soll und nicht nur ein Hack, um sich in einen Algorithmus einzupassen, um Schleifen zu vermeiden, und hoffentlich können Sie sie an vielen Stellen in Ihrem Code verwenden.

Jetzt werde ich einen benutzerdefinierten Funktor schreiben (Sie könnten auch eine Funktion verwenden) für unsere spezielle Schleife. Ich nehme einen Zeiger auf eine der oben genannten Klassen. (Das Problem bei einer Referenz ist, dass std::accumulate es zuweist, sodass es das Objekt kopiert, was nicht das ist, was wir wollen. Es wird effektiv ein Selbstzuweisung sein, aber sich selbst unseren Zeiger zuweisen ist so gut wie keine Operation)

struct AddPairToStats
{
  template< typename T >
  StatsCollector * operator()( StatsCollector * stats, const T& value_type ) const
  { 
     stats->add( value_type.second );
     return stats;
  }
};

Das oben Genannte funktioniert mit jedem Kartentyp unabhängig vom Schlüsseltyp und mit jedem Werttyp, der automatisch in Double konvertiert wird, auch wenn es tatsächlich nicht Double ist.

Angenommen, wir haben unseren Iteratorbereich in unserer Karte, so können wir accumulate wie folgt verwenden:

StatsCollector stats;
std::accumuluate( iterStart, iterEnd, &stats, AddPairToStats() );

Und stats wird bereit sein zur Analyse. Beachten Sie, dass Sie stats für die spätere Verwendung in ihrem Konstruktor anpassen können, sodass Sie z.B. Flaggen setzen können, um keine Kuben/4. Potenzen zu berechnen, wenn Sie keine Schiefe und Kurtosis berechnen möchten (und sogar keine Quadrate zu berechnen, wenn Sie sich nicht um die Varianz kümmern).

Answer 3

Ungefähr:

• map::upper_bound / lower_bound um den Iterator für den Indexbereich zu erhalten
• accumulate um die Summe über den Bereich zu berechnen (einfach), und count um die Elemente zu erhalten

---

Das läuft zweimal durch den Bereich (skaliert nicht gut). Für die Optimierung:

 struct RunningAverage
 {
     double sum;
     int count;
     RunningAverage() { sum = 0; count = 0; }
     RunningAverage & operator+=(double value) 
     { sum += value; ++count; }

     RunningAverage operator+(double value) 
     { RunningAverage result = *this; result += value; return result; }

     double Avg() { return sum / count; } 
 }

Den Sie an `accumulate` übergeben können, um sowohl Anzahl als auch Summe in einem Durchgang zu sammeln.

---

[bearbeiten] Wie im Kommentar angegeben, hier die Begründung für die Optimierung:

• ein O(N) Algorithmus ohne gegebenes Limit für N
• primitive Operationen (Knotentraversal und Addition)
• zufälliges Zugriffsmuster ist möglich

Unter diesen Umständen ist der Speicherzugriff nicht mehr garantiert im Cache zu liegen, und somit kann der Kostenunterschied verglichen mit der pro-Element Operation signifikant werden (oder diese sogar überschreiten). Zwei Mal durchlaufen zu lassen verdoppelt die Kosten des Speicherzugriffs.

Die "Variablen" in dieser Diskussion hängen nur vom Datensatz und der Client-Computerkonfiguration ab, nicht vom Algorithmus.

Ich würde diese Lösung einem benutzerdefinierten `accumulate` vorziehen, da sie einfach zu erweitern oder für andere Operationen anzupassen ist, während die Details des `accumulate` isoliert bleiben. Sie könnte auch mit einer hypothetischen `accumulate_p` Methode verwendet werden, die den Zugriff parallelisiert (Sie bräuchten auch einen `struct + struct` Operator, aber das ist einfach).

Ach ja, und die Konst-Korrektheit überlasse ich dem Leser als Übung :)