하스켈에서이 프로그램을 최적화 할 수있는 방법이 있습니까?

Question

나는 프로젝트 euler question 224을하고있다. 그리고 하스켈이 지능형리스트를 채찍질 :

prob39 = length [ d | d <- [1..75000000], c <- [1..37500000], b <-[1..c], a <- [1..b], a+b+c == d, a^2 + b^2 == (c^2 -1)] 

나는 GHC로 컴파일하고 그 결과를 반환하지 않고 시간 이상에 대한 평균 이상 커널 우선 순위로 실행되고있다. 이 솔루션을 최적화하려면 어떻게해야합니까? 순진한 방법으로 무차별 해법을 찾는 것이 더 좋아지고있는 것 같습니다. 이것에 대해 제가 할 수있는 일이 있습니까?

EDIT : '정수 길이'에 대한 정의도 명확하지 않습니다. 이는 양수 길이가 양수 세트 인 1,2,3,4,5에 해당하는 크기를 가짐을 의미합니다. ..?

Answer 1

내 하스켈은 훌륭하지 않지만, 이것은 n^5가 될 것이라고 생각합니다.

1에서 7500 만까지의 각 n에 대해 말하고있는 것처럼, perimiter n이 있는지 알아보기 위해 perimeter가 7500 만 개 이하인 모든 "간신히 둔한"삼각형을 확인하십시오.

또한 목록의 내포가 c^2의 현재 값 -1이 a^2 + b^2보다 크면보고를 멈출만큼 똑똑한 지 확신 할 수 없습니다.

간단한 리팩토링은

prob39 = length [ (a, b, c) | c <- [1..37500000], b <-[1..c], a <- [1..b], a^2 + b^2 == (c^2 -1), (a + b + c) <= 75000000] 

당신이 더 잘 할 수 있어야한다, 그러나 그것은 말 그대로 7500 만 배 더 빠르게해야한다.

이 리팩토링에 대한 특정 적은 있지만, 그것은 또한 상당히 일을 속도를해야합니다

prob39 = length [ (a, b, c) | a <- [1..25000000], b <-[a..(75000000 - 2*a)], c <- [b..(75000000 - a - b)], a^2 + b^2 == (c^2 -1)] 

구문이 100 %되지 않을 수 있습니다. 아이디어는 1 천 2 백만에서 1 천 2 백만까지만 가능합니다 (< = b < = c 및 a + b + c < = 75 백만). b는 a와 b 사이에서만 7500 만 (b < = c부터)이고 c는 7500 만 ~ (a + b) 일 수 있습니다. 그렇지 않으면 둘레가 7500 만이 넘습니다.

편집 : 업데이트 된 코드 스 니펫에는 몇 가지 버그가 있습니다.

또 다른 빠른 제안으로는 < - [b .. (75000000-a-b)]을 다음 행으로 대체 할 수 있습니다. <- [b..min ((75000000-a-b), sqrt (a + bb) + 1)]. (a^2 + b^2)의 제곱근 한도보다 큰 c의 값을 검사 할 필요가 없습니다. 그것들이 haskell의 정확한 min/sqrt 함수 이름인지는 기억할 수 없다.

이 부분에 대한 강박 신경통 (OCD)을 얻으려면 몇 가지 제안 사항이 있습니다.

1) b의 상한을 현재 상한의 최소값으로^2 * 2 + 1로 설정할 수 있습니다. 이것은 (x + 1)^2 - x^2 = 2x + 1.b는 (a^2) + (b^2) < (b + 1)^2를 보장 할 수있는 것보다 훨씬 클 수 없습니다.

2) c의 하한을 b + 1 및 floor (sqrt (a^2 + b^2) - 1)의 최대 값으로 설정합니다. C의 상한과 마찬가지로 정확하지 않을 수있는 값을 테스트 할 필요가 없습니다.