2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 И снова Haskell. Эффективный Трибоначчи.
Сообщение22.06.2015, 20:13 


16/12/14
472
Доброе время суток!
Столкнулся со следующей задачей: необходимо вывести список длиной 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 
Заслуженный участник
Аватара пользователя


06/10/08
6422
В аккумуляторе не обязательно хранить весь список, достаточно трех последних членов.

 Профиль  
                  
 
 Re: И снова Haskell. Эффективный Трибоначчи.
Сообщение22.06.2015, 22:17 
Заслуженный участник


27/04/09
28128
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 


05/09/12
2587
Потоки текут, фьюзятся и мемоизируются при вынуждении.
Используется синтаксис 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 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group