Manera eficiente de calcular el valor promedio sobre subintervalos disjuntos del mapa STL

Question

Estoy convirtiendo un algoritmo de C# a C++. Una pequeña parte del algoritmo es calcular valores promedio para ciertas áreas en un diccionario.

Los datos del diccionario se almacena en la siguiente forma:

Index  Value 
1   10 
3   28 
290  78 
1110  90 

necesito para calcular el valor medio de todos los valores con un índice menor que un cierto número y el índice de todos los valores mayores que un cierto número de . En C# lo hago de la siguiente manera:

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

Yo sé que no es muy eficiente y un código bastante malo, pero sabía que iba a tener que reescribir por completo esta parte del algoritmo en C++ de todos modos, así que decidí para implementarlo rápido y sucio.

De todos modos ahora estoy portando esto a C++ y porque se ejecutará en una plataforma móvil, el rendimiento es muy importante. Con mi conocimiento limitado de C++/STL, probablemente podría hacer el trabajo, pero el resultado probablemente sería mucho peor que el código de C#.

Así que si conoce una forma buena y eficiente para realizar esta tarea en C++, por favor dígame.

---

EDIT: Gracias por todas sus respuestas. Como mencioné en mi publicación, mi conocimiento de STL es limitado, por lo que es muy difícil para mí elegir una solución, especialmente dado que hay muchas opiniones diferentes. Sería genial si alguien pudiera ayudarme con la decisión, comparando las soluciones publicadas aquí. Para darle un poco más de información básica:

La función se llamará aproximadamente 500 veces con 1000 valores en el mapa. El aspecto más importante es la estabilidad, el rendimiento es el segundo más importante.

Answer 1

pares de valores-clave en std :: map están ordenados por claves - es fácil sumar los valores apuntados por teclas más pequeñas o más grandes que algún valor incluso con un bucle for (si no desea usar o aprender a usar Algoritmos STL). Para las claves más bajo que algunos 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 

Por medio de teclas más grandes que el valor, utilizar map.rbegin() (de tipo std::map<...>::const_reverse_iterator), map.rend() y >.

editar: Algoritmos STL pueden hacer que el código sea más corto (donde se usa, es decir). Por ejemplo, para calcular el promedio de las claves debajo de 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

Puede usar std::accumulate para calcular la suma de los valores, y luego dividir por el número de elementos. Aquí hay algunos examples de cómo calcular la media y otras estadísticas usando STL.

Answer 3

más o menos:

• map::upper_bound/lower_bound para obtener el iterador para el rango de índices
• accumulate para calcular la suma sobre la gama (fácil), y count para obtener los elementos

---

Eso corre a través de el rango dos veces (no escala bien). Para la optimización:

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

Que puede pasar para acumular para reunir el recuento y la suma en una sola pasada.

---

[editar] Según comentario, aquí es la razón fundamental para la optimización:

• un O (N) algoritmo sin límite dado para N
• operaciones primitivas (nodo de recorrido y Además)
• patrón de acceso aleatorio es posible

Und En estas circunstancias, ya no se garantiza que el acceso a memoria sea respaldado por caché, y por lo tanto el costo puede llegar a ser significativo en comparación con la operación por elemento (o incluso exceder eso). Iterar dos veces duplicará el costo de acceso a la memoria.

Las "variables" en esta discusión dependen solo del conjunto de datos y la configuración de la computadora del cliente, no del algoritmo.

Preferiría esta solución que una "acumulación" personalizada, porque es simple de ampliar o modificar para otras operaciones, mientras que los detalles de "acumulación" permanecen aislados. También podría usarse con un método hipotético accumulate_p que paraleliza el acceso (también necesitaría un operador struct + struct, pero eso es simple).

Ah, y la corrección const se deja como ejercicio para el lector :)

Answer 4

• A encontrar su gama con std :: límite distinto y std :: upper_bound, la diferencia es que es inclusivo de límite distinto de su valor así le dará al primer iterador> = su valor, mientras que upper_bound le dará el primer iterador> su valor. Si su valor no está en el mapa, devolverán el mismo iterador.

• Puede usar accumulate pero no puede simplemente agregar std :: pairs juntos, así que necesitaría un functor personalizado aquí, o use boost :: transform_iterator, o simplemente loop una vez que haya encontrado sus límites. Looping no es tan malo como algunos creen (y acumular es en realidad uno de los algoritmos más horribles).

Answer 5

En el caso de que el predicado es la función de comparación del mapa que mejor con std::map<>::lower_bound() y std::map<>::upper_bound() eres. Obtenga el iterador apuntando al límite correspondiente y úselo con std::accumulate() desde <numeric>.Debido a que está trabajando con un contenedor asociativo, deberá adaptarse mientras toma el promedio, de modo que trabaje con el valor second y no con un std::pair<>.

Si el predicado podría cambiar a otra cosa, puede utilizar 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; 

Tendrá las <vector>, <algorithm>, <numeric>, <iterator> y <functional> cabeceras aquí. EDITAR

Answer 6

: una pasada mapa acumulador - result2 contiene la información que necesita:

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

OLD VERSION:

Esto funciona para mí. El uso de accumulate en el rango recuperado de map::upper_bound fue problemático porque muchas operaciones STL requieren que los iteradores finales sean alcanzables desde el primer rango. Hay un poco tramposo aquí - suponiendo que los valores se map> = 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

Suponiendo que está usando un mapa, la solución más sencilla es tomar ventaja de la naturaleza ordenada de las teclas, como los demás tener también Recorra la primera parte de la lista, actualice el acumulador y cuente. Luego, repase la segunda parte de la lista, haciendo lo mismo. Dos bucles, uno después del otro, y puede inferir la longitud de la segunda parte a partir de la longitud de la primera parte.

Código muy sencillo, que debe ser claro a primera vista, y que no crea contenedores temporales. Yo personalmente preferiría este enfoque, por estas razones. De hecho, este es exactamente el código que escribiría si estuviera haciendo esto usando esta estructura de datos.

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; 

no veo ningún punto de encontrar el iterador final de la primera sección usando std::lower_bound antes de comenzar. De todos modos, caminarás por el mapa, así que puedes comprobarlo mientras avanzas. La iteración del mapa no es gratuita y potencialmente saltará un poco en la memoria, en comparación con esto, la comparación adicional en cada iteración no debería ser notable.

(Por supuesto, estoy obligado a decir que usted debe medir esto, si quieres salir de dudas, ya que debería. Esto es sólo mi conjetura sobre el comportamiento de la estructura optimizada.)

Answer 8

Ok, aquí está mi esquema para los que aman usar se acumulan para hacerlo un poco menos doloroso. Vamos a crear una clase llamada StatsCollector. No me importa lo que hay realmente, excepto que asumiremos que esta es una clase que usarás en diferentes lugares de tu código que reúne colecciones de números y te dará información. Vamos a definirlo libremente. Asumiré que toma los dobles como sus valores, pero puede modelarlo en 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; 
}; 

El propósito de lo anterior es para el cálculo de los momentos estadísticos de los datos transmitidos. Es una clase destinada a ser útil, no sólo un truco para encajar en un algoritmo para evitar el uso de bucles, y es de esperar que usted puede utilízalo en muchos lugares en tu código.

Ahora voy a escribir un functor personalizado (puede usar una función) para nuestro ciclo en particular. Tomaré un puntero a uno de los anteriores. (El problema con una referencia es que std :: accumulate le asigna para que copie el objeto que no es lo que queremos.Se va efectivamente a ser un auto-asignar, pero sí la asignación de nuestra puntero es prácticamente un no-op)

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

Lo anterior funcionará con cualquier mapa escribir sin importar el tipo de clave, y con cualquier valor tipo que se convierte automáticamente en doble, incluso si no es realmente doble.

adquiriendo ahora tenemos nuestro rango iterador en nuestro mapa podemos usar acumulan así:

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

Y las estadísticas estarán listos para analizar. Tenga en cuenta que puede personalizar las estadísticas para su uso posterior en su constructor, por lo que puede, por ejemplo, establecer indicadores para no calcular cubos/4ta. Potencias si no desea que calcule los sesgos y curtosis (e incluso no calcule los cuadrados si no lo hace preocuparse por la varianza).