Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Haskell
Перезагрузить страницу Оптимизация
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Jean-Esther Jean-Esther вне форума
Member
 
Сообщений: 22
Сказал(а) спасибо: 1
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.03.2009
По умолчанию Оптимизация - 28.02.2012, 16:30

Пытоюсь решить задачу https://www.spoj.pl/problems/FCTRL/
У меня выдает Time Limit Exceeded
На основании этого возник вопрос: а как вообще можно оптимизовать работу программы на Haskell
Сравнил разные реализации одного и того же алгоритма:
haskell Код:
import Data.Time.Clock
zeroes = foldr (\x y -> if x==0 then 0 else x+y) 0 . tail . iterate (flip div 5)
zeroes' = sum . takeWhile (/=0) . tail . iterate (flip div 5)
zeroes2 n
    | n<5 = 0
    | n<25 = div n 5
    | True = let d = div n 5 in d + zeroes2 d
act :: IO ()
act = (readLn :: IO Integer) >>= print . zeroes2
main :: IO ()
main = (readLn :: IO Int) >>= sequence . flip replicate act >> return ()

testfs = [zeroes, zeroes', zeroes2]
testas = [1..1000000]
testsg f a = map (const '.')$show$length$show$length$show$f a
testln f as= print $ length (map (testsg f) as >>= id)
test fs as = sequence [do
    start <- getCurrentTime
    testln f as
    finish <- getCurrentTime
    --print $ "Common Time"++show (diffUTCTime finish start)
    return (diffUTCTime finish start)
    | f <- fs]
test' m = (sequence $ map (test testfs) $ [[1..10^n]|n<-[1..m]]) >>=
       putStrLn.concat.map('\n':).map(concat.map('\t':).map show)
Три варианта главной функции: первые два друг другу эквивалентны, третий суть то же самое, но без использования каких-либо доп. функций, кроме арифметических.
testsg делает какие-то махинации, которые ничего не означают, просто с необходимо обеспечивают выполнение всех тестов, костыль от ленивости.
Один тест: вызов zeroes на каждом числе от 1 до 10^n. Время снимается.
Результат:
Код:
n	zeroes		zeroes'		zeroes2
10	0.000196s	0.000113s	0.000117s
100	0.001023s	0.00066s	0.001009s
1000	0.012733s	0.006127s	0.00891s
10^4	0.085524s	0.045326s	0.114166s
10^5	1.000706s	0.489576s	1.413582s
10^6	11.400834s	5.306326s	16.741006s
10^7	127.269131s	56.790279s	193.041757s
Как объяснить результат? Почему вторая функция в два раза быстрее первой, а третья, которая написана с явной хвостовой рекурсией, без списков и прочего работает хуже всего?

Кстати, как задачу решить-то, подскажите плз.
Ответить с цитированием
  (#2 (permalink)) Старый
Hydralisk Hydralisk вне форума
Новичок
 
Аватар для Hydralisk
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 25.07.2011
По умолчанию 29.02.2012, 12:11

Похоже, вы ошиблись:
В Википедии (Хвостовая рекурсия: Контрпример) описан данный случай.

Вот функция с хвостовой рекурсией:
haskell Код:
zeroes2' n = zeroesr n 0
zeroesr n acc
    | (n>4) = zeroesr d (acc+d)
    | True = acc
    where d = n `div` 5

Последний раз редактировалось Hydralisk; 29.02.2012 в 15:10
Ответить с цитированием
  (#3 (permalink)) Старый
korvin korvin вне форума
Member
 
Аватар для korvin
 
Сообщений: 337
Сказал(а) спасибо: 1
Поблагодарили 15 раз(а) в 15 сообщениях
Регистрация: 25.01.2010
По умолчанию 02.03.2012, 00:16

В Хаскелле хвостовую рекурсию нужно использовать умело из-за ленивости.


Object-oriented design is the roman numerals of computing. — Rob Pike
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Оптимизация SSD Egorro Накопители 0 30.04.2012 13:07
Оптимизация DocRain Любые вопросы от новичков 6 31.03.2012 00:05
Оптимизация по скорости Кошмар Python 21 29.01.2008 20:19
Многокритериальная оптимизация hector Информационные технологии 7 26.03.2007 18:02
Оптимизация программы EiZeRR С/С++ 3 20.11.2006 19:44
Оптимизация на Builder 6 Романнист C++ Builder 1 18.03.2006 11:05
Оптимизация при работе с HDC atomsk WinAPI 4 27.10.2005 19:35
Где взять VW 5 NC оптимизация 7.2 gerasim_sergey Smalltalk 8 01.06.2004 17:55
Оптимизация для Java eloiman Java 0 25.02.2004 14:27
Оптимизация кода BCB LaMiK C++ Builder 6 18.02.2004 18:26
Оптимизация Anonymous PHP 1 29.01.2004 14:37



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов