Por que os compiladores perdem a vetorização aqui?

Question

fghoussen

Asked: 2023-08-22 22:02:20 +0800 CST2023-08-22 22:02:20 +0800 CST 2023-08-22 22:02:20 +0800 CST

Como declarar/usar um `unordered_set` para trigêmeos (`tuple`) usando comparador personalizado?

772

Como declarar/usar um unordered_setpara trigêmeos ( tuple) usando comparador personalizado?

Preciso armazenar trigêmeos de float(tratados como tuple) em um conjunto para verificar possíveis duplicatas. Como se trata de float, acho que usar comparação regular com ==não funcionará, portanto, é necessário personalizar a comparação.

Este código mínimo não compila:

>> cat unordered_set_triplet.cpp 
#include <unordered_set>
#include <tuple>
#include <limits> // numeric_limits
#include <cmath> // fabs
#include <functional> // hash

using triplet = std::tuple<float, float, float>;
bool triplet_equal(triplet const & lhs, triplet const & rhs) {
  float const eps = std::numeric_limits<float>::epsilon();
  if (std::fabs(std::get<0>(lhs) - std::get<0>(rhs)) > eps) return false;
  if (std::fabs(std::get<1>(lhs) - std::get<1>(rhs)) > eps) return false;
  if (std::fabs(std::get<2>(lhs) - std::get<2>(rhs)) > eps) return false;
  return true;
}
using unordered_set_triplet = std::unordered_set<triplet,
                                                 std::hash<triplet>,
                                                 decltype(triplet_equal)>;

int main() {
  //unordered_set_triplet s; // Compilation: KO...
  unordered_set_triplet s(10, std::hash<triplet>, triplet_equal);
  s.insert({1.f, 2.f, 3.f});
}

Eu recebo:

>> g++ -std=c++20 -o unordered_set_triplet unordered_set_triplet.cpp 
In file included from /usr/include/c++/12/bits/hashtable.h:35,
                 from /usr/include/c++/12/unordered_set:46,
                 from unordered_set_triplet.cpp:1:
/usr/include/c++/12/bits/hashtable_policy.h: In instantiation of ‘struct std::__detail::_Hashtable_ebo_helper<0, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&), false>’:
/usr/include/c++/12/bits/hashtable_policy.h:1631:12:   required from ‘struct std::__detail::_Hashtable_base<std::tuple<float, float, float>, std::tuple<float, float, float>, std::__detail::_Identity, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&), std::hash<std::tuple<float, float, float> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, true, true> >’
/usr/include/c++/12/bits/hashtable.h:182:11:   required from ‘class std::_Hashtable<std::tuple<float, float, float>, std::tuple<float, float, float>, std::allocator<std::tuple<float, float, float> >, std::__detail::_Identity, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&), std::hash<std::tuple<float, float, float> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >’
/usr/include/c++/12/bits/unordered_set.h:100:18:   required from ‘class std::unordered_set<std::tuple<float, float, float>, std::hash<std::tuple<float, float, float> >, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&)>’
unordered_set_triplet.cpp:21:26:   required from here
/usr/include/c++/12/bits/hashtable_policy.h:1204:11: error: data member ‘std::__detail::_Hashtable_ebo_helper<0, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&), false>::_M_tp’ invalidly declared function type
 1204 |       _Tp _M_tp{};
      |           ^~~~~
/usr/include/c++/12/bits/hashtable.h: In instantiation of ‘class std::_Hashtable<std::tuple<float, float, float>, std::tuple<float, float, float>, std::allocator<std::tuple<float, float, float> >, std::__detail::_Identity, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&), std::hash<std::tuple<float, float, float> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >’:
/usr/include/c++/12/bits/unordered_set.h:100:18:   required from ‘class std::unordered_set<std::tuple<float, float, float>, std::hash<std::tuple<float, float, float> >, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&)>’
unordered_set_triplet.cpp:21:26:   required from here
/usr/include/c++/12/bits/hashtable.h:665:7: error: function returning a function
  665 |       key_eq() const
      |       ^~~~~~
In file included from /usr/include/c++/12/unordered_set:47:
/usr/include/c++/12/bits/unordered_set.h: In instantiation of ‘class std::unordered_set<std::tuple<float, float, float>, std::hash<std::tuple<float, float, float> >, bool(const std::tuple<float, float, float>&, const std::tuple<float, float, float>&)>’:
unordered_set_triplet.cpp:21:26:   required from here
/usr/include/c++/12/bits/unordered_set.h:632:7: error: function returning a function
  632 |       key_eq() const
      |       ^~~~~~
unordered_set_triplet.cpp: In function ‘int main()’:
unordered_set_triplet.cpp:21:49: error: expected primary-expression before ‘,’ token
   21 |   unordered_set_triplet s(10, std::hash<triplet>, triplet_equal);
      |                                                 ^

Como consertar isto?

EDITAR

Também não funciona usando (ordered) set:

>> cat set_triplet.cpp 
#include <iostream>
#include <set>
#include <tuple>
#include <limits> // numeric_limits
#include <cmath> // fabs
#include <functional> // hash

using triplet = std::tuple<float, float, float>;
bool triplet_equal(triplet const & lhs, triplet const & rhs) {
  float const eps = std::numeric_limits<float>::epsilon();
  if (std::fabs(std::get<0>(lhs) - std::get<0>(rhs)) > eps) return false;
  if (std::fabs(std::get<1>(lhs) - std::get<1>(rhs)) > eps) return false;
  if (std::fabs(std::get<2>(lhs) - std::get<2>(rhs)) > eps) return false;
  return true;
}
using set_triplet = std::set<triplet, std::hash<triplet>, decltype(triplet_equal)>;

int main() {
  //set_triplet s; // Compilation: KO...
  set_triplet s(10, std::hash<triplet>, triplet_equal);
  s.insert({1.f, 2.f, 3.f});
  s.insert({1.0000001f, 2.0000001f, 3.0000001f});
  for (auto const & t : s) std::cout << std::get<0>(t) << ", " << std::get<1>(t) << ", " << std::get<2>(t) << std::endl;
}

Qual recipiente poderia ser apropriado para uso? tripletpode ser visto um ponto 3D (XYZ): preciso manipular/detectar pontos duplicados.

MELHOR SOLUÇÃO ATÉ AGORA

Usando tuplas feitas de números inteiros iconstruídos desta forma i = (int) 1000000 * f a partir de float fe usando set (pois operator<respeitará a ordem estrita com precisão de até 6 dígitos após a multiplicação por 1.000.000).

>> cat set_uint32_triplet.cpp 
#include <iostream>
#include <set>
#include <tuple>

using triplet_uint32 = std::tuple<uint32_t, uint32_t, uint32_t>;
using triplet_float = std::tuple<float, float, float>;
triplet_uint32 convert(triplet_float const & f) {
  uint32_t precision = 1000000; // Allow for 6-digit precision.
  uint32_t x = (uint32_t) (std::get<0>(f) * precision);
  uint32_t y = (uint32_t) (std::get<1>(f) * precision);
  uint32_t z = (uint32_t) (std::get<2>(f) * precision);
  return {x, y, z};
}

int main() {
  triplet_float pt1 = {1.f, 2.f, 3.f};
  triplet_float pt2 = {1.0000001f, 2.0000001f, 3.0000001f}; // Considered     duplicate with pt1.
  triplet_float pt3 = {1.000001f,  2.000001f,  3.000001f};  // Considered NOT duplicate with pt1.

  std::set<triplet_uint32> s;
  s.insert(convert(pt1));
  s.insert(convert(pt2));
  s.insert(convert(pt3));
  std::cout << "set size " << s.size() << std::endl;
  for (auto const & t : s) std::cout << "set item " << std::get<0>(t) << ", " << std::get<1>(t) << ", " << std::get<2>(t) << ", " << std::endl;
}

>> g++ -std=c++20 -o set_uint32_triplet set_uint32_triplet.cpp

>> ./set_uint32_triplet 
set size 2
set item 1000000, 2000000, 3000000, 
set item 1000000, 2000001, 3000001,

2 respostas

Voted

Jeffrey · Answer 1 · 2023-08-23T01:34:33+08:00

Jeffrey

2023-08-23T01:34:33+08:002023-08-23T01:34:33+08:00

Provavelmente esta não é a resposta que você deseja, mas oferece uma solução para o problema de transitividade da resposta aceita.

Use std::tuple<int, int, int>e quantize seus floats multiplicando-os por alguma constante (digamos 10.000) e arredondando-os para baixo. O fator de escala dependerá do seu domínio.

Se você precisar manter o valor original, use um unordered_map. Use a tupla int para chave e adicione uma tupla flutuante para o valor. Então, ao pesquisar um determinado trigêmeo, você pode procurar a tupla adjacente em cada um dos três valores.

Isso é mais complexo e mais trabalhoso, mas seria uma abordagem mais correta e evitaria o UB devido a problemas de transitividade.

0

Jan Schultke · Answer 2 · 2023-08-22T22:26:55+08:00

Problemas com KeyEqual

Em primeiro lugar, o KeyEqual fornecido para std::unordered_setnão pode ser uma função, e é isso que você está tentando fazer decltype(triplet_equal). No entanto, pode ser um ponteiro de função. Normalmente, você deve usar um objeto de função da seguinte maneira:

struct triplet_equal {
    // note: static constexpr only since C++23, otherwise remove those two
    static constexpr bool operator()(triplet const & lhs, triplet const & rhs) const {
        float const eps = std::numeric_limits<float>::epsilon();
        if (std::fabs(std::get<0>(lhs) - std::get<0>(rhs)) > eps) return false;
        if (std::fabs(std::get<1>(lhs) - std::get<1>(rhs)) > eps) return false;
        if (std::fabs(std::get<2>(lhs) - std::get<2>(rhs)) > eps) return false;
        return true;
    }
};

// ...
std::unordered_set<triplet, std::hash<triplet>, triplet_equal> s(10);

Você não precisa fornecer nenhum valor para o hash ou para triplet_equalo construtor porque eles são construtíveis por padrão.

Problemas com Hash

O próximo grande problema é que a biblioteca padrão não possui std::hashespecialização para tuplas. Procure no hash genérico por tuplas em unordered_map / unordered_set se quiser fazer o seu próprio.

No entanto, mesmo que existisse, permanece o problema de que duas tuplas iguais (onde a igualdade é determinada por triplet_equal) também devem ter o mesmo hash. Você teria que std::hashse especializar para que duas tuplas iguais sempre tivessem o mesmo hash, apesar da imprecisão do ponto flutuante. Você pode conseguir fazer isso quantizando floats, mas imagino que seria muito difícil fazer isso corretamente.

Alternativa: use `std::set`e forneça um Compare

Seria muito mais fácil de usar std::set, o que exige apenas que você implemente uma comparação menor que:

// checks whether x < y after quantization to a multiple of epsilon
constexpr float eps_less_than(float x, float y) {
    constexpr float e = std::numeric_limits<float>::epsilon();
    // use simple comparison if numbers are far apart
    float d = x - y;
    if (std::fabs(d) >= 2 * e) {
        return d < 0;
    }
    return std::floor(x * (1 / e)) < std::floor(y * (1 / e));
}

// lexicographical comparison
struct triplet_less {
    // constexpr since C++23
    constexpr bool operator()(triplet const & lhs, triplet const & rhs) const {
        if (eps_less_than(std::get<0>(lhs), std::get<0>(rhs))) return true;
        if (eps_less_than(std::get<0>(rhs), std::get<0>(lhs))) return false;

        if (eps_less_than(std::get<1>(lhs), std::get<1>(rhs))) return true;
        if (eps_less_than(std::get<1>(rhs), std::get<1>(lhs))) return false;

        if (eps_less_than(std::get<2>(lhs), std::get<2>(rhs))) return true;
        return false;
    }
};

int main() {
    std::set<triplet, triplet_less> s;
    s.insert({1.f, 2.f, 3.f});
}

Veja o exemplo ao vivo no Compiler Explorer

Notas Adicionais

Seria muito melhor não usar std::tuple, mas usar um tipo agregado simples como segue:

struct vec3 {
    float x, y, z;
    // C++20: default all comparison operators
    // (you still need a custom vec3_equal to deal with precision issues)
    friend auto constexpr operator<=>(vec3 const&, vec3 const&) = default;
};

Com operadores de comparação padrão, é muito fácil obter todas as funcionalidades do std::tuple, e você pode escrever lhs.xem vez de precisar std::get<0>(lhs)de outros aborrecimentos.

Como declarar/usar um `unordered_set` para trigêmeos (`tuple`) usando comparador personalizado?

Problemas com KeyEqual

Problemas com Hash

Alternativa: use `std::set`e forneça um Compare

Notas Adicionais

destaque o código em HTML usando <font color="#xxx">

Por que a resolução de sobrecarga prefere std::nullptr_t a uma classe ao passar {}?

Você pode usar uma lista de inicialização com chaves como argumento de modelo (padrão)?

Por que as compreensões de lista criam uma função internamente?

Estou tentando fazer o jogo pacman usando apenas o módulo Turtle Random e Math

java.lang.NoSuchMethodError: 'void org.openqa.selenium.remote.http.ClientConfig.<init>(java.net.URI, java.time.Duration, java.time.Duratio

Por que 'char -> int' é promoção, mas 'char -> short' é conversão (mas não promoção)?

Por que o construtor de uma variável global não é chamado em uma biblioteca?

Comportamento inconsistente de std::common_reference_with em tuplas. Qual é correto?

Somente operações bit a bit para std::byte em C++ 17?

Como declarar/usar um `unordered_set` para trigêmeos (`tuple`) usando comparador personalizado?

2 respostas

Problemas com KeyEqual

Problemas com Hash

Alternativa: use std::sete forneça um Compare

Notas Adicionais

relate perguntas

Alternativa: use `std::set`e forneça um Compare