관리 가능한 크기의 데이터 세트에서 Data.Sequence와 관련된 메모리 문제가 발생했습니다.

Question

TL; DR : (긴) 배열을 생성하는 코드를 작성 중입니다. 이 배열을 생성하고 List으로 변환 한 다음 최대 값을 계산할 수 있습니다 (엄격한 왼쪽 접기 사용). 하지만 최대 값을 계산하기 전에 목록을 Sequence으로 변환하려고하면 메모리 문제가 발생합니다. 이것은 나에게 상당히 직관적입니다.

내 질문 : 왜 이런 일이 일어나고 데이터를 Sequence 구조로 변환하는 올바른 방법은 무엇입니까?

배경 : 나는 아래의 세 단계를 사용하여 해결할 문제에 대해 작업 중입니다.

* 참고 : 나는이 게시물이 힌트로 사용되지 않도록 의도적으로 문제 문장을 모호하게 유지하려고합니다.

어쨌든, 내 제안 된 접근 방법 :

는

(i)는 첫째, 정수의 긴 목록을 생성, 즉, 1 억 (의 NOT 요인 자체 단지 숫자 1에서 각 정수 요소의 수 요소)

(ii) 둘째,이 목록을 시퀀스로 변환합니다.

(III) 마지막으로,

(다시 말하지만, 문제의 특성이 아닌이 있습니다 (이 단계는 디큐 작업 시퀀스에 따라서 필요 필요) 내 대답을 CALC하는 효율적인 슬라이딩 윈도우 최대 알고리즘을 사용 관련성이 높은 이유는 처음에이 특정 문제를 다루는 이유에 대해 궁금해하기 때문입니다.)

내가 지금까지 해 온 것은 무엇입니까?
1 단계는 매우 간단합니다. 아래 출력을 참조하십시오 (전체 코드는 하단에 있습니다). 나는 Unboxed Array와 accumArray 함수를 사용하여 sieve를 브루 포스 포위했다. 참고 : 저는이 같은 알고리즘을 사용하여 여러 가지 다른 문제를 해결했습니다. 그래서 나는 그것이 올바른 답을주고 있다고 합리적으로 확신합니다.

실행 시간/메모리 사용 통계를 보여주기 위해 필자는 결과 배열의 최대 요소를 계산하도록 선택했습니다. 모든 요소를 ​​강제로 생성하는 기능을 사용하는 것이 좋습니다. 따라서 우리는 exec 시간/메모리 사용에 대해 의미있는 통계를 볼 수 있습니다.

다음 main 기능 ...

main = print $ maximum' $ elems (sieve (10^8)) 

... 결과 다음 (즉, 가장 약수와 1 억 이하 수는 768 개 약수의 총이 있다고 말한다) :

를 우리가 인터넷을 달성 할 수처럼

Linking maxdivSO ... 
768 
33.73s user 70.80s system 99% cpu 1:44.62 total 

344,214,504,640 bytes allocated in the heap 
    58,471,497,320 bytes copied during GC 
    200,062,352 bytes maximum residency (298 sample(s)) 
     3,413,824 bytes maximum slop 
      386 MB total memory in use (0 MB lost due to fragmentation) 

%GC  time  24.7% (30.5% elapsed) 

문제는

보인다 내 버추얼 박스에 총 5GB를 할당했기 때문에 땀을 흘리지 않고 첫 걸음을 내딛었습니다. 위의 코드는 < 400MB를 사용합니다 (참고로, 프로그램이 성공적으로 실행되고 전체 메모리가 3GB 이상인 것으로보고했습니다). 다른 말로하면, 1 단계를 많은 헤드 룸으로 완료 한 것처럼 보입니다.

그래서 main 함수의 다음 버전이 실패하는 이유에 대해 조금 놀랐습니다. 최대 값과 동일한 계산을 수행하지만 정수 목록을 시퀀스로 변환 한 후에 시도합니다. 다음에 다음 코드 ...

main = print $ maximum' $ fromList $ elems (sieve (10^8)) 

... 결과 :

Linking maxdivSO ... 
maxdivSO: out of memory (requested 2097152 bytes) 
    39.48s user 76.35s system 99% cpu 1:56.03 total 

내 질문 : 알고리즘을 수행하는 이유 (현재 작성된) 우리가 변환하려고하면 메모리가 부족 시퀀스 목록? 그리고 어떻게하면이 목록을 시퀀스로 성공적으로 변환 할 수 있을까요? "

(나는 이러한 유형의 문제에 대해 강박 관념에 완강하게 고집하는 사람이 아닙니다. 그러나이 특별한 문제는 때문에 내 평가에 대해 잘 추론 할 수 없다는까지)

---

코드 자체 :.

{-# LANGUAGE NoMonomorphismRestriction #-} 

import Data.Word (Word32, Word16) 
import Data.Foldable (Foldable, foldl') 

import Data.Array.Unboxed (UArray, accumArray, elems) 
import Data.Sequence (fromList) 

main :: IO() 
main = print $ maximum' $ elems (sieve (10^8))    -- <-- works 
--main = print $ maximum' $ fromList $ elems (sieve (10^8)) -- <-- doesn't work 

maximum' :: (Foldable t, Ord a, Num a) => t a -> a 
maximum' = foldl' (\x acc -> if x > acc then x else acc) 0 

sieve :: Int -> UArray Word32 Word16 
sieve u' = accumArray (+) 2 (1,u) ((1,-1) : factors) 
    where 
    u = fromIntegral u' 
    cap = floor $ sqrt (fromIntegral u) :: Word32 
    factors = [ (i*d,j) | d <- [2..cap] 
         , i <- [2..(u `quot` d)] 
         , d <= i, let j = if i == d then 1 else 2 
       ] 

Answer 1

내가 이것에 대한 이유는 순서가를 필요로 그의 첫 번째 요소를 얻는 것입니다 생각 메모리에 구축 될 전체 시퀀스 (시퀀스의 내부 표현은 트리이기 때문에). 목록의 경우 elems은 지연 요소를 산출합니다.

전체 배열을 시퀀스로 바꾸는 것이 아니라 시퀀스를 슬라이딩 윈도우만큼만 만들면 어떻습니까?