2

2次元配列の基本関数を書いています。"set" 関数の書き方には 2 つの方法があります。1 つ目は、行列のコピーを作成してから変更することです。

let copy_matrix (m: 'a array array): 'a array array =
  let l = Array.length m in
    if l = 0 then m else
      let result = Array.make l m.(0) in
        for i = 0 to l - 1 do
           result.(i) <- Array.copy m.(i)
        done;
        result

let set_copy (m: 'a array array) (r: int) (c: int) (v: 'a): 'a array array =
  let m' = copy_matrix m in
  m'.(r).(c) <- v;
  m'

2 つ目は、マトリックスを直接変更するだけです。

let set (m: 'a array array) (r: int) (c:int) (v: 'a) : unit =
  m.(r).(c) <- v

それが Java の場合、2 番目の関数が最初の関数よりも高速で経済的であることは明らかだと思います。しかし、誰かが (私は忘れました) 私に、1) OCaml のメモリ管理はset_copy非常にスマートで、あまりコストがかからないこと、2) よりも使用する方が良いいくつかの理由 (忘れていました) があることをset_copy教えてくれましたset。

これが本当かどうか誰か教えてもらえますか?

4

2 に答える 2

5

永続的な配列が必要な場合 (バックトラッキングの目的などですべてのバージョンを保持する必要がある場合)、もちろんコピー バージョンの方がはるかに優れていますが、遅くなります。この StackOverflow の投稿で永続配列データ構造について説明しました。永続性が必要な場合は、プレーン配列の代わりにそれらを使用することを検討してください。永続配列の永続配列を使用して行列を処理すると、おそらくうまく機能します。もちろん、開始点として型のキーを持つMap(int * int)を使用することもできます(ただし、アクセス コストは無視できません)。

永続化が必要ない場合 (「古い」配列を維持する必要がない場合)、コピーを避けて標準のデータ型を維持することをお勧めします。

matrix_copyまた、次のように実装することもできます

let matrix_copy m = Array.map Array.copy m
于 2013-05-10T16:58:13.297 に答える
3

1 つの値を変更するたびに配列全体をコピーすることをカバーできるメモリ管理の魔法はないと思います。

配列だけでなく他のすべてにも適用される、不変データを使用する非常に正当な理由があります。ただし、配列が小さい場合を除き、表示するコードをコピーすると、かなりのコストがかかります。

それほど多くのコピーを必要としない、配列を表現する他の方法 (差分リストやツリーなど) があります。しかし、もちろん、彼らには独自の問題があります。

于 2013-05-10T16:50:49.350 に答える