私はHaskellとFPに出くわし、その可能性に驚愕しました。そして、私の中の古い数学オタクは、実際の有用な目的のために素朴なコードを書くのに問題はありませんでした。しかし、すべての読書にもかかわらず、私はまだいくつかの驚くべきパフォーマンスのボトルネックにぶつからないようにする方法を理解するのに本当に苦労しています。
そのため、単純な実装を使用して非常に短いコードを記述し、少し変更を加えて、パフォーマンスがどのように応答するかを確認します。そして、これは私が本当に理解することができない1つの例です...私は、ナイーブなリストの実装で意図的に、ヨセフス問題の解決策を見つけるこの関数を書きました。
m = 3
n = 3000
main = putStr $ "Soldier #" ++ (show $ whosLeft [1..n]) ++ " survived...\n"
whosLeft [lucky] = lucky
whosLeft soldiers = whosLeft $ take (length soldiers -1) $ drop m $ cycle soldiers
後者は190ミリ秒で実行され、RTSによると63％の生産性があります。
それから私が最初に試したかったのは、（長さの兵士-1）を削除し、それをデクリメント整数に置き換えることでした。
実行時間は最大900ミリ秒に跳ね上がり、生産性は16％に低下し、上記の単純なコードの47倍のメモリを使用します。そこで、厳密な評価を追加し、Int型を強制し、グローバル変数などを削除するなどの試みを行いましたが、あまり役に立ちませんでした。そして、私はこの減速を理解することができません。
m = 3::Int
n = 3000::Int
main = putStr $ "Soldier #" ++ (show $ whosLeft n [1..n]) ++ " survived...\n"
whosLeft 1 [lucky] = lucky
whosLeft n' soldiers = n' `seq` left `seq` whosLeft (n'-1) left
where left = take (n'-1) $ drop m $ cycle soldiers
パフォーマンス関連の記事や投稿をふるいにかけましたが、これについてのヒントが得られていないようです。まだHaskellの初心者である私は何か大きなものを見逃しているに違いありません...この1つの追加されたパラメーター（事前に噛まれた計算...）はどのようにして速度をそれほど低下させることができますか？
PS：ヨセフスが本当に3000人の兵士と一緒にいたなら、彼らは自殺する必要はなかっただろうと私は知っています...