只想选择列表中的一些随机元素并在 OCaml 中返回它们

Question

我想在列表中选择

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 ;;

Answer 1

首先，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 (
  (* ... *)
)

这样您就可以很好地进行优化。

这里发生的情况是，当在 ocaml 中编写

if b then t else f

时，如果

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

。

Answer 2

感谢@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 [] ;;

Answer 3

为了提高效率，我建议使用从 -1 到 1 的随机 int 值对列表进行排序 first，然后 then 从排序列表中选择前 n 个元素。

let choose n l = 
  l 
  |> List.sort (fun _ _ -> Random.int 3 - 1) 
  |> List.to_seq 
  |> Seq.take n 
  |> List.of_seq