Просто хочу выбрать несколько случайных элементов списка и вернуть их в OCaml - PullRequest
Новая
       42

Просто хочу выбрать несколько случайных элементов списка и вернуть их в OCaml

0 голосов
/ 23 октября 2019

Я хочу выбрать n различных случайных элементов в списке l и вернуть их в choose_elements, но у меня есть ошибка StackOverFlow для достаточно больших списков!

Я пытался использовать функцию tail_recursive choose_elem_aux для этого, но я считаю, что мое условие List.mem недостаточно эффективно с точки зрения сложности! Я делаю это обычно на других языках программирования с массивом логических меток, который я отмечаю индексом каждого случайного числа, сгенерированного в true! Но я не могу сделать это в OCaml, потому что я не могу выполнить несколько инструкций в блоке if или else! например: 

... else {
mark[r] =true ;
choose_elem_aux l n mark tmp ;
} ...


let choose l = 
  nth l (Random.int (List.length l)) ;;

let rec choose_elem_aux l n tmp =
  if n=0 then tmp
  else
    let r=choose l in if List.mem r tmp then
      choose_elem_aux l n tmp else choose_elem_aux l (n-1) (r::tmp) ;;

let rec choose_elements l n = 
  choose_elem_aux l n [] ;;

StackOverflow для большого списка, например: 

choose_elements [1...10_000] 7 ;;

Ответы [ 2 ]

1 голос
/ 23 октября 2019

Прежде всего, ocaml позволяет вам написать несколько операторов в if then else, просто это не так, как в языках, подобных C. 

if condition then begin
  instruction1 ;
  instruction 2 ;
  (* ... *)
end
else begin
  (* ... *)
end

Блок begin (* ... *) end работает так же, каккруглые скобки, так что вы также можете просто заключить в скобки: 

if condition then (
  instruction1 ;
  instruction 2 ;
  (* ... *)
)
else (
  (* ... *)
)

Таким образом, вы можете сделать свою оптимизацию очень хорошо.

Здесь происходит то, что при написании if b then t else f в ocaml, вы создаетезначение типа T, если t : T и f : T. Например, вы можете написать if b then 0 else 1 или if b then "Hello" else "Goodbye". Он также работает с типом unit (тип большинства инструкций): 

if b then instruction1 else instruction2

Оператор точки с запятой позволяет последовательно выполнять две инструкции: 

(;) : unit -> unit -> unit

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

Проблема в том, что когда вы пишете 

if b then instruction1 else instruction2 ; instruction 3

, это не понимается как 

if b then instruction1 else (instruction2 ; instruction 3)

как вы хотели, но как 

(if b then instruction1 else instruction2) ; instruction 3

, что также имеет смысл, потому что выражение if также имеет тип unit.

0 голосов
/ 23 октября 2019

Благодаря @ théo-winterhalter я просто так: 

let rec choose_elem_aux l n mark tmp =
  if n=0 then tmp
  else
    let r=Random.int (length l) in if mark.(r) then
      choose_elem_aux l n mark tmp else (mark.(r) <- true ;
               choose_elem_aux l (n-1) mark ((nth l r)::tmp) ;);;

let rec choose_elements l n = 
  let mark = Array.make (length l) false in
  choose_elem_aux l n mark [] ;;
...