c++ - 通过唯一标识符描述数字列表

Question

我认为这是一个非常琐碎的问题。我有一个粒子系统，每个粒子都有一个坐标。我需要用数字描述系统的每种状态(即每个时间步所有粒子的位置)。

将它们相乘是错误的:
x1=0 * y1=0 * z1=0 * x2=1 * y2=1 * z2=1 = 0
例如
x1=1 * y1=1 * z1=1 * x2=0 * y2=0 * z2=0 = 0
给出相同的结果，尽管状态不同。

下面的算法要好一些，但仍然错误
1*(x1=1 * y1=1 * z1=1) + 2*(x2=0 * y2=0 * z2=0) + ...
如何将数字的列表转换为唯一的数字？

Answer 1

假设系统中有N个元素具有(x，y，z)坐标，其中x，y，z中的每个元素都由double(64位)表示，那么您的观点可能与此类似:

struct point { double x, y, z;};

将其表示为唯一的“数字”的最简单方法是将系统表示为大小为N的点的数组，并将其二进制表示形式解释为数字。数组在内存中是连续的，因此它本身就是一个数字。将其解释为数字的最简单方法是将其字节解释为大整数，其中总数字计算为
state[0] + 2^8 *state[1] + 2^16 * state[2] + ... 2^*((n - 1)*8) * state[n-1]
要计算该值，您当然需要一个bigint库，它可能对许多目的没有用。如果某些数字经常重复而又没有太多，这可能已经有所帮助，因为您可以在第一次运行数据期间通过将其别名为较小的ID开始用简单的ID替换它们。对于任何给定的运行，ID的大小将仅具有不同配置数目的大小，再加上存储从“数字”到较小ID的转换表的开销。因此，这显然只有在重复配置时才能得到返回。

为什么不能使用更小的东西？如果使用任何较小的值表示x，y和z坐标，则两个值将用相同的数字表示。这里的类型无关紧要:如果您的点是 bool，您会更清楚地看到，任何较小的值都必须将0和1合并。

具有(2 ^ 64 * 2 ^ 64 * 2 ^ 64)^ N个可能状态的系统不能用更少的比特来表示，同时仍然唯一地区分每个状态。

如果您不查看状态空间中大部分位置发生的情况，则可以使用散列来更快地查找这些状态。但是，这显然是基于较低的碰撞概率。哈希只是将您的大数映射到较小的数，以减少元素之间的冲突。如果您对例如上述点数组的内容进行哈希处理，则可以查找某个状态，例如，增加之前查看过该状态的次数的计数或添加观察到该状态的时间步长到由哈希图中此哈希键键入的列表。

如果状态的概率分布不均匀，则可以使用无损压缩，以减少最频繁状态的内存使用。您仍然需要相同的最坏情况存储器，但是在一个简化示例中，您将0分配给您最可能的值，将1分配给下一个最可能的值，等等。这里要查找的算法是霍夫曼编码和LZ / DEFLATE。通常可以通过库轻松获得它们。