•  09-06-2019
  •  | 
  •  

题

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

这里有很多很好的答案，今晚我将尝试所有答案，看看什么最适合我的问题。关于我正在做的事情，再多说几句。

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

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

有帮助吗？

解决方案

一个简单的解决方案是使用 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;
}

其他提示

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

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

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

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

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

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

编辑：忘了添加，你应该将它们或在一起。

如果你更喜欢便携性，那么 提升::元组 很好：

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

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

您可以这样分配：

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

boost元组已经支持比较、相等等，因此很容易在容器和算法中使用。

问题中“ID”的定义不太清楚：您需要使用它作为快速顶点查找的键吗？您可以定义一个比较器 std::map （参见下面的示例）

您是否需要能够区分具有相同坐标（但在另一个字段中不同）的两个 Vertex 对象？定义一些“id 工厂”（cfr.单例模式）生成例如与 Vertex 对象的值无关的整数序列。- 就像 Fire Lancer 建议的那样（但要注意线程安全问题！）

在我看来，具有相同坐标的两个顶点是相同的。那么为什么您还需要额外的身份证件呢？

一旦你定义了 '严格弱序' 在这种类型上，您可以将其用作例如中的键一个 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 );

如果您使用的是 Windows，您可以使用共同创建GUID API，在Linux上你可以使用/proc/sys/kernel/random/uuid，你也可以查看'libuuid'。

如果您正在构建一个哈希表来存储顶点，我可以想出几种方法来避免冲突：

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

或者，您可以使用哈希表实现来为您处理冲突（例如 无序映射/哈希映射），然后专注于应用程序的其余部分。

保证 ID 唯一的唯一方法是使 ID 组合比您获取的 ID 多

例如，对于 2 个 Shorts（假设 16 位），您应该使用 32 位 int 

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

对于 4 个 Shorts，你需要一个 64 位 int，等等......

基本上任何其他东西都会发生冲突（多个东西可能会获得相同的 id）。

然而，获取 id 的另一种方法（我认为更好）是在插入顶点时将它们分发出去：

unsigned LastId = 0;//global

unsigned GetNewId(){return ++LastId;}

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

我会即兴地说使用素数，

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

确保你的 id 空间没有溢出（长？长长长？）。由于您已经获得了固定数量的值，因此只需丢弃一些随机素数即可。不必费心生成它们，列表中有足够的可用内容可以让您暂时使用。

不过我对证明有点粗略，也许更数学的人可以帮我。可能与数字的唯一素因数分解有关。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top