2

のリストを生成する関数を作成し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：'リスト->'リスト->'リスト2つのリストを連結します。中置演算子@と同じ関数。末尾再帰ではありません（最初の引数の長さ）。@演算子も末尾再帰ではありません。

したがって、オーバーフローを引き起こしているのは関数ではなく、@関数です。ただし、シャッフルされたリストを作成することだけを考えているので、リストの最後に物事を追加する理由はありません。演算子が末尾再帰であったとしても@、リストの追加は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から、関数を呼び出さないでください。

  • 関数のユーザーは、再現可能な結果（テスト、結果の共有など）を取得するためにシードを制御したい場合があります。

  • これにより、それほどランダムではないエントロピーソースでシードがリセットされる可能性があり、おそらくこれを1回だけ実行する必要があります。

于 2013-02-26T19:31:50.450 に答える