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

Sie können std::accumulate verwenden, um die Summe der Werte zu berechnen und diese dann durch die Anzahl der Elemente zu teilen. Hier sind einige Beispiele, wie der Mittelwert und andere Statistiken mit STL berechnet werden können.

Answer 2

EDIT: Ein-Durchlauf-Karten-Aktor - result2 enthält die Informationen, die Sie benötigen:

#include 
#include 
#include 

typedef map Values;

struct averageMap
{
    averageMap() : lowerCount(0), lowerSum(0), upperSum(0) {}
    averageMap operator()(const averageMap& input, 
           const Values::value_type& current)
    {
        if (current.first > boundary)
        {
            upperSum += current.second;
        }
        else
        {
            lowerSum += current.second;
            ++lowerCount;
        }
        return *this;
    }

    static size_t boundary;
    size_t lowerCount;
    unsigned int lowerSum;
    unsigned int upperSum;
};

size_t averageMap::boundary(0);

struct averageRange
{
    averageRange() : count(0), sum(0) {}
    averageRange operator()(const averageRange& input, 
        const Values::value_type& current)
    {
        sum += current.second;
        ++count;

        return *this;
    }

    size_t count;
    unsigned int sum;
};

int main()
{
    Values values;

    values[1] = 10;
    values[3] = 28;
    values[290] = 78;
    values[1110] = 110;

    averageMap::boundary = 100;
    averageMap result = accumulate(values.begin(), values.end(), 
        averageMap(boundary), averageMap(boundary));

    averageRange result2 = accumulate(values.lower_bound(2), values.upper_bound(300), 
        averageRange(), averageRange());

    return 0;
};

ALTEN VERSION:

Dies funktioniert für mich. Die Verwendung von accumulate auf dem Bereich, der von map::upper_bound erhalten wurde, war problematisch, da viele STL-Operationen erfordern, dass die endgültigen Iteratoren vom ersten im Bereich erreichbar sind. Es gibt hier ein bisschen Schummeln - unter der Annahme, dass die Werte von map >= 0 sind.

#include 
#include 
#include 
#include 

using namespace std;

typedef map Values;

int main()
{
    Values values;

    values[1] = 10;
    values[3] = 28;
    values[290] = 78;
    values[1110] = 110;

    size_t boundary(100);
    Values::iterator iter = values.upper_bound(boundary);

    vector lowerRange(values.size(), -1);

    transform(values.begin(), iter, lowerRange.begin(), 
        [](std::pair p) 
                -> int { return p.second; });

    vector::iterator invalid(find(lowerRange.begin(), 
        lowerRange.end(), -1));
    size_t lowerCount(distance(lowerRange.begin(), invalid));
    lowerRange.resize(lowerCount);

    vector upperRange(values.size() - lowerCount);
    transform(iter, values.end(), upperRange.begin(), 
        [](std::pair p) 
                -> int { return p.second; });

    size_t lowerAverage = accumulate(lowerRange.begin(), 
        lowerRange.end(), 0) / lowerRange.size();
    size_t upperAverage = accumulate(upperRange.begin(), 
        upperRange.end(), 0) / upperRange.size();

    return 0;
};

Answer 3

• Sie finden Ihren Bereich mit std::lower_bound und std::upper_bound, der Unterschied besteht darin, dass lower_bound einschließlich Ihres Werts ist und somit den ersten Iterator >= Ihres Werts liefert, während upper_bound Ihnen den ersten Iterator > Ihres Werts liefert. Wenn Ihr Wert nicht in der Map ist, geben sie denselben Iterator zurück.

• Sie könnten accumulate verwenden, aber Sie können die std::pairs nicht einfach zusammenaddieren, daher benötigen Sie hier einen benutzerdefinierten Funktor oder verwenden boost::transform_iterator oder durchlaufen Sie einfach einmal, nachdem Sie Ihre Grenzen gefunden haben. Das Durchlaufen ist nicht so schlimm, wie es manche Leute behaupten (und accumulate ist tatsächlich einer der schrecklichsten Algorithmen).

Answer 4

Schlüssel-Wert-Paare in std::map werden nach Schlüsseln sortiert - es ist einfach, die Werte zu summieren, die von Schlüsseln kleiner oder größer als ein bestimmter Wert gezeigt werden, auch mit einer for-Schleife (wenn Sie nicht die STL-Algorithmen verwenden oder erlernen möchten). Für Schlüssel kleiner als einen bestimmten Wert:

std::map map;
map[...] = ...;

int count = 0, sum = 0;
for (std::map::const_iterator it = map.begin();
     it != map.end() && it->first < value; ++it, ++count)
{
    sum += it->second;
}
// Prüfen auf count == 0
int avg = sum / count; // beachten Sie die Ganzzahldivision, ändern Sie ggf.

Für den Durchschnitt von Schlüsseln größer als den Wert, verwenden Sie map.rbegin() (vom Typ std::map<...>::const_reverse_iterator), map.rend() und >.

Bearbeitung: STL-Algorithmen können den Code kürzer machen (wo sie verwendet werden). Zum Beispiel, um den Durchschnitt von Schlüsseln unterhalb von Wert zu berechnen.

int ipsum(int p1, const std::pair& p2) {
    return p1 + p2.second;
}

...

std::map map;
int sum = std::accumulate(map.begin(), map.lower_bound(value), 0, ipsum);

Answer 5

Im Falle, dass das Prädikat die Vergleichsfunktion der Map ist, sind Sie am besten dran mit std::map<>::lower_bound() und std::map<>::upper_bound(). Holen Sie sich den Iterator, der auf die relevante Grenze zeigt, und verwenden Sie diesen mit std::accumulate() aus . Da Sie mit einem assoziativen Container arbeiten, müssen Sie sich beim Durchschnitt anpassen, so dass Sie mit dem second Wert arbeiten und nicht mit einem std::pair<>.

Wenn Ihr Prädikat sich möglicherweise zu etwas anderem ändert, können Sie std::partition() verwenden:

// tmp container: sollte schnell mit std::distance() sein
typedef std::vector seq;

seq tmp(dict.size());
seq::iterator end(std::partition(dict.begin(), dict.end(),
                                 tmp.begin(),
                                 std::bind2nd(std::tmp(), UPPER_BOUND)));

// std::vector funktioniert gut mit std::distance()
seq::difference_type new_count = std::distance(tmp.begin(), end);
double lower_avg = std::accumulate(tmp.begin(), end, 0.0) / new_count;
seq::difference_type new_count = std::distance(end, tmp.end());
double higher_avg = std::accumulate(tmp.begin(), end, 0.0) / new_count;

Sie benötigen hier die Header , , , und .