22

次のコードでは:

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l x = x == maxel
           where maxel = maximum l

main = do
  let mylist = [1, 2, 3, 5]
  let ismax = ismaxl mylist
  --Is each call O(1)?  Does each call remember maxel?
  let c1 = ismax 1
  let c2 = ismax 2
  let c3 = ismax 3
  let c5 = ismax 5
  putStrLn (show [c1, c2, c3, c5])

部分関数 ismax は maxel を計算しますか? 具体的には、Haskell の部分関数の複雑さに関する規則を誰か指摘できますか? 上記の例で、コンパイラは maximum を 1 回だけ呼び出さなければなりませんか? 別の言い方をすれば、部分関数は、内部 where 句の以前の呼び出しの参照を保持しますか?

許容範囲内で実行されていない CPU バウンド コードがいくつかあり、複雑さについての推論で考えられるエラーを探しています。

4

4 に答える 4

17

Haskellコードのプロファイリングから何を学ぶことができるかを示すために、コードにいくつかの小さな変更を加えた結果を次に示します。まず、最大値の計算に時間がかかることを確認するためにに置き換えましmylistた。[0..10000000]

そのバージョンを実行した後のプロファイリング出力からのいくつかの行は次のとおりです。

COST CENTRE                    MODULE               %time %alloc

ismaxl                         Main                  55.8    0.0
main                           Main                  44.2  100.0

                                                         individual    inherited
COST CENTRE              MODULE         no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN            1           0   0.0    0.0   100.0  100.0
 CAF:main_c5             Main          225           1   0.0    0.0    15.6    0.0
  main                   Main          249           0   0.0    0.0    15.6    0.0
   ismaxl                Main          250           1  15.6    0.0    15.6    0.0
 CAF:main_c3             Main          224           1   0.0    0.0    15.6    0.0
  main                   Main          246           0   0.0    0.0    15.6    0.0
   ismaxl                Main          247           1  15.6    0.0    15.6    0.0
 CAF:main_c2             Main          223           1   0.0    0.0    14.3    0.0
  main                   Main          243           0   0.0    0.0    14.3    0.0
   ismaxl                Main          244           1  14.3    0.0    14.3    0.0
 CAF:main_c1             Main          222           1   0.0    0.0    10.4    0.0
  main                   Main          239           0   0.0    0.0    10.4    0.0
   ismaxl                Main          240           1  10.4    0.0    10.4    0.0
 CAF:main8               Main          221           1   0.0    0.0    44.2  100.0
  main                   Main          241           0  44.2  100.0    44.2  100.0

ここで最大値を再計算しているのは明らかです。

さて、これに置き換えismaxlます：

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l = let maxel = maximum l in (== maxel)

...そして再びプロファイリング：

COST CENTRE                    MODULE               %time %alloc

main                           Main                  60.5  100.0
ismaxl                         Main                  39.5    0.0

                                                         individual    inherited
COST CENTRE              MODULE         no.    entries  %time %alloc   %time %alloc

MAIN                     MAIN            1           0   0.0    0.0   100.0  100.0
 CAF:main_c5             Main          227           1   0.0    0.0     0.0    0.0
  main                   Main          252           0   0.0    0.0     0.0    0.0
   ismaxl                Main          253           1   0.0    0.0     0.0    0.0
 CAF:main_c3             Main          226           1   0.0    0.0     0.0    0.0
  main                   Main          249           0   0.0    0.0     0.0    0.0
   ismaxl                Main          250           1   0.0    0.0     0.0    0.0
 CAF:main_c2             Main          225           1   0.0    0.0     0.0    0.0
  main                   Main          246           0   0.0    0.0     0.0    0.0
   ismaxl                Main          247           1   0.0    0.0     0.0    0.0
 CAF:main_c1             Main          224           1   0.0    0.0     0.0    0.0
 CAF:main_ismax          Main          223           1   0.0    0.0    39.5    0.0
  main                   Main          242           0   0.0    0.0    39.5    0.0
   ismaxl                Main          243           2  39.5    0.0    39.5    0.0
 CAF:main8               Main          222           1   0.0    0.0    60.5  100.0
  main                   Main          244           0  60.5  100.0    60.5  100.0

...今回は、への1回の呼び出しにほとんどの時間を費やしてismaxlおり、他の呼び出しは速すぎて気付かないため、ここで最大値を1回だけ計算する必要があります。

于 2010-11-12T17:11:52.907 に答える
11

maxelこれは、再利用されているかどうかを確認できるようにするコードの変更バージョンです。

import Debug.Trace

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l x = x == maxel
           where maxel = trace "Hello" $ maximum l

main = do
  let mylist = [1, 2, 3, 5]
  let ismax = ismaxl mylist
  --Is each call O(1)?  Does each call remember maxel?
  let c1 = ismax 1
  let c2 = ismax 2
  let c3 = ismax 3
  let c5 = ismax 5
  putStrLn (show [c1, c2, c3, c5])

maxelこれは、アプリケーション間で「記憶」されていないことがわかります。

一般に、すべての引数が関数に提供されるまで、Haskellが削減を開始することを期待するべきではありません。

一方、積極的な最適化をオンにしている場合、特定のコンパイラが実際に何をするかを予測することは困難です。しかし、コードを簡単に書き直して必要なものを明示的にすることができる時期を予測するのが難しいコンパイラの部分に依存するべきではないでしょう。

于 2010-11-12T17:15:19.463 に答える
6

他の良い答えを基に、GHCは私の経験ではこの種の最適化を実行することに熱心ではありませんでした。簡単にポイントフリーにすることができない場合は、LHSとラムダのバインドされた変数を組み合わせて書くことに頼ることがよくあります。

ismaxl :: (Ord a) => [a] -> a -> Bool
ismaxl l = \x -> x == maxel
           where maxel = maximum l

私はこのスタイルが特に好きではありませんがmaxel、部分的に適用されたへの呼び出し間で共有されることを保証しismaxlます。

于 2010-11-12T18:25:30.790 に答える
1

Haskell Reportでそのような要件を見つけることができませんでした。実際、GHCはデフォルトでこの最適化を実行していないようです。

main関数をに変更しました

main = do
  let mylist = [1..99999]
  let ismax = ismaxl mylist
  let c1 = ismax 1
  let c2 = ismax 2
  let c3 = ismax 3
  let c5 = ismax 5
  putStrLn (show [c1, c2, c3, c5])

簡単なプロファイリングショー（私の古いPentium 4）：

$ ghc a.hs
$ time ./a.out 
[False,False,False,False]

real    0m0.313s
user    0m0.220s
sys     0m0.044s

しかし、、などの定義を変更するc2と（c3そのままにして）、次のようになります。c5let c2 = 2 == 99999c1

$ ghc a.hs
$ time ./a.out 
[False,False,False,False]

real    0m0.113s
user    0m0.060s
sys     0m0.028s
于 2010-11-12T17:11:15.063 に答える