6

修正オイラー問題 #4 を考えてみましょう。「100 から 9999 までの 2 つの数の積である回文数の最大値を見つけてください。」

rev :: Int -> Int
rev x = rev' x 0

rev' :: Int -> Int -> Int
rev' n r
    | n == 0 = r
    | otherwise = rev' (n `div` 10) (r * 10 + n `mod` 10)

pali :: Int -> Bool
pali x = x == rev x

main :: IO ()
main = print . maximum $ [ x*y | x <- nums, y <- nums, pali (x*y)]
    where
        nums = [9999,9998..100]
  • -O2とを使用したこの Haskell ソリューションにghc 7.4.1は、約18 秒かかります。
  • 同様のC解には0.1 秒かかります。

したがって、Haskell は 180 倍遅いです。私のソリューションの何が問題になっていますか? このタイプの問題は、Haskell がかなりうまく解決すると思います。

付録 - アナログ C ソリューション:

#define A   100
#define B   9999
int ispali(int n)
{
    int n0=n, k=0;
    while (n>0) {
        k = 10*k + n%10;
        n /= 10;
    }
    return n0 == k;
}
int main(void)
{
    int max = 0;
    for (int i=B; i>=A; i--)
        for (int j=B; j>=A; j--) {
            if (i*j > max && ispali(i*j))
                max = i*j;      }
    printf("%d\n", max);
}
4

6 に答える 6

9

同様のCソリューション

それはよくある誤解です。

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

また、リストを使用してループをエミュレートすると、コンパイラがコードからリストを削除できない限り、パフォーマンスに影響があります。

リンゴとリンゴを比較したい場合は、Haskell 構造をループ、末尾再帰ワーカーとほぼ同等に記述します (厳密なアキュムレータを使用しますが、多くの場合、コンパイラは厳密性を自分で判断できるほどスマートです)。

では、詳しく見ていきましょう。比較のために、gcc -O3 でコンパイルされた C はここで ~0.08 秒かかり、ghc -O2 でコンパイルされた元の Haskell は ~20.3 秒かかり、ghc -O2 -fllvm では ~19.9 秒かかります。かなりひどい。

元のコードの 1 つの間違いは、divandを使用することmodです。C コードは、 と に相当するものを使用しますquot。remこれらは機械除算命令にマップされ、 と よりも高速divですmod。正の引数の場合、セマンティクスは同じであるため、引数が常に非負であることがわかっている場合は常に and を使用divしないでmodください。

それを変更すると、実行時間は、ネイティブ コード ジェネレーターでコンパイルすると ~15.4 秒になり、LLVM バックエンドでコンパイルすると ~2.9 秒になります。

違いは、機械除算演算でさえも非常に遅く、LLVM は除算/剰余を乗算とシフト演算に置き換えるという事実によるものです。ネイティブ バックエンドに対して同じことを手動で行うと (実際には、引数が常に非負であることがわかっているという事実を利用した、わ​​ずかに優れた置換)、その時間が ~2.2 秒に短縮されます。

近づいていますが、C にはまだほど遠い状態です。

それはリストによるものです。このコードは、回文のリストを作成します (そしてInt、2 つの因子の s のリストをトラバースします)。

ボックス化されていない要素をリストに含めることはできないため、コード内で多くのボックス化とボックス化解除が行われ、時間がかかります。

リストを削除して、C を Haskell に変換した結果を見てみましょう。

module Main (main) where

a :: Int
a = 100

b :: Int
b = 9999

ispali :: Int -> Bool
ispali n = go n 0
  where
    go 0 acc = acc == n
    go m acc = go (m `quot` 10) (acc * 10 + (m `rem` 10))

maxpal :: Int
maxpal = go 0 b
  where
    go mx i
        | i < a = mx
        | otherwise = go (inner mx b) (i-1)
          where
            inner m j
                | j < a = m
                | p > m && ispali p = inner p (j-1)
                | otherwise = inner m (j-1)
                  where
                    p = i*j

main :: IO ()
main = print maxpal

ネストされたループは、2 つのネストされたワーカー関数に変換されます。アキュムレータを使用して、これまでに見つかった最大の回文を格納します。ghc -O2 でコンパイルすると、約 0.18 秒で実行され、ghc -O2 -fllvm で実行すると、約 0.14 秒で実行されます (そうです、LLVM はネイティブ コード ジェネレーターよりもループの最適化に適しています)。

まだ十分ではありませんが、約 2 倍というのはそれほど悪くはありません。

たぶん、ループが抽象化されて読みやすくなっている次のようになるかもしれません。生成されたコアは、すべての意図と目的が同一であり (モジュロ引数の順序の切り替え)、パフォーマンスはもちろん同じです。

module Main (main) where

a :: Int
a = 100

b :: Int
b = 9999

ispali :: Int -> Bool
ispali n = go n 0
  where
    go 0 acc = acc == n
    go m acc = go (m `quot` 10) (acc * 10 + (m `rem` 10))

downto :: Int -> Int -> a -> (a -> Int -> a) -> a
downto high low acc fun = go high acc
  where
    go i acc
        | i < low   = acc
        | otherwise = go (i-1) (fun acc i)

maxpal :: Int
maxpal = downto b a 0 $ \m i ->
            downto b a m $ \mx j ->
                let p = i*j
                in if mx < p && ispali p then p else mx

main :: IO ()
main = print maxpal
于 2012-10-25T19:02:49.887 に答える
2

@axblountは少なくとも部分的に正しいです。次の変更により、プログラムは元のプログラムのほぼ 3 倍の速度で実行されます。

maxPalindrome = foldl f 0
  where f a x | x > a && pali x = x
              | otherwise       = a

main :: IO ()
main = print . maxPalindrome $ [x * y | x <- nums, y <- nums]
  where nums = [9999,9998..100]

ただし、それでも 60 倍の速度低下が発生します。

于 2012-10-25T16:47:28.713 に答える
1

Haskell はそのリスト全体 [ x*y | ] を保存している可能性があります。x <- nums, y <- nums, pali (x*y)] ここで、C ソリューションはオンザフライで最大値を計算します。これについてはよくわかりません。

また、C ソリューションは、製品が以前の最大値を上回った場合にのみ ispali を計算します。x*y が可能な最大値であるかどうかに関係なく、Haskell の計算は回文積であるに違いありません。

于 2012-10-25T16:31:00.980 に答える
1

これは、C コードが行っていることにより当てはまります。

maxpali :: [Int] -> Int
maxpali xs = go xs 0
  where
    go [] m     = m
    go (x:xs) m = if x > m && pali(x) then go xs x else go xs m

main :: IO()
main = print . maxpali $ [ x*y | x <- nums, y <- nums ]
  where nums = [9999,9998..100]

私のボックスでは、C バージョンでは 0.5 秒かかるのに対し、これには 2 秒かかります。

于 2012-10-25T16:58:36.050 に答える
0

これを書く別の方法は、フラット化されたリストを 1 つ折りにする代わりに、2つ折りにすることです。

-- foldl g0 0 [x*y | x<-[b-1,b-2..a], y<-[b-1,b-2..a], pali(x*y)]      (A)
-- foldl g1 0 [x*y | x<-[b-1,b-2..a], y<-[b-1,b-2..a]]                 (B)
-- foldl g2 0 [ [x*y | y<-[b-1,b-2..a]] | x<-[b-1,b-2..a]]             (C)

maxpal b a = foldl f1 0 [b-1,b-2..a]                              --   (D)
  where
    f1 m x = foldl f2 m [b-1,b-2..a]
      where
        f2 m y | p>m && pali p = p
               | otherwise     = m  
           where p = x*y

main = print $ maxpal 10000 100

(B)（larsmansの回答のように）よりもはるかに高速に実行されるようです（次のループベースのコードよりも3倍から4倍遅いだけです）。融合foldlとenumFromThenTo定義により、「機能ループ」コードが得られます（DanielFischerの回答のように）、

maxpal_loops b a = f (b-1) 0                                      --   (E)
  where               
    f x m | x < a     = m 
          | otherwise = g (b-1) m 
      where
        g y m | y < a         = f (x-1) m
              | p>m && pali p = g (y-1) p 
              | otherwise     = g (y-1) m
           where p = x*y

バリアントは、フラット化によって破壊された、リスト内の隠された順序を利用するさらなるアルゴリズム(C)の改善 (もちろん元の Q の範囲外です) を非常に示唆しています。

{- foldl g2 0 [ [x*y | y<-[b-1,b-2..a]] | x<-[b-1,b-2..a]]             (C)
   foldl g2 0 [ [x*y | y<-[x,  x-1..a]] | x<-[b-1,b-2..a]]             (C1)
   foldl g0 0 [ safehead 0 . filter pali $
                [x*y | y<-[x,  x-1..a]] | x<-[b-1,b-2..a]]             (C2)
   fst $ until ... (\(m,s)-> (max m .
                safehead 0 . filter pali . takeWhile (> m) $
                                                   head s, tail s))          
           (0,[ [x*y | y<-[x,  x-1..a]] | x<-[b-1,b-2..a]])            (C3)
   safehead 0 $ filter pali $ mergeAllDescending
              [ [x*y | y<-[x,  x-1..a]] | x<-[b-1,b-2..a]]             (C4)
-}

(C3)x*yサブリストのヘッドが現在見つかっている最大値よりも小さくなるとすぐに停止できます。これは、短縮機能ループ コードが達成できるものですが、最初(C4)に最大回文数を見つけることが保証されているものではありません。さらに、リストベースのコードの場合、そのアルゴリズムの性質はより視覚的に明らかです.IMO.

于 2012-10-27T07:31:15.597 に答える
0

分岐予測の問題を抱えているようです。C コードでは、2 つの入れ子になったループがあり、内側のループで回文が検出されるとすぐに、内側のループの残りが非常に高速にスキップされます。

ネストされたループの代わりにこの製品リストをフィードする方法は、ghc がこの予測を行っているかどうかわかりません。

于 2012-10-25T17:21:38.470 に答える