1

プロジェクト内のマトリックスをリストのリストで表します[[a]]

  • これは良い考えですか、それとも配列を使用する方がよいでしょうか？

  • インデックス（i、j）を使用して要素をその場で変更するにはどうすればよいですか？

4

3 に答える 3

9

もちろん、リストベースのソリューションは、キャッシュの局所性の問題をすべて伴う必要な間接化のために、最適化されたタイトな配列ほど高速になることはありません。ただし、これは一定のオーバーヘッド要因にすぎません（ただし、おそらくかなり大きいですが、100程度です）。

ただし、興味深いことに、行列へのネストされたリストのアプローチは、見た目ほど悪くはありません。リストは、従来の純粋関数型の方法で最も自然に処理されるデータ構造のままです。ミリムースが言ったように、純粋な方法で要素をインプレースで変更することはできません。1つの要素を変更して全体のコピーを作成する必要があります*。n✕n個の密配列行列の場合、これはO（n 2 ）です。nが大きい場合はほとんど受け入れられません。

長さmのリストでのランダムアクセスはすでにO（m）であるため、配列の場合よりもはるかに悪くなりますが、より複雑な操作の場合はさらに悪くなることはありません。O（m ）でリストを「変更」したり、 O（n ）でn✕nのネストされたリストにアクセスしたり、O（n）でリストを変更したりできます。したがって、大きな行列に対して非破壊更新を実行する場合は、実際には。よりも高速です。[[a]]Array a i

ああ、これがどのように機能するか–ええと、

type Matrix a = [[a]]
updateMatrixAt :: (Int,Int) -> (a->a) -> Matrix a -> Matrix a
updateMatrixAt(i,j) f mat
 | (upperRows, thisRow : lowerRows ) <- splitAt i mat
 , (leftCells, thisCell: rightCells) <- splitAt j thisRow
         =                  upperRows
          ++ (leftCells ++ (f thisCell): rightCells)
                          : lowerRows
 | otherwise = error "Tried to index matrix outside range"

トリックを行います。

*これを回避する試みがありましたが、これは行き止まりであることが証明されたと思います。本当に高いパフォーマンスが必要な場合は、STモナドで破壊的な更新を使用する必要があります。それほど良くはないかもしれませんが、問題はありません。

于 2012-11-23T12:27:39.357 に答える
5

独自のデータ型をラッピングして使用するのはどうMap (Int,Int) aですか？要素の変更は簡単で、特にスパース行列の場合は多くのメモリを節約できます。

于 2012-11-23T15:09:25.520 に答える
0

インデックス（i、j）を使用して要素をその場で変更するにはどうすればよいですか？

一般的に言えば、できません。1つの要素を変更して新しいマトリックスを作成する必要があります。（リストの代わりに使用すると、演算子Arrayを使用するとこれが少し簡単になります。）インプレース変更を行うために使用できるようですが、ほとんどすべてのコードでを使用する必要があります。//MArrayIO

于 2012-11-23T11:51:08.037 に答える