Wydajny sposób obliczania wartości średniej z rozłącznych podzakresów mapy STL

Question

Konwertuję algorytm z C# na C++. Niewielką częścią algorytmu jest obliczanie średnich wartości dla niektórych obszarów w słowniku.

Dane w słowniku przechowywane są w następujący sposób:

Index  Value 
1   10 
3   28 
290  78 
1110  90 

muszę obliczyć średnią wartość wszystkich wartości z indeksem mniejszej niż określona liczba i wszystko wskaźnik wartości większe od pewnej liczby . W języku C# zrobić to w następujący sposób:

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]); 
    } 
} 

wiem, że nie jest bardzo wydajny i kod bardzo brzydko, ale wiedziałem, że muszę całkowicie przepisać tej części algorytmu w C++ tak, więc postanowiłem zaimplementować to szybko i brudno.

W każdym razie teraz przesyłam to do C++ i ponieważ działa na platformie mobilnej, wydajność jest bardzo ważna. Z moją ograniczoną znajomością C++/STL mogłem najprawdopodobniej wykonać zadanie, ale wynik byłby prawdopodobnie znacznie gorszy niż kod C#.

Więc jeśli znasz dobry i skuteczny sposób wykonania tego zadania w C++, proszę powiedz mi.

---

EDYCJA: Dziękuję za wszystkie odpowiedzi. Jak wspomniałem w moim poście, moja wiedza STL jest ograniczona, więc bardzo trudno jest mi wybrać rozwiązanie, zwłaszcza, że ​​istnieje wiele różnych opinii. Byłoby wspaniale, gdyby ktoś mógł mi pomóc w podjęciu decyzji, porównując przedstawione tutaj rozwiązania. Aby podać trochę więcej informacji podstawowych:

Funkcja zostanie wywołana około 500 razy z 1000 wartości na mapie. Najważniejszym aspektem jest stabilność, wydajność jest najważniejsza.

Answer 1

Pary klucz-wartość w std :: map są posortowane według klawiszy - łatwo jest zsumować wartości wskazane za pomocą klawiszy o wielkości mniejszej lub większej niż pewna wartość nawet z pętlą for (jeśli nie chcesz używać lub nauczyć się używać Algorytmy STL). Kluczy niższych niż niektóre 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 

dla średnich kluczy większych od wartości, użyć map.rbegin() (typu std::map<...>::const_reverse_iterator) map.rend() i >.

edytuj: Algorytmy STL mogą sprawić, że kod będzie krótszy (tam, gdzie jest używany). Na przykład, aby obliczyć średnią kluczy poniżej 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 2

Możesz użyć std::accumulate, aby obliczyć sumę wartości, a następnie podzielić przez liczbę elementów. Oto niektóre informacje na temat obliczania średniej i innych statystyk za pomocą STL: examples.

Answer 3

grubsza:

• map::upper_bound/lower_bound uzyskać iterator dla zakresu indeksu
• accumulate aby obliczyć sumę w całym zakresie (łatwe), a count aby uzyskać elementy

---

Który przechodzi przez zakres dwukrotnie (nie skaluje się dobrze). W celu optymalizacji:

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; } 
} 

Który można przekazać do zgromadzenia, aby zebrać zarówno liczbę jak i sumę w jednym przebiegu.

---

[Edycja] Zgodnie z komentarzem o to uzasadnienie dla optymalizacji:

• A O (N), algorytm nie granicznej określonej dla N
• pierwotne operacji (węzeł przemierzania i dodawanie)
• pseudolosowy wzór jest możliwy

Und W takich okolicznościach dostęp do pamięci nie jest już gwarantowany jako buforowany, a zatem koszt może stać się znaczący w porównaniu do operacji na elementach (lub nawet większy od tego). Iteracja dwukrotnie podwoi koszt dostępu do pamięci.

"Zmienne" w tej dyskusji zależą tylko od zestawu danych i konfiguracji komputera klienta, a nie od algorytmu.

Wolałbym to rozwiązanie od niestandardowego "gromadzenia", ponieważ można go łatwo rozszerzyć lub zmodyfikować w przypadku innych operacji, podczas gdy szczegóły "gromadzenia" pozostają odizolowane. Można go również użyć z hipotetyczną metodą, która umożliwia równoległy dostęp (potrzebny jest również operator struct + struct, ale to proste).

Aha, i const poprawności jest pozostawiamy jako ćwiczenie dla czytelnika :)

Answer 4

• tu swoją ofertę o std :: LOWER_BOUND i std :: UPPER_BOUND, różnica jest taka, że ​​LOWER_BOUND wliczone jest Twój wartość w ten sposób da pierwszy iterator> = twoja wartość while upper_bound da ci pierwszy iterator> twoją wartość. Jeśli twoja wartość nie znajduje się na mapie, zwrócą one ten sam iterator.

• Można użyć nagromadzenia ale nie można po prostu dodać std :: pary razem tak będzie trzeba niestandardowego funktor tutaj lub użyć boost :: transform_iterator, czy tylko pętlę po znalezieniu swoje granice. Pętla nie jest tak zła, jak niektórzy ludzie się okazują (a akumulacja jest w rzeczywistości jednym z najstraszniejszych algorytmów).

Answer 5

W przypadku, gdy orzeczenie jest funkcja porównanie mapie jesteś najlepiej wyłączyć z std::map<>::lower_bound() i std::map<>::upper_bound(). Pobierz iterator wskazując odpowiednie ograniczenie i użyj tego z std::accumulate() z <numeric>.Ponieważ pracujesz z kontenerem asocjacyjnym, musisz dostosować się, biorąc średnią, abyś pracował z wartością second, a nie z std::pair<>.

Jeśli orzecznik może się zmienić na coś innego, można korzystać 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; 

Musisz nagłówki <vector>, <algorithm>, <numeric>, <iterator> i <functional> tutaj.

Answer 6

EDIT: jeden-pass mapa akumulator - result2 zawiera potrzebne informacje:

#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; 
}; 

stara wersja:

Działa to dla mnie. Używanie accumulate w zakresie pobranym z map::upper_bound było problematyczne, ponieważ wiele operacji STL wymaga końcowych iteratorów, aby były osiągalne od pierwszego w zakresie. Jest to trochę oszustwo tutaj - przy założeniu wartości map są> = 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 7

Zakładając, że używasz mapę, najprostszym rozwiązaniem jest skorzystanie z posortowanej rodzaju kluczy, jak inni mieć też. Przejdź przez pierwszą część listy, aktualizując akumulator i policz. Następnie przejdź przez drugą część listy, robiąc to samo. Dwie pętle, jedna po drugiej, i można wywnioskować długość drugiej części z długości pierwszej części.

Bardzo prosty kod, który powinien być czytelny na pierwszy rzut oka i który nie tworzy żadnych tymczasowych kontenerów. Osobiście wolałbym takie podejście z tych powodów. Rzeczywiście jest to dokładnie kod, który bym napisał, gdybym robił to sam, używając tej struktury danych.

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; 

nie widzę żadnego punktu znalezienie iterator end dla pierwszej sekcji przy std::lower_bound przed uruchomieniem. I tak będziesz spacerować po mapie, więc równie dobrze możesz sprawdzić, jak idziesz. Iteracja mapy nie jest wolna i potencjalnie może przeskoczyć nieco w pamięci - w porównaniu z tym dodatkowe porównanie w każdej iteracji nie powinno być zauważalne.

(Oczywiście, jestem zobowiązany powiedzieć, że należy zmierzyć to, jeśli chcesz dowiedzieć się na pewno, bo powinieneś. To jest tylko moje przypuszczenie wykształcony o zachowaniu optymalnej kompilacji.)

Answer 8

Ok jest tutaj mój zarys dla tych, którzy uwielbiają używać akumulacji, aby uczynić go nieco mniej bolesnym. Stwórzmy klasę o nazwie StatsCollector. Nie obchodzi mnie, co jest w tym naprawdę, chyba że założymy, że jest to klasa, której użyjesz w różnych miejscach kodu, który gromadzi kolekcje liczb i da ci informacje. Określmy to luźno. Zakładam, że podwójne wartości to wartości, ale możesz je ustawić na wartość value_type.

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; 
}; 

Celem powyższego jest obliczenie momentów statystycznych z danych przekazywanych w. Jest to klasa ma być przydatny nie tylko hack, aby pasowały do ​​algorytmu, aby unikać pętli, i mam nadzieję, że można używaj go w wielu miejscach kodu.

Teraz napiszę niestandardowego funktora (możesz użyć funkcji) dla naszej konkretnej pętli. Wezmę wskazówkę do jednego z powyższych. (Problem z odniesieniem polega na tym, że std :: akumuluje przypisuje do niego, więc skopiuje obiekt, który nie jest tym, czego chcemy.To jest faktycznie będzie self-assign, ale self-przypisywanie nasz wskaźnik jest dość dużo no-op)

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

Powyższy będzie działać z każdą mapę niezależnie od typu klucza iz dowolnej wartości typ, który konwertuje się automatycznie na podwójny, nawet jeśli nie jest w rzeczywistości podwójny.

Teraz zakładając mamy zakres iterator w naszej mapie możemy użyć zgromadzić tak:

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

i statystyki będą gotowe do analizy. Zauważ, że możesz dostosować statystyki do późniejszego użycia w swoim konstruktorze, dzięki czemu możesz np. Ustawiać flagi, aby nie obliczyć sześcianów/czwartej potęgi, jeśli nie chcesz, aby obliczyć skośność i kurtozę (a nawet nie obliczyć kwadratów, jeśli nie chcesz troszcz się o wariancję).