Функциональные проблемы обучения

Question

Я новичок в функциональных языках, и я пытаюсь описать все это в Хаскеле. Вот простая и быстрая функция, которая находит все факторы числа:

factors :: (Integral a) => a -> [a]
factors x = filter (\z -> x `mod` z == 0) [2..x `div` 2]

Работает нормально, но я обнаружил, что для больших чисел это невыносимо медленно. Поэтому я сделал себя лучше:

factorcalc :: (Integral a) => a -> a -> [a] -> [a]
factorcalc x y z
    | y `elem` z      = sort z
    | x `mod` y == 0  = factorcalc x (y+1) (z ++ [y] ++ [(x `div` y)])
    | otherwise       = factorcalc x (y+1) z

Но вот моя проблема: хотя код работает и может сократить время выполнения моих программ буквально на несколько часов, это безобразно!

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

Я могу ошибаться, но просто должен быть лучший способ сделать то же самое ...

Answer 1

Обратите внимание, что в исходном вопросе были заданы все факторы, а не только простое факторы. Поскольку основных факторов намного меньше, их, вероятно, можно найти быстрее. Возможно, это то, что хотел OQ. Возможно нет. Но давайте решим исходную проблему и вернем «веселье» обратно в «функционал»!

Некоторые наблюдения:

• Эти две функции не выдают одинаковый вывод - если x является идеальным квадратом, вторая функция дважды включает квадратный корень.

• Первая функция перечисляет проверяет количество потенциальных факторов, пропорциональных размеру x; вторая функция проверяет только пропорционально квадратному корню из x, затем останавливается (с ошибкой, отмеченной выше).

• Первая функция (factors) выделяет список всех целых чисел от 2 до n div 2, где вторая функция никогда не выделяет список, а вместо этого посещает меньше целых чисел по одному за раз в параметре. Я запустил оптимизатор с помощью -O и посмотрел на вывод с помощью -ddump-simpl, а GHC просто не достаточно умен, чтобы оптимизировать эти распределения.

• factorcalc является хвост-рекурсивным, что означает, что он компилируется в замкнутый цикл машинного кода; filter нет и нет.

Некоторые эксперименты показывают, что квадратный корень - убийца :

Вот пример функции, которая выдает коэффициенты x от z до 2:

factors_from x 1 = []
factors_from x z 
  | x `mod` z == 0 = z : factors_from x (z-1)
  | otherwise      =     factors_from x (z-1)

factors'' x = factors_from x (x `div` 2)

Это немного быстрее, потому что не выделяет, но все равно не является хвостовой рекурсией.

Вот хвосто-рекурсивная версия, более верная оригиналу:

factors_from' x 1 l = l
factors_from' x z l
  | x `mod` z == 0 = factors_from' x (z-1) (z:l)
  | otherwise      = factors_from' x (z-1) l

factors''' x = factors_from x (x `div` 2)

Это все еще медленнее, чем factorcalc, поскольку оно перечисляет все целые числа от 2 до x div 2, тогда как factorcalc останавливается на квадратном корне.

Вооружившись этим знанием, теперь мы можем создать более функциональную версию factorcalc, которая копирует и скорость, и ошибку:

factors'''' x = sort $ uncurry (++) $ unzip $ takeWhile (uncurry (<=)) $ 
                [ (z, x `div` z) | z <- [2..x], x `mod` z == 0 ]

Я точно не рассчитал время, но, учитывая, что 100 миллионов в качестве входных данных, он и factorcalc мгновенно завершаются, тогда как все остальные занимают несколько секунд.

Как и почему эта функция работает, оставлено читателю в качестве упражнения: -)

---

ADDENDUM : ОК, чтобы уменьшить кровотечение из глазного яблока, вот немного более разумная версия (и без ошибки):

saneFactors x = sort $ concat $ takeWhile small $
                [ pair z | z <- [2..], x `mod` z == 0 ]
    where pair z = if z * z == x then [z] else [z, x `div` z]
          small [z, z'] = z < z'
          small [z]     = True

Answer 2

Хорошо, сделай глубокий вдох. Все будет хорошо.

Прежде всего, почему ваша первая попытка медленная? Как он проводит время?

Можете ли вы вспомнить рекурсивное определение простой факторизации, у которого нет этого свойства?

( Подсказка .)

Answer 3

Это казалось интересной проблемой, и я давно не кодировал ни одного настоящего Хаскелла, поэтому я дал ему трещину. Я запускал и его, и factors'''' Нормана с одинаковыми значениями, и он чувствует , как мой быстрее, хотя они оба настолько близки, что трудно сказать.

factors :: Int -> [Int]
factors n = firstFactors ++ reverse [ n `div` i | i <- firstFactors ]
    where
    firstFactors = filter (\i -> n `mod` i == 0) (takeWhile ( \i -> i * i <= n ) [2..n])

Факторы могут быть объединены в пары с коэффициентами, которые больше sqrt n, и с коэффициентами, которые меньше или равны (для простоты, точный квадратный корень, если n - идеальный квадрат, попадает в эту категорию) Поэтому, если мы просто возьмем те, которые меньше или равны, мы можем вычислить остальные позже, выполнив div n i. Они будут в обратном порядке, поэтому мы можем либо сначала поменять firstFactors, либо позже отменить результат Это не имеет значения.

Answer 4

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

На самом деле, это не обман; это - нет, сделайте это - стандартной техникой! Этот тип параметра обычно известен как «аккумулятор», и он обычно скрыт внутри вспомогательной функции, которая выполняет рекурсию после того, как настроена вызываемой вами функцией.

Обычный случай - когда вы выполняете операции со списком, которые зависят от предыдущих данных в списке. Две проблемы, которые вам нужно решить, это то, где вы получаете данные о предыдущих итерациях и как вы справляетесь с тем фактом, что ваша «рабочая область интереса» для любой конкретной итерации фактически находится в хвосте списка результатов, который вы ' перестройка. Для обоих из них на помощь приходит аккумулятор. Например, чтобы сгенерировать список, в котором каждый элемент является суммой всех элементов списка ввода до этой точки:

sums :: Num a => [a] -> [a]
sums inp = helper inp []
    where
        helper []     acc       = reverse acc
        helper (x:xs) []        = helper xs [x]
        helper (x:xs) acc@(h:_) = helper xs (x+h : acc)

Обратите внимание, что мы меняем направление аккумулятора, чтобы мы могли работать над его головкой, что гораздо более эффективно (как упоминает Доминик), а затем мы просто обращаем конечный результат в обратном направлении.

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

Answer 5

Во-первых, хотя factorcalc "уродливо", вы можете добавить функцию-оболочку factors' x = factorscalc x 2 [], добавить комментарий и двигаться дальше.

Если вы хотите сделать «красивый» factors быстрым, вам нужно выяснить, почему он медленный. Рассматривая две ваши функции, factors обходит список длиной n / 2 элемента, но factorcalc останавливается после sqrt n итераций.

Вот еще один factors, который также останавливается после sqrt n итераций, но использует сгиб вместо явной итерации. Это также разбивает проблему на три части: поиск факторов (factor); остановка в корне квадратном из x (small) и последующее вычисление пар факторов (factorize):

factors' :: (Integral a) => a -> [a]
factors' x = sort (foldl factorize [] (takeWhile small (filter factor [2..])))
  where
    factor z = x `mod` z == 0
    small z = z <= (x `div` z)
    factorize acc z = z : (if z == y then acc else y : acc)
      where y = x `div` z

Это немного быстрее, чем factorscalc на моей машине. Вы можете объединить factor и factorize, и это примерно в два раза быстрее, чем factorscalc.

Раздел Профилирование и оптимизация в Real World Haskell является хорошим руководством по инструментам производительности пакета GHC для решения более сложных проблем производительности.

Кстати, у меня есть мелкий мелкий стиль с factorscalc: гораздо эффективнее добавлять отдельные элементы к началу списка O (1), чем добавлять его в конец списка длины. n O (n). Списки факторов, как правило, невелики, так что это не такая уж большая проблема, но factorcalc, вероятно, должно выглядеть примерно так:

factorcalc :: (Integral a) => a -> a -> [a] -> [a]
factorcalc x y z
    | y `elem` z      = sort z
    | x `mod` y == 0  = factorcalc x (y+1) (y : (x `div` y) : z)
    | otherwise       = factorcalc x (y+1) z

Answer 6

Это мой «функциональный» подход к проблеме. («Функционально» в кавычках, потому что я подходил бы к этой проблеме одинаково даже в нефункциональных языках, но, возможно, это потому, что я был испорчен Хаскеллом.)

{-# LANGUAGE PatternGuards #-}
factors :: (Integral a) => a -> [a]
factors = multiplyFactors . primeFactors primes 0 [] . abs where
    multiplyFactors [] = [1]
    multiplyFactors ((p, n) : factors) =
        [ pn * x
        | pn <- take (succ n) $ iterate (* p) 1
        , x <- multiplyFactors factors ]
    primeFactors _ _ _ 0 = error "Can't factor 0"
    primeFactors (p:primes) n list x
        | (x', 0) <- x `divMod` p
        = primeFactors (p:primes) (succ n) list x'
    primeFactors _ 0 list 1 = list
    primeFactors (_:primes) 0 list x = primeFactors primes 0 list x
    primeFactors (p:primes) n list x
        = primeFactors primes 0 ((p, n) : list) x
    primes = sieve [2..]
    sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

primes - это наивное сито эратотенов. Там лучше, но это самый короткий метод.

   sieve [2..]
=> 2 : sieve [x | x <- [3..], x `mod` 2 /= 0]
=> 2 : 3 : sieve [x | x <- [4..], x `mod` 2 /= 0, x `mod` 3 /= 0]
=> 2 : 3 : sieve [x | x <- [5..], x `mod` 2 /= 0, x `mod` 3 /= 0]
=> 2 : 3 : 5 : ...

primeFactors - это простой алгоритм повторного пробного деления: он просматривает список простых чисел и пытается разделить заданное число на каждое, записывая коэффициенты по мере поступления.

   primeFactors (2:_) 0 [] 50
=> primeFactors (2:_) 1 [] 25
=> primeFactors (3:_) 0 [(2, 1)] 25
=> primeFactors (5:_) 0 [(2, 1)] 25
=> primeFactors (5:_) 1 [(2, 1)] 5
=> primeFactors (5:_) 2 [(2, 1)] 1
=> primeFactors _ 0 [(5, 2), (2, 1)] 1
=> [(5, 2), (2, 1)]

multiplyPrimes берет список простых чисел и степеней и разбирает его обратно на полный список факторов.

   multiplyPrimes [(5, 2), (2, 1)]
=> [ pn * x
   | pn <- take (succ 2) $ iterate (* 5) 1
   , x <- multiplyPrimes [(2, 1)] ]
=> [ pn * x | pn <- [1, 5, 25], x <- [1, 2] ]
=> [1, 2, 5, 10, 25, 50]

factors просто объединяет эти две функции вместе с abs для предотвращения бесконечной рекурсии в случае отрицательного ввода.

Answer 7

Я не знаю много о Haskell, но почему-то я думаю, что эта ссылка уместна:

http://www.willamette.edu/~fruehr/haskell/evolution.html

Редактировать: Я не совсем уверен, почему люди так агрессивно относятся к этому. Настоящая проблема оригинального плаката заключалась в том, что код был уродливым; хотя это смешно, смысл статьи в некоторой степени в том, что продвинутый код на Haskell на самом деле ужасен; чем больше вы узнаете, тем в меньшей степени ваш код получится. Смысл этого ответа заключался в том, чтобы указать ОП, что, по-видимому, уродливость кода, который он оплакивал, не редкость.