Haskell медленнее, чем Python в наивной целочисленной факторизации?

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

#!/usr/bin/env python3

import math
import sys

# Return a list representing the prime factorization of n. The factorization is
#   found using trial division (highly inefficient).
def factorize(n):

    def factorize_helper(n, min_poss_factor):
        if n <= 1:
            return []
        prime_factors = []
        smallest_prime_factor = -1
        for i in range(min_poss_factor, math.ceil(math.sqrt(n)) + 1):
            if n % i == 0:
                smallest_prime_factor = i
                break
        if smallest_prime_factor != -1:
            return [smallest_prime_factor] \
                   + factorize_helper(n // smallest_prime_factor,
                                      smallest_prime_factor)
        else:
            return [n]

    if n < 0:
        print("Usage: " + sys.argv[0] + " n   # where n >= 0")
        return []
    elif n == 0 or n == 1:
        return [n]
    else:
        return factorize_helper(n, 2)

if __name__ == "__main__":
    factorization = factorize(int(sys.argv[1]))
    if len(factorization) > 0:
        print(factorization)

Я также учил себя немного на Haskell, поэтому я решил попробовать переписать программу на Haskell. Эта программа выглядит следующим образом:

import System.Environment

-- Return a list containing all factors of n at least x.
factorize' :: (Integral a) => a -> a -> [a]
factorize' n x = smallestFactor
                 : (if smallestFactor == n
                    then []
                    else factorize' (n `quot` smallestFactor) smallestFactor)
    where
        smallestFactor = getSmallestFactor n x
        getSmallestFactor :: (Integral a) => a -> a -> a
        getSmallestFactor n x
            | n `rem` x == 0                          = x
            | x > (ceiling . sqrt . fromIntegral $ n) = n
            | otherwise                               = getSmallestFactor n (x+1)

-- Return a list representing the prime factorization of n.
factorize :: (Integral a) => a -> [a]
factorize n = factorize' n 2

main = do
    argv <- getArgs
    let n = read (argv !! 0) :: Int
    let factorization = factorize n
    putStrLn $ show (factorization)
    return ()

(примечание: для этого требуется 64-битная среда. На 32-битной импорте Data.Int и использовать Int64 как аннотация типа на read (argv !! 0))

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

$ ghc --make -O2 factorize.hs
$ /usr/bin/time -f "%Uu %Ss %E" ./factorize 89273487253497
[3,723721,41117819]
0.18u 0.00s 0:00.23

Затем, время программы Python:

$ /usr/bin/time -f "%Uu %Ss %E" ./factorize.py 89273487253497
[3, 723721, 41117819]
0.09u 0.00s 0:00.09

Естественно, времена меняются немного каждый раз, когда я запускаю одну из программ, но они всегда находятся в этом диапазоне, причем программа на Python в несколько раз быстрее, чем скомпилированная программа на Haskell. Мне кажется, что версия на Haskell должна работать быстрее, и я надеюсь, что вы сможете дать мне представление о том, как ее улучшить, чтобы это было так.

Я видел несколько советов по оптимизации программ на Haskell, как и в ответах на этот вопрос, но не могу заставить мою программу работать быстрее. Являются ли циклы намного быстрее, чем рекурсия? Является ли ввод-вывод Haskell особенно медленным? Я сделал ошибку в фактической реализации алгоритма? В идеале, я хотел бы иметь оптимизированную версию Haskell, которая все еще относительно проста для чтения

Источник

2 ответа

Решение

Если вы вычисляете limit = ceiling . sqrt . fromIntegral $ n только один раз, а не один раз за итерацию, тогда я вижу версию на Haskell быстрее:

limit = ceiling . sqrt . fromIntegral $ n
smallestFactor = getSmallestFactor x

getSmallestFactor x
    | n `rem` x == 0 = x
    | x > limit      = n
    | otherwise      = getSmallestFactor (x+1)

используя эту версию, я вижу:

$ time ./factorizePy.py 89273487253497
[3, 723721, 41117819]

real    0m0.236s
user    0m0.171s
sys     0m0.062s

$ time ./factorizeHs  89273487253497
[3,723721,41117819]

real    0m0.190s
user    0m0.000s
sys     0m0.031s
Источник

Помимо критической точки, сделанной Cactus, здесь также есть место для некоторых рефакторингов и аннотаций строгости, чтобы избежать создания ненужных громов. Обратите внимание, в частности, что factorize ленивый

factorize' undefined undefined = undefined : undefined

Это на самом деле не нужно, и вынуждает GHC выделить несколько громов. Лень в других местах делает то же самое. Я ожидаю, что вы получите несколько лучшую производительность, как это:

{-# LANGUAGE BangPatterns #-}

factorize' :: Integral a => a -> a -> [a]
factorize' n x
  | smallestFactor == n = [smallestFactor]
  | otherwise = smallestFactor : factorize' (n `quot` smallestFactor) smallestFactor
  where
    smallestFactor = getSmallestFactor n (ceiling . sqrt . fromIntegral $ n) x
    getSmallestFactor n !limit x
       | n `rem` x == 0 = x
       | x > limit = n
       | otherwise = getSmallestFactor n limit (x+1)

-- Return a list representing the prime factorization of n.
factorize :: Integral a => a -> [a]
factorize n = factorize' n 2

я сделал getSmallestFactor взять оба n и предел в качестве аргументов. Это мешает getSmallestFactor от выделения в качестве закрытия в куче. Я не уверен, стоит ли это дополнительного перетасовки аргументов; Вы можете попробовать это в обоих направлениях.

Источник
Другие вопросы по тегам