編集して質問に答える
私はこれを正しくしましたか？
コメントが言ったように、ほとんどの場合、大きなサンクを構築します1+(1+(1+...))-代わりに厳密なアキュムレータを使用するか、物事を処理する高レベルの関数を使用します。使用する代わりに 2 番目の要素を比較する関数を定義するなど、他にもマイナーなことがありますが、それはmaximumBy (comparing snd)よりスタイルです。
現状では、それを行うための適切なHaskellの方法はありますか?
それは容認できる慣用的な Haskell コードです。
どうすればもっと速くできますか？
以下のベンチマークを参照してください。オイラー性能に関する質問に対する非常に一般的な回答は次のとおりです。
- -O2 を使用します (あなたがしたように)
- -fllvm を試す (GHC NCG は準最適)
- ワーカー/ラッパーを使用して引数を減らすか、場合によってはアキュムレータを活用してください。
- 高速/ボックス化できない型を使用します (代わりに整数を使用できる場合は Int、移植性のために必要な場合は Int64 など)。
- すべての値が正
remの場合の代わりに使用します。あなたの場合、より遅いものにコンパイルする傾向があることmodを知っているか発見することも役に立ちます。divquot
また、メモリ使用量に関して、再帰は実際に低レベルでどのように実装されていますか? それはどのようにメモリを使用しますか？
これらの質問は両方とも非常に広範です。完全な回答は、遅延評価、テール コールの最適化、ワーカーの変換、ガベージ コレクションなどに対処する必要がある可能性があります。時間をかけてこれらの回答をさらに詳しく調べることをお勧めします (または、ここの誰かが私が避けている完全な回答をしてくれることを願っています)。
元の投稿 - ベンチマーク番号
オリジナル：
$ ghc -O2 so.hs ; time ./so
[1 of 1] Compiling Main ( so.hs, so.o )
Linking so ...
(837799,525)
real 0m5.971s
user 0m5.940s
sys 0m0.019s
のアキュムレータでワーカー関数を使用しますcollatzLength。
$ ghc -O2 so.hs ; time ./so
[1 of 1] Compiling Main ( so.hs, so.o )
Linking so ...
(837799,525)
real 0m5.617s
user 0m5.590s
sys 0m0.012s
を使用Intし、デフォルトではありませんInteger- 型シグネチャを使用すると読みやすくなります!
$ ghc -O2 so.hs ; time ./so
[1 of 1] Compiling Main ( so.hs, so.o )
Linking so ...
(837799,525)
real 0m2.937s
user 0m2.932s
sys 0m0.001s
使用し、使用remしないmod:
$ ghc -O2 so.hs ; time ./so
[1 of 1] Compiling Main ( so.hs, so.o )
Linking so ...
(837799,525)
real 0m2.436s
user 0m2.431s
sys 0m0.001s
quotRemand not remthenを使用div:
$ ghc -O2 so.hs ; time ./so
[1 of 1] Compiling Main ( so.hs, so.o )
Linking so ...
(837799,525)
real 0m1.672s
user 0m1.669s
sys 0m0.002s
これはすべて、前の質問と非常によく似ています: Project Euler との速度比較: C vs Python vs Erlang vs Haskell
編集：そして、はい、ダニエル・フィッシャーが示唆するように、ビット操作を使用し.&.てshiftR改善しquotRemます：
$ ghc -O2 so.hs ; time ./so
(837799,525)
real 0m0.314s
user 0m0.312s
sys 0m0.001s
または、LLVMを使用して魔法のようにすることもできます（NBこのバージョンはquotRemまだ使用しています）
$ time ./so
(837799,525)
real 0m0.286s
user 0m0.283s
sys 0m0.002s
LLVM は実際にはうまく機能しますが、これは という恐ろしさを回避し、手動でmod最適化された を使用してガードベースのコードを最適化するかrem、even同等に適切に最適化.&.しshiftRます。
オリジナルよりも約 20 倍高速な結果が得られます。
編集:人々は、 quotRem がビット操作と同様に実行されることに驚いていますInt。コードは含まれていますが、驚きの点は明確ではありません。何かが負である可能性があるからといって、適切なハードウェアで同じコストになる可能性のある非常によく似たビット操作でそれを処理できないわけではありません。の 3 つのバージョンはすべてnextStep同じように動作しているようです ( ghc -O2 -fforce-recomp -fllvm、ghc バージョン 7.6.3、LLVM 3.3、x86-64)。
{-# LANGUAGE BangPatterns, UnboxedTuples #-}
import Data.Bits
collatzLength :: Int -> Int
collatzLength x| x == 1 = 1
| otherwise = go x 0
where
go 1 a = a + 1
go x !a = go (nextStep x) (a+1)
longestChain :: (Int, Int) -> Int -> Int -> (Int,Int)
longestChain (num, numLength) bound !counter
| counter >= bound = (num, numLength)
| otherwise = longestChain (longerOf (num,numLength) (counter, collatzLength counter)) bound (counter + 1)
--I know this is a messy function, but I was doing this problem just
--for myself, so I didn't bother making some utility functions for it.
--also, I split the big line in half to display on here nicer, would
--it actually run with this line split?
longerOf :: (Int,Int) -> (Int,Int) -> (Int,Int)
longerOf (a1,a2) (b1,b2)| a2 > b2 = (a1,a2)
| otherwise = (b1,b2)
{-# INLINE longerOf #-}
nextStep :: Int -> Int
-- Version 'bits'
nextStep n = if 0 == n .&. 1 then n `shiftR` 1 else 3*n+1
-- Version 'quotRem'
-- nextStep n = let (q,r) = quotRem n 2 in if r == 0 then q else 3*n+1
-- Version 'almost the original'
-- nextStep n | even n = quot n 2
-- | otherwise = 3*n + 1
{-# INLINE nextStep #-}
main = print (longestChain (0,0) 1000000 1)