e

Posted on May 24, 2014 with tags: haskell.

Четыре года назад, я радовался работе с бесконечными списками и вычислял e суммируя ряд Тейлора так:

e = sum $ map (\x -> 1 / fac x) [0..]
    where
        fac n = foldl (*) 1 [1..n]
        sum (x:xs) = sumtr (x:xs) 0
        sumtr (x:xs) acc
            | (acc == acc + x) = acc
            | otherwise = sumtr xs (x + acc)

Случайно найдя предыдущий сниппет и смахнув слезу умиления, я переписал суммирование уже со знанием стандартной библиотеки.

e = sum $ takeWhile (/=0) $ map (\v -> 1 / product [1..v]) [0..]

Проблема в том, что этот вариант аллоцировал в 10 раз больше памяти чем первый. Стало как-то неудобно и я заменил вычисление факториала для каждого нового члена ряда Тейлора на вычисление непрерывного списка факториалов, где каждый следующий элемент умножение номера члена ряда на значение предыдущего элемента.

e = sum $ takeWhile (/=0) $ map (1/) $ scanl (*) 1 [1..]

Количество аллоцированной памяти вышло на уровень первого варианта. Однако в первом варианте у нас используется наивный факториал и он всё равно работает замечательно. Разница состоит в том, что первый вариант суммирует ряд до тех пор пока сумма изменяется, а третий — до тех пор пока n-ый член ряда не станет нулём. Любому кто знаком с числами с плавающей запятой понятно что первое условие выполнится быстрее второго. Попробуем использовать именно первое условие. Для этого из бесконечного списка факториалов получим бесконечный список сумм, выделим пары текущая сумма/следующая сумма и будем разматывать список до тех пор пока суммы не равны. Последняя сумма и есть наша.

e = fst $ last $ takeWhile (uncurry (/=)) $ (\v -> zip v (tail v)) $ scanl1 (\v0 v1 -> v0 + 1 / v1) $ scanl (*) 1 [1..]

Мы наконец заметно превзошли по выделенной памяти первый вариант. Но не в 10 раз, а в полтора и ценой дополнительного времени на сборку мусора. Это скажем так себе результат.

P.S: Продолжение следует.

comments powered by Disqus