2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 И снова Haskell. Эффективный Трибоначчи.
Сообщение22.06.2015, 20:13 
Доброе время суток!
Столкнулся со следующей задачей: необходимо вывести список длиной n, состоящий из чисел Трибоначчи (как Фибоначчи только по три складываются), сделать это быстро и памяти много не занимать!
Сначала я решил задачу так:
Используется синтаксис Haskell
Trib :: (a, a, a) -> Int -> [Int]
Trib (a, b, c) n = map Tribonachi [1.. n]
     where Tribonachi 1 = a
                 Tribonachi 2 = b
                 Tribonachi 3 = c
                 Tribonachi n = Tribonachi (n - 1) + Tribonachi (n - 2) + Tribonachi (n - 3)
 

Но это было слишком медленно, что впрочем легко предсказуемо. Тогда я, вспомнив про идею использования аккумулятора, написал такой код:
Используется синтаксис Haskell
Trib :: (a, a, a) -> Int -> [Int]
Trib (a,b,c) n = Tribonachi [a, b, c] n
    where Tribonachi xs n = if length xs == n then xs
                                                                              else Tribonachi (xs ++ [last xs + last (init xs) + last (init(init xs))]) n
 

На этот раз сожрало слишком много памяти, тогда я попытался сэкономить память там, где у меня идет слияние двух список (а именно на втором ее аргументе), введя еще 3 аккумулятора (чтобы не нужно было создавать кучу разных список с init), но тогда снова вышел за рамки времени. Последняя надежда какая-нибудь лямбда-абстракция,но я точно ее не придумал пока. Прошу помощи. Где тут можно оптимизировать дальше?

 
 
 
 Re: И снова Haskell. Эффективный Трибоначчи.
Сообщение22.06.2015, 20:31 
Аватара пользователя
В аккумуляторе не обязательно хранить весь список, достаточно трех последних членов.

 
 
 
 Re: И снова Haskell. Эффективный Трибоначчи.
Сообщение22.06.2015, 22:17 
Pulseofmalstrem в сообщении #1029762 писал(а):
last (init(init xs))
Код намекает, что его лучше переписать с pattern matching’ом. В самом деле, у вас и в оригинальном варианте, и в улучшении Xaositect в списке будет не менее трёх элементов — так зачем писать xs, когда можно (a:b:c:_) (или во втором случае просто [a,b,c])?

Плюс, надо было воспринимать список задом наперёд, т. к. init и last не так безобидны как tail и head.

 
 
 
 Re: И снова Haskell. Эффективный Трибоначчи.
Сообщение22.06.2015, 22:50 
Потоки текут, фьюзятся и мемоизируются при вынуждении.
Используется синтаксис Haskell
task n = take n t where
    t = 0:1:1:zipWith3 (\x y z -> x+y+z) t (tail t) (tail $ tail t)
 

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group