从时间复杂度为O(1)的集合中抽取一个元素

2024-04-25 18:52:13 发布

您现在位置:Python中文网/ 问答频道 /正文

我在Python中有一个集合,我想从中抽取一个元素,就像使用random.sample()方法一样。问题是sample()在内部将set转换为tuple,即O(n),我必须以最佳方式进行转换

是否有一个函数可以用来从时间复杂度为O(1)的集合中对元素进行采样,或者唯一的方法是创建自己的集合实现


Tags: sample方法函数元素方式时间random复杂度
1条回答
网友
1楼 · 发布于 2024-04-25 18:52:13

因为数据布局是不规则的,所以不可能从O(1)中基于散列的set均匀地采样,除非ω(n) 查询,通过将其预处理为某种数组(当然,在构建set时可以维护这样一个数组,但这不是给定的起点,而且添加的速度并不比tuple转换快。)

相关问题 更多 >