从具有 O(1) 时间复杂度的集合中采样一个元素
Sample one element from a set with O(1) time complexity
我在 Python 中有一个集合，我想从中抽取一个元素，就像使用 random.sample() 方法一样。问题是 sample() 在内部将集合转换为元组，这是 O(n)，我必须以最佳方式进行。
是否有一个函数可用于从时间复杂度为 O(1) 的集合中采样元素，或者唯一的方法是创建您自己的集合实现？
因为数据布局是不规则的，所以不可能均匀地从基于散列的set中抽样，复杂度为O(1)，除非，在ω( n) 查询，通过将其预处理成某种数组。 （当然，在构建 set 时可以维护这样的数组，但这不是给定的起点，添加起来并不比 tuple 转换快。）
我在 Python 中有一个集合，我想从中抽取一个元素，就像使用 random.sample() 方法一样。问题是 sample() 在内部将集合转换为元组，这是 O(n)，我必须以最佳方式进行。
是否有一个函数可用于从时间复杂度为 O(1) 的集合中采样元素，或者唯一的方法是创建您自己的集合实现？
因为数据布局是不规则的，所以不可能均匀地从基于散列的set中抽样，复杂度为O(1)，除非，在ω( n) 查询，通过将其预处理成某种数组。 （当然，在构建 set 时可以维护这样的数组，但这不是给定的起点，添加起来并不比 tuple 转换快。）