5

最近、List.permute を使用してリストをシャッフルするFisher-Yates シャッフルを実装しましたが、リストのサイズが大きくなるにつれて、パフォーマンスが大幅に低下することに気付きました。これは、アルゴリズムが配列で動作していると想定している一方で、順列は O(n) であるインデックスによってリスト要素にアクセスする必要があるという事実によるものと思われます。

これを確認するために、リストに順列を適用してその要素を逆にし、リストで直接作業を比較し、リストを配列に変換してリストに戻すことを試みました。 

let permute i max = max - i - 1
let test = [ 0 .. 10000 ]

let rev1 list =
   let perm i = permute i (List.length list)
   List.permute perm list

let rev2 list =
   let array = List.toArray list
   let perm i = permute i (Array.length array)
   Array.permute perm array |> Array.toList

次の結果が得られます。これは、私の仮定を裏付ける傾向があります。

rev1 test;;
Real: 00:00:00.283, CPU: 00:00:00.265, GC gen0: 0, gen1: 0, gen2: 0
rev2 test;;
Real: 00:00:00.003, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

私の質問は次のとおりです。

1) パフォーマンス上の理由から List.permute を避けるべきですか? それに関連して、List.permute の実装は自動的に Array への変換を舞台裏で行うべきではありませんか?

2) 配列を使用する以外に、要素のシャッフルなど、このタイプの作業に適したより機能的な方法/データ構造はありますか? それとも、これは単に配列が使用する適切なデータ構造であるという問題ですか?

4

2 に答える 2

7

List.permute リストを配列にArray.permute変換し、 を呼び出してから、リストに変換し直します。それに基づいて、おそらく何をする必要があるかを理解することができます (ヒント: 配列を操作してください!)。

于 2012-04-20T18:47:06.030 に答える
2

パフォーマンス上の理由から List.permute は避けるべきですか?

ここでの唯一のパフォーマンスの問題は、独自のコード、特に を呼び出すことList.lengthです。

配列を使用する以外に、このタイプの作業、つまり要素のシャッフルに適した、より機能的な方法/データ構造はありますか? それとも、これは単に配列が使用する適切なデータ構造であるという問題ですか?

実際には、要素を変更しないことで配列を機能的に使用できる場合、配列を機能的に使用できないと想定しています。permute関数を考えてみましょう:

let permute f (xs: _ []) = Array.init xs.Length (fun i -> xs.[f i])

配列に作用して配列を生成しますが、何も変更していないため、配列を純粋に機能的なデータ構造として使用しています。

于 2012-04-22T10:39:08.080 に答える