查找值落入哪个bin

Question

我试图找到双x所属的C类.我的类别被定义为这样的文件中的字符串名称和双精度值

A 1.0
B 2.5
C 7.0 

应该这样解释

"A": 0 < x <= 1.0
"B": a < x <= 2.5
"C": b < x <= 7.0

(输入可以是任意长度,可能必须按其值排序).我只需要这样的功能

std::string findCategory(categories_t categories, double x) {
    ...insert magic here
}

所以对于这个例子,我期待

findCategory(categories, 0.5) == "A"
findCategory(categories, 1.9) == "B"
findCategory(categories, 6.0) == "C"

所以我的问题是a)如何编写函数和b)category_t的最佳选择是什么(在前11 C++中使用stl).我做了几次尝试,所有这些都是......不太成功.

Answer 1

一种选择是使用std::map具有双精度的容器作为键,并且对应于分配给上端点是给定值的范围的值的值.例如,给定您的文件,您将拥有如下地图:

std::map<double, std::string> lookup;
lookup[1.0] = "A";
lookup[2.5] = "B";
lookup[7.0] = "C";

然后,您可以使用该std::map::lower_bound函数,在某个点上,返回键/值对,其键(上端点)是地图中至少与所讨论的点一样大的第一个键.例如,使用上面的映射,lookup.lower_bound(1.37)将返回值为"B"的迭代器. lookup.lower_bound(2.56)将返回一个值为"C"的迭代器.这些查找速度很快; 他们花费O(log n)时间来获得具有n个元素的地图.

在上面,我假设你正在查找的值都是非负的.如果允许负值,则可以在执行任何查找之前添加快速测试以检查值是否为负数.这样,您可以消除虚假结果.

值得一提的是,如果您碰巧知道查找的分布(比如,它们是均匀分布的),就可以构建一个称为最优二叉搜索树的特殊数据结构,它将提供比访问时间更好的访问时间std::map.此外,根据您的应用程序,可能会有更快的选项.例如,如果你这样做是因为你想随机选择一个具有不同概率的结果,那么我建议你在alias方法中查看这篇文章,它允许你在O(1)时间内生成随机值.

希望这可以帮助!

Answer 2

您可以使用 <algorithm> http://www.cplusplus.com/reference/algorithm/lower_bound/中的对类型和“lower_bound” 。

让我们根据上边缘定义您的类别： typedef 对categories_t;

然后只需创建这些边的向量并使用二分搜索来搜索它。请参阅下面的完整示例。

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;
typedef pair<double,string> category_t;

std::string findCategory(const vector<category_t> &categories, double x) {
   vector<category_t>::const_iterator it=std::lower_bound(categories.begin(), categories.end(),category_t(x,""));
   if(it==categories.end()){
      return "";
   }
   return it->second;
}

int main (){

   vector< category_t > edges;
   edges.push_back(category_t(0,"bin n with upper edge at 0 (underflow)"));
   edges.push_back(category_t(1,"bin A with upper edge at 1"));
   edges.push_back(category_t(2.5,"bin B with upper edge at 2.5"));
   edges.push_back(category_t(7,"bin C with upper edge at 7"));
   edges.push_back(category_t(8,"bin D with upper edge at 8"));
   edges.push_back(category_t(9,"bin E with upper edge at 9"));
   edges.push_back(category_t(10,"bin F with upper edge at 10"));

   vector< double > examples ;
   examples.push_back(1);
   examples.push_back(3.3);
   examples.push_back(7.4);
   examples.push_back(-5);
   examples.push_back(15);

   for( vector< double >::const_iterator eit =examples.begin();eit!=examples.end();++eit)
      cout << "value "<< *eit << " : " << findCategory(edges,*eit) << endl;   
}

比较按照我们想要的方式进行，因为双精度数是该对中的第一个，并且首先通过比较第一个组成部分然后比较第二个组成部分来比较对。否则，我们将定义一个比较谓词，如我上面链接的页面中所述。