2

そこで、Cコードの一部をHaskellに変換したいと思います。この部分 (やりたいことの単純化された例です) は C で書きましたが、Haskell の初心者なので、実際に機能させることはできません。

float g(int n, float a, float p, float s)
{
    int c;
    while (n>0)
    {
        c = n % 2;
        if (!c) s += p;
        else s -= p;
        p *= a;
        n--;
    }
    return s;
}

アイデアや解決策はありますか？

4

7 に答える 7

15

Lee の翻訳はすでにかなり優れています (まあ、彼は奇数と偶数のケースを混同していました(1) ) が、いくつかのパフォーマンス トラップに陥りました。

g n a p s =
  if n > 0
  then
    let c = n `mod` 2
        s' = (if c == 0 then (-) else (+)) s p
        p' = p * a
    in g (n-1) a p' s'        
  else s

  1. 彼はmodの代わりに使用しましたrem。後者は機械除算に対応し、前者は追加のチェックを実行して、負でない結果を保証します。したがってmod、 は よりも少し遅く、remどちらかがニーズを満たしている場合 - 両方の引数が負でない場合に同じ結果が得られるためです。または、結果が 0 とのみ比較されるため (ここでは両方の条件が満たされています) -remが望ましいです。さらに良いのは、もう少し慣用的に使用することですeven(これはrem上記の理由で使用されます)。ただし、違いはそれほど大きくありません。

  2. 型シグネチャはありません。これは、コードが (型クラス) ポリモーフィックであることを意味し、厳密性分析も特殊化も不可能です。コードが同じモジュール内の特定の型で使用されている場合、GHC はその特定の型に特化したバージョンを作成できます (最適化が有効になっている場合は通常そうします)。これにより、厳密性分析やその他の最適化 (クラス メソッドのインライン化など) が可能になります(+)。 ）、その場合、ポリモヒズムのペナルティは支払われません。しかし、使用場所が別のモジュールにある場合、それは起こりません。(型クラス) ポリモーフィック コードが必要な場合は、 (GHC < 7 の場合)INLINABLEまたはINLINE(GHC < 7 の場合) とマークして、その展開が.hiファイル内で公開され、関数が使用場所で特化および最適化されるようにする必要があります。

    は再帰的であるためg、インライン化できません [つまり、GHC はインライン化できません。原則として、それは可能です] 使用場所では、単なる専門化よりも多くの最適化を可能にすることがよくあります。

    再帰関数をより適切に最適化できるテクニックの 1 つは、ワーカー/ラッパー変換です。再帰的 (ローカル) ワーカーを呼び出すラッパーを作成すると、非再帰的ラッパーをインライン化できます。ワーカーが既知の引数で呼び出されると、定数の折りたたみなどのさらなる最適化が可能になります。関数引数の場合は、インライン化。特に後者は、static-argument-transformation (再帰呼び出しで変更されない引数は、再帰ワーカーに引数として渡されません) と組み合わせると、大きな影響を与えることがよくあります。

    この場合、 type の static 引数が 1 つしかないFloatため、SAT を使用したワーカー/ラッパー変換は通常、違いはありません (経験則として、SAT は次の場合に効果があります)。

    • static 引数は関数です
    • いくつかの非関数引数は静的です

    したがって、この規則により、w/w + SAT からの利益は期待できません。一般的には、何もありません)。ここで、w/w + SAT が大きな違いを生む特殊なケースが1 つaあります。それは、係数が 1 の場合です。GHC には{-# RULES #-}、さまざまな型に対して 1 の乗算をなくす機能があり、そのような短いループ本体では、乗算は 1 倍以上になります。反復ごとに少ないほど違いが生じ、ポイント 3 と 4 が適用された後、実行時間は約 40% 短縮されます。(それぞれがNaN を保持しないためRULES、0 による乗算または-1浮動小数点型のby はありません0*x = 0。 ) 他のすべての場合、 w/w + SATed(-1)*x = -xa

    {-# INLINABLE g #-}
g n a p s = worker n p s
  where
    worker n p s
      | n <= 0    = s
      | otherwise = let s' = if even n then s + p else s - p
                    in worker (n-1) a (p*a) s'

    同じ最適化を行っても、最上位の再帰バージョンと大きく異なるパフォーマンスはありません。

  3. 厳格さ。GHC の厳密性アナライザーは優れていますが、完全ではありません。関数が

    • 厳格なpif (追加 - - が両方の引数で厳格であるとn >= 1 仮定)(+)
    • aifでも厳密(両方の引数n >= 2が厳密であると仮定)(*)

    そして、両方に厳格なワーカーを生成します。代わりに、ボックス化されていない for とボックス化されていないfor (ここでは C に対応する型を使用しています)、およびボックス化されたs forInt#とを使用するワーカーを取得します。したがって、各イテレーションで、2 回のボックス化解除と 1 回の再ボックス化が行われます。これには (比較的) 多くの時間がかかります。それ以外は、単純な計算とテストに過ぎないからです。GHC を少し助けて、ワーカ (またはワーカ/ラッパー変換を行わない場合はそれ自体) を正格にします(たとえば、bang パターン)。ボックス化されていない値を使用して GHC がワーカを作成できるようにするには、これで十分です。nFloat#sInt -> Float -> Float -> Float -> FloatFloatapgp

  4. 除算を使用してパリティをテストします (タイプがIntで、LLVM バックエンドが使用されている場合は適用されません)。

    GHC のオプティマイザーはまだ低レベルのビットにあまり取り掛かっていないので、ネイティブ コード ジェネレーターは次の除算命令を発行します。

    x `rem` 2 == 0

    そして、ループ本体の残りの部分がここと同じくらい安価な場合、それには多くの時間がかかります。LLVM のオプティマイザーは、それを type のビットマスキングに置き換えるように既に教えられているIntのでghc -O2 -fllvm、手動で行う必要はありません。ネイティブコードジェネレーターを使用して、それを次のように置き換えます

    x .&. 1 == 0

    （もちろん必要import Data.Bitsです）大幅な高速化を実現します（通常のプラットフォームでは、ビットごとの と は除算よりもはるかに高速です）。

最終結果

{-# INLINABLE g #-}
g n a p s = worker n p s
  where
    worker k !ap acc
        | k > 0 = worker (k-1) (ap*a) (if k .&. (1 :: Int) == 0 then acc + ap else acc - ap)
        | otherwise = acc

gcc が乗算を否定に置き換える (すべての NaN が同等であると仮定する)ことgcc -O3 -msse2 loop.cを除いて、 の結果と (テストされた値に対して) 測定可能なほどの違いはありません。a = -1

(1)それは彼だけではなく、

c = n % 2;
if (!c) s += p;
else s -= p;

私が見る限り、誰もが（2）それを間違えているようです.

(2) 1 つの例外を除いて ;)

于 2012-11-28T15:39:22.297 に答える
5

最初のステップとして、コードを単純化しましょう。

float g(int n, float a, float p, float s) {
    if (n <= 0) return s;

    float s2 = n % 2 == 0 ? s + p : s - p;
    return g(n - 1, a, a*p, s2)
}

元の関数を特定の構造を示す再帰関数に変えました。シークエンスです！これを Haskell に便利に変換できます。

gs :: Bool -> Float -> Float -> Float -> [Float]
gs nb a p s = s : gs (not nb) a (a*p) (if nb then s - p else s + p)

最後に、このリストにインデックスを付ける必要があります。

g :: Integer -> Float -> Float -> Float -> Float
g n a p s = gs (even n) a p s !! (n - 1)

コードはテストされていませんが、動作するはずです。そうでない場合は、おそらく 1 つずれただけのエラーです。

于 2012-11-28T13:29:20.230 に答える
5

Haskell でこの問題に取り組む方法を次に示します。まず、いくつかのループが 1 つにマージされていることがわかります。

  1. 等比数列の形成 (その因数は p の適切な負のバージョン)
  2. シーケンスの接頭辞を取る
  3. 結果を合計する

したがって、私のソリューションもこの構造に従います。これは、コードが行うことであるため、適切な測定のためにわずかなsとがpスローされます。ゼロからのバージョンでは、おそらくこれら 2 つのパラメーターを完全に削除します。

g n a p s = sum (s : take n (iterate (*(-a)) start)) where
    start | odd n     = -p
          | otherwise = p
于 2012-11-28T14:56:32.497 に答える
4

関数のシグネチャg(つまり float g (int n, float a, float p, float s)) を見てください。Haskell 関数が 4 つの要素を受け取り、float を返すことがわかっているため、次のようになります。

g :: Integer -> Float -> Float -> Float -> Float

ループを調べてみましょう。これn > 0が停止ケースでありn--;、再帰呼び出しで使用される減少ステップであることがわかります。したがって：

g :: Integer -> Float -> Float -> Float -> Float
g n a p s | n <= 0 = s

to 、ループ内にn > 0別の条件があります。が奇数のif (!(n % 2)) s += p; else s -= p;場合、 、および. Haskell では次のようになります。ns += pp *= an--

g :: Integer -> Float -> Float -> Float -> Float
g n a p s | n <= 0 = s
          | odd n = g (n-1) a (p*a) (s+p)

あなたnがするよりも偶数である場合s-=p、p*=a;およびn--。したがって：

g :: Integer -> Float -> Float -> Float -> Float
g n a p s | n <= 0 = s
          | odd n = g (n-1) a (p*a) (s+p)
          | otherwise = g (n-1) a (p*a) (s-p)
于 2012-11-28T15:28:42.670 に答える
3

@Landei と @MathematicalOrchid の質問の下のコメントを拡張するには: 目前の問題を解決するために提案されたアルゴリズムは常に O(n) です。ただし、実際に行っているのは等比級数の部分和の計算であることがわかっている場合は、よく知られた和の公式を使用できます。

g n a p s = s + (-1)**n * p * ((-a)**n-1) / (-a-1)

これは、現代のコンパイラによって整数累乗に自動的に採用される可能性が高い二乗または他の巧妙な方法を繰り返すことにより、累乗が O(n) よりも高速に実行できるため、高速になります。

于 2012-11-30T03:12:14.150 に答える
3

Haskell Prelude 関数を使用すると、ほぼ自然にループをエンコードできますuntil :: (a -> Bool) -> (a -> a) -> a -> a。

g :: Int -> Float -> Float -> Float -> Float
g n a p s = 
  fst.snd $ 
    until ((<= 0).fst) 
          (\(n,(!s,!p)) -> (n-1, (if even n then s+p else s-p, p*a)))
          (n,(s,p))

bang-patterns!sと!pmark は、厳密に計算された中間変数を使用して、効率を損なう過度の怠惰を防ぎます。

until pred step startstep最後に生成された値で呼び出されるまで関数を繰り返し適用し、pred初期値から始めますstart。これは、次の擬似コードで表すことができます。

def until (pred, step, start):             // well, actually,
  while( true ):                         def until (pred, step, start): 
    if pred(start): return(start)          if pred(start): return(start)
    start := step(start)                   call until(pred, step, step(start))

最初の疑似コードは、テール コールの最適化が存在する場合の 2 番目の疑似コード (これが実際の実装until方法です)と同等です。これが、TCO が存在する多くの関数型言語でループが再帰によってエンコードされる理由です。

したがって、Haskell では、次のuntilようにコーディングされます。

until p f x  | p x       = x
             | otherwise = until p f (f x)

ただし、別の方法でコーディングして、中間結果を明示することもできます。

until p f x = last $ go x     -- or, last (go x)
  where go x | p x       = [x]
             | otherwise = x : go (f x)

Haskell 標準の高階関数を使用するbreakと、iterateこれをストリーム処理コードとして記述できます。

until p f x = let (_,(r:_)) = break p (iterate f x) in r
                       -- or: span (not.p) ....

あるいは単に

until p f x = head $ dropWhile (not.p) $ iterate f x    -- or, equivalently,
           -- head . dropWhile (not.p) . iterate f $ x

特定の Haskell 実装に TCO が存在しない場合は、最後のバージョンが使用されます。

うまくいけば、これにより、ダニエル・ワグナーの回答からのストリーム処理コードがどのように発生するかが明確になります。

g n a p s = s + (sum . take n . iterate (*(-a)) $ if odd n then (-p) else p)

関連する述語は からのカウントダウンに関するものであるためn、

fst . snd . head . dropWhile ((> 0).fst) $
  iterate (\(n,(!s,!p)) -> (n-1, (if even n then s+p else s-p, p*a)))
          (n,(s,p))
===
fst . snd . head . dropWhile ((> 0).fst) $
  iterate (\(n,(!s,!p)) -> (n-1, (s+p, p*(-a))))
          (n,(s, if odd n then (-p) else p))          -- 0 is even
===
fst . (!! n) $
  iterate (\(!s,!p) -> (s+p, p*(-a)))
          (s, if odd n then (-p) else p)    
===
foldl' (+) s . take n . iterate (*(-a)) $ if odd n then (-p) else p

純粋な FPでは、ストリーム処理パラダイムにより、計算のすべての履歴が値のストリーム (リスト) として利用可能になります。

于 2012-11-29T10:48:30.670 に答える