Выберите случайный элемент из набора, быстрее, чем линейное время (Haskell)

Question

Я хотел бы создать эту функцию, которая выбирает случайный элемент из Set :

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. избегают использования каких-либо внешних функций учета помимо внутренних функций набора, а
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 (в отношении интерфейса и производительности), которое также имеет журнал(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 - начальный диапазон набора;это только реальные данные, которые могут привести к очень плохой производительности в интервале деления (или других типах данных, чей тип заказа имеет точки накопления).

PS.Это обеспечивает идеально равномерное распределение, если только следить за тем, чтобы отдельные элементы находились сверху и снизу.

Редактирование: добавлено 'code'

Какой-то не элегантный, непроверенный (псевдо?) Код.На моем компьютере нет компилятора для тестирования дыма, возможен случайный отказ, и он, вероятно, может быть выполнен с меньшим количеством 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

Начиная с container-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) раз.

Один из вариантов - использовать предложение Джонаса, чтобы сначала взять размер и выбрать индекс случайного элемента на его основе, а затем использовать функцию (еще не добавленную elemAt) в Data.Set.

Answer 6

Другим способом достижения этого может быть использование 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 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

Если вам не нужно модифицировать ваш набор или вам нужно изменять его нечасто, вы можете использовать массивы в качестве справочной таблицы со временем доступа 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`