4

我真的不明白：

我正在读取点，每个点都包含 3 个浮点值，来自二进制文件。将此点保存在 unordered_map 中

因此我尝试从这 3 个浮点值中创建一个键：

第一个意图：只需使用确切的位作为密钥：

unordered_map<string, vector<float>> points;
string vecToKey( float* a ) {
char bytes[12];
memcpy(bytes, a, 12);
return string(bytes);
}

关键是我绝对想以这种方式消除相同的点，但是

在一个读取大约 21374 点的示例项目中，地图结果大小 = 10640 点

使用以下方法作为密钥创建导致 10687 点的正确结果

string vec3ToKey( float a[3] ) {
float a1[3];
a1[0] = a[0];
a1[1] = a[1];
a1[2] = a[2];
stringstream ss;
boost::archive::text_oarchive oa(ss);
oa << a1;
return ss.str();
}

问题是速度。第二种方法需要大约 16 秒，第一种方法只需 1-2 秒……我无法解释自己为什么会有差异……

我欣赏每一个想法:)

4

5 回答 5

5 
string vecToKey( float* a ) {
  char bytes[12];
  memcpy(bytes, a, 12);
  return string(bytes);
}

您正在使用的字符串构造函数在第一个空字节处停止。浮点值可以包含空字节。所以字符串可能不能准确地表示三个浮点数。您可以通过在其中粘贴一个断言来查看：

  string s(bytes);
  assert(s.size() == sizeof bytes);
  return s;
}

另一个问题是它bytes可能不包含空字节，并且程序可能会将随机垃圾复制到字符串中或以其他方式表现出未定义的行为。

我建议您不要尝试以这种方式滥用字符串。你想要一个三个浮点数的键，所以使用一个完全代表的键：std::array<float,3>。或者更好的是使用“Point”类，因为这就是三个浮点数所代表的。

由于没有内置的数组哈希函数，您可以使用以下内容：

// taken from http://stackoverflow.com/questions/6899392/generic-hash-function-for-all-stl-containers
template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct Hasher {
    size_t operator() (std::array<float,3> const &v) {
        size_t h = std::hash<float>()(v[0]);
        hash_combine(h,v[1]);
        hash_combine(h,v[2]);
        return h;
    }
};


std::unordered_map<std::array<float,3>,vector<float>,Hasher> map;
于 2012-05-29T18:36:26.837 回答
1

将索引更改为整数类型，例如unsigned int。尝试更像这样的代码：

unsigned int vec3toKey( float a[3] )
{
   unsigned char *in = reinterpret_cast<unsigned char>(a);
   unsigned int ret = 2654435761u;
   for(int i = 0; i < (3 * sizeof(float)); ++i)
     ret = (ret * 2654435761u) ^ *in++;
   return ret;
}
于 2012-05-29T18:25:16.930 回答
0

通用容器可以使用任何类型作为键。当然，您在此应用程序中有某种点类。那应该是你的关键。

显然，您需要重载散列函数才能使用您自己的类型（感谢 DavidSchwartz）。这个问题解决了：

C++ unordered_map 用户定义类型

PS：如果你没有点结构或类，你可能想要一个：p

于 2012-05-29T18:27:33.793 回答
0

http://www.boost.org/doc/libs/1_49_0/doc/html/hash/combine.html

于 2012-05-29T18:45:24.663 回答
0

我试图使用@bames53 解决方案，但遇到了一些编译问题。在考虑这个答案时，这里给出的@bames53 是我拥有的最终版本

  #include <iostream>
  #include <string>
  #include <vector>
  #include <unordered_map>


  template <typename C> struct Hasher{
                      typedef typename C::value_type value_type;
                      inline std::size_t operator() (const C &c) const{
                          std::size_t seed = 0;
                          for(typename C::const_iterator it = c.begin(); it != c.end(); ++it){
                              std::hash<value_type> hasher;
                              seed ^= hasher(*it) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
                          }
                          return seed;
                      }
  };

  int main()
  {

              std::unordered_map<std::array<float, 3>, std::vector<float>, Hasher<std::array<float, 3>>> E;
                  std::array<float, 3> t1 = {34, 56,78};
                  std::vector<float> result;
                  result.push_back(45);
                  E[t1] = result;

  }
于 2019-07-18T09:21:47.140 回答