Проблемы с функциональным обучением

Question

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

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

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

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

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

Answer 2

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

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

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

(Hint.)

Answer 3

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

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

Вот еще factors, который также останавливается после примерно sqrt n итераций, но использует сложение вместо явной итерации. Он также разбивает проблему на три части: поиск факторов (factor); остановка на квадратный корень из х (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.

Profiling and Optimization chapter of Real World Haskell - хорошее руководство для инструментов производительности набора GHC для решения более сложных проблем с производительностью.

Кстати, у меня есть незначительный стиль nitpick с 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 4

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

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

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

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

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

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

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

Вот пример функции, которая производит факторы х от г до 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 заканчиваются мгновенно, а остальные все занимают несколько секунд.

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

---

ДОБАВЛЕНИЯ: OK, чтобы смягчить глазное яблоко кровотечения, вот немного разумнее версий (и без ошибки):

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 5

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

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

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

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) 

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

Кстати, я нашел чтение The Little Schemer, чтобы быть полезным введением и предлагать хорошую практику в мышлении рекурсивно.

Answer 6

Это казалось интересной проблемой, и я не закодировал ни одного реального Haskell через некоторое время, поэтому я дал ему трещину. Я запустил оба и Norman's 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 7

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

{-# 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 является наивным решето Eratothenes. Там лучше, но это самый короткий метод.

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, чтобы предотвратить зацикливание в случае, если вход отрицательный.