Как улучшить производительность этой программы Haskell?

Ответ 1

Для целей тестирования я только что установил searchTo = 100000. Затраченное время 7.34s. Несколько изменений приводят к некоторому большому улучшению:

• Используйте Integer вместо Int64. Это улучшает время 1,75 с.

• Используйте аккумулятор (вам не нужна последовательностьLength, чтобы быть ленивой правильно?) 1.54s.

  seqLen2 :: Int -> Integer -> Int
  seqLen2 a 1 = a
  seqLen2 a n = seqLen2 (a+1) (nextNumber n)
  
  sequenceLength :: Integer -> Int
  sequenceLength = seqLen2 1
  

• Перепишите nextNumber с помощью quotRem, тем самым избегая вычисления разделения дважды (один раз в even и один раз в div). 1.27s.

  nextNumber :: Integer -> Integer
  nextNumber n 
      | r == 0    = q
      | otherwise = 6*q + 4
      where (q,r) = quotRem n 2 
  

• Используйте преобразование Шварца вместо maximumBy. Проблема maximumBy . comparing заключается в том, что функция sequenceLength вызывается более одного раза для каждого значения. 0.32s.

  longestSequence = snd $ maximum [(sequenceLength a, a) | a <- [1..searchTo]]
  

Примечание:

• Я проверяю время, компилируя с помощью ghc -O и запускаю с +RTS -s)
• Моя машина работает в Mac OS X 10.6. Версия GHC - 6.12.2. Скомпилированный файл находится в архитектуре i386.)
• Задача C работает с 0,078 с с соответствующим параметром. Он скомпилирован с помощью gcc -O3 -m32.

Ответ 2

Хотя это уже довольно старо, позвольте мне перезвонить, есть один важный момент, который ранее не рассматривался.

Во-первых, тайминги разных программ на моем ящике. Поскольку я нахожусь в 64-битной Linux-системе, они показывают несколько разные характеристики: использование Integer вместо Int64 не улучшает производительность, как это было бы при использовании 32-разрядного GHC, где каждая операция Int64 стоимость C-вызова, в то время как вычисления с Integer фитингом в подписанных 32-битных целых числах не нуждаются в внешнем вызове (так как здесь только несколько операций превышают этот диапазон, Integer - лучший выбор на 32-битном GHC).

• C: 0,3 секунды
• Оригинальный Haskell: 14.24 секунды, используя Integer вместо Int64: 33.96 секунд
• Улучшенная версия KennyTM: 5.55 секунд, используя Int: 1.85 секунд
• версия Chris Kuklewicz: 5.73 секунды, используя Int: 1.90 секунд
• Версия FUZxxl: 3,56 секунды, используя quotRem вместо divMod: 1,79 секунды

Итак, что мы имеем?

• Рассчитать длину с аккумулятором, чтобы компилятор мог преобразовать его (в основном) в цикл
• Не пересчитывайте длины последовательностей для сравнения
• Не используйте div соответственно. divMod, когда это не необходимо, quot соответственно. quotRem намного быстрее

Что еще не хватает?

if (j % 2 == 0)
    j = j / 2;
else
    j = 3 * j + 1;

Любой компилятор C, который я использовал, преобразует тест j % 2 == 0 в бит-маскировку и не использует инструкцию деления. GHC пока не делает этого. Поэтому тестирование even n или вычисление n `quotRem` 2 является довольно дорогостоящей операцией. Замена nextNumber в версии KennyTM Integer с помощью

nextNumber :: Integer -> Integer
nextNumber n
    | fromInteger n .&. 1 == (0 :: Int) = n `quot` 2
    | otherwise = 3*n+1

сокращает время его работы до 3,25 секунды (Примечание: для Integer, n `quot` 2 работает быстрее, чем n `shiftR` 1, что занимает 12,69 секунды!).

Выполнение этого же в версии Int сокращает время работы до 0,41 секунды. Для Int s бит-сдвиг для деления на 2 бит быстрее, чем операция quot, сокращая время его работы до 0,39 секунды.

Устранение конструкции списка (не отображаемого в версии C),

module Main (main) where

import Data.Bits

result :: Int
result = findMax 0 0 1

findMax :: Int -> Int -> Int -> Int
findMax start len can
    | can > 1000000 = start
    | canlen > len = findMax can canlen (can+1)
    | otherwise = findMax start len (can+1)
      where
        canlen = findLen 1 can

findLen :: Int -> Int -> Int
findLen l 1 = l
findLen l n
    | n .&. 1 == 0  = findLen (l+1) (n `shiftR` 1)
    | otherwise     = findLen (l+1) (3*n+1)

main :: IO ()
main = print result

дает дополнительное небольшое ускорение, в результате чего время работы составляет 0,37 секунды.

Итак, версия Haskell, которая в близком соответствии с версией C не занимает гораздо больше времени, это коэффициент ~ 1.3.

Хорошо, пусть справедливо, есть неэффективность версии C, которая отсутствует в версиях Haskell,

if (this_terms > terms)
{
    terms = this_terms;
    longest = i;
}

появляется во внутреннем цикле. Подъем, выходящий из внутреннего контура в версии C, сокращает время его работы до 0,27 секунды, делая коэффициент ~ 1,4.

Ответ 3

Списки Haskell основаны на куче, тогда как ваш C-код чрезвычайно плотный и вообще не использует кучу. Вам нужно реорганизовать, чтобы удалить зависимость от списков.

Ответ 4

Сравнение может слишком много повторять длину последовательности. Это моя лучшая версия:

type I = Integer
data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !I deriving (Eq,Ord,Show)

searchTo = 1000000

nextNumber :: I -> I
nextNumber n = case quotRem n 2 of
                  (n2,0) -> n2
                  _ -> 3*n+1

sequenceLength :: I -> Int
sequenceLength x = count x 1 where
  count 1 acc = acc
  count n acc = count (nextNumber n) (succ acc)

longestSequence = maximum . map (\i -> P (sequenceLength i) i) $ [1..searchTo]

main = putStrLn $ show $ longestSequence

Ответ и время медленнее, чем C, но он использует произвольную точность Integer:

ghc -O2 --make euler14-fgij.hs
time ./euler14-fgij
P 525 837799

real 0m3.235s
user 0m3.184s
sys  0m0.015s

Ответ 5

Даже если я немного опоздал, вот мой, я удалил зависимость от списков, и это решение тоже не использует кучу.

{-# LANGUAGE BangPatterns #-}
-- Compiled with ghc -O2 -fvia-C -optc-O3 -Wall euler.hs
module Main (main) where

searchTo :: Int
searchTo = 1000000

nextNumber :: Int -> Int
nextNumber n = case n `divMod` 2 of
   (k,0) -> k
   _     -> 3*n + 1

sequenceLength :: Int -> Int
sequenceLength n = sl 1 n where
  sl k 1 = k
  sl k x = sl (k + 1) (nextNumber x)

longestSequence :: Int
longestSequence = testValues 1 0 0 where
  testValues number !longest !longestNum
    | number > searchTo     = longestNum
    | otherwise            = testValues (number + 1) longest' longestNum' where
    nlength  = sequenceLength number
    (longest',longestNum') = if nlength > longest
      then (nlength,number)
      else (longest,longestNum)

main :: IO ()
main = print longestSequence

Я скомпилировал этот фрагмент с ghc -O2 -fvia-C -optc-O3 -Wall euler.hs, и он работает через 5 секунд по сравнению с 80 из начала реализации. Он не использует Integer, но поскольку я на 64-битной машине, результаты могут быть обмануты.

В этом случае компилятор может распаковать все Int, что приведет к действительно быстрому коду. Он работает быстрее, чем все другие решения, которые я видел до сих пор, но C все еще быстрее.