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

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

Answer 2

EDIT: Kartenakkumulator in einem Durchgang - result2 enthält die benötigten Informationen:

#include <map>
#include <algorithm>
#include <numeric>

typedef map<const unsigned int, unsigned int> 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;
};

ALTE VERSION:

Das funktioniert bei mir. Verwendung von accumulate auf Bereich abgerufen von map::upper_bound war problematisch, weil viele STL-Operationen erfordern, dass die endgültigen Iteratoren vom ersten im Bereich erreichbar sind. Hier gibt es einen kleinen Trick - unter der Annahme, dass die map Werte sind >= 0.

#include <map>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

typedef map<unsigned int, unsigned int> 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<int> lowerRange(values.size(), -1);

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

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

    vector<int> upperRange(values.size() - lowerCount);
    transform(iter, values.end(), upperRange.begin(), 
        [](std::pair<unsigned int, unsigned int> 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 Ihren Wert einschließt und daher den ersten Iterator >= Ihren Wert liefert, während upper_bound den ersten Iterator > Ihren Wert liefert. Wenn Ihr Wert nicht in der Map enthalten ist, geben sie denselben Iterator zurück.

• Sie könnten accumulate verwenden, aber Sie können die std::pairs nicht einfach addieren, so dass Sie hier einen benutzerdefinierten Funktor benötigen, oder Sie können boost::transform_iterator verwenden, oder einfach eine Schleife laufen lassen, sobald Sie Ihre Grenzen gefunden haben. Schleifen sind nicht so böse, wie manche Leute es darstellen (und accumulate ist tatsächlich einer der schrecklichsten Algorithmen).

Answer 4

Schlüssel-Wert-Paare in std::map sind nach Schlüsseln sortiert - es ist einfach, die Werte zu summieren, auf die Schlüssel zeigen, die kleiner oder größer als ein bestimmter Wert sind, sogar mit einer for-Schleife (wenn Sie keine STL-Algorithmen verwenden oder lernen wollen, sie zu verwenden). Für Schlüssel, die kleiner als ein bestimmter value :

std::map<int, int> map;
map[...] = ...;

int count = 0, sum = 0;
for (std::map<int, int>::const_iterator it = map.begin();
     it != map.end() && it->first < value; ++it, ++count)
{
    sum += it->second;
}
// check for count == 0
int avg = sum / count; // do note integer division, change if appropriate

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

edit: STL-Algorithmen könnten den Code kürzer machen (dort, wo er verwendet wird, d.h.). Zum Beispiel, um den Durchschnitt der folgenden Schlüssel zu berechnen value .

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

...

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

Answer 5

In dem Fall, dass das Prädikat die Vergleichsfunktion der Karte ist, sind Sie am besten dran mit std::map<>::lower_bound() y std::map<>::upper_bound() . Holen Sie sich den Iterator, der auf die entsprechende Bindung zeigt, und verwenden Sie diesen mit std::accumulate() de <numeric> . Da Sie mit einem assoziativen Container arbeiten, müssen Sie sich bei der Durchschnittsbildung anpassen, damit Sie mit dem second Wert und nicht mit einem std::pair<> .

Wenn sich Ihr Prädikat in etwas anderes ändern könnte, können Sie std::partition() :

// tmp container: should be fast with std::distance()
typedef std::vector<int> seq;

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

// std::vector works well with 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 die <vector> , <algorithm> , <numeric> , <iterator> y <functional> Kopfzeilen hier.