logo标签列表

STL map中计算不相交子区间平均值的高效方法

c++stldictionaryaverage
5
我正在将一个算法从C#转换到C++。算法的一小部分是计算字典中某些区域的平均值。
字典中的数据存储方式如下：
Index     Value
1         10
3         28
290       78
1110      90

我需要计算所有索引小于某个数字和所有索引大于某个数字的值的平均值。在C#中，我是这样做的：
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]);
    }
}

我知道这不是很高效和优秀的代码，但我知道我需要完全重写算法的这一部分，所以我决定快速而肮脏地实现它。现在我正在将它移植到C++上，在移动平台上运行，所以性能非常重要。凭借我的有限的C++/STL知识，我可能能够完成工作，但结果很可能比C#代码差得多。
如果你知道在C++中完成这个任务的好方法，请告诉我。
编辑：感谢您所有的回答。正如我在帖子中提到的，我的STL知识有限，因此很难选择一个解决方案，特别是因为有很多不同的意见。如果有人能够通过比较这里发布的解决方案来帮助我做出决定，那将是非常好的。为了给您更多的背景信息：
该函数将被调用大约500次，其中包含1000个映射值。最重要的方面是稳定性，其次是性能。
你遇到了哪些问题？ - Johan Kotlinski
@gregg 我认为答案应该使用STL中的<algorithm>。 - Flexo
使用map计算两个平均值。我可以遍历所有值并计算平均值，但我真的怀疑这是最好的解决方案。 - xsl
1
这里有一个链接，你可以在这里提高你的C++/STL知识：http://www.cplusplus.com/reference/stl/map/ - bjoernz
8个回答
3

编辑：一次通过的地图累加器 - 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;
};

旧版本：

这个对我有用。使用从map::upper_bound检索的范围上accumulate存在问题，因为许多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;
};
我会尝试您的新解决方案并发布结果。 - xsl
@xsl - 是的，在这里boundary中的static是有效的。正在更新代码。 - Steve Townsend
我需要一个上下边界的平均值。例如，所有键值小于250和所有键值大于750的值。我正在更新您的代码以获取这些值，但如果您愿意，您也可以编辑您的帖子，以便我可以确保我做得没错。 - xsl
谢谢。我自己尝试了一下，但遇到了一些问题。我想在这里发布它们，但现在我正在等待您的更新 :) - xsl
谢谢，但我再次没有告诉你我需要什么。我需要两个单独的值：所有值<X的较低平均值和所有值>X的较高平均值。 - xsl
显示剩余3条评论
3
你可以使用 std::accumulate 来计算值的总和，然后除以元素数量。 这里有一些使用 STL 计算平均值和其他统计数据的 示例。
1
那么如果只选择具有特定范围内索引的项目，该怎么办呢？ - sbi
3
使用std::map::lower_bound获取到所需值的迭代器，然后将这些迭代器传递给std::accumulate函数。对于索引小于 x 的值：std::accumulate(m.begin(),m.lower_bound(x))，其中 m 是该映射表，对于索引大于等于 x 的值：std::accumulate(m.lower_bound(x),m.end())。请注意不要改变原有含义，同时让翻译更通俗易懂。 - user470379
如果您想将小于改为小于或等于，或者将大于改为严格的大于，则可以使用upper_bound。另外，我认为我忘记传递到accumulate的必需的init参数应该是0。 - user470379
累加函数不提供将值转换的选项。您可以使用自定义函数，但仍需要处理std::pair集合。在迭代映射时，需要先使用boost::transform_iterator或类似工具来提取出第二个元素。 - CashCow
2

  • 使用std::lower_bound和std::upper_bound可以确定范围，两者的区别在于lower_bound包括值本身，因此将返回第一个大于或等于该值的迭代器，而upper_bound将返回第一个大于该值的迭代器。如果map中不存在该值，则它们将返回相同的迭代器。

  • 您可以使用accumulate，但不能直接将std::pair相加，因此需要使用自定义函数对象，或使用boost::transform_iterator，或者在找到边界后循环一次。循环并不像有些人所说的那样可怕（实际上，accumulate是最可怕的算法之一）。

1
累加有什么可怕的？ - Steve M
谢谢您的回答。如果我理解正确，您建议使用std::lower_bound和std::upper_bound来查找范围，并循环查找平均值。我没有理解accumulate部分为什么糟糕。STL实现糟糕还是使用自定义函数对象不好？ - xsl
1
@xsl - accumulate在没有自定义函数执行累加的情况下无法与map一起使用，因为std::pair(即map元素)没有默认的operator+。由于您有两个要累加的范围，我找不到一个很好的单次处理方式。也许可以提供一个有状态的函数对象，根据给定的映射键在两个位置进行累加，例如pair<int,int>.first。我通过将您的映射拆分成两个vector，然后简单地使用accumulate来实现这一点。 - Steve Townsend
@Steve_M 的累加函数使用运算符+，格式为x=x+y，因此如果您使用自定义对象，则会在每次迭代中复制该对象。您可以提供一个初始对象，结果是您的对象处于完成状态。您可以放置一个自定义运算符，它将通过引用接受您的对象，并欺骗您的模板使用引用，但您的代码可能看起来很混乱。 - CashCow
1

在std::map中，键值对是按键排序的 - 即使使用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算法可能会使代码更短（在使用它的地方）。例如，计算小于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);
谢谢你的回答。我的解决方案与你发布的第一段代码非常相似。使用STL的优缺点是什么？ - xsl
1
如果你正在使用map（std :: map），则使用STL。STL算法有时可能会使代码更清晰，但在这种情况下几乎没有区别（for循环版本可能会稍微快一点）。 - eq-
谢谢您的快速回复。基本上，我可以选择两次循环遍历地图，这样更有效率；或者使用上下界、自定义函数和累加器，虽然较慢，但代码会更短。我理解得对吗？ - xsl
1
请注意，for循环并不是遍历整个映射 - 只遍历小于（或大于）value的键（看条件）。但除此之外，是的，这就是情况。 - eq-
显然这个答案被踩了。如果有人能告诉我原因，我会很高兴的。 - xsl
@eq-: 对于我来说很抱歉错过了那个问题。整个迭代器的主题对我来说是全新的，而我的STL知识有限，很难理解所有答案，更不用说选择一个了。 - xsl
1
如果谓词是映射的比较函数，最好使用std::map<>::lower_bound()和std::map<>::upper_bound()。获取指向相关界限的迭代器，并将其与<numeric>中的std::accumulate()一起使用。因为您正在使用关联容器，所以在取平均数时需要进行适应，以便使用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>、<numeric>、<iterator>和<functional>。
@Steve Townsend：这是你推荐的解决方案吗？ - xsl
如果空间有限，我建议使用自定义函数对象进行单次累加（您需要计算元素数量并对其求和，因此总共需要三到四个状态变量）- 换句话说，避免使用临时的“vector”。否则，这对我来说是有意义的，而且性能应该不错。您在这里尝试过其他选项吗？ - Steve Townsend
@xsl 我建议使用 std::map<>::upper_bound() 和 std::map<>::lower_bound()，因为这意味着第一次遍历字典时，您只需要按照 2*log n 元素的顺序遍历。这也意味着谓词必须是映射比较器的绑定。但是，如果您发现需要更改谓词，则分区映射允许任何谓词。然后，第一次遍历映射的运行时间为 n 的顺序。 - wilhelmtell
@Steve Townsend：我还没有决定。整个迭代器主题对我来说是新的，所以我很难理解所有的答案。eq-的回答非常直接，是我完全理解的唯一一个答案。你和wilhelmtell似乎都对这个主题有很多了解，并且你们两个也测试了提交的代码，这很棒。所以基本上我在你的解决方案、wilhelmtell的解决方案和eq-的解决方案之间做出决定。 - xsl
修复了一个愚蠢的 bug：除以分区的大小，而不是整个容器的大小。 - wilhelmtell
1

假设您正在使用地图，最简单的解决方案是利用键的排序特性，就像其他人一样。首先遍历列表的第一部分，更新累加器和计数器。然后遍历列表的第二部分，执行相同的操作。两个循环，依次进行，您可以从第一部分的长度推断出第二部分的长度。

非常直接的代码，一眼就能看清楚，并且不会创建任何临时容器。出于这些原因，我个人更喜欢这种方法。实际上，如果我自己使用这种数据结构来完成此操作，几乎完全是我要编写的代码。

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查找第一部分的结束迭代器有任何意义。无论如何，您都将遍历整个映射，因此可以边走边检查。映射迭代不是免费的，并且可能会在内存中跳来跳去 - 相比之下，每次迭代的额外比较应该不会引起注意。

（当然，如果您想确定，我必须说您应该测量这一点，因为您应该这样做。这只是我的教育猜测关于优化构建的行为。）

如果调试版本太慢，有两个明显的改变：1. 对于第二个循环使用for循环（因为你知道还剩下多少项），避免调用std::map<int,int>::const_iterator::operator!=。2. 对于第一个循环，在查看之前获取指向*it的指针，并避免（实际上）一次调用std::map<int,int>::const_iterator::operator->。 - please delete me
1

对于那些喜欢使用accumulate函数但又觉得有些繁琐的人，这里是我的提纲。让我们创建一个名为StatsCollector的类。我并不在意它里面具体包含什么，只要我们假设这是一个你会在代码中不同地方使用的类，用于收集数字集合并提供信息。让我们宽泛地定义它。我会假设它以double类型作为值，但你也可以将其模板化为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;
};

上述代码的目的是从传入的数据中计算统计矩。这是一个旨在实用的类，而不仅仅是为了适应算法而进行的hack，希望您可以在代码中的许多地方使用它。
现在我将编写一个自定义函数对象（您也可以使用函数）来处理我们特定的循环。我将取一个指向上述类的指针。（使用引用的问题在于std::accumulate会对其进行赋值，因此它将复制对象，这不是我们想要的。它实际上将成为一个自我分配，但自我分配我们的指针几乎没有任何操作）。
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() );

并且统计数据将准备好进行分析。请注意，您可以在构造函数中自定义统计数据以供以后使用，因此您可以设置标志，以便在不想计算偏度和峰度（甚至不想计算方差的情况下）不计算立方体/四次幂。

0

大致如下：

  • 使用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; } 
 }

您可以传递给accumulate以在一次传递中收集计数和总和。

[编辑]根据评论，这是优化的理由:

  • 给定N没有限制的O（N）算法
  • 原始操作（节点遍历和加法）
  • 随机访问模式是可能的

在这些情况下，内存访问不再保证被缓存支持，因此成本可能会与每个元素操作相比变得显著（甚至超过）。两次迭代将使内存访问成本翻倍。

这个讨论中的“变量”只取决于数据集和客户端计算机配置，而不是算法。

我更喜欢这种解决方案而不是自定义的“累加”，因为它很容易扩展或修改其他操作，而“累加”的细节仍然是孤立的。它也可以与一个假设的 accumulate_p 方法一起使用，该方法并行访问（你还需要一个 struct + struct 运算符，但那很简单）。

哦，关于常量正确性，留给读者作为练习 :)

对这个进行基准测试并查看是否“优化”。我曾经遇到过非常类似的问题，也写了一个累加器。但我还存储了值的平方，这样如果需要的话就可以找到方差/标准差。嘿，为什么不同时存储立方和四次方，这样我们在计算偏度和峰度时也可以顺便计算呢？ - CashCow
不行。第一个测试是简单实现是否足够快。除非你相信编译器可以折叠这两个循环（我不相信），或者期望现在有一次重大的硬件革命，否则这只是一个关于N和你的客户缓存大小的问题。 - peterchen
足够快可能就足够好，但是当你在代码前加上注释“用于优化时：”，我想知道为什么你认为这段代码是为了优化而存在的。顺便说一下，我过去常常实现自己的算法，并实现了一个叫做accumulate2的算法，它使用+=或者一个自定义的函数对象/函数，以修改左值和右值。计算均值需要存储两个数字，即总和和计数。你的类还不符合const正确性。 - CashCow
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接