Как я могу ускорить свою программу Haskell (до уровня Python)
У меня есть следующая игрушечная программа, которая циклически сдвигает вектор и добавляет его себе (под мод). Он делает это для разных сдвигов и большого количества итераций (по сравнению с размером вектора). Программа работает, но ее собака медленная. Я все еще изучаю Haskell, поэтому мой вопрос: я делаю что-то неправильно?
import Data.List (foldl')
import qualified Data.Sequence as Seq
import Data.Sequence (index, zipWith, Seq, (><), (<|), (|>))
seqSize = 100
numShifts = 10000
cycleShift :: Integer -> Seq a -> Seq a
cycleShift s l = Seq.drop (fromInteger s) l >< Seq.take (fromInteger s) l
modAdd :: Seq Integer -> Seq Integer -> Seq Integer
modAdd s t = Seq.zipWith (\ a b -> (a + b) `mod` 10^16) s t
step :: Seq Integer -> Integer -> Seq Integer
step l shift = modAdd l (cycleShift shift l)
allshifts = [i `mod` seqSize |i <- [1..numShifts]]
start = Seq.fromList (1 : [0 | i <- [1..(seqSize - 1)]])
end = foldl' step start allshifts
main :: IO ()
main = print (Seq.index end 0)
Эта же программа в Python
seq_size = 100
num_shifts = 10000
S = [i % seq_size for i in xrange(1, num_shifts + 1)]
ssums = [1] + [0 for i in range(seq_size - 1)]
for s in S:
shift = ssums[s:] + ssums[:s]
ssums = [(ssums[i] + shift[i]) % 10**16 for i in range(seq_size)]
print ssums[0]
Вот тайминги.
Haskell: реальный 0m5.596s
Python: real 0m0.551s
Python не известен своей скоростью и все же в x10 раз быстрее?!?
Ответы
Ответ 1
Как вы его используете?
Я получаю 1,6 секунды для версии Haskell. (Скомпилировано с ghc.exe -O2 seq.hs
.)
Кроме того, есть ли причина, по которой вы используете Seq? Если я изменю его на использование списков, я получаю 0,3 секунды времени выполнения.
Вот он со списками:
import Data.List (foldl')
seqSize = 100
numShifts = 10000
cycleShift s l = drop (fromInteger s) l ++ take (fromInteger s) l
modAdd s t = zipWith (\ a b -> (a + b) `mod` 10^16) s t
step l shift = modAdd l (cycleShift shift l)
allshifts = [i `mod` seqSize |i <- [1..numShifts]]
start = (1 : [0 | i <- [1..(seqSize - 1)]])
end = foldl' step start allshifts
main :: IO ()
main = print (end !! 0)
Ответ 2
- Используйте простые списки. Они сильно оптимизированы. Использование
Data.Vector
еще быстрее.
- Используйте
rem
вместо mod
- Избегайте ненужной работы. (см.
cycleShift
. До этого вы дважды разделили список)
- Используйте
Int
вместо Integer
, если ваш расчет не может превышать границы. Первый - это аппаратное обеспечение, а позднее - произвольная точность, но эмулируется с помощью программного обеспечения.
Результат: от 3,6 секунды до 0,5 секунды. Возможно, возможно больше.
код:
import Data.List (foldl')
import Data.Tuple
seqSize, numShifts :: Int
seqSize = 100
numShifts = 10000
cycleShift :: Int -> [a] -> [a]
cycleShift s = uncurry (++) . swap . splitAt s
modAdd :: [Int] -> [Int] -> [Int]
modAdd = zipWith (\ a b -> (a + b) `rem` 10^16)
step :: [Int] -> Int -> [Int]
step l shift = modAdd l (cycleShift shift l)
allshifts = map (`rem` seqSize) [1..numShifts]
start = 1 : replicate (seqSize - 1) 0
end = foldl' step start allshifts
main :: IO ()
main = print (head end)
Изменить
Он становится еще быстрее, используя Data.Vector
. Я получаю около 0,4 секунды на своей машине, используя этот код:
import Data.List (foldl')
import Data.Tuple
import Data.Vector (Vector)
import qualified Data.Vector as V
seqSize, numShifts :: Int
seqSize = 100
numShifts = 10000
cycleShift :: Int -> Vector a -> Vector a
cycleShift s = uncurry (V.++) . swap . V.splitAt s
modAdd :: Vector Int -> Vector Int -> Vector Int
modAdd = V.zipWith (\ a b -> (a + b) `rem` 10^16)
step :: Vector Int -> Int -> Vector Int
step l shift = modAdd l (cycleShift shift l)
allshifts = map (`rem` seqSize) [1..numShifts]
start = 1 `V.cons` V.replicate (seqSize - 1) 0
end = foldl' step start allshifts
main :: IO ()
main = print (V.head end)
Изменить 2
Используя Data.Vector.Unboxed
(просто измените импорт и исправьте подписи), время выполнения падает до 0.074 сек. Но результаты верны, если Int
имеет 64 бит. Это также может быть так быстро, используя Int64
, хотя.
Ответ 3
Убедитесь, что код Haskell скомпилирован и результирующий исполняемый файл синхронизирован, а не интерпретированная версия кода.
TheGeekStuff