변경 불가능한 데이터 구조로 데이터 변경

Question

특정 알고리즘을 구현하고 싶습니다만 작업에 적합한 데이터 구조를 찾는 데 문제가 있습니다.

C++에서

Input: A set of points. 
Output: A new set of points. 
Step 1: For each point, calculate the closest points in a radius. 
Step 2: For each point, calculate a value "v" from the closest points subset. 
Step 3: For each point, calculate a new value "w" from the closest points and 
     the values "v" from the previous step, i.e, "w" depends on the neighbors 
     and "v" of each neighbor. 
Step 4: Update points. 

, 나는 이런 식으로이 문제를 해결 할 수 있습니다 : 같은 점의 목록으로 순진 구조로

struct Point { 
    Vector position; 
    double v, w; 
    std::vector<Point *> neighbors; 
}; 

std::vector<Point> points = initializePoints(); 
calculateNeighbors(points); 
calculateV(points); // points[0].v = value; for example. 
calculateW(points); 

을, 나는을 업데이트 할 수 없습니다 알고리즘의 간단한 버전은 다음과 같이 작동합니다 값 "v"를 원래의 점 집합으로 바꾸고 이웃을 두 번 계산해야합니다. 이웃을 계산하는 것이 알고리즘의 가장 비싼 부분 (30 % 이상)이기 때문에 어떻게 이것을 피하고 함수를 순수하게 유지할 수 있습니까?

추 신 : 수치 방법 및 CFD 경험이있는 사용자의 경우 Smoothed Particle Hydrodynamics 방법의 단순화 된 버전입니다.

업데이트 : 3 단계가 변경되어 명확 해졌습니다.

Answer 1

하스켈이 돌연변이를 전혀 제공하지 않는다는 공통된 신화입니다. 실제로 이것은 매우 특별한 종류의 돌연변이를 제공합니다. 평가되지 않은 것에서 평가 된 것까지 한 번 정확하게 변이 될 수 있습니다. 이 특별한 종류의 돌연변이를 이용하는 기술은 tying the knot입니다. 우리는 C++에서 같은 데이터 구조로 시작됩니다

data Vector -- held abstract 

data Point = Point 
    { position :: Vector 
    , v, w  :: Double 
    , neighbors :: [Point] 
    } 

지금, 우리가 할거야 누구의 Array Pointneighbors가 같은 배열 내에서 다른 요소에 대한 포인터를 포함 구축이다. 다음 코드에서 Array의 주요 기능은 척추 게으른 (요소가 너무 빨리 적용되지 않음) 빠른 임의 액세스가 있다는 점입니다. 원하는 경우 선호하는 대체 데이터 구조를 이러한 속성으로 대체 할 수 있습니다.

이웃 찾기 기능의 인터페이스에는 다양한 선택 항목이 있습니다. 구체성과 자신의 일을 간단하게하기 위해 나는 Vector과 Vectors의 목록을 가지고 이웃의 지수를주는 함수를 가지고 있다고 가정합니다.

findNeighbors :: Vector -> [Vector] -> [Int] 
findNeighbors = undefined 

는의도 computeV 및 computeW 장소에서 몇 가지 유형을 넣어 보자.nonce의 경우 position 및 neighbors 필드가 Point이며, v 또는 w 필드는 볼 수 없다는 내용의 비공식 계약서를 computeV에 부탁합니다. 마찬가지로, computeW은 Point의 w 필드를 볼 수도 있지만 너무 많은 체조가 없으면 유형 수준에서이를 적용 할 수 있지만 실제로는 건너 뜁니다.

computeV, computeW :: Point -> Double 
(computeV, computeW) = undefined 

이제 우리는 (라벨이 붙은) 인 - 메모리 그래프를 만들 준비가되었습니다.

buildGraph :: [Vector] -> Array Int Point 
buildGraph vs = answer where 
    answer = listArray (0, length vs-1) [point pos | pos <- vs] 
    point pos = this where 
     this = Point 
      { position = pos 
      , v = computeV this 
      , w = computeW this 
      , neighbors = map (answer!) (findNeighbors pos vs) 
      } 

그리고 그게 사실입니다.

update :: [Vector] -> [Vector] 
update = newPositions <=< elems . buildGraph 

편집 : ... 설명 지금 당신은

newPositions :: Point -> [Vector] 
newPositions = undefined 

newPositions 그것을 건네 년대 Point의 필드 중 하나를 검사하고, 함께 모든 기능을 넣어 완벽하게 무료

하여 쓸 수 있습니다 처음에는 "특별한 종류의 돌연변이"주석이 있습니다. 평가 중에는 다음과 같은 일들이 일어날 것이라고 w 필드에 요구합니다. computeW은 v 필드를 강제합니다. computeV은 강제로 neighbors 필드를 나타냅니다. neighbors 필드는 평가되지 않은 것으로부터 평가 된 것으로 변합니다. v 필드는 평가되지 않은 값에서 평가 된 값으로 변경됩니다. w 필드는 평가되지 않은 것으로부터 평가 된 것으로 변합니다. 마지막 세 단계는 C++ 알고리즘의 세 가지 돌연변이 단계와 매우 유사합니다!

두 번 편집 : 나는이 일을보고 싶다고 결심했다. 그래서 위에서 추상화 된 모든 것들을 더미 구현으로 인스턴스화했다. 나는 또한 내가 그것을 올바르게했다고 확신하지 못했기 때문에 그것이 단지 한 번만 평가하는 것을보고 싶었다! 그래서 나는 trace 전화를 던졌다.

import Control.Monad 
import Data.Array 
import Debug.Trace 

announce s (Vector pos) = trace $ "computing " ++ s ++ " for position " ++ show pos 

data Vector = Vector Double deriving Show 

data Point = Point 
    { position :: Vector 
    , v, w  :: Double 
    , neighbors :: [Point] 
    } 

findNeighbors :: Vector -> [Vector] -> [Int] 
findNeighbors (Vector n) vs = [i | (i, Vector n') <- zip [0..] vs, abs (n - n') < 1] 

computeV, computeW :: Point -> Double 
computeV (Point pos _ _ neighbors) = sum [n | Point { position = Vector n } <- neighbors] 
computeW (Point pos v _ neighbors) = sum [v | Point { v = v } <- neighbors] 

buildGraph :: [Vector] -> Array Int Point 
buildGraph vs = answer where 
    answer = listArray (0, length vs-1) [point pos | pos <- vs] 
    point pos = this where { this = Point 
     { position = announce "position" pos $ pos 
     , v   = announce "v" pos $ computeV this 
     , w   = announce "w" pos $ computeW this 
     , neighbors = announce "neighbors" pos $ map (answer!) (findNeighbors pos vs) 
     } } 

newPositions :: Point -> [Vector] 
newPositions (Point { position = Vector n, v = v, w = w }) = [Vector (n*v), Vector w] 

update :: [Vector] -> [Vector] 
update = newPositions <=< elems . buildGraph 

과 ghci에서 실행 : 당신이 볼 수 있듯이

*Main> length . show . update . map Vector $ [0, 0.25, 0.75, 1.25, 35] 
computing position for position 0.0 
computing v for position 0.0 
computing neighbors for position 0.0 
computing position for position 0.25 
computing position for position 0.75 
computing w for position 0.0 
computing v for position 0.25 
computing neighbors for position 0.25 
computing v for position 0.75 
computing neighbors for position 0.75 
computing position for position 1.25 
computing w for position 0.25 
computing w for position 0.75 
computing v for position 1.25 
computing neighbors for position 1.25 
computing w for position 1.25 
computing position for position 35.0 
computing v for position 35.0 
computing neighbors for position 35.0 
computing w for position 35.0 
123 

, 각 필드는 대부분 한 번 각 위치에서 계산 다음은 전체 파일입니다.

Answer 2

다음과 같이 할 수 있습니까? 다음과 같은 유형의 서명

calculateNeighbours :: [Point] -> [[Point]] 

calculateV :: [Point] -> Double 

calculateW :: [Point] -> Double -> Double 

을 감안할 때 당신은

algorithm :: [Point] -> [(Point, Double, Double)] 
algorithm pts =        -- pts :: [Point] 
    let nbrs = calculateNeighbours pts  -- nbrs :: [[Point]] 
     vs = map calculateV nbrs   -- vs :: [Double] 
     ws = zipWith calculateW nbrs vs -- ws :: [Double] 
    in zip3 pts vs ws      --  :: [(Point,Double,Double)] 

을 쓸 수 있습니다이 한 번만 이웃의 목록을 계산하고 v 및 w에 대한 계산의 값을 재-사용합니다.

이것이 원하는 것이 아니라면, 조금 더 자세히 설명해 주시겠습니까?

Answer 3

지도 (HashMap)를 사용하여 Point에서 계산 한 v (및 w)를 별도로 저장하거나 mutable variables을 사용하여 C++ 알고리즘을 반영해야한다고 생각합니다. 첫 번째 방법은 더 "기능적"입니다. 당신은 쉽게 모든 데이터가 불변이므로 parralelism을 쉽게 추가 할 수 있습니다. 그러나 v가 끝날 때마다 해쉬를 계산해야하기 때문에 조금 느려야합니다.