logo标签列表

在c++中生成唯一标识符

c++hash
9
什么是在C++中从两个（或更多）short int生成唯一ID的最佳方法？我试图唯一地标识图中的顶点。顶点包含两到四个short int作为数据，理想情况下，ID将是它们的某种哈希值。优先考虑可移植性和唯一性，而不是速度或易用性。
这里有很多好的答案，我今晚会尝试它们并看看哪个最适合我的问题。我再多说几句我正在做什么。
该图是来自音频文件的样本集合。我使用图作为马尔科夫链，从旧文件生成新的音频文件。由于每个顶点存储几个样本并指向另一个样本，并且所有样本都是short int，因此从数据生成ID似乎很自然。将它们组合成一个long long听起来不错，但也许只需要一个0 1 2 3 generateID就足够了。如果每个顶点存储2个16位样本，则需要多少空间才能保证唯一性？有2^32种可能的组合，对吗？因此，如果每个顶点存储4个样本，则有2^64种可能的组合？
与库和平台特定的解决方案无关。我不希望其他人编译我的程序需要下载其他库或更改代码以适应其操作系统。
11个回答
10

有时候最简单的方法效果最好。

你能否只是给顶点对象添加一个id字段，并按照构造顺序为其分配一个数字？

static int sNextId = 0;
int getNextId() { return ++sNextId; }
5

一种简单的解决方案是使用一个64位整数，其中低16位是第一个顶点坐标，接下来的16位是第二个顶点坐标，以此类推。这对于所有顶点都是唯一的，但不是非常紧凑。

所以这里有一些半吊子代码来实现这个功能。希望我得到了正确的转换。

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的绝佳想法，请参见评论）。 这种方式非常干净：

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;
}
2
我真的认为union会提供更清晰的方法来做到这一点，但那只是品味问题。 - Leon Timmermans
5
使用联合体进行类型转换是未定义行为。 - scpayson
0

尝试使用这个：

int generateID()
{
    static int s_itemID{ 0 };
    return s_itemID++; // makes copy of s_itemID,
                         increments the real s_itemID, 
                         then returns the value in the copy
}

这里来自这里。

OP提出了一个不同的问题：如何生成给定2或4个短整数的唯一ID。此外，您的解决方案已经作为解决方案＃2发布。 - zkoza
0

确保ID唯一的唯一方法是使用比获取ID更多的ID组合

例如，对于2个shorts（假设为16位），应使用32位int

int ID = ((int)short1 << 16) | short2;

对于4个shorts，您需要一个64位的int，等等...

基本上任何其他事情的碰撞（多个东西可能会获得相同的id）都几乎是确定的。

然而，一个不同的方法（我认为更好的方法）获得ids将是在插入顶点时分配它们：

unsigned LastId = 0;//global

unsigned GetNewId(){return ++LastId;}

这也有助于您向每个顶点添加更多/不同的数据。但是，如果您希望创建超过2^32个顶点而不重置它，则这可能不是最佳方法。

使用“and”将始终导致低8位全部为0。应该将其移位16并执行或操作。 - Patrick
0
如果您喜欢可移植性，那么 boost::tuple 是不错的选择：
您需要一个包含 4 个项目的元组：
typedef boost::tuple<uint16,uint16,uint16,uint16> VertexID;

你可以像这样赋值：

VertexID id = boost::make_tuple(1,2,3,4);

Boost元组已经支持比较、相等等操作，因此在容器和算法中使用起来非常方便。

0
问题中“ID”的定义不是很清晰：您是否需要将其用作快速顶点查找的键？ 您可以为std::map定义一个比较器（请参见下面的示例）。
您是否需要能够区分具有相同坐标但在另一个字段中不同的两个顶点对象？定义一些“id工厂”（参见单例模式），它生成例如与Vertex对象的值无关的int序列。-就像Fire Lancer建议的那样（但请注意线程安全问题！）
我认为，具有相同坐标的两个顶点是相同的。那么，您为什么需要额外的ID呢？
只要在此类型上定义一个“严格弱排序”，您就可以将其用作例如std::map中的键。
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 );
0

使用long long可以存储所有4种可能性，然后对每个short进行位移：

((long long)shortNumberX) << 0、4、8或12

确保在移位之前进行类型转换，否则数据可能会丢失。

编辑：忘记添加了，你应该将它们进行OR运算。

0

如果您使用的是Windows系统，您可以使用CoCreateGUID API；如果您使用的是Linux系统，您可以使用/proc/sys/kernel/random/uuid，您还可以查看'libuuid'。

0
如果您正在构建哈希表以存储顶点，我可以想到几种避免碰撞的方法：
  1. 直接从输入数据生成ID而不丢弃任何位，并使用足够大的哈希表来容纳所有可能的ID。对于64位ID，后者将非常棘手：您必须使用比ID范围小的表，因此您必须处理碰撞。即使是32位ID，您也需要超过4GB的RAM才能在没有冲突的情况下完成此操作。
  2. 在读取顶点时按顺序生成ID。不幸的是，这使得搜索先前读取的顶点以更新其概率变得非常昂贵，因为顺序ID生成器不是哈希函数。如果用于构建马尔可夫链的数据量明显小于用于生成马尔可夫链的数据量（或如果它们都很小），则可能不是问题。

另外，您可以使用一个实现了冲突处理的哈希表实现（例如unordered_map/hash_map），并将重点放在应用程序的其余部分。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接