我需要一个带有浮点键的关联数据结构,其中具有几乎相等值的键被合并在一起。我正在使用C ++,但是语言并不重要。
基本上我目前的策略是
-
仅处理单精度浮点数
-
使用具有自定义键类型的unordered_map
-
在键类型上将哈希函数定义为
a。给定的浮点数
v
以两倍的精度将v
除以某个公差(例如0.0005),得到k
。b。将
k
转换为64位整数,产生ki
c。返回
ki
的std :: hash。
首先,是否有一个标准的命名数据结构可以执行以下操作?是否没有比我一般的方法更好的方法呢?
对于以下实现,我最不喜欢的是对哪个浮点值进行装箱不直观。通过大致了解我想将输入中的哪些值视为相同的值并测试各种容差,我可以解决此问题,但是如果将12.0453添加到容器中,那么将得到12.0453 +/- 0.0005的值将是一个很好的解决方案如果公差参数为0.0005,则认为是相等的,但事实并非如此-我什至不认为在unordered_map上可能会发生这种行为,因为我认为哈希函数将取决于表中的值。
基本上,我的实现是将数字行划分为一维网格,其中每个网格单元的宽度均为epsilon单位,然后将浮点值分配给它们所属的网格单元的从零开始的索引。我的问题是,有没有更好的办法来实现公差也为O(1)的浮点值的关联容器?并且下面的实现是否存在问题?
template<typename V,int P=4>
class float_map
{
private:
struct key {
public:
long long val;
static constexpr double epsilon(int digits_of_precision)
{
return (digits_of_precision == 1) ? 0.5 : 0.1 * epsilon(digits_of_precision - 1);
}
static constexpr double eps = epsilon(P);
key(float fval) : val(static_cast<long long>( fval / eps))
{}
bool operator==(key k) const {
return val == k.val;
}
};
struct key_hash
{
std::size_t operator()(key k) const {
return std::hash<long long>{}(k.val);
}
};
std::unordered_map<key,V,key_hash> impl_;
public:
V& operator[](float f) {
return impl_[key(f)];
}
const V& at(float f) const {
return impl_.at(key(f));
}
bool contains(float f) const {
return impl_.find(f) != impl_.end();
}
double epsilon() const {
return key::eps;
}
};
int main()
{
float_map<std::string> test;
test[12.0453f] = "yes";
std::cout << "epsilon = " << test.epsilon() << std::endl; // 0.0005
std::cout << "12.0446f => " << (test.contains(12.0446f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0447f => " << (test.contains(12.0447f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0448f => " << (test.contains(12.0448f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0449f => " << (test.contains(12.0449f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0450f => " << (test.contains(12.0450f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0451f => " << (test.contains(12.0451f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0452f => " << (test.contains(12.0452f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0453f => " << (test.contains(12.0453f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0454f => " << (test.contains(12.0454f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0455f => " << (test.contains(12.0455f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0456f => " << (test.contains(12.0456f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0457f => " << (test.contains(12.0457f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0458f => " << (test.contains(12.0458f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0459f => " << (test.contains(12.0459f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0460f => " << (test.contains(12.0460f) ? "yes" : "no") << std::endl; // no
}