2

我写了一个生成 in 列表的randomized ints函数OCaml。

let create_shuffled_int_list n = 
  Random.self_init;
  let rec create n' acc =
    if n' = 0 then acc
    else 
      create (n'-1) (acc @ [Random.int (n/2)])
  in 
  create n [];;

当我尝试生成10000整数时，它给出了Exception: RangeError: Maximum call stack size exceeded.错误。

但是，我相信这个功能，我用过tail-recursion，它应该不会stackoverflow出错，对吧？

任何想法？

4

2 回答 2

5

来自核心库文档

val append : 'a list -> 'a list -> 'a list 连接两个列表。与中缀运算符@ 相同的功能。不是尾递归的（第一个参数的长度）。@ 运算符也不是尾递归的。

所以导致溢出的不是你的函数，而是@函数。但是，由于您只关心生成洗牌列表，因此没有理由将内容附加到列表的末尾。即使@运算符是尾递归的，列表追加仍然是 O(n)。然而，列表前置是 O(1)。因此，如果您将新的随机数放在列表的前面，则可以避免溢出（并使您的函数更快）：

let create_shuffled_int_list n = 
  Random.self_init;
  let rec create n' acc =
    if n' = 0 then acc
    else 
      create (n'-1) (Random.int (n/2) :: acc)
  in 
  create n [];;

如果您关心订单（不知道为什么），那么只需在最后粘贴一个 List.rev ：

List.rev (create n []);;
于 2013-02-25T11:46:16.273 回答
2

顺便说一句，您不应该调用Random.self_init函数，因为：

  • 您的功能的用户可能想要控制种子以获得可重现的结果（测试、共享结果......）

  • 这可能会使用不那么随机的熵源重置种子，您可能只想这样做一次。

于 2013-02-26T19:31:50.450 回答