Modo efficiente per calcolare il valore medio su intervalli secondari disgiunti della mappa STL

Question

Sto convertendo un algoritmo da C# a C++. Una piccola parte dell'algoritmo consiste nel calcolare i valori medi per determinate aree in un dizionario.

I dati del dizionario sono memorizzati nel seguente modo:

Index  Value 
1   10 
3   28 
290  78 
1110  90 

Ho bisogno di calcolare il valore medio di tutti i valori, con un indice più piccolo di un certo numero e tutti i valori index più grande di un certo numero di . In C# Io lo faccio nel modo seguente:

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

So che non è molto efficiente e il codice piuttosto scadente, ma sapevo che avrei dovuto riscrivere completamente questa parte del algoritmo in C++ in ogni caso, così ho deciso per implementarlo veloce e sporco.

In ogni caso, ora sto eseguendo il porting su C++ e poiché verrà eseguito su una piattaforma mobile, le prestazioni sono molto importanti. Con la mia conoscenza limitata di C++/STL, molto probabilmente avrei finito il lavoro, ma il risultato sarebbe probabilmente molto peggio del codice C#.

Quindi, se si conosce un modo valido ed efficiente per eseguire questa attività in C++, per favore dimmi.

---

MODIFICA: Grazie per tutte le vostre risposte. Come ho accennato nel mio post, la mia conoscenza STL è limitata, quindi è davvero difficile per me scegliere una soluzione, soprattutto perché ci sono molte opinioni diverse. Sarebbe bello se qualcuno potesse aiutarmi con la decisione, confrontando le soluzioni pubblicate qui. Per darvi qualche informazione in più:

La funzione verrà chiamata circa 500 volte con 1000 valori nella mappa. L'aspetto più importante è la stabilità, la performance è la seconda più importante.

Answer 1

Le coppie valore-chiave in std :: map sono ordinate per chiavi: è facile sommare i valori puntati da tasti più piccoli o più grandi di qualche valore anche con un ciclo for (se non si desidera utilizzare o imparare ad usare Algoritmi STL). Per le chiavi inferiori a qualche 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 

per media di tasti più grandi del valore, usi map.rbegin() (di tipo std::map<...>::const_reverse_iterator), map.rend() e >.

modifica: gli algoritmi STL potrebbero rendere il codice più breve (dove è usato, cioè). Ad esempio, per calcolare la media delle chiavi sotto 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

È possibile utilizzare std::accumulate per calcolare la somma dei valori e quindi dividere per il numero di elementi. Ecco alcuni examples su come calcolare la media e altre statistiche usando STL.

Answer 3

all'incirca:

• map::upper_bound/lower_bound per ottenere l'iteratore per la gamma dell'indice
• accumulate per calcolare la somma su tutta la gamma (facile), e count per ottenere gli elementi

---

Che scorre attraverso la gamma due volte (non scala bene). Per l'ottimizzazione:

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

Quale è possibile passare ad accumulare per raccogliere sia conteggio e somma in un unico passaggio.

---

[modifica] Come da commento, ecco il razionale per l'ottimizzazione:

• un O (N) algoritmo senza il limite dato per N
• operazioni primitive (nodo attraversamento e Inoltre)
• casuale modello di accesso è possibile

Und In queste circostanze, l'accesso alla memoria non è più garantito per il backup della cache, e quindi il costo può diventare significativo rispetto all'operazione per elemento (o addirittura superare quella). L'iterazione raddoppierà raddoppierà il costo dell'accesso alla memoria.

Le "variabili" in questa discussione dipendono solo dal set di dati e dalla configurazione del computer client, non dall'algoritmo.

Preferirei questa soluzione su un "accumulo" personalizzato, perché è semplice estenderlo o modificarlo per altre operazioni, mentre i dettagli "accumula" rimangono isolati. Potrebbe anche essere utilizzato con un ipotetico metodo accumulate_p che consente il parallelismo dell'accesso (anche l'operatore struct + struct è necessario, ma è semplice).

Oh, e const correttezza è lasciato come esercizio per il lettore :)

Answer 4

• Potete trovare il vostro range con std :: lower_bound e std :: superiore limite, la differenza è che lower_bound è comprensivo della vostra valore quindi darà il primo iteratore> = il tuo valore mentre upper_bound ti darà il primo iteratore> il tuo valore. Se il tuo valore non è nella mappa, restituirà lo stesso iteratore.

• È possibile utilizzare accumulare ma non è sufficiente aggiungere le coppie std :: così sarà necessario un functor personalizzato qui, oppure utilizzare boost :: transform_iterator o semplicemente loop una volta individuati i propri limiti. Looping non è così malvagio come alcuni pensano (e si accumula in realtà uno degli algoritmi più orrendi).

Answer 5

Nel caso il predicato è la funzione di confronto della mappa si sta meglio fuori con std::map<>::lower_bound() e std::map<>::upper_bound(). Ottieni l'iteratore puntato al limite pertinente e usalo con std::accumulate() da <numeric>.Perché si sta lavorando con un contenitore associativo è necessario adattarsi durante l'assunzione della media, in modo che si lavora con il valore second e non con un std::pair<>.

Se il predicato potrebbe cambiare a qualcosa d'altro, allora si può usare 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; 

Avrete bisogno le intestazioni <vector>, <algorithm>, <numeric>, <iterator> e <functional> qui. EDIT

Answer 6

: in un solo passaggio mappa accumulatore - result2 contiene le informazioni necessarie:

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

vecchia versione:

Questo funziona per me. Utilizzando accumulate sulla gamma ritirato dall'archivio map::upper_bound era problematico perché molte operazioni STL richiedono iteratori finali di essere raggiungibile dal primo intervallo. C'è un po 'di un imbroglio qui - assumendo i valori map sono> = 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

Supponendo che si sta utilizzando una mappa, la soluzione più semplice è quella di sfruttare la natura ordinata delle chiavi, come altri avere anche. Percorrere la prima parte dell'elenco, aggiornare l'accumulatore e contare. Quindi percorri la seconda parte dell'elenco, facendo lo stesso. Due anelli, uno dopo l'altro, e puoi dedurre la lunghezza della seconda parte dalla lunghezza della prima parte.

codice molto semplice, che dovrebbe essere chiaro a prima vista, e che non crea i contenitori temporanei. Preferirei personalmente questo approccio, per queste ragioni. In effetti questo è praticamente il codice che scriverò se lo stessi facendo io stesso usando questa struttura dati.

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; 

non vedo alcun punto di trovare l'iteratore finale per la prima sezione utilizzando std::lower_bound prima di iniziare. Camminerai comunque attraverso la mappa, quindi potresti anche controllare come vai. L'iterazione della mappa non è gratuita, e potenzialmente salterà in memoria un po '- rispetto a questo, il confronto extra su ogni iterazione non dovrebbe essere evidente.

(Naturalmente, io sono obbligato a dire che si dovrebbe misurare questo, se si vuole scoprire con certezza, perché si dovrebbe. Questa è solo la mia ipotesi istruiti circa il comportamento della costruzione ottimizzata.)

Answer 8

Ok ecco il mio profilo per chi ama utilizzare accumulano per renderlo un po 'meno doloroso. Creiamo una classe chiamata StatsCollector. Non mi interessa cosa ci sia realmente, eccetto che assumeremo che questa è una classe che userete in diversi punti del vostro codice che raccoglie raccolte di numeri e vi darà informazioni. Definiamola vagamente. Immagino che serva per raddoppiare i suoi valori, ma è possibile stamparlo su 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; 
}; 

Lo scopo di quanto sopra è di calcolare momenti statistici dai dati passati. È una classe destinata ad essere utile, non solo un trucco per inserirsi in un algoritmo per evitare l'uso di loop, e, auspicabilmente, si può usalo in molti posti nel tuo codice.

ora voglio scrivere un funtore personalizzato (è possibile utilizzare una funzione) per il nostro particolare ciclo. Prenderò un puntatore a uno dei precedenti. (Il problema con un riferimento è che std :: accumula assegnandogli così che copierà l'oggetto che non è ciò che vogliamo.Si è effettivamente sarà un auto-assegnazione, ma auto-assegnazione nostro puntatore è praticamente un no-op)

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

È possibile che questo funziona con qualsiasi tipo di mappa a prescindere dal tipo di chiave, e con qualsiasi valore digita che converte automaticamente in double, anche se in realtà non è double.

Ora Supponendo che abbiamo la nostra gamma iteratore nella nostra mappa possiamo usare accumulare in questo modo:

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

e le statistiche saranno pronti da analizzare. Nota che puoi personalizzare le statistiche per uso futuro nel suo costruttore, quindi puoi ad esempio impostare flag per non calcolare cubi/4 ° poteri se non vuoi che calcoli l'asimmetria e la curtosi (e anche non calcolare i quadrati se non lo fai cura della varianza).