时间戳

首页 > 解决方案 > 将多个非数字插入 std::unordered_set

c++ - 将多个非数字插入 std::unordered_set

问题描述

std::unordered_set<double>IEEE 754 标准的后果之一是在插入非数字元素时的非直观行为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元素，无论插入NAN的 s （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
}

标签： c++c++11ieee-754

解决方案

您可以定义自己的谓词来比较键，并为此目的确保 NaN 比较相等。这可以作为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。

推荐阅读