Python中具有多个属性值的树的快速查找

Question

我需要在Python中创建一个树形对象，这个树要非常快。查找的速度比占用内存更重要。树的叶子节点就是我想要的值。

比如，给定状态=NY，位置=3，小时=2，星期几=3，我需要快速得到值=100。带有*的节点是叶子节点。

0) root
    1) {state: [NY,LA]}
        2) {howOfDay:[1,2,3,4,5], postion:[1,2,3]}
                             *3) {dayOfWeek:[234]} => value:100
            4) {state: [FL,NV,……rest of the states]}
                5) {howOfDay:[1,6,7,8,9….23]}
                      *6) {dayOfWeek:[1,5,6,7]} => value:120

在我的数据库中，数据看起来像这样，属性是以json对象的形式存在的。

parent child attribute value

0 1 state NY,LA
1 2 {howOfDay:[1,2,3,4,5], postion:[1,2,3]}
2 3 dayOfWeek dayOfWeek [2,3,4] 100
0 3 state  [FL,NV,……rest of the states]
4 5 howOfDay:[1,6,7,8,9….23]
5 6 dayOfWeek:[1,5,6,7] 120

那么，我应该使用哪个Python库和树形结构来最好地找到一个值呢？我该如何转换数据，以便能够快速查找？

Answer 1

如果你更看重速度而不是内存使用，可以把所有数据放到一个字典里，使用一个 tuple(state, position, hourOfDay, dayOfWeed) 作为键。

data = dict()

现在，对于每个叶子节点，把数据插入到字典中：

data[state, position, hourOfDay, dayOfWeed] = value

然后你可以通过以下方式访问数据：

value = data[state, position, hourOfDay, dayOfWeed]

这样做比任何树的遍历都要快，因为它利用了CPython优化过的哈希字典实现。