6

マージソートとクイックソートのベンチマークを行っています。

Random_list.create、Mergesort.sort_listおよびを実装しQuicksort.sort_listました。この質問では、3 つの関数が正しく実装されており、実装は重要ではないと想定できます。

聞きたいのは OCaml の GC についてです。

ここに私のベンチマークコードがあります:

let _ = 
  let l = Random_list.create 10000000 in

  let len1 = List.length (Mergesort.sort_list l) in
  Printf.printf "mergesort done for %d elements" len1;

  let len2 = List.length (Quicksort.sort_list l) in
  Printf.printf "quicksort done for %d elements" len2

上記のコードを実行すると、Fatal error: exception Out_of_memoryafterが表示されmergesort done for 10000000 elementsます。

メモリ不足です。問題ありません。また、出力はOut_of_memory成功した後に発生したことを示していmergesortます。

次に、コードを分割して個別にテストしました。

let _ = 
      let l = Random_list.create 10000000 in
      let len1 = List.length (Mergesort.sort_list l) in
      Printf.printf "mergesort done for %d elements" len1

その後

let _ = 
      let l = Random_list.create 10000000 in
      let len2 = List.length (Quicksort.sort_list l) in
      Printf.printf "quicksort done for %d elements" len2

どちらもなし Out_of_memoryで正常に動作します。

これが私の質問です：

私のベンチマークコードから、はい、シリアルソートを行いました：マージソートとクイックソート。

実行中に、3 つの主要なリストが作成されるはずです:lマージソートからのリストとクイックソートからのリスト。

GCedしかし、mergesort から作成されたリストは、quicksort の前にあるはずですよね? そのリストにはそれへの参照がありませんよね？

クイックソートの前に、元の主要なリストは 1 つだけlですよね?

それでもOut_of_memoryエラーが発生するのはなぜですか？

4

2 に答える 2

2

コードを見ずに結論を出すのは難しいですが、最初のプログラムでは、スタック フレームへのポインターMergesort.sort_list lとQuicksort.sort_list lスタック フレーム内にポインターがあり、最初のリストがガベージ コレクションされるのを妨げている可能性があります。二つlet _ = ...？

于 2013-07-19T19:43:03.633 に答える