haskell - 数字の大きなリストを合計するのが遅すぎる

Question

タスク: 「最初の 15,000,000 個の偶数を合計します。」

ハスケル:

nats = [1..] :: [Int]
evens = filter even nats :: [Int]

MySum:: Int
MySum= sum $ take 15000000 evens

...しかし、時間がMySumかかります。より正確には、C/C++ よりも約 10 ～ 20 倍遅くなります。

自然にコード化された Haskell ソリューションは、C よりも 10 倍遅いことが何度もわかりました。

したがって、C よりも 1.5 ～ 2 倍遅いことが予想されます。どこに問題があるのでしょうか。

これはもっとうまく解決できますか？

これは私が比較しているCコードです：

long long sum = 0;
int n = 0, i = 1;

for (;;) {

  if (i % 2 == 0) {
    sum += i;
    n++;
  }

  if (n == 15000000)
    break;

  i++;
}

編集1：O（1）で計算できることは本当に知っています。抵抗してください。

編集2：私は本当に知っています[2,4..]が、関数は別のevenものO(1)である可能性があり、関数として実装する必要があります。

score 24 · Accepted Answer

リストはループではありません

したがって、ループの代わりにリストを使用しても驚かないでください。ループ本体が小さいと、コードが遅くなります。

nats = [1..] :: [Int]
evens = filter even nats :: [Int]

dumbSum :: Int
dumbSum = sum $ take 15000000 evens

sumは「良い消費者」ではないため、GHC は (まだ) 中間リストを完全に排除することはできません。

最適化してコンパイルする (そしてをエクスポートしない) 場合、GHC は列挙型とnat融合するのに十分スマートです。filter

Rec {
Main.main_go [Occ=LoopBreaker]
  :: GHC.Prim.Int# -> GHC.Prim.Int# -> [GHC.Types.Int]
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType L]
Main.main_go =
  \ (x_aV2 :: GHC.Prim.Int#) ->
    let {
      r_au7 :: GHC.Prim.Int# -> [GHC.Types.Int]
      [LclId, Str=DmdType]
      r_au7 =
        case x_aV2 of wild_Xl {
          __DEFAULT -> Main.main_go (GHC.Prim.+# wild_Xl 1);
          9223372036854775807 -> n_r1RR
        } } in
    case GHC.Prim.remInt# x_aV2 2 of _ {
      __DEFAULT -> r_au7;
      0 ->
        let {
          wild_atm :: GHC.Types.Int
          [LclId, Str=DmdType m]
          wild_atm = GHC.Types.I# x_aV2 } in
        let {
          lvl_s1Rp :: [GHC.Types.Int]
          [LclId]
          lvl_s1Rp =
            GHC.Types.:
              @ GHC.Types.Int wild_atm (GHC.Types.[] @ GHC.Types.Int) } in
        \ (m_aUL :: GHC.Prim.Int#) ->
          case GHC.Prim.<=# m_aUL 1 of _ {
            GHC.Types.False ->
              GHC.Types.: @ GHC.Types.Int wild_atm (r_au7 (GHC.Prim.-# m_aUL 1));
            GHC.Types.True -> lvl_s1Rp
          }
    }
end Rec }

しかし、それはGHCの融合がそれを取る限りです. ボクシングIntとリストセルの構築が残っています。Cコンパイラに与えるように、ループを与えると、

module Main where

import Data.Bits

main :: IO ()
main = print dumbSum

dumbSum :: Int
dumbSum = go 0 0 1
  where
    go :: Int -> Int -> Int -> Int
    go sm ct n
        | ct >= 15000000 = sm
        | n .&. 1 == 0   = go (sm + n) (ct+1) (n+1)
        | otherwise      = go sm ct (n+1)

C と期待した Haskell バージョンの間の実行時間のおおよその関係が得られます。

この種のアルゴリズムは、GHC が適切に最適化するように教えられてきたものではありません。限られたマンパワーがこれらの最適化に投入される前に、別の場所で揚げるべき大きな魚が存在します。

score 11 · Accepted Answer

ここでリストの融合が機能しない問題は、実際にはかなり微妙です。RULEリストを融合する権利を定義するとしましょう:

import GHC.Base
sum2 :: Num a => [a] -> a
sum2 = sum
{-# NOINLINE [1] sum2 #-}
{-# RULES "sum" forall (f :: forall b. (a->b->b)->b->b).
                sum2 (build f) = f (+) 0 #-}

(簡単な説明はsum2、のエイリアスとして定義し、sumGHC が早期にインライン化することを禁止するため、が削除さRULEれる前に起動する可能性があるということです。次に、リストビルダーのすぐ隣sum2を探し(定義を参照)、それを置き換えます)。直接演算による。)sum2build

次のコアが生成されるため、これはさまざまな成功を収めています。

Main.$wgo =
  \ (w_s1T4 :: GHC.Prim.Int#) ->
    case GHC.Prim.remInt# w_s1T4 2 of _ {
      __DEFAULT ->
        case w_s1T4 of wild_Xg {
          __DEFAULT -> Main.$wgo (GHC.Prim.+# wild_Xg 1);
          15000000 -> 0
        };
      0 ->
        case w_s1T4 of wild_Xg {
          __DEFAULT ->
            case Main.$wgo (GHC.Prim.+# wild_Xg 1) of ww_s1T7 { __DEFAULT ->
            GHC.Prim.+# wild_Xg ww_s1T7
            };
          15000000 -> 15000000
        }
    }

$wgoこれは素晴らしい、完全に融合されたコードです -非テールコール位置での呼び出しがあるという唯一の問題があります。これは、ループを見ているのではなく、実際にはプログラムの結果が予測可能な、深く再帰的な関数を見ていることを意味します。

Stack space overflow: current size 8388608 bytes.

ここでの根本的な問題は、Prelude のリストフュージョンが右フォールドのみを融合できることであり、合計を右フォールドとして計算すると、過度のスタック消費が直接発生します。明らかな修正は、実際にフュージョンを実装するDuncan のstream-fusion パッケージなど、実際に左折畳みを処理できるフュージョンフレームワークを使用することsumです。

別の解決策は、それをハックして、右折りを使用して左折りを実装することです。

main = print $ foldr (\x c -> c . (+x)) id [2,4..15000000] 0

これにより、現在のバージョンの GHC で実際にほぼ完璧なコードが生成されます。一方、部分的に適用された関数を排除するのに十分スマートなGHCに依存しているため、これは一般的に良い考えではありません。すでにfilterチェーンに a を追加すると、その特定の最適化が中断されます。

score 5 · Accepted Answer

最初の 15,000,000 個の偶数を合計します。

{-# LANGUAGE BangPatterns #-}

g :: Integer    -- 15000000*15000001 = 225000015000000
g = go 1 0 0
  where
    go i !a c  | c == 15000000 = a       
    go i !a c  | even i = go (i+1) (a+i) (c+1)
    go i !a c           = go (i+1) a c

最速のはずです。

score 4 · Accepted Answer

リストを一度だけトラバースしたい場合は、トラバーサルを明示的に記述できます。

nats = [1..] :: [Int]

requiredOfX :: Int -> Bool -- this way you can write a different requirement
requiredOfX x = even x

dumbSum :: Int
dumbSum = dumbSum' 0 0 nats
  where dumbSum' acc 15000000 _ = acc
        dumbSum' acc count (x:xs)
          | requiredOfX x = dumbSum' (acc + x) (count + 1) xs
          | otherwise     = dumbSum' acc (count + 1) xs

score 3 · Accepted Answer

まず、若いガウスのように賢く、 O(1)で合計を計算できます。

楽しいことはさておき、Haskell ソリューションではリストを使用します。あなたの C/C++ ソリューションはそうではないと確信しています。(Haskell のリストは非常に使いやすいので、適切でない場合でも使用したくなるでしょう。) これをベンチマークしてみてください:

sumBy2 :: Integer -> Integer
sumBy2 = f 0
  where
    f result n | n <= 1     = result
               | otherwise  = f (n + result) (n - 2)

-O2引数を指定して GHC を使用してコンパイルします。この関数は末尾再帰であるため、コンパイラは非常に効率的に実装できます。

更新:even関数を使用して必要な場合は、次のことが可能です。

sumBy2 :: Integer -> Integer
sumBy2 = f 0
  where
    f result n | n <= 0     = result
               | even n     = f (n + result) (n - 1)
               | otherwise  = f result (n - 1)

フィルタリング関数をパラメーターにすることも簡単にできます。

sumFilter :: (Integral a) => (a -> Bool) -> a -> a
sumFilter filtfn = f 0
  where
    f result n | n <= 0     = result
               | filtfn n   = f (n + result) (n - 1)
               | otherwise  = f result (n - 1)

score 2 · Accepted Answer

厳密なバージョンははるかに高速に動作します:

foldl' (+) 0 $ take 15000000 [2, 4..]

score 1 · Accepted Answer

注意すべきもう 1 つのことは、natsとevensがいわゆる定数適用形式 (Constant Applicative Forms)、略して CAF であるということです。基本的に、これらは引数のないトップレベルの定義に対応しています。CAF は少し変わったアヒルです。たとえば、恐ろしい単形性制限の理由です。言語定義でCAFをインライン化できるかどうかはわかりません。

私の Haskell の実行方法のメンタルモデルでdumbSumは、値が返されるまでに、とtoのevensように評価されます。ここで、s はまだ調べていないものを表します。私の理解が正しければ、これらの割り当ては発生する必要があり、最適化して取り除くことはできません。2:4: ... : 30000000 : <thunk>nats1:2: ... : 30000000 : <thunk><thunk>:

したがって、コードをあまり変更せずに高速化する 1 つの方法は、単純に次のように記述することです。

dumbSum :: Int
dumbSum = sum . take 15000000 . filter even $ [1..]

また

dumbSum = sum $ take 15000000 evens where
    nats = [1..]
    evens = filter even nats

でコンパイルした私のマシンでは-O2、それだけで約 30% の速度向上が見られます。

私は GHC の専門家ではありません (Haskell プログラムのプロファイルを作成したことさえありません!)。

haskell - 数字の大きなリストを合計するのが遅すぎる

7 に答える 7

リストはループではありません

Related

Reference