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

Ответ 1

Вот идея: вы можете делать интервальную деление пополам.

• size s - постоянное время. Используйте randomR, чтобы определить, насколько далеко вы выбрали набор.
• Сделайте split с различными значениями между исходными findMin и findMax, пока вы не получите элемент в нужном месте. Если вы действительно боитесь, что набор составлен, скажем о реалах, и он чрезвычайно плотно сгруппирован, вы можете каждый раз пересчитывать findMin и findMax, чтобы гарантировать сбивание некоторых элементов каждый раз.

Производительность будет O (n log n), в основном не хуже вашего текущего решения, но при достаточно слабых условиях, что набор не будет полностью сгруппирован вокруг некоторой точки накопления, средняя производительность должна быть ~ ( (logn) ^ 2), что является довольно постоянным. Если это набор целых чисел, вы получаете O (log n * log m), где m - начальный диапазон набора; это только реалы, которые могут вызвать очень неприятную производительность при делении по интервалу (или другие типы данных, у которых тип порядка имеет точки накопления).

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

Изменить: добавлен код '

Некорректный, непроверенный (псевдо?) код. Нет компилятора на моем текущем компьютере до smoke test, возможности по-одному, и, вероятно, можно было бы сделать с меньшим количеством if s. Одна вещь: проверить, как mid генерируется; это потребует некоторой настройки в зависимости от того, ищете ли вы что-то, что работает с наборами ints или reals (интервал биссекции по своей сути является топологическим и не должен работать совершенно одинаково для наборов с различными топологиями).

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

Ответ 2

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

Ответ 3

Насколько я знаю, правильным решением было бы использовать индексированный набор, т.е. IntMap. Вам просто нужно сохранить общее количество добавленных элементов вместе с картой. Каждый раз, когда вы добавляете элемент, вы добавляете его с ключом выше предыдущего. Удаление элемента в порядке - просто не изменяйте счетчик общих элементов. Если при поиске ключевого элемента этот элемент больше не существует, тогда генерируйте новое случайное число и повторите попытку. Это работает до тех пор, пока общее количество удалений не будет доминировать над количеством активных элементов в наборе. Если это проблема, вы можете сохранить отдельный набор удаленных ключей для рисования при вставке новых элементов.

Ответ 4

Если у вас был доступ к внутренним компонентам Data.Set, который является просто двоичным деревом, вы могли бы проходить по дереву, на каждом узле выбирая одну из ветвей с вероятностью согласно их соответствующим размерам. Это довольно просто и дает вам очень хорошую производительность с точки зрения управления памятью и распределения, так как вам не нужно делать дополнительную бухгалтерию. OTOH, вы должны вызвать RNG O (log n) раз.

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

Ответ 5

В 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)

Ответ 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`

Ответ 7

Эта проблема может быть немного затруднена, если вы не возражаете, полностью поглощая ваш RandomGen. С расщепляемыми генераторами это дело A-OK. Основная идея состоит в том, чтобы создать таблицу поиска для набора:

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 номеров в границах, конечно.)

Ответ 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) (это будет средний случай для равномерно случайных индексов).