повторное использование результатов в Haskell

tokuchu

В мануалах про Haskell пишут, что одним из бонусов чистоты функций является то, что если мы считали какую-то функцию с определёнными аргументами, то 2-й раз её считать не нужно уже.
И вот у меня вопрос - почему в ghci такое выполняется в 2 раза дольше:

(maximumBy (compare `on` length) $ map collatzSeq [1..10000]) ++ (maximumBy (compare `on` length) $ map collatzSeq [1..10000])

чем такое:

maximumBy (compare `on` length) $ map collatzSeq [1..10000]

Предварительно подгружается такой файл с определениями:

import Data.List

import Data.Function



collatz n

  | even n    = n `div` 2

  | otherwise = 3 * n + 1



collatzSeq 1 = [1]

collatzSeq n = n : (collatzSeq $ collatz n)

Dasar

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

tokuchu

Про какую функцию он не знает, что она одна и та же?

Dasar

что код слева от ++ совпадает с кодом справа от ++

tokuchu

что код слева от ++ совпадает с кодом справа от ++

Так этот перебор быстро выполняется. Основное время уходит на вызовы функций. Для примера тот 1 цикл отрабатывает где-то за 7 секунд, а вот такое сразу результат выдаёт:

maximumBy (compare `on` length) $ map collatzSeq $ take 10000 $ repeat 1

Или вот так ещё попробовал — работает гораздо дольше 7 секунд уже:

maximumBy (compare `on` length) $ map collatzSeq $ take 10000 $ repeat 6171

Хотя очевидно, что вызовы collatzSeq 6171 и даже length $ collatzSeq 6171 вполне могут ссылаться на одно и то же.

tokuchu

В общем по ключевым словам Haskell Memoization гуглятся ответы. Там оказывается не всё так хорошо, не всё запоминается. Надо будет почитать, разобраться получше.

Maurog

мы считали какую-то функцию с определёнными аргументами, то 2-й раз её считать не нужно уже

если быть точным, то "2-й раз ее могут и не вызвать", т.к. это не повлияет на результат, а по времени может быть выигрыш.
такую оптимизацию может провернуть компилятор, но часто ему надо помочь в этом. для мемоизации нужно организовывать вычисления так, чтобы выполнение наткнулось на уже вычисленный thunk.
чистые вычисления еще хорошо параллелятся и у ghc есть ключики для этого

Maurog

И вот у меня вопрос - почему в ghci такое выполняется в 2 раза дольше:

ты бы лучше весь код выложил, чтобы его можно было запустить на ideone
пока я вижу у тебя очень тормознутый ++, который заставляет перелопатить весь первый аргумент, что лишает возможности получить плюс от ленивости
ну и попробуй завести промежуточный список
x = maximumBy ...;
y = x ++ x;

tokuchu

Так я вроде весь код и показал.
И "++" там совсем капля в море. Он объединяет уже в конце 2 списка относительно небольших, которые если явно указать, то выполняется очень быстро. Долго вычисляются именно аргументы.
Через промежуточный список будет конечно быстрее, т.к. его уж точно не будет 2 раза вычислять. Но ++ я использовал просто для того, чтобы 2 раза вызвать то, что мне нужно. Вместо этого может быть всё что угодно. Там в принципе и оно само долго отрабатывает, т.к. вызовы всего остального тоже не мемоизируются. Там много чего повторно вычисляется.

daru

почему в ghci такое выполняется в 2 раза дольше

CSE

В мануалах про Haskell пишут

скорее всего речь идёт об одной из двух вещей:
либо о ленивых вычислениях - тогда речь о том, что каждое подвыражение вычисляется не более одного раза (в языках с нестрогой семантикой это не обязательно выполняется автоматически)
либо о том, что мемоизацию чистой функции всегда можно корректно реализовать (понятно, что компилятор этого автоматически не делает, например, по тем же причинам, по которым он не делает CSE).

tokuchu

Спасибо за ссылку. В данном случае вопрос был про мемоизацию именно, просто при повторении явно становилось видно, что время выполнения удваивается. Хотя если был бы CSE, то он бы заставил меня на время усомниться в том, что мемоизации нет.

Оставить комментарий