为所有节点提供唯一 ID？

Question

我正在 Python 中创建一个 class，它将很多节点和边关联在一起。我还有其他操作，可以将两个单独的对象合并为一个相同类型的对象，等等。

但是，我需要一种方法来为每个节点提供一个唯一的 ID，以便于查找。是否有 "proper way" 来执行此操作，或者我是否只需要保留一个外部 ID 变量，每次我向任何对象添加更多节点时，我都会将其递增并传递到我的 class 方法中？

我也考虑过在创建时为每个节点生成一个随机字符串，但仍然存在碰撞错误的风险（即使这个概率接近于零，它仍然存在并且似乎是一个设计缺陷，如果不是无论如何，冗长的过度设计的方式）。

Answer 1

您可以保留一个 class 变量并将其用于序号 ID：

class Node(object):
    _id = 0

    def __init__(self):
        self._id = Node._id
        Node._id += 1

它的另一个好处是您的 class 将能够知道总共创建了多少个对象。

这也比随机 ID 便宜得多。

Answer 2

你的两个方案基本上都是实践中做的。

你的第一个解决方案是增加一个数字，只要你不溢出（使用 python 双整数，这不是真正的问题）。这种方法的缺点是，如果您开始并发，则必须确保在递增和读取外部值时使用锁定来防止数据竞争。

生成随机数的另一种方法在并发情况下效果很好。您使用的位数越多，您运行发生碰撞的可能性就越小。事实上，如果您使用 128 位作为您的 ID，您几乎可以保证不会发生冲突。

一种可以用来进一步保证不会发生冲突的方法是使您的唯一 ID 类似于 TIMESTAMP_HASHEDMACHINENAME_PROCESSID/THREADID_UNIQUEID。然后几乎不会发生冲突，除非您在 1 秒内在同一个 process/thread 上生成两个相同的 UNIQUEID。 MongoDB 做了类似的事情，他们只是增加了 UNIQUEID。我不确定他们在溢出的情况下会做什么（我认为这在实践中不会经常发生）。一种解决方案可能只是等到下一秒再生成更多 ID。

这对于您正在尝试做的事情来说可能有点矫枉过正，但这确实是一个有点有趣的问题。

Answer 3

如果您只需要一个唯一标识符，built-in Python id() function 就可以做到：

Return the “identity” of an object. This is an integer (or long integer) which is guaranteed to be unique and constant for this object during its lifetime. Two objects with non-overlapping lifetimes may have the same id() value.

Answer 4

UUID 很适合这种事情。

>>> from uuid import uuid4
>>> uuid4().hex
'461dd72c63db4ae9a969978daadc59f0'

通用唯一 ID 的冲突率非常低——除非您要创建数十亿个节点，否则它应该可以解决问题。

为所有节点提供唯一 ID？

Giving unique IDs to all nodes?

python

tree

class

nodes