목록 프로그램의 공간 누설

Question

하스켈에서 Project Euler의 일부 문제를 해결하고 있습니다. 나는 그것에 수수께끼를위한 프로그램을 썼다. 그리고 그것은 내가 예상했던 것처럼 작동하지 않았다.

프로그램을 실행할 때 작업 관리자를 살펴보면 ghc에서> 1 기가 바이트의 RAM을 사용하고있는 것으로 나타났습니다. 내 친구가 자바에서 같은 의미의 프로그램을 작성하고 7 초 만에 성공했습니다.

import Data.List 

opl = find vw $ map (\x-> fromDigits (x++[0,0,9])) 
     $ sequence [[1],re,[2],re,[3],re,[4],re,[5],re,[6],re,[7],re,[8],re] 

vw x = hh^2 == x 
    where hh = (round.sqrt.fromIntegral) x 

re = [0..9] 

fromDigits x = foldl1 (\n m->10*n+m) x 

는이 프로그램이 출력 내가 충분히 RAM와 시간을 부여 할 번호를 것이라고 알고 있지만, 더 나은 성능의 방법이 있어야한다.

Answer 1

여기서 주요 문제는 시퀀스에 공간 누수가 있다는 것입니다. 다음과 같이 정의된다 :

sequence [] = [[]] 
sequence (xs:xss) = [ y:ys | y <- xs, ys <- sequence xss ] 

그렇게 문제가 끝날 때까지 삭제 될 수 재귀 호출 sequence xss 의해 생성 된리스트는, xs의 각 요소에 대해 재사용된다는 것이다. 공간 누설이없는 버전은

myseq :: [[a]] -> [[a]] 
myseq xs = go (reverse xs) [] 
where 
    go [] acc = [acc] 
    go (xs:xss) acc = concat [ go xss (x:acc) | x <- xs ] 

PS입니다. 그들은이 문제에 대한 작업을하는 동안, 그래서 이러한 버전 모두 표준 sequence에서 다른 순서로 결과를 생성하는 것을

seqlists :: [[a]] -> [[a]] 
seqlists xss = go (reverse xss) [] [] 
where 
    go []  acc rest = acc : rest 
    go (xs:xss) acc rest = foldr (\y r -> go xss (y:acc) r) rest xs 

주 : 대답은 Just 1229314359627783009

편집 CONCAT을 피 버전 것 같다 sequence의 특수 버전으로 사용할 수 없습니다.

Answer 2

EDIT : 형식 서명을 다음과 같이 변경하는 것은 잘못된 것 같습니다. Word64 (이 문제에 대한 충분한 비트가 될 수 있음) 또한 영원히 걸리고/공간 누수가 있으므로 가능하지 않을 수 있습니다. 이전 Integer 버그

정수가 공간 누수의 원인이되는 오래된 GHC 버그 (문제가 해결 된 것 같습니다)가 문제인 것 같습니다. 아래 코드는 -O2로 컴파일하면 약 150ms 후에 끝납니다. 당신은 폭스 바겐에서 발견되는 특성을 가진 아홉 자리 숫자를 찾고 있기 때문에

import Data.List 
import Data.Word 

main = print opl 

opl :: Maybe Word32 
opl = find vw $ map (\x-> fromDigits (x++[0,0,9])) $ sequence [[1],re,[2],re,[3],re,[4],re,[5],re,[6],re,[7],re,[8],re] 

vw x = hh^2 == x 
    where hh = (round.sqrt.fromIntegral) x 

re = [0..9] 

fromDigits x = foldl1 (\n m->10*n+m) x 

Answer 3

, 난 그냥 우선 fromDigits x*1000+9 말 매핑 기능의 구성을 단순화하려고 것입니다. 목록에 추가하는 것은 O (left-of-the-left-list)이므로 마지막 세 자리를 던지면 계산 시간이 한꺼번에 줄어 듭니다.

제쳐두고 (두 사람 모두) 엄격한 버전의 폴드 (foldl1')를 사용하면 도움이됩니다.

Answer 4

Simon Marlow가 제공 한 답변에 이어 우주의 누출을 피할 수있는 순서의 버전이 있습니다. 주문을 보존하는 것을 포함하여 원본과 똑같이 작동하는 동안.

원래 시퀀스의 nice, simple list comprehension을 사용합니다. 유일한 차이점은 재귀 호출을 공유하지 못하도록 가짜 데이터 종속성이 도입된다는 것입니다.

sequenceDummy d [] = d `seq` [[]] 
sequenceDummy _ (xs:xss) = [ y:ys | y <- xs, ys <- sequenceDummy (Just y) xss ] 

sequenceUnshared = sequenceDummy Nothing 

공간 누설을 유발하는 공유를 피하는 더 좋은 방법이라고 생각합니다.

"완전한 게으름"변환에 대한 과도한 공유를 비난했습니다. 일반적으로 이것은 재 계산을 피하는 공유를 만드는 훌륭한 작업이지만, 때로는 재 계산은 공유 결과를 저장하는 것보다 훨씬 효율적입니다.

위의 더미 Maybe 인수가 효과적이지만 특정 표현을 공유하지 않도록 컴파일러에 지시하면 좋겠지 만 근본적으로 ghc가 ' 진정한 의존성이 없다는 것을 말하지 마십시오. 엄격한 언어에서는 변수를 값에 명시 적으로 바인딩하는 위치 만 공유하기 때문에 이러한 문제가 발생하지 않습니다.