하스켈에서보다 효율적인 알고리즘 프리폼 더

Question

내 친구가 그가 참석하는 C++ 코스에서 가정 운동을 보여주었습니다. 저는 C++을 이미 알고 있기 때문에 하스켈을 배우기 시작 했으므로 저는 "하스켈 방식"으로 운동을 풀려고했습니다.

이는 운동 지침 (내가 지시가 명확하지 않은 경우 그래서 의견을하시기 바랍니다 우리의 모국어 번역)입니다

읽기 프로그램을 작성 비 - 제로 계수 (A, B, C, D) A * x + B * y + C * z = D 또한 프로그램은 범위를 나타내는 사용자 N에서 읽어야합니다. 프로그램은 -N/2 ~ N/2 범위의 방정식에 대해 가능한 모든 통합 솔루션을 찾아야합니다. 예를 들어

:

Input: A = 2,B = -3,C = -1, D = 5, N = 4 
Output: (-1,-2,-1), (0,-2, 1), (0,-1,-2), (1,-1, 0), (2,-1,2), (2,0, -1) 

가장 솔직 알고리즘은 무력에 의한 모든 가능성을 시도하는 것입니다.

triSolve :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)] 
triSolve a b c d n = 
    let equation x y z = (a * x + b * y + c * z) == d 
     minN = div (-n) 2 
     maxN = div n 2 
    in [(x,y,z) | x <- [minN..maxN], y <- [minN..maxN], z <- [minN..maxN], equation x y z] 

지금까지 너무 좋은,하지만 운동 지침은보다 효율적인 알고리즘이 구현 될 수 있습니다, 그래서 그것을 더 나은 만드는 방법을 생각 : 나는 다음과 같은 방법으로 하스켈에서 구현. 방정식은 선형이기 때문에 Z가 항상 처음으로 증가한다는 가정에 기초하여 솔루션이 발견되면 Z를 증가시킬 포인트가 없습니다. 대신 Y를 증가시키고 Z를 범위의 최소값으로 설정하고 계속가. 이렇게하면 중복 실행을 줄일 수 있습니다. Haskell에는 루프가 없으므로 (적어도 필자의 이해로) 이러한 알고리즘은 재귀를 사용하여 구현되어야 함을 깨달았습니다. 나는 다음과 같은 방식으로 알고리즘을 구현했다.

solutions :: (Integer -> Integer -> Integer -> Bool) -> Integer -> Integer -> Integer -> Integer -> Integer ->  [(Integer,Integer,Integer)] 
solutions f maxN minN x y z 
    | solved = (x,y,z):nextCall x (y + 1) minN 
    | x >= maxN && y >= maxN && z >= maxN = [] 
    | z >= maxN && y >= maxN = nextCall (x + 1) minN minN 
    | z >= maxN = nextCall x (y + 1) minN 
    | otherwise = nextCall x y (z + 1) 
    where solved = f x y z 
     nextCall = solutions f maxN minN 

triSolve' :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)] 
triSolve' a b c d n = 
    let equation x y z = (a * x + b * y + c * z) == d 
     minN = div (-n) 2 
     maxN = div n 2 
    in solutions equation maxN minN minN minN minN 

두 결과 모두 똑같은 결과를 산출한다. 바보 알고리즘이 실제로 더 정교보다 더 나은 예비 적 의미

*Main> length $ triSolve' 2 (-3) (-1) 5 100 
3398 
(2.81 secs, 971648320 bytes) 
*Main> length $ triSolve 2 (-3) (-1) 5 100 
3398 
(1.73 secs, 621862528 bytes) 

그러나, 실행 시간을 측정하려고하면 다음과 같은 결과를 얻었다. 내 알고리즘이 올바르다는 가정에 기반하여 (나는 잘못된 것으로 바뀌지 않을 것입니다. :)), 두 번째 알고리즘은 재귀에 의해 생성 된 오버 헤드로 인해 발생한다고 가정합니다. 첫 번째 알고리즘은 목록 이해력. Haskell에서 바보 같은 알고리즘을 구현하는 방법이 있습니까? (내 코딩 스타일에 대한 일반적인 피드백을받을 수있어서 기쁩니다)

Answer 1

물론 있습니다.

a*x + b*y + c*z = d 

을하고 곧 우리가 x와 y의 값을 가정, 우리는이 n은 우리가 알고있는 숫자입니다

a*x + b*y = n 

이 : 우리는 가지고있다. 따라서

c*z = d - n 
z = (d - n)/c 

그리고 우리는 정수 z만을 유지합니다.

Answer 2

목록 작성에는 GHC의 특별한 대우가 주어지고 일반적으로 매우 빠르다는 점에 유의해야합니다. 이것은 왜 triSolve (리스트 이해력을 사용하는)이 triSolve'보다 빠르다는 것을 설명 할 수 있습니다.예를 들어

, 내 컴퓨터에

solve :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)] 
-- "Buffalo buffalo buffalo buffalo Buffalo buffalo buffalo..." 
solve a b c d n = 
    [(x,y,z) | x <- vals, y <- vals 
      , let p = a*x +b*y 
      , let z = (d - p) `div` c 
      , z >= minN, z <= maxN, c * z == d - p ] 
    where 
     minN = negate (n `div` 2) 
     maxN = (n `div` 2) 
     vals = [minN..maxN] 

실행 빠른 해결책 : do 표기법을 사용하여 기록에 해당하는 코드 반면

> length $ solve 2 (-3) (-1) 5 100 
3398 
(0.03 secs, 4111220 bytes) 

:

solveM :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)] 
solveM a b c d n = do 
    x <- vals 
    y <- vals 
    let p = a * x + b * y 
     z = (d - p) `div` c 
    guard $ z >= minN 
    guard $ z <= maxN 
    guard $ z * c == d - p 
    return (x,y,z) 
    where 
     minN = negate (n `div` 2) 
     maxN = (n `div` 2) 
     vals = [minN..maxN] 

는에 한 두 번한다 실행하고 두 배의 메모리를 사용합니다 :

> length $ solveM 2 (-3) (-1) 5 100 
3398 
(0.06 secs, 6639244 bytes) 

GHCI 내에서 테스트하는 것에 관한 일반적인주의 사항 - 실제로 차이점을 확인하려면 -O2를 사용하여 코드를 컴파일하고 적절한 기준 (criterion) 라이브러리를 사용해야합니다.