Andy Melnikov (nponeccop) wrote,
Andy Melnikov
nponeccop

Масштабируемость SplitString и ленивые вычисления

Продолжая тему парсинга строк на Haskell и Сlean:

Реализации с использованием foldr и foldl, к сожалению, не работают на очень больших массивах данных. Так, мои реализации с foldr при попытке скормить им ленивый 26-мегабайтный список падали с переполнением стека, а реализации на основе foldl - с переполнением кучи. Конечно, были установлены довольно жесткие границы стека и  кучи - сотни килобайт при 2.5 гб физической памяти. Но меня волновал сам факт того, что потребление памяти растет с увеличением объема данных в такой простой функции. На императивном языке последовательное чтение и токенизация файла занимает фиксированное количество памяти вне зависимости от размера файла.

Проблема оказалась в функции fold.Функция fold на каждой итерации принимает весь свой предыдущий результат целиком, не давая возможности получить часть результата до окончания работы. Эта мысль привела меня к следующей реализации, эффективно использующей ленивую рекурсию:
module fileReader

import StdEnv

splitString7 sep lst = [ firstToken : splitString7 sep firstTail ]
where
	(firstToken, firstTail) = splitFirstToken lst
	splitFirstToken [hd:tl]
		| isMember hd sep = ([], tl)
		= ([hd : tokenTail ], lstTail) 
		where 
			(tokenTail, lstTail) = splitFirstToken tl
	 
Start world = splitString7 [';\n'] megaList
where
	(megaList, _) = CharListRead infile
	(_, infile, _) = sfopen "in.txt" FReadText world

CharListRead f
	| sfend f = ([], f)
	= ([c : charTail ], fileAtEof)
	where
		(_ , c, fileAtNextChar) = sfreadc f
		(charTail, fileAtEof) = CharListRead fileAtNextChar
В продолжение нашего туториала теперь можно реализовать функцию СharListRead, выполнающую чтение файла в ленивый список символов, и проверить на ней потребление памяти нашей функцмей токенизации.
Tags: compiler design
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 11 comments