在Python 3中以恒定时间从字典中选择随机值？

Question

我知道您可以通过多种方式从字典中选择随机值.

在Python 2中:

random.choice(d.keys())

在Python 3中:

random.choice(list(d.keys()))

尽管如此,两种方法都需要在随机选择之前将变换(即线性时间O(n))转换为列表.例如,我知道在Python 3中d.keys()返回一个迭代器,我猜测在Python 3中,列表是从字典内部创建的.

是否可以在恒定时间内从字典中选择一个值,即O(1)？

编辑:到目前为止的评论,我认为这是不可能的,至少不是直截了当的方式.需要辅助结构.

编辑2:我认为字典可以在恒定时间内随机选择,因为内部它是一个哈希表,即内部它必须有一个数组或类似的东西.当然,这取决于内部实现,但理论上我认为这是可能的.

Answer 1

在这种情况下，我只能想象一种（较小的）优化：不创建列表，只需获取一个随机数r并迭代d.keys()，直到获得r第一项。

def take_nth(sequence, n):
    i = iter(sequence)
    for _ in range(n):
        next(i)

    return next(i)

import random
rand_key = d[take_nth(d.keys(), random.randint(0, len(d)-1))]

这会给你带来更好的性能，因为你不必每次都迭代整个列表，但这仍然是一个坏主意。

如果您想在固定字典上重复进行随机选择，那么只需将其键缓存到单独的列表中并使用随机索引值对其进行索引即可。

更新：

总结评论中的讨论，以下具有前向/后向缓存和重用已删除项目的类可能会有所帮助：

import random

class RandomSampleDict(object):

    def __init__(self):
        self.data     = {}
        self.cache_ik = {}
        self.cache_ki = {}
        self.track    = []

    def lookup(self, key):
        return self.data[key]

    def set(self, key, value):
        self.data[key] = value

    def add(self, key, value):
        self.data[key] = value
        if len(self.track) == 0:
            i = len(self.data) - 1
        else:
            i = self.track.pop()

        self.cache_ik[i] = key
        self.cache_ki[key] = i

    def delete(self, key):
        del self.data[key]
        i = self.cache_ik[i]
        del self.data_ik[i]
        del self.data_ki[key]

        self.track.append(i)

    def random_sample_key(self):
        key = None
        while key is None:
            i = random.randint(0, len(self.data))
            if i in self.cache_ik:
                return self.cache_ik[i]