查找基于世界上的地位在一维数组通用的项目？ [英] Find generic item in 1D array based on world position?
问题描述
我有数据阵列（通用vertexdata）。我需要能够搜索用于基于位置的数组的元素。目前，每个顶点元素记录自己的位置，我只是使用 for循环通过每一个元素搜索和比较的位置。我必须这样做了很多我的程序中，它的表现相当关键。通过每一个元素循环似乎真的，真的很低效。
I have an array of data (generic vertexdata). I need to be able to search for elements of the array based on a position. Currently, each vertex element records its own position and I simply use a for-loop to search through every element and compare the positions. I have to do this a LOT in my program and it's fairly performance-critical. Looping through every single element seems really, really inefficient.
我使用C ++，顺便说一句。
I using C++, btw.
我的问题是：有没有更好的办法？也就是说，有没有直接访问基于三维位置，必要元素的一种方式？该位置是整数，所以可能有帮助。
My question is this: Is there a better way? That is, is there a way of accessing the necessary element directly based on a 3D position? The positions are ints, so that might help.
我想过简单地使用3D阵列（即顶点[256] [256] [256]），但我不能浪费内存，因为只有约30-50％的顶点位置实际上包含顶点。也许这可以与指针的实现？他们使用的内存没有分配时？
I thought about simply using a 3D array (ie. vertex[256][256][256]), but I can't afford the wasted memory, since only about 30-50% of the vertex positions actually contain a vertex. Maybe this could be achieved with pointers? Do they use memory when not assigned?
的另一个问题三维数组是顶点可以跨越几乎无限区域，这将使一个非常非常大的。数组s $ P $垫。另外，顶点被有效地动态地添加，这意味着他们可以在一个与所述被添加; 0的位置，这意味着该阵列将必须向后移动并每一个元素重新分配
The other problem with a 3D array is that the vertices can be spread across a virtually infinite area, which would make for a very, very large array. Also, the vertices are effectively added dynamically which means they could be added at a <0 position, meaning the array would have to be shifted backwards and every element reassigned.
如果任何人有任何建议，我会非常感激：）
If anyone has any suggestions, I'd be very grateful :)
推荐答案
您可以考虑的解决方案是用一个稀疏网格作为您的ADT。
A solution you may consider would be to use a sparse grid as your ADT.
的的std :: unordered_map 是一个哈希地图，可用于创建稀疏网格数据结构。如果你写的三维矢量好的哈希，你可以得到很大的O（1）的读取性能将得到接近原始阵列的性能。
The std::unordered_map is a hashed map which can be used to create the sparse grid data structure. If you write a good hash for the 3d-vectors, you can get great O(1) read performance which will get close to the performance of a the raw array.
散列地图还允许你使用一个几乎有无限区域，以及（当然约束将是底层数据类型。
The hashed map will also allow you to use a "virtually infinite" area as well (of course the constraint would be in the underlying data type.
抱歉耽搁。
有关unordered_map，这是一个好的信息资源： unordered_map哈希函数的C ++
For unordered_map, this is a good resource for information: unordered_map hash function c++
我在自己的项目实施采用一对整数，但我敢肯定，它可用于三维坐标。
I implemented in my own project using a pair of ints, but I'm sure that it could be used for three dimensional coordinates.
namespace std {
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);
}
template<> struct hash<pair<int, int> > {size_t operator()(pair<int, int> x) const { size_t seed=0; hash_combine(seed, x.first); hash_combine(seed, x.second); return(seed); } };
}
然后你就可以宣布你的 unordered_map
std::unordered_map<std::pair<int, int>, [VALUE] > my_map; //[VALUE] being the data type of vertex
在这之后，你可以把像一个普通的的std ::地图的结构。如果你不知道如何使用一个，有很多的例子在那里。
After this, you can treat the structure like a regular std::map. If you are not sure how to use one, there are lots of examples out there.
有关三维坐标，你可以声明自己的结构
For 3d coordinates, you can declare your own struct
struct vector
{
int i,j,k;
};
然后修改散列函数（格式化的可读性）
And then modify the hash function (formatted for readability)
template<> struct hash<vector > {
size_t operator()(vector x) const {
size_t seed=0;
hash_combine(seed, x.i);
hash_combine(seed, x.j);
hash_combine(seed, x.k);
return(seed);
}
};
这篇关于查找基于世界上的地位在一维数组通用的项目？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
