5

私は現在、ループごとに1つの新しい要素を構築中の配列に追加する再帰関数を持つプログラムを構築しようとしています。私の関数は多数のループを実行することになっているため、append関数を何度も使用したくありませんでした。以前の経験から、append関数は一般に時間がかかることがわかりました。配列の末尾に1つの要素を追加するだけの関数をどこでも探してみましたが、そのような種類のものは見つかりませんでした。だからここで聞いてみようと思っていました。

したがって、私の質問は基本的に、「appendを使用するよりも、配列の後ろに1つの要素を追加するより効果的な方法はありますか？」です。

前の質問に関する新しい質問で更新されました

そこで、代わりにリストを使用し、新しい各要素をヘッドとして挿入し、関数が終了するとリストを元に戻しました。これにより、機能が約70倍高速になりました。しかし、ほとんど同じことを行う別の関数があり、それが約4倍遅くなり、メイン関数の全体的な時間が長くなるため、問題は残ります。機能は非常に似ています。最初の関数（はるかに高速になった関数）はintを生成し、新しい各intをリストに追加します。2番目の関数（非常に遅くなった関数）はオブジェクトを生成し、新しい各オブジェクトをリストに追加します。なぜ一方の関数が非常に速くなり、もう一方の関数が非常に遅くなったのか、誰かが知っていますか？

4

3 に答える 3

10

ResizeArrayは、このタスクのより効率的なデータ構造です。次に例を示します。

let filterRange predicate (i, j) =
    let results = ResizeArray(j-i+1)
    for k = i to j do
        if predicate k then results.Add(k)
    results.ToArray()

F＃PowerPackのResizeArrayモジュールは、機能的な方法で操作するための高階関数を提供しますResizeArray。ただし、これらの関数は新しいResizeArrayインスタンスを作成するため、.NETメソッドよりも効率が低下することに注意してください。

純粋に機能的な代替手段は、リストをアキュムレータとして使用し、要素をアキュムレータの前に追加し、それを逆にして（順序が重要な場合）、最後に配列に変換することです。

let filterRange predicate (i, j) =
    let rec loop k acc =
        if k = j+1 then acc
        elif predicate k then loop (k+1) (k::acc)
        else loop (k+1) acc
    loop i [] |> List.rev |> Array.ofList
于 2012-04-09T14:13:00.453 に答える
6

配列ではなくリストを使用することをお勧めします。配列の最終結果が本当に必要な場合は、プロセスの最後にリストを配列に変換できます。それでも高速です。

于 2012-04-09T14:15:02.310 に答える
3

いいえ。別のデータ構造を使用することをお勧めします。

于 2012-04-09T13:56:32.413 に答える