9

从 C++ 中的两个(或更多)短整数生成唯一 ID 的最佳方法是什么?我正在尝试唯一标识图中的顶点。顶点包含两到四个短整数作为数据,理想情况下,ID 是它们的某种散列。比起速度或易用性,更喜欢便携性和独特性。

这里有很多很棒的答案,我今晚将全部尝试,看看最适合我的问题。再说几句我在做什么。

该图是来自音频文件的样本集合。我使用该图作为马尔可夫链从旧文件生成一个新的音频文件。由于每个顶点存储几个样本并指向另一个样本,并且样本都是短整数,因此从数据中生成 ID 似乎很自然。将它们组合成一个 long long 听起来不错,但也许generateID我只需要像 0 1 2 3 这样简单的东西。不确定需要多少空间来保证唯一性,如果每个顶点存储 2 个 16 位样本,那么有 2^32 种可能的组合是否正确?那么如果每个顶点存储 4 个样本,那么有 2^64 种可能的组合?

库和平台特定的解决方案与这个问题并不真正相关。我不希望任何可能编译我的程序的人不得不下载其他库或更改代码以适应他们的操作系统。

4

11 回答 11

10

有时最简单的事情效果最好。

您可以只向 Vertex 对象添加一个 id 字段并按构造顺序为其分配一个数字吗?

static int sNextId = 0;
int getNextId() { return ++sNextId; }
于 2008-09-15T18:47:26.170 回答
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;
}
于 2008-09-15T18:46:18.183 回答
0

那么,保证 ID 唯一的唯一方法是使 id 组合比您获得的 id 多

例如,对于 2 条短裤(假设 16 位),您应该使用 32 位 int

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

对于 4 条短裤,你需要一个 64 位的 int 等......

基本上任何其他冲突(多个事物可能获得相同的 id)几乎都可以保证。

然而,获取 id 的另一种方法(我认为会更好)是在插入顶点时将它们分发出去:

unsigned LastId = 0;//global

unsigned GetNewId(){return ++LastId;}

这还具有允许您向每个顶点添加更多/不同数据的效果。但是,如果您希望在不重置的情况下创建超过 2^32 个顶点,这可能不是最好的方法。

于 2008-09-15T18:43:19.673 回答
0

使用 long long 这样您就可以存储所有 4 种可能性,然后对每个 short 进行位移:

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

确保在移动之前进行投射,否则您的数据可能会丢失。

编辑:忘记添加,您应该将它们组合在一起。

于 2008-09-15T18:43:21.017 回答
0

如果您更喜欢可移植性,那么boost::tuple很好:

您需要一个包含 4 个项目的元组:

typedef boost::tuple<uint16,uint16,uint16,uint16> VertexID;

您可以这样分配:

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

boost tuple 已经支持比较、相等等,所以在容器和算法中很容易使用。

于 2008-09-15T19:13:32.643 回答
0

问题中“ID”的定义不是很清楚:您是否需要将其用作快速顶点查找的键?您可以定义一个比较器std::map(参见下面的示例)

您是否需要能够区分具有相同坐标(但在另一个字段中不同)的两个 Vertex 对象?定义一些“id 工厂”(参见单例模式),它生成例如与 Vertex 对象的值无关的整数序列。- 与 Fire Lancer 建议的方式很相似(但要注意线程安全问题!)

在我看来,具有相同坐标的两个顶点是相同的。那么为什么你甚至需要一个额外的ID呢?

只要您在此类型上定义了“严格弱排序”,您就可以将其用作例如 an 中的键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 );
于 2008-09-15T19:18:01.713 回答
0

如果你在 Windows 上,你可以使用CoCreateGUID API,在 Linux 上你可以使用 /proc/sys/kernel/random/uuid,你也可以查看'libuuid'。

于 2008-09-15T19:36:13.230 回答
0

如果您正在构建一个用于存储顶点的哈希表,我可以想到几种避免冲突的方法:

  1. 直接从输入数据生成 ID,不丢弃任何位,并使用足够大的哈希表来保存所有可能的 ID。对于 64 位 ID,后者将是非常有问题的:您将不得不使用一个小于您的 ID 范围的表,因此您将不得不处理冲突。即使使用 32 位 ID,您也需要超过 4GB 的 RAM 才能在不发生冲突的情况下实现这一目标。
  2. 在读取顶点时按顺序生成 ID。不幸的是,这使得搜索先前读取的顶点以更新它们的概率非常昂贵,因为顺序 ID 生成器不是散列函数。如果用于构建马尔可夫链的数据量明显小于马尔可夫链用于生成的数据量(或者如果两者都很小),这可能不是问题。

或者,您可以使用为您处理冲突的哈希表实现(例如unordered_map / hash_map),并专注于应用程序的其余部分。

于 2008-09-16T03:15:06.947 回答
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
}

这从这里

于 2021-05-12T09:09:29.630 回答
0

实现自己的散列可能很乏味,并且容易出现一些在您推出或部分推出系统时难以调试和解决的问题。Windows API 中已经存在更好的唯一 ID 实现。您可以在此处查看更多详细信息;

https://docs.microsoft.com/en-us/windows/win32/api/guiddef/ns-guiddef-guid

于 2021-05-12T15:12:48.623 回答
-1

即兴发挥我会说使用素数,

id = 3 * value1 + 5 * value2 + .... + somePrime * valueN

确保你没有溢出你的 id 空间(长?长长?)。由于您有固定数量的值,因此只需丢弃一些随机素数。不要费心生成它们,列表中有足够的可用内容让您继续使用一段时间。

不过,我对证明有点粗略,也许更数学的人可以把我联系起来。可能与数字的唯一素数分解有关。

于 2008-09-15T18:50:29.750 回答