Python数据结构

Question

我对编程知之甚少，因此这是一个不知道从哪里寻找答案的情况。我想要创建如下所示的数据结构：

vertexTopology = {vertexIndex: {clusterIndexes: intersection point}}

然而，实际上集群索引是一个由集群索引组成的集合。因此，现在我真正拥有的是：

vertexTopology = {5: [[(1, 2, 3), intx_1], 
                      [(2, 3, 4), intx_2]]
                  6: [[(1, 2, 3), intx_3]]
                  ...}

我该如何创建一个与每个集群集合和其顶点索引相关联的唯一索引？类似于：

vertexTopology = {5: {index associated with (1, 2, 3) AND vertex 5, intx_1}, 
                     {index associated with (2, 3, 4) AND vertex 5, intx_2},
                  6: {index associated with (1, 2, 3) AND vertex 6, intx_3}]
                  ...}

我不确定使用字典是否最好实现我想做的事情，因此非常欢迎任何建议！

下面是一个四路口的图片，这样你就能想象一下我正在处理什么。

- grasshopper

---

给这张好看的图片点赞。 - user2665694

你的索引需要具备哪些属性？如果我理解正确，元组 ((1,2,3), 5) 本身就是一个可行的索引；它简单、可哈希、可排序等等。或者你确实需要一个整数？ - DSM

你说的可能是对的。问题是我不知道碰撞可能发生在哪里，所以我想采取一种保险的方法。@EveryEvery的解决方案似乎很容易实现。我会选择它并进行彻底测试。 - grasshopper

@grasshopper 如果你不需要一些数字或字符串作为索引，你可以直接使用元组作为键。这样更容易 :-) - Curry

@grasshopper：如果您直接使用元组本身，则不会发生任何危险的冲突。可能会发生哈希冲突，但这是幕后实现细节：您永远不会将错误值与键相关联。如果您尝试通过自己的哈希替换键，则可能会发生我所提供的此类危险冲突，因为您正在丢弃信息。[frozenset也是如此，甚至更好，因为然后您就不必担心顺序问题。] - DSM

Answer 1

Python 中有一种叫做“冻结集合”的东西。这是一种可以用作字典索引的集合。

vertexTopology = {
    5: {
        (frozenset({1, 2, 3}), 5): intx_1,
        (frozenset({2, 3, 4}), 5): intx_2
    },
    6: {
        (frozenset({1, 2, 3}), 5): intx_3
    },
    ...
}

与集合不同，冻结集合是不可变的。这就是为什么它们可以用作索引的原因。

- Noctua

---

我曾尝试使用集合作为字典的键，但它没有起作用。很高兴你告诉我可以使用frozenset作为键。 - grasshopper

Answer 2

使用hash()来生成集群集和顶点索引的索引。元组是一种可哈希类型。

vertexTopology = {5: {hash(((1, 2, 3),5)): intx_1, 
                      hash(((2, 3, 4),5)): intx_2},
                  6: {hash(((1, 2, 3),6)): intx_3},
                  ...}

或者使用元组作为键

vertexTopology = {5: {((1, 2, 3),5): intx_1, 
                      ((2, 3, 4),5): intx_2},
                  6: {((1, 2, 3),6): intx_3},
                  ...}

如果您的数据使用了 set，tuple() 可以轻松地从 set 中创建一个 tuple。

s = set([1, 2, 3])    # s is set
t = tuple(s)    # t is tuple

更新：

如果你想使用其他哈希方法，str()是一个简单的解决方案。

In [41]: import hashlib

In [42]: hashed = hashlib.sha512(str(((1, 2, 3), 4))).digest()

In [43]: hashed
Out[43]:
'mtE7\xf6N\xfc\xca\xc7\xb1\x0fA\x86|\xbe9j\xbb\xdf\xbaa\xd1\x05V\x84\xe8S\xfb\xe1\x16\xe05\x89,C\xa8\x94n\xae\x1e\n\xc0Y-)\xfa\xceG D\xe0C\xc9\xef\xb0\x8eCk\xe3`\xc2s\x97\xec'

- Curry

---

这可能会导致意外的碰撞。例如，对于我来说，hash(((0,34,89),6)) == hash(((9,79,76),9))。 - DSM

所有哈希算法都可能存在碰撞。如果需要的话，可以使用更安全的哈希算法。 - Curry

@DSM。明白了！根据我正在处理的内容，我相信这是可能发生的。 - grasshopper

@EveryEvery：我想表达的是，在这里使用哈希时没有必要丢弃信息，因为有无风险的选项。 - DSM

@DSM 你是对的。我以为grasshopper需要一些索引键，比如数字或字符串。这是我的误解。使用元组作为键是一个无风险的选择。 - Curry