1

我正在寻找一个将浮点数分类为任意箱的类。垃圾箱。所需的语法类似于：

std::vector<double> bin_vector;

// ..... fill the vector with 1, 1.4, 5, etc not evenly spaced values

Binner bins(bin_vector); 

for (std::vector<double>::const_iterator d_itr = some_vector.begin(); 
     d_itr != some_vector.end(); d_itr++) { 
  int bin = bins.categorize(*d_itr); 

  // bin would be 0 for x < 1, 1 for 1 < x < 1.4, etc
  // do something with bin
}

不幸的是，由于便携性要求，我仅限于 boost 和 stl。我已经使用地图和重载自定义范围对象推出了自己的 O(log n) 解决方案<，但该解决方案似乎容易出错并且充其量是丑陋的。

有一些简单的 stl 或 boost 对象解决方案吗？

4

2 回答 2

4

使用 std::map，将区间边界映射到 bin 编号。然后使用 .upper_bound() 找到 bin。

于 2012-04-25T07:19:46.950 回答
0

这是一个未经测试的通用算法，它采用任意长度 M 的输入向量和 N-1 个 bin 边界的排序向量，并返回 N 个 bin 计数的向量。Bin i 计算区间 [breaks[i-1], breaks[i]) 中的值。T1 和 T2 类型应该是相互可比的。复杂度等于 O(M * log (N))。

#include<algorithm>     // std::is_sorted, std::lower_bound
#include<cassert>       // assert
#include<iterator>      // std::distance
#include<vector>        // std::vector

template<typename T1, typename T2>
std::vector<std::size_t> bin_count(const std::vector<T1>& input, const std::vector<T2>& breaks)
{
    // breaks is a sorted vector -INF < a0 < a1 < ... < aN-2 < +INF
    assert(std::is_sorted(breaks.begin(), breaks.end()));
    auto N = breaks.size() + 1;

    std::vector<std::size_t> output(N, 0);

    if (N == 1) {
        // everything is inside [-INF, INF)
        output[0] = input.size();
        return output;
    }

    for(auto it = input.begin(), it != input.end(); ++it) {
        if (*it < breaks.front()) {
            // first bin counts values in [-INF, a0)
            ++output[0];
            break;
        }
        if (*it >= breaks.back()) {
            // last bin counts values in [aN-1, +INF)
            ++output[N-1];
            break;
        }

        const auto break_it = std::lower_bound(breaks.begin(), breaks.end(), *it);
        bin_index = std::distance(breaks.begin(), break_it) + 1;
        ++output[bin_index];
    }

    return output;  
}
于 2012-04-25T08:07:17.853 回答