Как я могу случайно выбрать элемент в Ocaml?

Question

В моей программе на OCaml мне нужно случайным образом выбрать строку из огромного набора строк. До сих пор я пробовал два разных способа сделать это, каждый из которых имел небольшой успех Сначала я сохранил все строки в списке, а затем случайным образом выбрал элемент из списка:

let randomelement l =
    List.nth l (Random.int (List.length l))

Но это займет много времени, если он выберет 1000-ю строку в списке. Поэтому я положил все это в набор, думая, что Set.choose вернет случайный элемент из набора. Но это не похоже на работу. Наверное, у меня есть два вопроса ... как работает Set.choose, и есть ли лучший способ случайного выбора элемента в Ocaml?

Answer 1

Если вам важна скорость выбора, вы должны использовать другой контейнер.Зачем использовать List с доступом в O (n) или Set с O (log n), если вы можете использовать Array с O (1), то есть с постоянным временем.

Чтобы настроить ваш пример:

let randomelement arr =
    let n = Random.int (Array.length arr) in
    Array.get arr n;;

Answer 2

Set.choose - псевдоним для Set.min_elt; хотя может и не быть в будущем.

List.nth наверняка будет отстой, если вам придется делать это очень часто.

Массив будет отлично работать, но если вам нужно добавить больше элементов или удалить элементы, это может стать кошмаром для бухгалтерии.

Взгляните на реализации списков произвольного доступа , которые имеют довольно оптимальное время для вставки, удаления, поиска и кардинала, не ограничиваясь массивами.

Когда я впервые столкнулся с этой проблемой, я расширил реализацию Set и Map, включив в нее random и nth. Чтобы расширить модуль, вам нужно заново реализовать структуру и добавить функции идентичности для преобразования между ними. Я написал новый модуль под названием XSet со следующим шаблоном:

module Make (Ord : Set.OrderedType) =
    struct
        include Set.Make(Ord)

        type impl = Empty | Node of impl * elt * impl * int

        external impl_of_t : t -> impl = "%identity"
        external t_of_impl : impl -> t = "%identity"

        ...
    end

Вам придется использовать impl_of_t и наоборот для вызова нормальных Set функций или вызова ваших личных из переданных аргументов - то, что передается вашей функции, должно быть реализацией Set.Make t не impl.

Answer 3

Ваш вопрос подразумевает, что у вас есть все время, когда вы хотите подготовить структуру, которая содержит строки, и что затем вы выберете несколько раз случайным образом без изменения набора.

Если это правильно, то я бы рекомендовал хранить их в массиве. Это дает самый быстрый доступ к случайному элементу (сразу после выбора случайного индекса). Наборы и реализация списка неудобны для доступа к i-му элементу после того, как вы выбрали случайный индекс i (хотя для Наборов, если вы не возражаете против случайного выбора с плохой случайностью, вы можете выбрать случайный путь в двоичном дереве это представляет собой набор. Вы не можете сделать это извне реализации, но вы можете скопировать и вставить его и добавить свою функцию в модуль).

Answer 4

Нет, Set.choose является детерминированным, и я думаю, что это указано в документации. Я думаю, что в текущей реализации он возвращает минимальный элемент.

В какой структуре данных хранится ваш набор строк? Простой способ получить случайный элемент - это подсчитать количество различных имеющихся у вас строк, выбрать случайное число K между ними и получить «K-ую строку», которая у вас есть. Это может быть сделано довольно эффективно для некоторых структур данных (например, для массивов, это операция с постоянным временем), менее эффективно для других.

Answer 5

Во-первых, есть функция List.nth, которая может заменить вашу вспомогательную функцию.

let n = Random.int (List.length lst) in
    List.nth n lst ;;

(хотя это не будет быстрее, так как я уверен, что это примерно то же самое, что и ваша вспомогательная функция)

Что касается ускорения: если число строк у вас фиксированное, вы можете использовать массив, который значительно ускорит процесс, так как время доступа к массиву постоянно.

Answer 6

Set.choose гарантирует, что он будет выбирать один и тот же элемент каждый раз для данного набора. Какой элемент он выбирает, не указано, но если вы посмотрите на его исходный код, то увидите, что он возвращает минимальный элемент.

Лучше всего использовать массив. Если вы хотите вместо этого неизменную структуру данных, я бы предложил карту с целыми числами.