计算STL图不相交子范围平均值的有效方法

STD:键值是按键排序的,很容易用比某个值更小或更大的键来表示值,即使是for循环(如果你不想使用或学习使用STL算法)。对于一些低于 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

对于大于值的键的平均值,请使用 map.rbegin() (属于类型) std::map<...>::const_reverse_iterator ), map.rend() 和 > .

编辑:STL算法可能会缩短代码的长度(在使用它的地方,也就是说)。例如,计算以下键的平均值 价值 .

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

你可以用 std::accumulate 计算这些值的和,然后除以元素的数目。这是一些 examples 如何使用STL计算平均值和其他统计数据。

编辑:一通图累加器- result2 包含您需要的信息:

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

旧版本:

这对我有用。使用 accumulate 在从中检索到的范围内 map::upper_bound 是有问题的,因为许多STL操作要求从范围的第一个到达最终迭代器。这里有一个小骗子-假设 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;
};

• 找到STD::LoeReLoWix:STD::UpFullBoad,差异是LoeLoSLIVE包含了您的值,因此将给出第一迭代器& Gt;=您的值,而uPlfIdBand将给您第一个迭代器& Gt;您的值。如果您的值不在映射中,它们将返回相同的迭代器。

• 可以使用累加,但不能只将STD::对加在一起,所以这里需要自定义函子,或者使用Boosi::TraveSyter迭代器,或者在找到边界后只使用循环。循环并不像有些人所说的那样邪恶(积累实际上是最可怕的算法之一)。

在这种情况下,谓词是最适合使用的映射的比较函数 std::map<>::lower_bound() 和 std::map<>::upper_bound() . 获取指向相关绑定的迭代器,并将其与 std::accumulate() 从 <numeric> . 因为您使用的是关联容器,所以在取平均值时需要进行调整,以便使用 second 值而不是 std::pair<> .

如果谓词可能更改为其他内容,则可以使用 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;

你需要 <vector> , <algorithm> , <数字> , <iterator> 和 <functional> 标题在这里。

假设您正在使用一个映射,最简单的解决方案是利用键的排序性质,就像其他人一样。浏览列表的第一部分,更新累加器和计数。然后浏览列表的第二部分,做同样的事情。两个循环,一个接一个,您可以从第一部分的长度推断第二部分的长度。

非常简单的代码,乍一看应该很清楚,并且不会创建临时容器。出于这些原因,我个人更喜欢这种方法。事实上,如果我自己使用这个数据结构来做的话,这几乎就是我要写的代码。

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;

我看不到在第一节中使用 std::lower_bound 开始之前。不管怎样,你还是要在地图上走走,所以你最好在走的同时检查一下。地图迭代不是免费的,并且可能会在内存中跳跃一点——与此相比,每个迭代的额外比较不应该是明显的。

(当然,我不得不说,如果你想确定的话,你应该测量这个,因为你应该。这只是我对优化构建行为的有根据的猜测。)

好吧,这是我的提纲,给那些喜欢用积攒来减轻痛苦的人。让我们创建一个名为StatsCollector的类。我不在乎它到底包含了什么,除非我们假定这是一个类,您将在代码的不同位置使用它来收集数字集合并向您提供信息。让我们粗略地定义一下。我假设它的值为double,但您可以在value_类型上对其进行模板化。

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

上述目的是根据输入的数据计算统计力矩。它是一个旨在有用的类,而不仅仅是一个适合于避免使用循环的算法的黑客,并且希望您可以在代码中的许多地方使用它。

现在我将为我们的特定循环编写一个自定义函数(您可以使用函数)。我将用一个指针指向上面的其中一个。一个参考的问题是:STD::累积分配给它,这样它将复制不是我们想要的对象。实际上,它将是一个自分配,但自分配指针几乎是一个无操作)

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

上面的内容适用于任何映射类型,不管键类型如何,也适用于任何自动转换为double的值类型,即使它实际上不是double。

现在假设我们在地图中有迭代器范围,我们可以这样使用accumulate:

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

统计数据将准备分析。请注意,您可以自定义统计信息以供以后在其构造函数中使用,因此,如果您不希望将标志设置为不计算多维数据集/四次幂,则可以将其设置为计算偏度和峰度(如果不关心方差,甚至不计算平方)。

大致上:

• map::upper_bound / lower_bound 获取索引范围的迭代器
• accumulate 计算范围内的总和(简单),以及 count 获取元素

它在范围内运行两次(不能很好地缩放)。对于优化:

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

它可以通过累计一次收集计数和和。

[编辑] 根据评论,以下是优化的基本原理:

• 一种不受n限制的O(N)算法
• 基本操作(节点遍历和添加)
• 随机访问模式是可能的

在这种情况下,内存访问不再保证有缓存备份,因此与每个元素的操作相比,成本可能会变得很高(甚至超过这一点)。重复两次将使内存访问成本增加一倍。

讨论中的“变量”仅取决于数据集和客户机配置,而不是算法。

比起自定义的“累计”,我更喜欢这个解决方案,因为它很容易扩展或修改其他操作,而“累计”细节仍然是孤立的。它也可以用于假设 accumulate_p 并行访问的方法(您需要 struct + struct 操作员也是,但这很简单)。

噢,常量正确性留给读者作为练习:)