使用浮点键实现类似于哈希 table 的数据结构，其中容差范围内的值被合并在一起

Question

我需要一个带有浮点键的关联数据结构，其中值几乎相等的键被合并在一起。我正在使用 C++，但语言并不重要。

基本上我现在的策略是

只处理单精度浮点数
使用带有自定义键类型的unordered_map
将键类型的散列函数定义为

一个。给定 float v 将 v 除以一些公差，例如 0.0005，双精度，产生 k.

b。将 k 转换为 64 位整数，得到 ki

c。 return std::hash 共 ki。

首先，是否有一个标准的命名数据结构可以做这样的事情？如果没有，是否有比我的一般方法更好的方法来做到这一点？

我不喜欢以下实现的主要一点是，我不直观地认为哪些浮点值将合并在一起；我通过大致了解输入中的哪些值我想算作相同的值并测试各种公差来解决这个问题，但是如果您将 12.0453 添加到容器中那么值 12.0453 +/- 0.0005 会很好如果公差参数为 0.0005，则被认为是相等的，但事实并非如此——我什至认为这种行为在 unordered_map 之上是不可能的，因为我认为哈希函数将依赖于table。

基本上，我的实现是将数字线划分为一维网格，其中每个网格单元的宽度为 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

    }

Answer 1

嗯，也许你可以使用一个 unordered_map 键控整数，并用类似的东西确定键值：

key = floor(val/precision);

这是相当透明的，键 0 将包含从 0.0 到 0.0005 的值（或任何您的精度）。此外，负数在逻辑上也适用于此。

如果您想使用二维值执行此操作，您可能需要查看 geohashes。

Answer 2

最好的方法是使用定点运算。

问题详细信息中的实现有效，但比需要的更加模糊。它视为 epsilon 或公差的实际上是“bin 宽度”——划分实数线的网格线之间的一维间距——因此，如果您期望 epsilon 值表现得像公差，您会注意到容器边缘/网格线附近的反直觉行为。

无论如何，考虑这个问题的更清晰的方法是不要尝试使用“容差”的概念，而是使用“有效数字”的概念。仅将小数点右侧的 n 以 10 为底的数字视为重要的，并对该 n 进行参数化。这本质上导致使用定点值而不是浮点值作为键；在上面的实现中，它类似于使用 epsilon 0.0001 而不是 0.0005.

但是现在没有理由不只是修改原始代码中的 epsilon，而是将定点值设为 public 类型并将该类型用作 [=24= 的键] 暴露给用户。以前我们想通过将实现的 unordered_map 包装在自定义数据结构中来隐藏键类型，因为在那种情况下键是不透明的，没有直观的含义。在普通的 unordered_map 中使用定点键有一个附带的好处，即我们不必为所有标准 std::unordered_map 调用实现包装方法，因为现在给用户一个实际的 [=24] =].

代码如下：

template<int P=4>
class fixed_point_value
{
    static constexpr double calc_scaling_factor(int digits_of_precision)
    {
        return (digits_of_precision == 1) ? 10.0 : 10.0 * calc_scaling_factor(digits_of_precision - 1);
    }

    static constexpr double scaling_factor = calc_scaling_factor(P);

    template<int P>
    friend struct fixed_point_hash;

public:
    fixed_point_value(float val) : 
        impl_(static_cast<long long>(std::llround(scaling_factor * val)))
    {}

    bool operator==(fixed_point_value<P> fpv) const 
    {
        return impl_ == fpv.impl_;
    }

    float to_float() const
    {
        return static_cast<float>(impl_ / scaling_factor);
    }

private:
    long long impl_;
};

template<int P = 4>
struct fixed_point_hash
{
    std::size_t operator()(fixed_point_value<P> key) const {
        return std::hash<long long>{}(key.impl_);
    }
};

template<typename V, int P = 4>
using fixed_point_table = std::unordered_map<fixed_point_value<P>, V, fixed_point_hash<P>>;

int main()
{
    fixed_point_table<std::string, 4> t4;

    t4[12.0453f] = "yes";

    // these will all be "no" except 12.0453f because we have 4 base-10 digits of precision i.e.
    // 4 digits right of the decimal must be an exact match
    std::cout << "precision = 4" << std::endl;
    std::cout << "12.0446f => " << (t4.find(12.0446f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0447f => " << (t4.find(12.0447f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0448f => " << (t4.find(12.0448f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0449f => " << (t4.find(12.0449f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0450f => " << (t4.find(12.0450f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0451f => " << (t4.find(12.0451f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0452f => " << (t4.find(12.0452f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0453f => " << (t4.find(12.0453f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0454f => " << (t4.find(12.0454f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0455f => " << (t4.find(12.0455f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0456f => " << (t4.find(12.0456f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0457f => " << (t4.find(12.0457f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0458f => " << (t4.find(12.0458f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0459f => " << (t4.find(12.0459f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "12.0460f => " << (t4.find(12.0460f) != t4.end() ? "yes" : "no") << std::endl;
    std::cout << "\n";

    fixed_point_table<std::string, 3> t3;
    t3[12.0453f] = "yes"; // 12.0453 will round to the fixed point value 12.045.
    std::cout << "precision = 3" << std::endl;
    std::cout << "12.0446f => " << (t3.find(12.0446f) != t3.end() ? "yes" : "no") << std::endl; // rounds to 12.045 so yes;
    std::cout << "12.0447f => " << (t3.find(12.0447f) != t3.end() ? "yes" : "no") << std::endl; // rounds to 12.045 so yes;
    std::cout << "12.0448f => " << (t3.find(12.0448f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0449f => " << (t3.find(12.0449f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0450f => " << (t3.find(12.0450f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0451f => " << (t3.find(12.0451f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0452f => " << (t3.find(12.0452f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0453f => " << (t3.find(12.0453f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0454f => " << (t3.find(12.0454f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0455f => " << (t3.find(12.0455f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0456f => " << (t3.find(12.0456f) != t3.end() ? "yes" : "no") << std::endl; // 12.0456f rounds to the 3 digits of precison fixed point value 12.046 so no
    std::cout << "12.0457f => " << (t3.find(12.0457f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0458f => " << (t3.find(12.0458f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0459f => " << (t3.find(12.0459f) != t3.end() ? "yes" : "no") << std::endl; // '
    std::cout << "12.0460f => " << (t3.find(12.0460f) != t3.end() ? "yes" : "no") << std::endl; // '

}

Answer 3

简单地将数据点合并在一起可能无法满足您的需求，因为在 bin 边界的两侧总会有非常靠近的点。您需要使用其他方法。

例如：

假设您将域划分为边长 epsilon 的正方形。然后你可以构建一个 std::map 将每个数据点分配给一个正方形；给定一个任意点 P=(x,y)，你可以找到包含 P 的正方形 S(P)。现在你要做的是查看一个 3x3 网格中的所有九个方块，其中包含 S(P) 作为中心方块。然后您可以扫描这九个 bin 以找到最接近 P.

的数据点

此方法保证找到距 (x,y) 距离 epsilon 内的点（如果存在的话）。

使用浮点键实现类似于哈希 table 的数据结构，其中容差范围内的值被合并在一起

implementing a hash table-like data structure with floating point keys where values within a tolerance are binned together

c++

data-structures

floating-point

hashtable

fixed-point