Мне нужна ассоциативная структура данных с ключами с плавающей запятой, в которой ключи с почти равными значениями объединяются вместе. Я работаю в C ++, но язык на самом деле не имеет значения.
В основном моя текущая стратегия состоит в том, чтобы
обрабатывать только числа с плавающей запятой одинарной точности
использовать unordered_map с пользовательским типом ключа
определить хэш-функцию для типа ключа как
a. для заданного числа с плавающей запятой v разделить v на некоторый допуск, например 0,0005, с двойной точностью, получив k.
b. приведите k к 64-битному целому числу, получая ki
c. return std :: hash of ki.
Прежде всего, существует ли стандартная именованная структура данных, которая делает что-то подобное? Если нет, то есть ли лучший способ сделать это, чем мой общий подход?
Главное, что мне не нравится в следующей реализации, это то, что мне не понятно, какие значения с плавающей запятой будут объединены вместе;Я справляюсь с этим, имея общее представление о том, какие значения в моих входных данных я хочу считать одним и тем же значением, и просто проверяю различные допуски, но было бы неплохо, если бы вы добавили 12.0453 в контейнер, тогда значения 12.0453 +/- 0.0005 были бысчитается равным, если параметр допуска равен 0,0005, но это не так - я даже не думаю, что такое поведение было бы возможно поверх unordered_map, потому что я думаю, что хеш-функция будет зависеть от значений в таблице.
По сути, моя реализация делит числовую линию на одномерную сетку, в которой каждая ячейка сетки имеет ширину в эпсилон-единицы, а затем присваивает значения с плавающей запятой нулевому индексу ячейки сетки, в которую они попадают. У меня вопрос, есть ли лучший способ реализовать ассоциативный контейнер значений с плавающей запятой с допуском, который также равен O (1)? и есть ли проблемы с реализацией ниже?
template<typename V, int P=4>
class float_map
{
private:
struct key {
public:
long long val;
static constexpr double epsilon(int digits_of_precision)
{
return (digits_of_precision == 1) ? 0.5 : 0.1 * epsilon(digits_of_precision - 1);
}
static constexpr double eps = epsilon(P);
key(float fval) : val(static_cast<long long>( fval / eps))
{}
bool operator==(key k) const {
return val == k.val;
}
};
struct key_hash
{
std::size_t operator()(key k) const {
return std::hash<long long>{}(k.val);
}
};
std::unordered_map<key, V, key_hash> impl_;
public:
V& operator[](float f) {
return impl_[key(f)];
}
const V& at(float f) const {
return impl_.at(key(f));
}
bool contains(float f) const {
return impl_.find(f) != impl_.end();
}
double epsilon() const {
return key::eps;
}
};
int main()
{
float_map<std::string> test;
test[12.0453f] = "yes";
std::cout << "epsilon = " << test.epsilon() << std::endl; // 0.0005
std::cout << "12.0446f => " << (test.contains(12.0446f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0447f => " << (test.contains(12.0447f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0448f => " << (test.contains(12.0448f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0449f => " << (test.contains(12.0449f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0450f => " << (test.contains(12.0450f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0451f => " << (test.contains(12.0451f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0452f => " << (test.contains(12.0452f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0453f => " << (test.contains(12.0453f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0454f => " << (test.contains(12.0454f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0455f => " << (test.contains(12.0455f) ? "yes" : "no") << std::endl; // yes
std::cout << "12.0456f => " << (test.contains(12.0456f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0457f => " << (test.contains(12.0457f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0458f => " << (test.contains(12.0458f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0459f => " << (test.contains(12.0459f) ? "yes" : "no") << std::endl; // no
std::cout << "12.0460f => " << (test.contains(12.0460f) ? "yes" : "no") << std::endl; // no
}