Будет ли этот код на Haskell занимать слишком много памяти?

Question

Как в этом коде:

import Data.Char
groupsOf _ [] = []
groupsOf n xs = 
    take n xs : groupsOf n ( tail xs )

problem_8 x = maximum . map product . groupsOf 5 $ x
main = do t <- readFile "p8.log" 
      let digits = map digitToInt $concat $ lines t
      print $ problem_8 digits

Я понимаю, что в Haskell многие программы создают и, похоже, хранят некоторые промежуточные результаты, такие как groupsOf список в приведенном выше коде. Приведенный выше код является справочным ответом на проблему 8 проекта Эйлера, взятым с веб-сайта Haskell. В исходном вопросе задается самый большой продукт из 5 последовательных цифр в очень длинной цепочке цифр, такой как 45343231635723421312443535767983456, Таким образом, код рассчитает все продукты и сохранит их в виде списка. В других языках я думаю, что они сохранят только временное наибольшее значение и откажутся от всего меньшего.

Так же groupsOf действительно хранит все промежуточные результаты? Что делать, если проблема масштабируется? Будет ли он выделять слишком много памяти?

Answer 1

Нет не из-за groupsOf, Этому нужно будет хранить только одну группу за раз. Тем не мение, maximum может создать большой поток, так как он слишком ленив, поэтому убедитесь, что либо скомпилировать с -O или же -O2 так что анализ строгости выполняется, или использовать foldl1' max вместо ¹.

_¹ foldl1' _{находится в} Data.List

Answer 2

Я понимаю, что в Haskell многие программы создают и, похоже, хранят некоторые промежуточные результаты, такие как список groupsOf в приведенном выше коде.

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

Одна изящная вещь о ленивых IO (например, readFile) заключается в том, что он будет читать только столько файлов, сколько необходимо, и этот файл можно будет собирать мусором по мере использования его содержимого. (Ну, примерно так. Это зависит от того, как вы установили буферизацию.)

Вот примерный план того, как будет выполняться ваша программа:

t <- readFile "p8.log"

Создать Thunk для t :: String, Вероятно, проверьте, что файл существует, и откройте его в режиме чтения.

 let digits = map digitToInt $concat $ lines t

Создать Thunk для digits :: [Int]

 print $ problem_8 digits

Как только мы попытаемся выполнить это, вся работа будет фактически выполнена. Нам нужно полностью оценить problem_8 digits :: Int для того, чтобы распечатать его. Таким образом, мы создаем Thunk для problem_8 digits и заставить его.

maximum . map product . groupsOf 5 $ digits

С этой точки зрения, maximum нужны первые два элемента map product . groupsOf 5 $ digits чтобы увидеть, какой из двух больше. Следовательно map product необходимо увидеть первые два элемента groupsOf 5 digits пройти вместе.

Сейчас, groupsOf 5 понадобятся первые 5 элементов digits чтобы произвести свой первый элемент. На этом этапе первая строка файла, вероятно, будет прочитана и пройдена через определенные преобразования. groupsOf может создать свой первый элемент и, возможно, второй элемент (при условии, что в этой строке более 6 символов). groupsOf 5 digits передает свои первые два элемента вверх по цепочке, мы отображаем product на эти две вещи, а затем maximum проверяет, какой из двух больше. Мы сохраняем результат, больший из двух.

На данный момент (на самом деле несколько раньше, чем этот момент) мы можем полностью отказаться от промежуточных результатов. Первые два элемента groupOf 5 digits теперь совершенно не нужны; нам никогда больше не нужно будет их проверять, и сборщик мусора может собрать их в любое время. Первые два символа этого файла также больше не будут использоваться и могут быть отброшены.

---

Теперь, это очень ручная работа и, возможно, немного неточно. Но вы поняли идею? Haskell ленив (ну технически Haskell "не строг", который обычно реализуется через лень), что делает его стиль исполнения сильно отличающимся от любого строгого языка. Это позволяет нам использовать то, что кажется тоннами промежуточных представлений и структур данных, фактически не занимая тонны памяти. Хорошие компиляторы, такие как GHC, могут оптимизировать использование памяти, как вы не поверите.

Answer 3

Я не уверен, что вы подразумеваете под "промежуточными результатами" здесь, в точности... Но ваш код выглядит хорошо для меня. В частности, ваша реализация groupsOf является хвостовой рекурсивной по модулю минусов, так что я не думаю, что вам придется беспокоиться о переполнении стека, если это то, что вас беспокоит.

Возможно, я неправильно понимаю ваш вопрос. Не могли бы вы уточнить?