15

私がこの関数を持っているとしましょう:(Haskell構文）

f x = (x,x)

関数によって実行される作業（計算量）は何ですか？

最初は明らかに一定だと思っていましたが、タイプがx有限でない場合、つまりxが任意の量のメモリを使用できる場合はどうでしょうか。コピーによって行われる作業も考慮に入れる必要がありxますよね？

これにより、関数によって実行される作業は、実際には入力のサイズで線形であると私は信じました。

これはそれ自体が宿題ではありませんが、関数によって実行される作業を定義する必要があるときに思いついたものです。

f x = [x]

同様の問題があると私は信じています。

4

2 に答える 2

33

非常に非公式に、行われる作業は言語の操作的意味論に依存します。Haskell、まあ、それは怠惰なので、あなたは一定の要素だけを支払います：

  • ポインタをxスタックにプッシュする
  • ヒープセルを割り当てる(,)
  • (,)その引数に適用する
  • ヒープセルへのポインタを返す

終わり。O（1）作業、呼び出し元がの結果を確認するときに実行されfます。

ここで、-の内部を見ると、さらに評価をトリガーします。その作業は、それ自体(,)を評価する作業に依存しています。xHaskellではへの参照xが共有されているので、あなたはそれを一度だけ評価します。

したがって、結果を完全に評価すると、Haskellでの作業はO（xの作業）になります。関数fは一定の要素のみを追加します。

于 2012-05-31T00:20:46.057 に答える
1

クリス・オカサキは、いくらかの（または全体的な）怠惰が導入されたときに関数呼び出しに課金される作業を決定する素晴らしい方法を持っています。純粋に機能的なデータ構造に関する彼の論文にあると思います。私はそれが本のバージョンにあることを知っています-私は先月本のその部分を読みました。基本的に、作成されたプロミス/サンクに対して一定の係数を請求し、渡されたプロミス/サンクを評価するために何も請求しません（それらがすでに強制されている/ [WHNFだけでなく]通常の形式であると仮定します）。それは過小評価です。過大評価したい場合は、関数によって作成された各プロミス/サンクを強制/通常の形式に変換するコストも必要です。少なくとも、それは私が非常に疲れた状態でそれを覚えている方法です。

岡崎で調べてみてください：http ：//www.westpoint.edu/eecs/SitePages/Chris%20Okasaki.aspx#thesis-使用した論文はダウンロード可能であることを誓います。

于 2012-06-07T04:17:01.730 に答える