2

特定のアルゴリズムを実装したいのですが、ジョブに適したデータ構造を見つけるのに苦労しています。アルゴリズムの単純なバージョンは、次のように機能します。

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.

C++ では、次のように解決できます。

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」を元のポイントのセットに更新することはできず、隣接点を 2 回計算する必要があります。これを回避し、関数を純粋に保つにはどうすればよいでしょうか? アルゴリズムの中で最もコストがかかる部分 (時間の 30% 以上) は、近傍の計算です。

追伸: 数値法と CFD の経験者向けに、これは平滑化粒子流体力学法の簡略化されたバージョンです。

更新: ステップ 3 を変更して、より明確にしました。

4

3 に答える 3

6

Haskell がミューテーションをまったく提供しないというのはよくある神話です。実際には、これは非常に特別な種類の変更を提供します。値は、未評価から評価済みに一度だけ変更できます。この特別な種類の突然変異を利用する技術は、結び目を結ぶことと呼ばれます。C++ のものと同じようなデータ構造から始めます。

data Vector -- held abstract

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

次に、同じ配列内の他の要素へのポインターを含むArray Pointを作成します。neighbors次のコードの主な機能はArray、spine-lazy (その要素をすぐに強制しない) であり、高速なランダム アクセスを備えていることです。必要に応じて、お気に入りの代替データ構造をこれらのプロパティに置き換えることができます。

近隣探索機能のインターフェースには多くの選択肢があります。具体的にし、自分の仕事を簡単にするために、Vectorと のリストを取り、Vectors隣人のインデックスを与える関数があると仮定します。

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

computeVとのいくつかの型も配置しましょうcomputeW。ノンスについては、computeVあなたが述べた非公式の契約に従うようにお願いします。つまり、任意のフィールドのpositionandフィールドを参照できますが、 orフィールドは参照できません。(同様に、それが手に入れることができる任意のフィールド以外は何でも見ることができます。) あまり多くの体操をしなくても、型レベルでこれを強制することは実際には可能ですが、今はそれをスキップしましょう。neighborsPointvwcomputeWwPoint

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)
            }

それだけです。今、あなたはあなたを書くことができます

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

wherenewPositionsは、渡されたフィールドのいずれかを完全に自由に検査し、Pointすべての機能をまとめます。

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

編集: ...冒頭の「特別な種類の突然変異」コメントを説明する: 評価中にw、 a のフィールドを要求すると、次のPoint順序で物事が起こることが期待できます:フィールドcomputeWを強制しvます; 次に、フィールドcomputeVを強制します。neighbors次に、neighborsフィールドは未評価から評価済みに変化します。次に、vフィールドは未評価から評価済みに変化します。その後、wフィールドは未評価から評価済みに変化します。これらの最後の 3 つのステップは、C++ アルゴリズムの 3 つの変更ステップと非常によく似ています。

二重編集: 私はこのことが実行されるのを見たいと思ったので、上記の抽象化されたすべてのものをダミーの実装でインスタンス化しました。また、正しく評価したかどうかさえ確信が持てなかったので、一度だけ評価するのを見たかったのです! それで私はいくつかの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

ご覧のとおり、各フィールドは位置ごとに最大 1 回計算されます。

于 2013-10-08T23:51:41.807 に答える
3

このようなことができますか？次の型シグネチャが与えられた場合

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これにより、近傍のリストが 1 回だけ計算され、 およびの計算で値が再利用されますw。

これがあなたの望むものではない場合、もう少し詳しく説明していただけますか?

于 2013-10-04T09:17:29.563 に答える
0

Map ( HashMap ) を使用して v (および w) を個別に格納するか、可変変数Pointを使用して C++ アルゴリズムを反映する必要があると思います。最初の方法はより「機能的」です。たとえば、すべてのデータが不変であるため、簡単に並列処理を追加できますが、ポイントごとに v を取得する必要があるたびにハッシュをカウントする必要があるため、少し遅くなるはずです。

于 2013-10-07T20:59:21.130 に答える