0

たとえば、ある関数はconsingを介してリストを作成します。

fun example1 _ _ [] = []
  | example1 f g (x::xs) =
    if f x
    then (g x)::(example1 f g xs)
    else x::(example1 f g xs)

末尾呼び出しアキュムレータを介してリストを作成します。

fun example2 f g xs =
    let fun loop acc [] = acc
          | loop acc (x::xs') =
            if f x
            then loop (acc@[(g x)]) xs'
            else loop (acc@[x]) xs'
    in
        loop [] xs
    end

同じ引数を指定して同じリストを作成します。

実行時間が長い関数はどれですか？

追加操作@はリストの最後までトラバースして、追加し、consingソリューションで同じ実行時間になりますが、使用するスペースがはるかに少なく、コードが少し複雑になりますか？

元の要素に変更がない場合や、既存の要素を再利用するだけの場合でも、consingまたはappendingはまったく新しい要素（オブジェクトのディープコピー）を作成しますか？

この質問は、この質問のより具体的な例を示しています

4

1 に答える 1

3

x :: xsxヘッドがで、テールがである1つの新しいリストセルを作成しますxs。のコピーは作成されませんxs-深いものでも浅いものでもありません。つまり、これはO（1）操作です。

xs @ [x]xs以前の最後のノードのテールが現在であるという変更を加えて、の浅いコピーを作成します[x]。これはO(n)操作です。

したがって、関数の時間計算量はであり、関数example1の時間計算量はです。どちらの機能も補助スペースを消費します。スタックの使用と、結果のリストの一部ではないリストをヒープ上に作成するためです。O(n)example2O(n^2)O(n)example1example2@

リストの最後に到達したときに結果を使用するのではなくexample2使用するように変更すると、実行時間は長くなりますが、最後にリストを元に戻すための追加コストのために、それでも多少遅くなります。ただし、スタックオーバーフローなしで大きなリストを処理できるようにするために支払うのは許容できる価格かもしれません。::@List.revO(n)example1

于 2013-03-24T13:33:46.760 に答える