O（1）在dict中查找单个元组元素？

Question

我在头脑中有一个类似于以元组作为键的dict的结构，只是您可以只使用一个元组元素来查找条目。在

类似的东西。不是真正的Python代码，只是一个想法）

>>> d[(100, "apple")] = 5.0 # putting entry into dict
>>> d[(100, "pear")] = 10.0 # putting entry into dict
>>> d[(200, "pear")] = 10.0 # putting entry into dict
>>> d[100] # O(1) lookup
[("apple", 5.0), ("pear", 10.0)]
>>> d["pear"] # O(1) lookup
[(100, 10.0), (200, 10.0)]

当前不能使用defaultdict()执行此操作。在Python中实现这一点的最佳方法是什么，或者使用的最佳数据结构是什么？我希望查找是O（1），就像是对dict一样

在这种情况下，元组元素和值都不唯一。在

我正在考虑：

• 嵌套dicts
• 两个口述？在
• 一些类似数据库的结构

Answer 1

为什么不使用namedtuple之类的

>>>>from collections import namedtuple  
>>>>Fruit = namedtuple("Fruit", ["name", "count"])  
>>>>f1 = Fruit(name="apple", count=100)  
>>>>f2 = Fruit(name="pear", count=100)  
>>>>print f1  
Fruit(name='apple', count=100)  
>>>>print f2  
Fruit(name='pear', count=100)  
>>>>f1.name  
'apple'  
>>>>f1.count
100
>>>>f2.name  
'pear'  

现在使用fruitcount字典作为

^{pr2}$

更多信息请参考：python-docs

Answer 2

有两种常见的可能性。在

• 对于较小的字典：重写__getitem__和{}的dict来实现您的需求。关于这件事有几个问题。在
• 对于更大的字典：使用一个可以使用查询语言的数据库。例如：sqlite在内存中，但它取决于持久性和API要求。在

来回答你的问题

import sqlite3

con = sqlite3.connect(":memory:") # could also be a file
con.isolation_level = None
cur = con.cursor()

# Create table
cur.execute("CREATE TABLE foo (key INTEGER, fruit TEXT, value REAL)")
# Create indexes for fast lookup
cur.execute("CREATE INDEX index_key ON foo (key)")
cur.execute("CREATE INDEX index_fruit ON foo (fruit)")

def insert(key, fruit, value):
    cur.execute("INSERT INTO foo VALUES (?, ?, ?)", (key, fruit, value))

insert(100, "apple", 5.0)
insert(100, "pear", 10.0)
insert(200, "pear", 10.0)

print cur.execute("SELECT * FROM foo WHERE key=?", (100,)).fetchall()
print cur.execute("SELECT * FROM foo WHERE fruit=?", ("pear",)).fetchall()

[(100, u'apple', 5.0), (100, u'pear', 10.0)]
[(100, u'pear', 10.0), (200, u'pear', 10.0)]

您还可以使用一个对象关系映射器或另一个类似键值存储的数据库，它可能更符合您的需要。在

使用数据库并不比查字典快。但是您有一些优势，比如持久性和查询API。如果数据库能满足您的需求，我不会提前优化速度。这取决于你。在

Answer 3

考虑如下内容：

class MyDict(object):

    def __init__(self):
        self._data = {}

    def __setitem__(self, key, val):
        self._data[key] = val
        if key[0] not in self._data:
            self._data[key[0]] = {}
        self._data[key[0]][key[1]] = val

    def __getitem__(self, key):
        return self._data[key]

这允许元组或其第一个元素在O(1)中进行查找。然后可以为key[1]实现相同的功能。使用字典字典也可以对键O(1)的另一部分进行后续查找。使用中：

^{pr2}$

注意，这假设每个组合key[0], key[1]将只有一个val。在

参见How to "perfectly" override a dict?关于定制词典的制作。在