Python在O(1)中的字典中获取随机密钥

Question

我需要一个支持FAST插入和删除(键,值)对的数据结构,以及"获取随机密钥",它与random.choice(dict.keys())的字典相同.我在互联网上搜索过,大多数人似乎对random.choice(dict.keys())方法感到满意,尽管它是线性时间.

我知道可以更快地实现这个:

• 我可以使用调整大小的哈希表.如果我认为密钥与插槽的比例在1和2之间,那么我可以选择随机索引,直到我遇到非空插槽.我期望只看1到2把钥匙.
• 我可以使用AVL树在保证最坏情况O(log n)中获得这些操作,并使用rank进行扩充.

有没有简单的方法在Python中获得这个？好像应该有!

Answer 1

这可能与上面列出的特定用例没有特别的关系,但这是我在搜索一种很好地获取字典中"任意"键的方法时得到的问题.

如果你不需要一个真正的随机选择,但只需要一些任意键,这里有两个我发现的简单选项:

key = next(iter(d))    # may be a little expensive, but presumably O(1)

第二个是非常有用的,只有当你乐于使用字典中的键+值时,并且由于变异将不具有算法效率:

key, value = d.popitem()     # may not be O(1) especially if next step
if MUST_LEAVE_VALUE:
    d[key] = value

Answer 2

[编辑：完全重写，但保留问题并保留完整的评论。]

下面是一个字典包装器的实现，具有 O(1) 获取/插入/删除和 O(1) 随机元素选取。

主要思想是我们希望有一个 O(1) 但任意的从range(len(mapping))键到键的映射。这将使我们获得random.randrange(len(mapping))，并将其传递给映射。

这很难实现，除非您意识到我们可以利用映射可以是任意的这一事实。实现 O(1) 时间硬限制的关键思想是：每当删除一个元素时，都将其与最高任意 id 元素交换，并更新所有指针。

class RandomChoiceDict(object):
    def __init__(self):
        self.mapping = {}  # wraps a dictionary
                           # e.g. {'a':'Alice', 'b':'Bob', 'c':'Carrie'}

        # the arbitrary mapping mentioned above
        self.idToKey = {}  # e.g. {0:'a', 1:'c' 2:'b'}, 
                           #      or {0:'b', 1:'a' 2:'c'}, etc.

        self.keyToId = {}  # needed to help delete elements

获取、设置和删除：

    def __getitem__(self, key):  # O(1)
        return self.mapping[key]

    def __setitem__(self, key, value):  # O(1)
        if key in self.mapping:
            self.mapping[key] = value
        else: # new item
            newId = len(self.mapping)

            self.mapping[key] = value

            # add it to the arbitrary bijection
            self.idToKey[newId] = key
            self.keyToId[key] = newId

    def __delitem__(self, key):  # O(1)
        del self.mapping[key]  # O(1) average case
                               # see http://wiki.python.org/moin/TimeComplexity

        emptyId = self.keyToId[key]
        largestId = len(self.mapping)  # about to be deleted
        largestIdKey = self.idToKey[largestId]  # going to store this in empty Id

        # swap deleted element with highest-id element in arbitrary map:
        self.idToKey[emptyId] = largestIdKey
        self.keyToId[largestIdKey] = emptyId

        del self.keyToId[key]
        del self.idToKey[largestId]

随机选择一个（键，元素）：

    def randomItem(self):  # O(1)
        r = random.randrange(len(self.mapping))
        k = self.idToKey[r]
        return (k, self.mapping[k])