从集合中选择随机元素,比线性时间快(Haskell)

Question

我想创建这个函数,它从集合中选择一个随机元素:

randElem :: (RandomGen g) => Set a -> g -> (a, g)

可以编写简单的列表实现.例如(代码更新,验证工作):

import Data.Set as Set
import System.Random (getStdGen, randomR, RandomGen)

randElem :: (RandomGen g) => Set a -> g -> (a, g)
randElem s g = (Set.toList s !! n, g')
    where (n, g') = randomR (0, Set.size s - 1) g

-- simple test drive
main = do g <- getStdGen
          print . fst $ randElem s g
    where s = Set.fromList [1,3,5,7,9]

但是使用!!大型(随机选择)会导致线性查找成本n.有没有更快的方法来选择集合中的随机元素？理想情况下,重复的随机选择应该在所有选项上产生均匀分布,这意味着它不喜欢某些元素而不是其他元素.

---

编辑:答案中出现了一些很棒的想法,所以我只想对我正在寻找的内容进行更多的澄清.我用套装这个问题作为解决这种情况的方法.我更喜欢两者的答案

1. 避免在Set的内部使用之外使用任何功能外的簿记,以及
2. 保持良好的性能(平均优于O(n)),即使该功能仅在每个唯一集合中使用一次.

我也喜欢工作代码,所以如果你的答案包括一个有效的解决方案,那么期望(至少)给我+1.

Answer 1

Data.Map有一个索引函数(elemAt),所以使用这个:

import qualified Data.Map as M
import Data.Map(member, size, empty)
import System.Random

type Set a = M.Map a ()

insert :: (Ord a) => a -> Set a -> Set a
insert a = M.insert a ()

fromList :: Ord a => [a] -> Set a
fromList = M.fromList . flip zip (repeat ())

elemAt i = fst . M.elemAt i

randElem :: (RandomGen g) => Set a -> g -> (a, g)
randElem s g = (elemAt n s, g')
    where (n, g') = randomR (0, size s - 1) g

并且你有一些与Data.Set(关于接口和性能)完全兼容的东西,它还有一个log(n)索引函数和你请求的randElem函数.

请注意,randElem是log(n)(它可能是这种复杂性可以获得的最快实现),并且所有其他函数都具有与Data.Set相同的复杂性.如果您需要Set API中的任何其他特定功能,请告诉我,我将添加它们.

Answer 2

据我所知,正确的解决方案是使用索引集 - 即IntMap.您只需存储随地图添加的元素总数.每次添加元素时,都会使用比以前更高的键添加元素.删除元素很好 - 只是不要改变总元素计数器.如果在查找键控元素时该元素不再存在,则生成一个新的随机数并重试.这一直有效,直到删除的总数占据集合中活动元素的数量.如果这是一个问题,您可以保留一组单独的已删除键,以便在插入新元素时进行绘制.

Answer 3

这是一个想法：你可以进行区间二分。

1. size s是常数时间。用于randomR了解您选择的集合的程度。
2. 使用split原始值findMin和原始值之间的各种值findMax，直到将元素置于所需的位置。如果您确实担心该集合由实数组成并且非常紧密地聚集，则可以每次重新计算findMin和findMax，以保证每次都会删除一些元素。

性能将为 O(n log n)，基本上不比当前的解决方案差，但只有相当弱的条件，即集合没有完全聚集在某个累积点周围，平均性能应该为 ~((logn) ^2)，这是相当恒定的。如果它是一组整数，则得到 O(log n * log m)，其中 m 是该集合的初始范围；只有实数可能会在区间二分（或其他具有累积点的顺序类型的数据类型）中导致非常糟糕的性能。

附言。这会产生完全均匀的分布，只要注意是否有相互偏离的元素以确保可以获取顶部和底部的元素。

编辑：添加“代码”

一些不优雅的、未经检查的（伪？）代码。我当前的机器上没有编译器来进行冒烟测试，可能会出现逐一的情况，并且可能可以用更少的ifs 来完成。一件事：查看是如何mid生成的；它需要一些调整，具体取决于您是否正在寻找适用于整数集或实数集的东西（区间二分本质上是拓扑的，并且对于具有不同拓扑的集合不应该完全相同）。

import Data.Set as Set
import System.Random (getStdGen, randomR, RandomGen)

getNth (s, n) = if n = 0 then (Set.findMin s) else if n + 1 = Set.size s then Set.findMax s
    else if n < Set.size bott then getNth (bott, n) else if pres and Set.size bott = n then n
    else if pres then getNth (top, n - Set.size bott - 1) else getNth (top, n - Set.size)
    where mid = ((Set.findMax s) - (Set.findMin s)) /2 + (Set.findMin s)
          (bott, pres, top) = (splitMember mid s)

randElem s g = (getNth(s, n), g')
    where (n, g') = randomR (0, Set.size s - 1) g