从集合中选择随机元素，比线性时间更快（Haskell）

Question

我想创建这个函数，它从 Set：

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

可以编写简单的listy实现。例如（代码更新，验证工作）：

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 的线性查找成本。有没有更快的方法来选择集合中的随机元素？理想情况下，重复随机选择应该在所有选项上产生均匀分布，这意味着它不会比其他元素更喜欢某些元素。

---

编辑：答案中出现了一些很棒的想法，所以我只想对我到底在寻找什么进行更多说明。我用 Sets 提出了这个问题，作为这种情况的解决方案。我更喜欢这样的答案：既

1. 避免使用超出集合内部的任何函数外簿记，又
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. 在原始 findMin 和 findMax 之间使用不同的值进行split，直到在您想要的位置获得元素。如果您确实担心该集合是由实数组成并且非常紧密地聚集，则可以每次重新计算 findMin 和 findMax 以保证每次删除一些元素。

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

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

编辑：添加了“代码”

一些不优雅的、未经检查的（伪？）代码。我当前的机器上没有编译器来进行冒烟测试，可能会出现错误，并且可能可以用更少的 if 来完成。一件事：检查 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

Answer 4

从 containers-0.5.2.0 开始，Data.Set 模块有一个 elemAt 函数，它通过元素排序序列中从零开始的索引检索值。所以现在编写这个函数很简单

import           Control.Monad.Random
import           Data.Set (Set)
import qualified Data.Set as Set

randElem :: (MonadRandom m, Ord a) -> Set a -> m (a, Set a)
randElem xs = do
  n <- getRandomR (0, Set.size xs - 1)
  return (Set.elemAt n xs, Set.deleteAt n xs)

，因为 Set.elemAt 和 Set.deleteAt 都是 O(log n)，其中 n 是集合中元素的数量，整个操作是O(log n)

Answer 5

如果您有权访问 Data.Set 的内部结构只是一棵二叉树，您可以在树上递归，在每个节点根据各自的大小概率选择一个分支。这非常简单，并且在内存管理和分配方面为您提供了非常好的性能，因为您无需进行额外的簿记工作。 OTOH，您必须调用 RNG O(log n) 次。

一种变体是使用 Jonas 的建议，首先获取大小并根据该大小选择随机元素的索引，然后使用 Data.Set 中的（尚未添加 elemAt）函数。

Answer 6

如果您不需要修改集合或不需要经常修改它，则可以使用数组作为查找表，访问时间为 O(1)。

import qualified Data.Vector 
import qualified Data.Set

newtype RandSet a = RandSet (V.Vector a)

randElem :: RandSet a -> RandomGen -> (a, RandomGen)
randElem (RandSet v) g
  | V.empty v = error "Cannot select from empty set" 
  | otherwise = 
    let (i,g') = randomR (0, V.length v - 1) g
    in (v ! i, g')

-- Of course you have to rebuild array on insertion/deletion which is O(n)
insert :: a -> RandSet a -> RandSet a
insert x = V.fromList . Set.toList . Set.insert x . Set.fromList . V.toList`

Answer 7

如果您不介意完全消耗您的 RandomGen，这个问题可以稍微解决一下。对于可拆分的生成器，这是一件很不错的事情。基本思想是为集合创建一个查找表：

randomElems :: Set a -> RandomGen -> [a]
randomElems set = map (table !) . randomRs bounds where
    bounds = (1, size set)
    table  = listArray bounds (toList set)

这将具有非常好的性能：它将花费 O(n+m) 时间，其中 n 是集合的大小，m 是结果的元素数量列出您评估的内容。 （当然，还要加上在范围内随机选择 m 个数字所需的时间。）

Answer 8

实现此目的的另一种方法可能是使用 Data.Sequence 而不是 Data.Set。这将允许您在 O(1) 时间内将元素添加到末尾，并在 O(log n) 时间内索引元素。如果您还需要能够进行成员资格测试或删除，则必须使用更通用的 Fingertree 包并使用诸如 FingerTree (Sum 1, Max a) a 之类的东西。要插入元素，请使用 Max a 注释来找到正确的插入位置；这基本上需要 O(log n) 时间（对于某些使用模式可能会少一些）。要进行成员资格测试，请执行基本相同的操作，因此时间为 O(log n)（同样，对于某些使用模式，这可能会少一些）。要选择随机元素，请使用 Sum 1 注释进行索引，需要 O(log n) 时间（这将是均匀随机索引的平均情况）。

Answer 9

我想也许很多答案都是旧的，因为现在 set 模块有自己的 elemAt 函数可以很容易地完成这类事情。这是我的实现：

import Data.Set(Set)
import qualified Data.Set as S
import System.Random

randomMember :: RandomGen g => Set a -> g -> (Maybe a, g)
randomMember s g | null s = (Nothing, g)
                 | otherwise = let (a, g') = randomR (0, length s) g
                               in (Just (S.elemAt a s), g')

Prelude 函数 null 和 length 在集合上工作，因为 Set 是 Foldable 的实例。

hskl> newStdGen >>= return . fst . randomMember (S.fromList [1..10])
Just 7
hskl> newStdGen >>= return . fst . randomMember (S.fromList [1..10])
Just 4
hskl> newStdGen >>= return . fst . randomMember (S.fromList [1..10])
Just 4
hskl> newStdGen >>= return . fst . randomMember (S.fromList [1..10])
Just 9
hskl> newStdGen >>= return . fst . randomMember (S.fromList [1..10])
Just 8
hskl> newStdGen >>= return . fst . randomMember S.empty
Nothing
hskl> newStdGen >>= return . fst . randomMember S.empty
Nothing