我知道可以用几种方法从字典中选择随机值。
在Python 2中：
random.choice(d.keys())
random.choice(list(d.keys()))
dict公共API是不可能实现的。然而，有几个可替换dict的插件提供对某些排序后键的高效访问。这可以被索引以获取随机元素。虽然它们的理论渐近复杂度与dict不同，但在实践中，它们通常表现得更好。从Stutzbach Enterprises提供的blist包提供了专门经过测试以完全兼容字典的blist.sorteddict。它提供了对其键视图进行对数复杂度索引的功能。它是使用B+树实现的。Grant Jenks的SortedContainers包类似地提供了对其键视图进行高效索引的sortedcontainers.SortedDict。其他可用的插件通常基于搜索树。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]
None，如果需要，重复使用randint。如果您不必最终删除大多数项目，则此方法可行。 - firegurafiku在Python 3中，next(islice(d.values(),np.random.randint(0, len(d)-1),None))是我发现的从字典d中选择随机值的最佳方法。以下讨论对此进行了解释。
一些标准库的随机方法比可比较的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
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
random.sample似乎不接受字典：TypeError: Population must be a sequence or set. For dicts, use list(d). - toto_ticorandom.sample并没有执行任何神奇操作 - 在这种情况下它只是在内部调用list(population)，因此与OP直接调用它没有任何区别。 - DSMnext(islice(d.values(),np.random.randint(0, len(d)-1),None)时，它给了我一个ValueError: high <= 0的错误。我不得不将其更改为next(islice(d.values(),np.random.randint(0, len(d)),None)。 - undefineddict无法完成此操作，需要第二个数据结构。这里提供了一种简单高效的辅助数据结构，它只跟踪当前节点。它只是将节点保存在列表中。为了支持删除，它只清空位置并保留另一个自由空间列表。请注意，如果您只随机删除节点，则可以正常使用。如果您想要删除通过其他方法选择的节点，则需要在节点中存储序列号，以便找到它们进行删除。除非随机抽样变慢时节点列表变得大部分为空，否则它能很好地工作。如果您需要处理该情况，那么您需要在那一点上重新分配列表-这是一种摊销成本，但会增加相当多的复杂性。例如，您需要添加从节点到序列号的字典，并在重新分配节点列表时更新它。import random
RNG = random.Random()
class Tracker(object):
def __init__(self):
self.free = []
self.nodes = []
def add(self,node):
if self.free:
seq_num = self.free.pop()
self.nodes[seq_num] = node
else:
seq_num = len(self.nodes)
self.nodes.append(node)
def random_node(self):
seq_num = RNG.randint(0,len(self.nodes)-1)
while self.nodes[seq_num] == None:
seq_num = RNG.randint(0,len(self.nodes)-1)
return self.nodes[seq_num],seq_num
def delete(self,seq_num):
self.nodes[seq_num] = None
self.free.append(seq_num)
def delete_random_node(self):
node,seq_num = self.random_node()
self.delete(seq_num)
return node
collections.deque，可能会使其更快，因为如果列表的大小经常改变，它们会变慢一些。但这并不是什么大问题。我认为你的节点列表将达到一个平衡点，然后变得非常高效，但你可以使用Nones填充它以避免反复增长的启动成本。你可以进行一些公共子表达式消除。但所有这些都只会有很小的影响。
dict.keys()并从中选择一个随机值）对你来说不够好吗？ - wkldict.keys()。我非常确定在Python 3中它需要O(n)的时间，因为dict.keys()返回一个迭代器。我认为在Python 2中情况也不会更好，因为它可能会在内部转换字典。 - toto_tico