python - 在 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

next(islice(d.values(),np.random.randint(0, len(d)-1),None)) 是我发现从 dict d 中选择随机值的最佳性能方法Python 3。这在下面的讨论中解释。

一些标准库随机方法比类似的 numpy.random 方法需要更多的运行时间。例如:

import numpy as np

timeit random.randint(0, 10)
100000 loops, best of 3: 2.52 µs per loop

timeit np.random.randint(0, 10)
1000000 loops, best of 3: 453 ns per loop

使用 numpy.random.randint 可以提高选择字典随机值的方法的运行时间:

from itertools import islice
import random

d = {1:'a',2:'b',3:'c',4:'d',5:'e',6:'f',7:'g',8:'h',9:'i',10:'j'}

timeit next(islice(d.values(),random.randint(0, len(d)-1),None))
100000 loops, best of 3: 3.58 µs per loop

timeit next(islice(d.values(),np.random.randint(0, len(d)-1),None))
100000 loops, best of 3: 1.26 µs per loop

# d[5] access time is about 25X smaller than 1.26 µs
timeit d[5]
10000000 loops, best of 3: 51.3 ns per loop

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

timeit d[take_nth(d.keys(), random.randint(0, len(d)-1))]
100000 loops, best of 3: 5.07 µs per loop

timeit d[take_nth(d.keys(), np.random.randint(0, len(d)-1))]
100000 loops, best of 3: 2.66 µs per loop