최적화가 가능하거나 병렬 컴퓨팅을 사용하십시오.

Question

숫자와 같은 거듭 제곱 수를 찾아야하는이 문제가 있습니다. 그래서 예를 들면 : 100 2의 입력이 문제를 해결하기 위해 1 그래서

100 = 1^3 + 2^3 + 3^3 + 4^3 때문에 내 함수의 출력을 얻을 것 3100 = 10^2 = 6^2 + 8^2 = 1^2 + 3^2 + 4^2 + 5^2 + 7^2 때문에 출력과 100 3의 입력을 얻을 것이다

입니다 :

내 번호 집합에 포함될 수있는 가능한 모든 값을 찾아 원하는 숫자를 찾습니다. 그런 다음 목록에 가능한 모든 하위 목록을 찾아서 원하는 숫자까지 추가 할 수 있는지 확인하십시오. 이것은 작동하지만 철저한 검색이므로 800 2과 같은 입력에는 오랜 시간이 걸립니다. "그럴듯한"서브 시퀀스 만 반환되도록 시퀀스를 최적화 할 수 있습니까? 아니면 이런 종류의 문제에 대한 병렬 계산을 보는 것이 더 나은가?

Answer 1

몇 가지를 살펴 봅시다.

벤치마킹

첫 번째 : 우리가 실제로 우리가 가서 개선을하고 있는지 만들자!이를 위해 몇 가지 벤치 마크가 필요합니다. criterion 패키지가 이에 적합합니다. 또한 최적화 (GHC 호출시 모두 -O2)로 컴파일해야합니다.

이

import Criterion.Main 

-- your code goes here 

main = defaultMain 
    [ bench "findNums 100 2" (nf (uncurry findNums) (100, 2)) 
    , bench "findNums 800 2" (nf (uncurry findNums) (800, 2)) 
    ] 

하나는 nf (findNums 100) 2로 벤치 마크를 구현할 수 있지만, 우리가 100에 대한 조회 테이블을 미리 계산에 의해 "속임수"할 수 있도록 내가 이렇게 밀어,이 방법을 선택합니다 : 여기에 벤치 마크가 될 수있는 방법을 간단한 설정이야 모든 작업은 벤치 마크가 실제로 실행되는 부분이 아닌 벤치 마크 설정으로 진행됩니다.

benchmarking 100 2 
time     762.7 ns (757.4 ns .. 768.5 ns) 
        1.000 R² (1.000 R² .. 1.000 R²) 
mean     762.5 ns (760.4 ns .. 765.3 ns) 
std dev    7.706 ns (6.378 ns .. 10.59 ns) 

benchmarking 800 2 
time     29.17 s (28.28 s .. 29.87 s) 
        1.000 R² (1.000 R² .. 1.000 R²) 
mean     29.26 s (29.08 s .. 29.35 s) 
std dev    159.2 ms (0.0 s .. 165.2 ms) 
variance introduced by outliers: 19% (moderately inflated) 

를 사용하여 라이브러리

이제, 저 매달려 열매는 가지의 기존의 구현을 사용하고 그 저자가 우리보다 더 나은 뭔가를했다 희망하는

다음은 원래의 구현에 대한 결과입니다. 이를 위해 root 대신에 pow 대신 (^)이라는 표준 함수를 사용하고 패키지의 integerRoot을 사용합니다. 또한, 우리는 게으른 foldr을 엄격한 foldl으로 교체 할 것입니다. 내 자신의 온건함을 위해 나는 또한 매우 긴 줄을 짧은 줄로 다시 포맷했다. 전체 결과는 이제 다음과 같습니다

import Criterion.Main 
import Data.List 
import Math.NumberTheory.Powers 

sum' :: Num a => [a] -> a 
sum' = foldl' (+) 0 

findNums :: Int -> Int -> Int 
findNums a b = length 
    [ xs 
    | xs <- drop 1 . subsequences $ [x^b | x <- [1..c]] 
    , sum' xs == a 
    ] where c = integerRoot b a 

main = defaultMain 
    [ bench "100 2" (nf (uncurry findNums) (100, 2)) 
    , bench "800 2" (nf (uncurry findNums) (800, 2)) 
    ] 

벤치 마크 결과는 지금과 같이 :

benchmarking 100 2 
time     722.8 ns (721.3 ns .. 724.3 ns) 
        1.000 R² (1.000 R² .. 1.000 R²) 
mean     722.6 ns (721.4 ns .. 724.1 ns) 
std dev    4.440 ns (3.738 ns .. 5.674 ns) 

benchmarking 800 2 
time     17.16 s (16.93 s .. 17.64 s) 
        1.000 R² (1.000 R² .. 1.000 R²) 
mean     17.05 s (16.99 s .. 17.15 s) 
std dev    88.10 ms (0.0 s .. 94.58 ms) 

작은 배에서 빠른 속도로 아주 작은 노력으로. 좋은!

더 나은 알고리즘

subsequences에 중요한 문제는 우리가 sum' [x,y,z] > a, 우리는 여전히 [x,y,z]로 시작하는 모든 이상 시퀀스 볼 것을 계산하는 경우에도, 그. subsequences '반환 유형의 구조를 감안할 때 우리가 할 수있는 일은별로 없습니다. 그래서 우리에게 좀 더 많은 구조를 제공하는 구현을 설계합시다. 루트에서 임의의 내부 노드까지의 경로가 서브 시퀀스를 제공하는 트리를 만듭니다.

이 (그냥 재미를 위해, 이것은 매우 작은 공간 사용에 기하 급수적으로 큰 의미 나무를 생산 - 원래 목록과 거의 같은 정도의 공간 -. 공격적인 서브 트리 공유에)

import Data.Tree 

subsequences :: [a] -> Forest a 
subsequences [] = [] 
subsequences (x:xs) = Node x rest : rest where 
    rest = subsequences xs 

이 표현에 대한 멋진 무엇이며, 우리의 경우 검색을 중단하면, 우리는 흥미로운 결과를 엄청나게 잘라냅니다. 이것은 목록에 대한 takeWhile 뭔가를 구현하여 실현 될 수있다 :

takeWhileTree :: Monoid m => (m -> Bool) -> Forest m -> Forest m 
takeWhileTree predicate = goForest mempty where 
    goForest m forest = forest >>= goTree m 
    goTree m (Node m' children) = 
     [Node m (goForest (m <> m') children) | predicate m'] 

것은 그것은 시도 줘 보자. 전체 코드는 이제 :

는

import Criterion.Main 
import Data.Foldable 
import Data.Monoid 
import Data.Tree 
import Math.NumberTheory.Powers 

subsequencesTree :: [a] -> Forest a 
subsequencesTree [] = [] 
subsequencesTree (x:xs) = Node x rest : rest where 
    rest = subsequencesTree xs 

takeWhileTree :: Monoid m => (m -> Bool) -> Forest m -> Forest m 
takeWhileTree predicate = goForest mempty where 
    goForest m forest = forest >>= goTree m 
    goTree m (Node m' children) = let m'' = m <> m' in 
     [Node m' (goForest m'' children) | predicate m''] 

leaves :: Forest a -> [[a]] 
leaves [] = [[]] 
leaves forest = do 
    Node x children <- forest 
    xs <- leaves children 
    return (x:xs) 

findNums :: Int -> Int -> Int 
findNums a b = length 
    [ xs 
    | xs <- leaves 
      . takeWhileTree (<= Sum a) 
      . subsequencesTree 
      $ [Sum (x^b) | x <- [1..c]] 
    , fold xs == Sum a 
    ] where c = integerRoot b a 

main = defaultMain 
    [ bench "100 2" (nf (uncurry findNums) (100, 2)) 
    , bench "800 2" (nf (uncurry findNums) (800, 2)) 
    ] 

이 많은 작업처럼 보이지만 타이밍에서, 정말 떨어져 지불 : findNums 800 2에 약 1000의 속도 향상 요인이다

benchmarking 100 2 
time     16.67 μs (16.53 μs .. 16.77 μs) 
        0.999 R² (0.999 R² .. 1.000 R²) 
mean     16.60 μs (16.52 μs .. 16.72 μs) 
std dev    325.4 ns (270.5 ns .. 444.1 ns) 
variance introduced by outliers: 17% (moderately inflated) 

benchmarking 800 2 
time     22.59 ms (22.26 ms .. 22.89 ms) 
        0.999 R² (0.999 R² .. 1.000 R²) 
mean     22.44 ms (22.34 ms .. 22.57 ms) 
std dev    260.3 μs (191.6 μs .. 332.2 μs) 

합니다. 나무의 별도의 가지가 병렬로 탐구 될 수 있도록

병렬화

나는, takeWhileTree 대신 (>>=)에 concat 및 parMap를 사용하여이 작업을 병렬에서 이동을했다.모든 경우에 병렬 처리의 오버 헤드가 여러 스레드를 갖는 이점을 훨씬 능가했습니다. 처음에 그 벤치 마크를 제자리에 두는 것이 좋습니다!

Answer 2

당신이 제안했듯이, 병렬화에 의존하지 않고 여기서 최적화를위한 여지가 있습니다 (하나의 스레드에서 4 개의 병렬 스레드로 가면 4 배속 향상이 가능하다는 것을 명심하십시오).

함수가 수행하는 작업은 기본적으로 목록을 통해 진행되며 각 요소에 대해 두 개의 실행 분기를 만듭니다. 하나는 요소가 포함되고 다른 하나는 그렇지 않습니다. 즉, subsequences [1,2,3]을 수행합니다

이

      start 
        /-------/ \-------\   (take 1 or not) 
      [1,..]     [..] 
      / \    / \  (take 2 or not) 
    [1,2,..]  [1,..]  [2,..] [..] 
    /\   /\  /\ /\ (take 3 or not) 
[1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] [] 

subsequences [1,2,3]의 결과는 다음 하단에있는 리프 노드를 포함하는 목록입니다.

이제, 중간 노드들 각각 (즉, [1,2,..])에서, 이미 취해진 수에 값 함수 (즉, 제곱 또는 큐브의 합 등)를 적용한 결과를 확인할 수있다. 우리가 이미 목표를 초과한다면, 그 지점을 계속할 필요가 없습니다. 우리가 우리 자신에 의해이 서브 생성 로직을 작성하는 경우, 우리는 그 작업을 수행 할 수 있습니다

다음

findNums :: Int -> Int -> Int 
findNums a b = findNums' a b 1 0 

findNums' :: Int -> Int -> Int -> Int -> Int 
findNums' a b c s 
    | s + c^b > a = 0 
    | s + c^b == a = 1 
    | otherwise = findNums' a b (c+1) (s + c^b) + 
        findNums' a b (c+1) s 

c 우리의 카운터와 s 우리가 고른 숫자의 힘의 합이다. findNums'에 세 가지 경우가 있습니다.

첫 번째 경우에는이 번호를 포함하면 Google이 목표를 초과하는지 여부가 확인됩니다. 이 경우,이 분기는 유효한 결과를 제공하지 않으므로 0을 반환하여 솔루션을 포함하지 않음을 나타냅니다.

두 번째 경우에는이 숫자를 포함하면 오른쪽에 넣을 지 여부가 검사됩니다 자리. 이 경우 우리는 1을 반환하며, 본질적으로 해결책을 찾았다는 사실에 주목해야합니다.

이들 중 어느 것도 사실이 아닌 경우 우리는 합계에 c^b을 추가하는 두 가지 분기와 추가로 분기하지 않는 분기를 사용합니다. 결과를 함께 추가합니다. 즉, 결과는이 지점 아래에 유효한 솔루션을 발견 한 지점 수입니다.

Answer 3

실제 시퀀스를 반환하는 함수를 작성하는 것이 유용합니다.이 함수는 그 자체로 재귀 적으로 이라고 쓸 수 있기 때문입니다.

간단히하기 위해 제곱의 합계를 고려해 보겠습니다. 또한 먼저 순서가 지정된 시퀀스를 고려합니다 ( 반복 값 허용). 나중에 번호를 반복하지 않고 순서가없는 시퀀스 만 생성하도록 알고리즘을 수정하는 방법을 살펴 보겠습니다.

첫 번째 시도입니다. 알고리즘은 이러한 생각에 기초한다 :

아이디어 1 : 그 합계

합의 제곱의 N 인 시퀀스를 획득하기 위해, 제 값 C 및 시퀀스를 선택 XS 사각형의 은 nc * c이고 두 개를 합치십시오.

-- an integer sqrt function 
isqrt n = floor $ (sqrt (fromIntegral n) :: Double) 

pows2a :: Int -> [ [Int] ] 
pows2a n 
    | n < 0  = [] 
    | n == 0 = [ [] ] 
    | otherwise = [ (c:xs) | c <- [start,start-1..1], xs <- pows2a (n-c*c) ] 
    where start = isqrt n 

이 작동하지만, 반복 요소와 솔루션의 순열뿐만 아니라 솔루션을 반환 - 예를 들어, pos2a 6은 [2,1,1], [1,2,1], [1,1,2] 및 [1,1,1,1,1,1]을 반환합니다.

단지 우리는이 개념 사용 (반복없이) 순서화 시퀀스를 되돌리려 : 값 선택

합의 제곱의 N 인 시퀀스를 획득하기 위해, 제 :

아이디어 2 c 및 그 시퀀스가 ​​ 인 xs의 시퀀스는 nc * c이고 모든 요소는 모두 < c 및 두 개를 함께 넣습니다.

이 우리의 첫 알고리즘의 단지 약간의 수정이다

pows2b :: Int -> [[Int]] 
pows2b n 
    | n < 0  = [] 
    | n == 0 = [ [] ] 
    | otherwise = [ (c:xs) | c <- [start, start-1..1], xs <- pows2b (n-c*c), all (< c) xs ] 
    where 
    start = isqrt n 

이 작동하지만 pows2b 100 같은 호출이 우리가 호출을하기 때문에 같은 인수를 여러 번에 pows2b에 완료하는 데 시간이 오래 걸립니다 .

우리는 결과를 memoizing하여 해당 문제를 해결할 수 있습니다, 이것은 pows2c가하는 일입니다 :

여기

powslist = map pows2c [0..] 
pows2c n 
    | n == 0 = [ [] ] 
    | otherwise = [ (c:xs) | c <- [s,s-1..1], xs <- powslist !! (n-c*c), all (< c) xs ] 
    where s = isqrt n 

인수 n-c*c로 재귀 호출이를 캐싱하는 방법이다 목록으로 조회로 대체 대답.