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

Question

IEEE 754标准的结果之一是std::unordered_set<double>当NAN插入非数字元素时的非直观行为.

由于事实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(见它直播):NAN和NAN!

我的主要问题是,当N NANs被插入到散列集中时,它们都会击中相同的散列桶,并且N插入到散列集中的性能会退化为最坏情况下的运行时间 - O(N^2).

例如,请参阅问题末尾的列表或此处实时插入NAN比"正常"浮点数花费的时间多一些数量级.

我的问题:是否有可能(如果是 - 如何)以std::unordered_set<double>这种方式进行调整NAN,无论插入的NANs(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

您可以定义自己的谓词来比较键,并确保NaNs为此目的进行比较.这可以作为std::unordered_set类模板的第三个参数提供.

请参阅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

根据您在安德鲁斯回答中的评论，

我认为这个解决方案的问题是： -NAN 将具有与 NAN 不同的哈希值，但对于哈希函数 h 必须保持：如果 x==y 那么 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
}

演示