私はCodeChefを初めて使い、いくつかの問題を考えているので、 "Bytelandian gold coins"問題を解決しました。 (http://www.codechef.com/problems/COINS/)私のコンピュータ上で即座に結果が得られますが、CodeChefは9秒の時間制限を設定しますが、CodeChefからTimeOutsを取得しています。私はこれを引き起こす原因をもう何も持っていません。どんなヒントも役に立つでしょう。TimeOut on CodeChef
マイコード:
module Main where
import qualified Data.Map as M
import Data.Map (Map)
import Data.Maybe
main = do
catch (main' M.empty 1) (const $ return())
main' _ 11 = return()
main' m c = do
x <- readLn
let (k,m2) = sol m x
print k
main' m2 (c+1)
sol :: Map Integer Integer -> Integer -> (Integer, Map Integer Integer)
sol m x |M.member x m = (fromJust $ M.lookup x m,m)
|x > x2+x3+x4 = (x,M.insert x x m)
|otherwise = (fullSoll, M.insert x fullSoll m4)
where
x2 = div x 2
x3 = div x 3
x4 = div x 4
(sx2, m2) = sol m x2
(sx3, m3) = sol m2 x3
(sx4, m4) = sol m3 x4
fullSoll = sx2+sx3+sx4
IntegerではなくIntキーを使用することができれば、Data.IntMapはData.Mapより効率的です。 –
おそらくそれは少し効率を助けるでしょう。しかし、私は10台の可能な最高のテストケースでも、私のPC上で即座の結果を得ています(そして、1回の実行は最大10のケースのみで構成されています)。だから私のIOには何か問題があるはずですが、私は本当にもうどこを見るべきかわかりません。 – Ingdas
CodeChefはハードウェア上でプログラムを実行しますか? IOはあなたのコードで特に疑わしいとは思われません.CodeChefがコンパイルを行っている場合、パフォーマンスを落とすための十分なオプションがあります。 -O2でコンパイルしない、ヒープを小さすぎる(ガベージコレクションが増えるなど)など、あなたのマシンより遅いマシンで実行するかもしれません。おそらく、使用しているコンパイルオプションを見つけて、それらをあなたのPCでテストしようとします。 –