Вставка нескольких не-чисел в std :: unordered_set <double> - PullRequest
Новая
       22

Вставка нескольких не-чисел в std :: unordered_set <double>

0 голосов
/ 26 июня 2018

Одним из следствий стандарта IEEE 754 является неинтуитивное поведение std::unordered_set<double>, когда вставляются элементы не числа (NAN s).

В связи с тем, что 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 NAN s вставляются в хэш-набор, все они попадают в один и тот же хэш-контейнер, а производительность N вставок в хэш-набор вырождается в наихудшее время работы - O(N^2).

Например, см. Листинг в конце вопроса или здесь в прямом эфире - вставка NAN занимает на порядок больше времени, чем «обычное» плавающее число.

Мой вопрос: возможно ли (и если да - как) настроить 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
}

Ответы [ 2 ]

0 голосов
/ 26 июня 2018

Из вашего комментария в ответе Эндрюса,

Я думаю, что проблема с этим решением: -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
}

Демо

0 голосов
/ 26 июня 2018

Вы можете определить свой собственный предикат для сравнения ключей и обеспечить равное сравнение 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.

...