Project Euler 14: производительность по сравнению с C и запоминание

Question

В настоящее время я работаю над проблемой проекта Эйлера 14 .

Я решил это, используя плохо закодированную программу, без напоминаний, для выполнения которой потребовалось 386 5 секунд (см. Редактирование).

Вот оно:

step :: (Integer, Int) -> Integer -> (Integer, Int)
step (i, m) n   | nextValue > m         = (n, nextValue)
                | otherwise             = (i, m)
                where nextValue = syr n 1

syr :: Integer -> Int -> Int
syr 1 acc   = acc
syr x acc   | even x    = syr (x `div` 2) (acc + 1)
            | otherwise = syr (3 * x + 1) (acc + 1)

p14 = foldl step (0, 0) [500000..999999]

У меня вопрос к нескольким комментариям в теме, относящимся к этой проблеме, где упоминалось время выполнения программ менее 1 с, как указано ниже (код C, кредиты пользователю форума проекта euler ix для кода - примечание: я не проверял, что время выполнения на самом деле соответствует указанному):

#include <stdio.h>


int main(int argc, char **argv) {
    int longest = 0;
    int terms = 0;
    int i;
    unsigned long j;
    for (i = 1; i <= 1000000; i++) {
        j = i;
        int this_terms = 1;
        while (j != 1) {
            this_terms++;
            if (this_terms > terms) {
                terms = this_terms;
                longest = i;
            }
            if (j % 2 == 0) {
                j = j / 2;
            } else {
                j = 3 * j + 1;
            }
        }
    }
    printf("longest: %d (%d)\n", longest, terms);
    return 0;
}

Мне кажется, что эти программы похожи, если говорить об алгоритме.

Так мне интересно, почему такая большая разница? Или есть какие-то принципиальные различия между нашими двумя алгоритмами, которые могут оправдать фактор x6 в производительности?

Кстати, в настоящее время я пытаюсь реализовать этот алгоритм с запоминанием, но я немного растерялся, его гораздо проще реализовать на императивном языке (и я пока не манипулирую монадами, поэтому не могу использовать эта парадигма). Поэтому, если у вас есть хороший учебник, который подходит новичку для изучения запоминания, я буду рад (те, с которыми я столкнулся, были недостаточно подробными или вышли из моей лиги).

Примечание: я пришел к декларативной парадигме через Пролог и все еще нахожусь в очень раннем процессе открытия Хаскелла, поэтому я могу пропустить важные вещи.

Примечание 2: любые общие советы по поводу моего кода приветствуются.

РЕДАКТИРОВАТЬ: благодаря помощи Делнана я скомпилировал программу, и теперь она запускается через 5 секунд, поэтому я в основном ищу подсказки по запоминанию (даже если идеи о существующем разрыве x6 все еще приветствуются) .

Answer 1

После компиляции с оптимизацией все еще есть несколько отличий от программы C

• , которую вы используете div, в то время как программа C использует машинное деление (которое усекает) [но любоеуважаемый компилятор C превращает это в сдвиг, так что это делает его еще быстрее], это было бы quot в Haskell;это сократило время выполнения примерно на 15%.
• программа на C использует 64-битную фиксированную ширину (или даже 32-битную, но тогда просто удача, что она получает правильный ответ, так как некоторые промежуточные значенияпревышают 32-битный диапазон), программа на Haskell использует произвольную точность Integer с.Если в вашем GHC есть 64-разрядные Int s (64-разрядные ОС, отличные от Windows), замените Integer на Int.Это сократило время выполнения примерно в 3 раза.Если вы работаете в 32-битной системе, вам не повезло, GHC не использует там собственные 64-битные инструкции, эти операции реализованы как вызовы C, но это все еще довольно медленно.

Для создания памятки вы можете передать ее на рассмотрение одному из пакетов памятки о хакерстве, я помню только один: data-memocombinators , но есть и другие.Или вы можете сделать это самостоятельно, например, сохраняя карту ранее вычисленных значений - это будет лучше всего работать в монаде State,

import Control.Monad.State.Strict
import qualified Data.Map as Map
import Data.Map (Map, singleton)

type Memo = Map Integer Int

syr :: Integer -> State Memo Int
syr n = do
    mb <- gets (Map.lookup n)
    case mb of
      Just l -> return l
      Nothing -> do
          let m = if even n then n `quot` 2 else 3*n+1
          l <- syr m
          let l' = l+1
          modify (Map.insert n l')
          return l'

solve :: Integer -> Int -> Integer -> State Memo (Integer,Int)
solve maxi len start
    | len > 1000000 = return (maxi,len)
    | otherwise = do
         l <- syr start
         if len < l
             then solve start l (start+1)
             else solve maxi len (start+1)

p14 :: (Integer,Int)
p14 = evalState (solve 0 0 500000) (singleton 1 1)

, но это, вероятно, не принесет слишком много (даже когда выдобавили необходимую строгость).Проблема в том, что поиск в Map не слишком дешевый, а вставка относительно дорогая.

Другой метод - сохранить изменяемый массив для поиска.Код становится более сложным, поскольку вы должны выбрать разумную верхнюю границу для значений для кэширования (должна быть не намного больше, чем граница для начальных значений) и иметь дело с частями последовательностей, выходящими за пределы запомненного диапазона.Но поиск и запись в массив выполняется быстро.Если у вас есть 64-битные Int с, приведенный ниже код выполняется довольно быстро, здесь требуется 0,03 с для предела в 1 миллион, и 0,33 с для предела в 10 миллионов, что соответствует (насколько я могу разумно)C-код работает в 0,018 соотв.0,2 с.

module Main (main) where

import System.Environment (getArgs)
import Data.Array.ST
import Data.Array.Base
import Control.Monad.ST
import Data.Bits
import Data.Int

main :: IO ()
main = do
    args <- getArgs
    let bd = case args of
               a:_ -> read a
               _   -> 100000
    print $ collMax bd

next :: Int -> Int
next n
    | n .&. 1 == 0  = n `unsafeShiftR` 1
    | otherwise     = 3*n + 1

collMax :: Int -> (Int,Int16)
collMax upper = runST $ do
    arr <- newArray (0,upper) 0 :: ST s (STUArray s Int Int16)
    let go l m
            | upper < m = go (l+1) $ next m
            | otherwise = do
                l' <- unsafeRead arr m
                case l' of
                  0 -> do
                      l'' <- go 1 $ next m
                      unsafeWrite arr m (l'' + 1)
                      return (l+l'')
                  _ -> return (l+l'-1)
        collect mi ml i
            | upper < i = return (mi, ml)
            | otherwise = do
                l <- go 1 i
                if l > ml
                  then collect i l (i+1)
                  else collect mi ml (i+1)
    unsafeWrite arr 1 1
    collect 1 1 2

Answer 2

Хорошо, программа на C использует unsigned long, но Integer может хранить произвольно большие целые числа (это bignum ). Если вы импортируете Data.Word, то вы можете использовать Word, что является целым числом без знака в машинном слове.

После замены Integer на Word и использования ghc -O2 и gcc -O3 программа на C запускается за 0,72 секунды, а программы на Haskell - за 1,92 секунды. 2.6x не плохо. Тем не менее, ghc -O2 не всегда помогает, и это одна из программ, в которой он не помогает! Использование только -O, как вы сделали, сокращает время выполнения до 1,90 секунды.

Я попытался заменить div на quot (который использует тот же тип деления, что и C; они отличаются только на отрицательных входах), но странным образом это фактически заставило программу на Haskell работать немного медленнее.

Вы должны быть в состоянии ускорить функцию syr с помощью этого предыдущего вопроса переполнения стека Я ответил о той же проблеме Project Euler.

Answer 3

В моей текущей системе (32-битный Core2Duo) ваш код на Haskell, включая все оптимизации, приведенные в ответах, требует 0.8s для компиляции и 1.2s для запуска.

Вы можете передать прогонвремя компиляции и сокращение времени выполнения почти до нуля.

module Euler14 where

import Data.Word
import Language.Haskell.TH

terms :: Word -> Word
terms n = countTerms n 0
  where
    countTerms 1 acc             = acc + 1
    countTerms n acc | even n    = countTerms (n `div` 2) (acc + 1)
                     | otherwise = countTerms (3 * n + 1) (acc + 1)

longestT :: Word -> Word -> (Word, Word) 
longestT mi mx = find mi mx (0, 0)
  where
      find mi mx (ct,cn) | mi == mx  = if ct > terms mi then (ct,cn) else (terms mi, mi)
                         | otherwise = find (mi + 1) mx
                                       (if ct > terms mi then (ct,cn) else (terms mi, mi))

longest :: Word -> Word -> ExpQ
longest mi mx = return $ TupE [LitE (IntegerL (fromIntegral a)),
                               LitE (IntegerL (fromIntegral b))]
  where
    (a,b) = longestT mi mx

и

{-# LANGUAGE TemplateHaskell #-}
import Euler14

main = print $(longest 500000 999999)

В моей системе для компиляции требуется 2.3s, но запусквремя уменьшается до 0.003s.Выполнение функции времени компиляции (CTFE) - это то, что вы не можете сделать в C / C ++.Единственный из известных мне языков программирования, который поддерживает CTFE, - это D язык программирования .И чтобы быть полным, код C требует 0.1s для компиляции и 0.7s для запуска.