代码之家 › 专栏 › 技术社区 › ead

在std::无序集合中插入多个非a-数字<double>

ieee-754 c++11 c++

ead · 技术社区 · 6 年前

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 ( see it live )以下内容: 南 和 南 啊!

我的主要问题是 N 南 s被插入到哈希集中,它们都命中同一个哈希桶,并且 n个 插入到哈希集中会退化到最坏的运行时间- O(N^2) 是的。

例如,请参见问题末尾的列表或 here live -插入 南 比一个“正常”的浮点数花费更多数量级的时间。

我的问题是:是否有可能(如果有-如何)调整 std::无序集合<双> 以这种方式,最多只有一个 南 -元素在集合中,无论插入的味道如何 南 S公司( 南 ,,- 南 等等?

列表:

#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
}

2 回复 | 直到 6 年前

rmawatson 6 年前

从你在安德鲁斯回答中的评论来看,

我认为这个解决方案的问题是:nan的散列值与nan不同,但是对于散列函数h必须保持:如果x==y,那么h(x)==h(y)

这与散列不同,因此如果需要,还需要定义自己的散列函数 h(-NAN) == h(NAN) …

(由@andrew answer补充)

#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

Andrew 6 年前

您可以定义自己的谓词来比较键,并为此目的确保nan compare相等。这可以作为第三个参数提供给 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 可能哈希到不同的值。如果您想将它们处理为相同的,则需要提供第二个模板参数hash函数的不同实现。这将检测任何nan并每次散列相同的nan。