从C中的两个(或更多)短整数生成唯一ID的最佳方法是什么？我试图唯一地标识图中的顶点。顶点包含2到4个短整数作为数据，理想情况下，ID是它们的某种哈希。相对于速度或易用性，更喜欢可移植性和独特性。
这里有很多很棒的答案，我今晚将尝试所有答案，以找出最适合我的问题的方法。关于我在做什么，再说几句话。
该图是来自音频文件的样本的集合。我将图形用作马尔可夫链，从旧文件生成新的音频文件。由于每个顶点都存储一些样本并指向另一个样本，并且这些样本都是短整数，因此从数据生成ID似乎很自然。将它们组合成很长的声音听起来不错，但是我只需要像0 1 2 3 generateID这样简单的东西即可。不知道要保证唯一性需要多少空间，如果每个顶点存储2个16位样本，那么2 ^ 32种可能的组合正确吗？因此，如果每个顶点存储4个样本，那么有2 ^ 64种可能的组合吗？
与库和平台相关的解决方案与该问题并不真正相关。我不希望其他可能编译我的程序的人不得不下载其他库或更改代码以适合他们的操作系统。
有时候最简单的方法效果最好。
能否仅将一个id字段添加到Vertex对象并按构造顺序为其分配一个数字？
1
2
| static int sNextId = 0;
int getNextId() { return ++sNextId; } |
一个简单的解决方案是使用64位整数，其中低16位是第一个顶点坐标，后16位是第二个顶点坐标，依此类推。尽管不是非常紧凑，但它对于所有顶点都是唯一的。
所以这是一些半定的代码。希望我的演员表正确。
1
2
3
4
5
6
| uint64_t generateId( uint16_t v1, uint16_t v2, uint16_t v3, uint16_t v4)
{
uint64_t id;
id = v1 | (((uint64_t)v2) << 16) | (((uint64_t)v3) << 32) | (((uint64_t)v4) << 48);
return id;
} |
可选地，这可以通过工会来完成(Leon Timmermans的好主意，请参见评论)。这样很干净：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| struct vertex
{
uint16_t v1;
uint16_t v2;
uint16_t v3;
uint16_t v4;
};
union vertexWithId
{
vertex v;
uint64_t id;
};
int main()
{
vertexWithId vWithId;
// Setup your vertices
vWithId.v.v1 = 2;
vWithId.v.v2 = 5;
// Your id is automatically setup for you!
std::cout <<"Id is" << vWithId.id << std::endl;
return 0;
} |
如果您要构建用于存储顶点的哈希表，我可以想到几种避免冲突的方法：
直接从输入数据生成ID，而不会丢掉任何位，并使用足够大的哈希表来容纳所有可能的ID。使用64位ID时，后者将非常成问题：您将不得不使用一个小于ID范围的表，因此必须处理冲突。即使使用32位ID，您也需要超过4GB的RAM才能顺利实现这一目标。
在顶点读取时，顺序生成ID。不幸的是，这使得搜索先前读取的顶点以更新其概率非常昂贵，因为顺序ID生成器不是哈希函数。如果用于构造马尔可夫链的数据量明显小于用于马尔可夫链生成的数据量(或者它们都很小)，那么这可能不是问题。
或者，您可以使用哈希表实现为您处理冲突(例如unordered_map / hash_map)，并专注于应用程序的其余部分。
如果在Windows上，则可以使用CoCreateGUID API，在Linux上，可以使用/ proc / sys / kernel / random / uuid，也可以查看" libuuid"。
问题中" ID"的定义尚不清楚：您是否需要将其用作快速查找顶点的键？您可以为std::map定义一个比较器(请参见下面的示例)
您是否需要能够区分两个具有相同坐标(但在另一个字段中不同)的顶点对象？定义一些生成例如一系列整数，与Vertex对象的值无关。 -Fire Lancer的建议方式很多(但请注意线程安全性问题！)
在我看来，两个具有相同坐标的顶点是相同的。那么，为什么还需要一个额外的ID？
一旦您为此类型定义了"严格弱排序"，就可以将其用作例如std::map，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| struct Vertex {
typedef short int Value;
Value v1, v2;
bool operator<( const Vertex& other ) const {
return v1 < other.v1 || ( v1 == other.v1 && v2 < other.v2 ) ;
};
Vertex x1 = { 1, 2 };
Vertex x2 = { 1, 3 };
Vertex y1 = { 1, 2 }; // too!
typedef std::set<Vertex> t_vertices;
t_vertices vertices;
vertices.insert( x1 );
vertices.insert( x2 );
vertices.insert( y1 ); // won't do a thing since { 1, 2 } is already in the set.
typedef std::map<Vertex, int> t_vertex_to_counter;
t_vertex_to_counter count;
count[ x1 ]++;
assert( count[x1] == 1 );
assert( count[y1] == 1 );
count[ x2 ]++;
count[ y1 ]++;
assert( count[x1] == 2 );
assert( count[y1] == 2 ); |
如果您更喜欢可移植性，那么boost :: tuple很不错：
您需要一个包含4个项目的元组：
1
| typedef boost::tuple<uint16,uint16,uint16,uint16> VertexID; |
您可以这样分配：
1
| VertexID id = boost::make_tuple(1,2,3,4); |
boost元组已经支持比较，相等等，因此很容易在容器和算法中使用。
使用长时长，以便您可以存储所有4种可能性，然后将每个短时位移位：
(((long long)shortNumberX)<< 0、4、8或12
请确保在转换之前先进行投射，否则数据可能会掉到头。
编辑：忘记添加，您应该将它们或在一起。
确保ID唯一的唯一方法是使ID组合比您从
获取的ID多
例如，对于2个短裤(假设为16位)，应使用32位int
1
| int ID = ((int)short1 << 16) | short2; |
对于4个短裤，您将需要一个64位int，依此类推...
基本上可以确保发生其他冲突(多个事物可能具有相同的id)。
但是获取ID的另一种方法(我认为会更好)是在插入顶点时将它们分发出去：
1
2
3
| unsigned LastId = 0;//global
unsigned GetNewId(){return ++LastId;} |
这还具有允许您向每个顶点添加更多/不同数据的效果。但是，如果您希望创建多个2 ^ 32个顶点而不重置它，则这可能不是最佳方法。
我要说的是使用质数，
1
| id = 3 * value1 + 5 * value2 + .... + somePrime * valueN |
确保您没有溢出ID空间(长？长长？)。由于您有固定数量的值，所以只需要填充一些随机素数即可。不用担心生成它们，列表中有足够的可用空间让您暂时离开。
不过，我对证明有些粗略，也许有一些数学家可以将我联系起来。可能与数的唯一素数分解有关。
