Effizienter Weg zur Berechnung des Durchschnittswerts über disjunkte Teilbereiche der STL-Karte

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 werden auf folgende Weise gespeichert:

Index     Value
1         10
3         28
290       78
1110      90

Ich muss den Durchschnittswert aller Werte mit einem Index kleiner als eine bestimmte Zahl und aller Indexwerte größer als eine bestimmte Zahl berechnen. In C# mache ich das auf die folgende Weise:

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ß, das ist nicht sehr effizient und ziemlich mieser Code, aber ich wusste, dass ich diesen Teil des Algorithmus sowieso komplett in C++ umschreiben müsste, also beschloss ich, ihn schnell und schmutzig zu implementieren.

Jedenfalls portiere ich es jetzt nach C++ und da es auf einer mobilen Plattform laufen wird, ist die Leistung sehr wichtig. Mit meinen begrenzten C++/STL-Kenntnissen könnte ich höchstwahrscheinlich die Aufgabe erledigen, aber das Ergebnis wäre wahrscheinlich viel schlechter als der C#-Code.

Wenn Sie also einen guten und effizienten Weg kennen, diese Aufgabe in C++ zu bewältigen, sagen Sie es mir bitte.

---

EDIT: Ich danke Ihnen für alle Antworten. Wie ich in meinem Beitrag erwähnt habe, sind meine STL-Kenntnisse begrenzt, so dass es wirklich schwer für mich ist, eine Lösung zu wählen, zumal es viele verschiedene Meinungen gibt. Es wäre toll, wenn mir jemand bei der Entscheidung helfen könnte, indem er die hier geposteten Lösungen vergleicht. Um Ihnen ein wenig mehr Hintergrundinformationen zu geben:

Die Funktion wird etwa 500 Mal mit 1000 Werten in der Karte aufgerufen. Der wichtigste Aspekt ist die Stabilität, die Leistung ist der zweitwichtigste.

Answer 1

Wenn Sie eine Map verwenden, ist die einfachste Lösung, die Sortierung der Schlüssel auszunutzen, wie es auch andere getan haben. Gehen Sie durch den ersten Teil der Liste und aktualisieren Sie Akkumulator und Zähler. Dann gehen Sie durch den zweiten Teil der Liste und tun dasselbe. Zwei Schleifen, eine nach der anderen, und Sie können die Länge des zweiten Teils von der Länge des ersten Teils ableiten.

Sehr einfacher Code, der auf den ersten Blick klar sein sollte und der keine temporären Container erzeugt. Aus diesen Gründen würde ich persönlich diesen Ansatz bevorzugen. In der Tat ist dies ziemlich genau der Code, den ich schreiben würde, wenn ich dies selbst mit dieser Datenstruktur tun würde.

int key = <whatever>;

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

size_t num1 = 0;
long total1 = 0;

while (it != end && it->first < key) {
    total1 += it->second;
    ++num1;
    ++it;
}

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

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

int avg_less = num1 > 0 ? total1 / num1 : 0;
int avg_greater_equal = num2 > 0 ? total2 / num2 : 0;

Ich sehe keinen Sinn darin, den End-Iterator für den ersten Abschnitt zu finden, indem ich std::lower_bound bevor Sie beginnen. Sie werden ohnehin durch die Karte gehen, also können Sie das auch unterwegs überprüfen. Die Iteration der Karte ist nicht kostenlos und springt möglicherweise ein wenig im Speicher herum - im Vergleich dazu sollte der zusätzliche Vergleich bei jeder Iteration nicht auffallen.

(Natürlich muss ich Ihnen sagen, dass Sie das messen sollten, wenn Sie es genau wissen wollen, denn das sollten Sie. Dies ist nur meine Vermutung über das Verhalten des optimierten Builds).

Answer 2

Ok, hier ist meine Übersicht für diejenigen, die es lieben zu akkumulieren, um es etwas weniger schmerzhaft zu machen. Lassen Sie uns eine Klasse namens StatsCollector erstellen. Es ist mir egal, was darin steht, außer dass wir annehmen, dass dies eine Klasse ist, die Sie an verschiedenen Stellen in Ihrem Code verwenden werden, die Sammlungen von Zahlen sammelt und Ihnen Informationen liefert. Definieren wir sie grob. Ich gehe davon aus, dass sie Doubles als Werte annimmt, aber man kann sie auch als Vorlage für value_type verwenden.

class StatsCollector
{
public:
   StatsCollector();

   void add(double val);

 // some stats you might want
   size_t count() const;
   double mean() const;
   double variance() const;
   double skewness() const;
   double kurtosis() const;
};

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

Jetzt werde ich einen benutzerdefinierten Funktor (Sie können eine Funktion verwenden) für unsere spezielle Schleife schreiben. Ich werde einen Zeiger auf einen der oben genannten nehmen. (Das Problem mit einem Verweis ist, dass std::accumulate diesem Verweis zuweist, so dass das Objekt kopiert wird, was nicht das ist, was wir wollen. Es wird effektiv eine Selbstzuweisung sein, aber die Selbstzuweisung unseres Zeigers ist so ziemlich ein No-op)

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

Die obige Methode funktioniert mit jedem Map-Typ, unabhängig vom Schlüsseltyp, und mit jedem Wertetyp, der automatisch in double konvertiert wird, auch wenn er nicht wirklich double ist.

Wenn wir nun unseren Iteratorbereich in unserer Map haben, können wir accumulate wie folgt verwenden:

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

Und die Statistiken werden zur Analyse bereitstehen. Beachten Sie, dass Sie stats für die spätere Verwendung in seinem Konstruktor anpassen können. So können Sie z. B. Flags setzen, um keine Kuben/4. Potenzen zu berechnen, wenn Sie nicht wollen, dass es Schiefe und Kurtosis berechnet (und sogar, um 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

---

Dadurch wird der Bereich zweimal durchlaufen (nicht gut skalierbar). Zur 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; } 
 }

Diese können Sie an accumulate übergeben, um sowohl Zählung als auch Summe in einem Durchgang zu erfassen.

---

[Bearbeiten] Wie in den Kommentaren erwähnt, ist hier die Begründung für die Optimierung:

• ein O(N)-Algorithmus, bei dem es keine Grenze für N gibt
• primitive Operationen (Knotentraversal und Addition)
• zufälliges Zugriffsmuster ist möglich

Unter diesen Umständen ist nicht mehr gewährleistet, dass der Speicherzugriff im Cache erfolgt, so dass die Kosten im Vergleich zu den Kosten pro Element beträchtlich sein können (oder diese sogar übersteigen). Zweimaliges Iterieren verdoppelt die Kosten des Speicherzugriffs.

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

Ich würde diese Lösung einer benutzerdefinierten "Akkumulation" vorziehen, da sie einfach zu erweitern oder für andere Operationen zu ändern ist, während die Details der "Akkumulation" isoliert bleiben. Es könnte auch mit einem hypothetischen "accumulate" verwendet werden accumulate_p Methode, die den Zugriff parallelisiert (Sie benötigen eine struct + struct Operator auch, aber das ist einfach).

Oh, und die Korrektheit bleibt dem Leser als Übung überlassen :)