将多个非数字插入 std::unordered_set<double>

Question

IEEE 754 标准的后果之一是 std::unordered_set<double> 在插入非数字元素 (NANs) 时的非直观行为。

由于NAN!=NAN，经过以下顺序：

#include <iostream>
#include <cmath>
#include <unordered_set>

int main(){
    std::unordered_set<double> set;
    set.insert(NAN);
    set.insert(NAN);
    std::cout<<"Number of elements "<<set.size()<<"\n";  //there are 2 elements!
}

set(see it live)中有两个元素：NAN和NAN!

我的主要问题是，当 N NAN 被插入哈希集时，它们都命中相同的哈希桶和 N 的性能插入哈希集退化到最坏情况运行时间 - O(N^2)。

例如，请参阅问题末尾的列表或 here live - 插入 NAN 比插入 "normal" 浮点数要多花费一些数量级的时间。

我的问题：是否有可能（如果是 - 如何）以这样一种方式调整 std::unordered_set<double>，即集合中最多有一个 NAN 元素，无论插入的 NAN 的味道（NAN、-NAN 等等）?

清单：

#include <iostream>
#include <cmath>
#include <unordered_set>
#include <chrono>

constexpr int N=5000;
void test_insert(double value)
{
    std::unordered_set<double> s;
    auto begin = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; i++) {
        s.insert(value);
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Duration: " << (std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() / 1e9) << "\n";
    std::cout << "Number of elements: "<<s.size()<<"\n";
}

int main(){
    std::cout << "Not NAN\n";
    test_insert(1.0);           //takes 0.0001 s
    std::cout << "NAN\n";
    test_insert(NAN);           //takes 0.2 s
}

Answer 1

您可以定义自己的谓词来比较键，并为此目的确保 NaN 比较相等。这可以作为第三个参数提供给 std::unordered_set class 模板。

请参阅下面 EqualPred 的定义（从问题中复制并修改的代码），以及它在声明 unordered_set 变量时的用途。我从 https://en.cppreference.com/w/cpp/container/unordered_set

的文档中获取了第二个参数的默认值

现场演示：http://coliru.stacked-crooked.com/a/7085936431e6698f

#include <iostream>
#include <cmath>
#include <unordered_set>
#include <chrono>

struct EqualPred
{
    constexpr bool operator()(const double& lhs, const double& rhs) const
    {
        if (std::isnan(lhs) && std::isnan(rhs)) return true;
        return lhs == rhs;
    }
};

constexpr int N=5000;
void test_insert(double value)
{
    std::unordered_set<double, std::hash<double>, EqualPred> s;
    auto begin = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; i++) {
        s.insert(value);
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Duration: " << (std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() / 1e9) << "\n";
    std::cout << "Number of elements: "<<s.size()<<"\n";
}

int main(){
    std::cout << "Not NAN\n";
    test_insert(1.0);           //takes 0.0001 s
    std::cout << "NAN\n";
    test_insert(NAN);           //takes 0.2 s
}

值得注意（感谢@ead 的评论）-NaN 和 +NaN 可能散列为不同的值。如果你想把它们当作相同的来处理，你需要提供第二个模板参数的不同实现，哈希函数。这应该检测任何 NaN 并每次散列相同的 NaN。

Answer 2

根据您在 Andrews 回答中的评论，

I think the problem with this solution: -NAN will have a different hash-value then NAN but for hash-function h must hold: if x==y then also h(x)==h(y)

这会以不同的方式进行散列，因此如果需要，您还需要定义自己的散列函数 h(-NAN) == h(NAN) ...

（根据@Andrew 的回答扩充）

#include <iostream>
#include <cmath>
#include <unordered_set>
#include <chrono>

struct EqualPred
{
    constexpr bool operator()(const double& lhs, const double& rhs) const
    {
        if (std::isnan(lhs) && std::isnan(rhs)) return true;
        return lhs == rhs;
    }
};

template <typename T>
struct Hash
{
    size_t operator()(const T& value) const
    {
        return  std::hash<T>()( std::isnan(value) ? NAN : value);
    }


};

std::unordered_set<double, Hash<double>, EqualPred> s;

constexpr int N=5000;
void test_insert(double value)
{

    auto begin = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; i++) {
        s.insert(value);
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Duration: " << (std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() / 1e9) << "\n";
    std::cout << "Number of elements: "<<s.size()<<"\n";
}

int main(){
    std::cout << "Not NAN\n";
    test_insert(1.0);           //takes 0.0001 s
    std::cout << "NAN\n";
    test_insert(NAN);  
    test_insert(-NAN);

    std::cout << s.size() << std::endl;
    //takes 0.2 s
}

Demo

将多个非数字插入 std::unordered_set<double>

Inserting multiple not-a-numbers into a std::unordered_set<double>

c++

c++11

ieee-754