python - 从列表范围中获取随机项目

Question

假设我有一组未排序的项目:

input = set([45, 235, 3, 77, 55, 80, 154])

我需要从此输入中获取特定范围内的随机值。例如。当我有

ran = [50, 100]

我希望它返回 77 或 55 或 80。在 python 中获取大型集合的最快方法是什么？

Answer 1

为此使用 set 不是正确的方法，因为元素未排序。这将导致一个 O(N) 解决方案来测试每个元素是否符合边界。

我建议将数据转换为排序列表，然后您可以使用 bisect 找到边界值的开始和结束索引，然后应用 random.choice 在切片列表上:

import bisect,random

data = sorted([45, 235, 3, 77, 55, 80, 154])

def rand(start,stop):
    start_index = bisect.bisect_left(data,start)
    end_index = bisect.bisect_right(data,stop)
    return data[random.randrange(start_index,end_index)]

print(rand(30,100))

bisect 在排序列表上具有 O(log(N)) 复杂性。然后使用 random.randrange 选择一个索引。

bisect在主流平台上使用编译代码，因此除了复杂度低之外还非常高效。

通过执行极限测试来验证边界:

print(rand(235,235))

按预期打印 235(使用随机时总是很难确保数组没有越界)

(如果你想在运行时更新你的数据，你也可以使用 bisect 来插入元素，它比 set 慢，因为 O( log N) 复杂性 + 在 list 中插入，当然，但你不能拥有一切)