12

Project Euler's Challenge 14 のコードをHaskellとC++の両方で作成しました(ideone リンク)。どちらも、以前に配列で行った計算を記憶しています。

それぞれ とを使用するghc -O2とg++ -O3、C++ は Haskell バージョンよりも 10 ～ 15 倍速く実行されます。

Haskell バージョンの実行速度が遅くなる可能性があり、Haskell の方が書き込みに適した言語であることは理解していますが、Haskell バージョンを高速に実行できるようにするためにコードを変更できることを知っておくとよいでしょう (理想的には 2 倍または 2 倍以内)。 C++ バージョンの 3)?

Haskell コードは次のとおりです。

import Data.Array
import Data.Word
import Data.List

collatz_array = 
  let
    upperbound = 1000000
    a = array (1, upperbound) [(i :: Word64, f i :: Int) | i <- [1..upperbound]]
    f i = i `seq`
      let
        check_f i = i `seq` if i <= upperbound then a ! i else f i
      in
        if (i == 1) then 0 else (check_f ((if (even i) then i else 3 * i + 1) `div` 2)) + 1
  in a

main = 
  putStrLn $ show $ 
   foldl1' (\(x1,x2) (y1,y2) -> if (x2 >= y2) then (x1, x2) else (y1, y2)) $! (assocs collatz_array)

編集：

ボックス化されていない可変配列を使用したバージョンも作成しました。C++ バージョンよりも 5 倍遅いですが、大幅に改善されています。コードは ideone hereにあります。

C++ バージョンに近づける可変配列バージョンの改善点を知りたいです。

4

2 に答える 2

4

（可変配列）コードに関するいくつかの問題：

  • foldを使用して最大チェーン長を見つけます。これは、配列を関連付けリストに変換する必要があるため、時間がかかり、C++バージョンの割り当ては必要ありません。
  • を使用evenしてdiv、respを2で割ってテストします。これらは遅いです。g ++は、両方の操作をより高速なビット操作に最​​適化します（少なくとも、それがより高速であると思われるプラットフォームでは）が、GHCはこれらの低レベルの最適化を（まだ）実行しないため、当面は手動で実行する必要があります。
  • とを使用readArrayしwriteArrayます。C ++コードで行われない余分な境界チェックも時間がかかります。他の問題が処理されると、実行時間のかなりの部分（私のボックスでは約25％）になります。アルゴリズムでの多くの読み取りと書き込み。

それを実装に組み込むと、

import Data.Array.ST
import Data.Array.Base
import Control.Monad.ST
import Data.Bits

collatz_array :: ST s (STUArray s Int Int)
collatz_array = do
    let upper = 10000000
    arr <- newArray (0,upper) 0
    unsafeWrite arr 2 1
    let check i
            | upper < i = return arr
            | i .&. 1 == 0 = do
                l <- unsafeRead arr (i `shiftR` 1)
                unsafeWrite arr i (l+1)
                check (i+1)
            | otherwise = do
                let j = (3*i+1) `shiftR` 1
                    find k l
                        | upper < k = find (next k) $! l+1
                        | k < i     = do
                            m <- unsafeRead arr k
                            return (m+l)
                        | otherwise = do
                            m <- unsafeRead arr k
                            if m == 0
                              then do
                                  n <- find (next k) 1
                                  unsafeWrite arr k n
                                  return (n+l)
                              else return (m+l)
                          where
                            next h
                                | h .&. 1 == 0 = h `shiftR` 1
                                | otherwise = (3*h+1) `shiftR` 1
                l <- find j 1
                unsafeWrite arr i l
                check (i+1)
    check 3

collatz_max :: ST s (Int,Int)
collatz_max = do
    car <- collatz_array
    (_,upper) <- getBounds car
    let find w m i
            | upper < i = return (w,m)
            | otherwise = do
                l <- unsafeRead car i
                if m < l
                  then find i l (i+1)
                  else find w m (i+1)
    find 1 0 2

main :: IO ()
main = print (runST collatz_max)

そしてタイミング（両方とも1000万）：

$ time ./cccoll
8400511 429

real    0m0.210s
user    0m0.200s
sys     0m0.009s
$ time ./stcoll
(8400511,429)

real    0m0.341s
user    0m0.307s
sys     0m0.033s

それほど悪くはありません。

重要な注意：中間チェーン要素が32を超えるため、このコードは64ビットGHCでのみ機能します（特に、Windowsではghc-7.6.1以降が必要です。以前のGHCは64ビットWindowsでも32ビットでした）。 -ビット範囲。32ビットシステムでは、基本的な64ビット演算（算術およびシフト）が外部呼び出しとして実装されるため、大幅なパフォーマンスコストで、チェーンを追跡するためにIntegerまたは64ビット整数型（Int64または）を使用する必要があります。 Word64Cは32ビットGHCで機能します（高速の外部呼び出しですが、直接のマシン操作よりもはるかに低速です）。

于 2012-06-04T10:57:49.407 に答える
2

ideone サイトはかなり古い ghc 6.8.2 を使用しています。ghc バージョン 7.4.1 では、違いははるかに小さくなっています。

ghc の場合:

$ ghc -O2 euler14.hs && time ./euler14
(837799,329)
./euler14  0.63s user 0.04s system 98% cpu 0.685 total

g++ 4.7.0 の場合:

$ g++ --std=c++0x -O3 euler14.cpp && time ./a.out
8400511 429
./a.out  0.24s user 0.01s system 99% cpu 0.252 total

私にとって、ghc バージョンは c++ バージョンよりも 2.7 倍遅いだけです。また、2 つのプログラムは同じ結果を出していません... (特にベンチマークでは良い兆候ではありません)

于 2012-06-04T07:03:13.440 に答える