Генерация случайных чисел в OCaml

Question

При использовании строго функциональных языков вы обязаны писать программы. Я столкнулся с проблемой генерации большого количества псевдослучайных чисел с помощью OCaml, и я не уверен, что использую лучший способ для генерации этих чисел на таком языке.

Я создал модуль с функцией ( gen ), которая принимает целое число в качестве размера и пустой список и возвращает список псевдослучайных чисел размера размер . Проблема в том, что когда размер слишком велик, он утверждает StackOverflow , что и является ожидаемым.

Должен ли я использовать хвостовую рекурсию? Должен ли я использовать лучший метод, о котором я не знаю?

module RNG =
struct
  (* Append a number n in the end of the list l *)
  let rec append l n =
    match l with
    | [] -> [n]
    | h :: t -> h :: (append t n)

  (* Generate a list l with size random numbers *)
  let rec gen size l =
    if size = 0 then
      l
    else
      let n = Random.int 1000000 in
      let list = append l n in
      gen (size - 1) list
end

Тестирование кода для генерации миллиарда псевдослучайных чисел возвращает:

# let l = RNG.gen 1000000000 [];;
Stack overflow during evaluation (looping recursion?).

Answer 1

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

Как вы предложили в вопросе, способ избежать этого - использовать хвостовую рекурсию. При работе со списками это обычно означает построение списков в обратном порядке. Функция добавления становится просто ::.

Если порядок результирующего списка важен, список необходимо поменять местами в конце. Так что нередко видеть код, возвращающий List.rev acc. Это занимает O (n) времени, но постоянное пространство и является хвостовой рекурсивной. Так что стеку нет предела.

Таким образом, ваш код станет:

let rec gen size l =
  if size = 0 then
    List.rev l
  else
    let n = Random.int 1000000 in
    let list = n :: l in
    gen (size - 1) list

Еще несколько вещей для оптимизации:

При построении результата побитово через рекурсию результатом обычно являются имена acc, сокращенно от аккумулятора, и передаются первыми:

let rec gen acc size =
  if size = 0 then
    List.rev acc
  else
    let n = Random.int 1000000 in
    let list = n :: acc in
    gen list (size - 1)

Это позволяет затем использовать функцию и сопоставление с образцом вместо аргумента размера, и если конструкция:

let rec gen acc = function
| 0 -> List.rev acc
| size ->
    let n = Random.int 1000000 in
    let list = n :: acc in
    gen list (size - 1)

Список случайных чисел обычно так же хорошо перевернут. Если вам не нужны списки разных размеров, но с одним и тем же начальным числом для начала с одинаковой последовательности чисел, вы можете пропустить List.rev. И n :: acc такая простая структура, которую обычно не связывают с переменной.

let rec gen acc = function
| 0 -> acc
| size ->
    let n = Random.int 1000000 in
    gen (n :: acc) (size - 1)

И, наконец, вы можете воспользоваться дополнительными аргументами. Хотя это делает код более сложным для чтения, он значительно упрощает его использование:

let rec gen ?(acc=[]) = function
  | 0 -> acc
  | size ->
      let n = Random.int 1000000 in
      gen ~acc:(n :: acc) (size - 1)

# gen 5;;
- : int list = [180439; 831641; 180182; 326685; 809344]

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

Примечание. Альтернативным способом является использование функции-оболочки:

let gen size =
  let rec loop acc = function
    | 0 -> acc
    | size ->
        let n = Random.int 1000000 in
        loop (n :: acc) (size - 1)
  in loop [] size

Answer 2

Стандартный модуль List имеет функцию init, которую можно использовать для записи всего этого в одну строку:

let upperbound = 10

let rec gen size =
  List.init size (fun _ -> Random.int upperbound)

Answer 3

Зачем вам нужно явно вычислять полный список? Другой вариант может состоять в том, чтобы генерировать элемент лениво (и детерминистически), используя новый модуль последовательности:

   let rec random_seq state () =
     let state' = Random.State.copy state in
     Seq.Cons(Random.State.int state' 10, random_seq state')

Тогда случайная последовательность random_seq state полностью определяется начальным состоянием state: ее можно без проблем использовать повторно и генерировать только новые элементы по мере необходимости.

Answer 4

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

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