Python数据结构设计

Question

这个数据结构应该满足以下几个目的：

• 每个对象都是独一无二的，包含一些特定的键值对
• 这些键和值不是事先确定的，可以是任何字符串
• 查询对象的速度要快

举个例子：

• object_123({'stupid':True, 'foo':'bar', ...})
• structure.get({'stupid':True, 'foo':'bar', ...}) 应该返回 object_123

理想情况下，这个结构是通过标准库中提供的标准Python数据结构来实现的。

你会怎么实现这个呢？

Answer 1

假设 object_123 是一个字典，看起来就是这样。你的 structure 似乎是一个标准的字典，里面的键像是 (('foo', 'bar'), ('stupid', True))；换句话说，就是 tuple(sorted(object_123.items()))，这样它们总是按照一定的顺序排列。

之所以要有这个固定的顺序，是因为 dict.items() 并不能保证返回的列表是按特定顺序排列的。如果你的字典键是 (('foo', 'bar'), ('stupid', True))，你可不想因为你在找 (('stupid', True),('foo', 'bar')) 时出现错误。对值进行排序可能是防止这种情况发生的最快方法。

Answer 2

我觉得你需要的是SQLite。虽然它可能不是用标准的Python结构实现的，但它可以通过标准库来使用。

Answer 3

我能想到的最简单的解决办法就是使用排序的元组作为键：

def key(d): return tuple(sorted(d.items()))

x = {}
x[key({'stupid':True, 'foo':'bar', ...})] = object_123

x.get(key({'stupid':True, 'foo':'bar', ...})) => object_123

另外一个选择是自己设计一个哈希方案来处理你的键（可以把它们放在一个类里，或者直接在字典中使用数字键），不过根据你访问数据的方式，这可能会比较慢。