3

これが明らかな質問のように思われる場合は申し訳ありません。

ダイクストラやプリムなどのグラフ アルゴリズムのプライオリティ キュー + 隣接リストを実装するために、リスト {実際には整数とリストのタプル (Integer, [(Integer, Integer)])} の Data.map を作成していました。

Data.map はバイナリ ツリーを使用して実装されているので (私はそれを読みました)、マップ操作を実行するときに (ローテーションになると思います)、インタープリターがリストの深いコピーを行わず、参照の浅いコピーを行うことを確認したいだけです。リストの右？

n = noの場合、O（nlogn + mlogn）時間で実行されるhaskellでプリムアルゴリズムを実装するためにこれを行っています。頂点とm =いいえ。純粋に機能的な方法で、リストが優先キューに格納されている場合、アルゴリズムはその時間内に機能します。私がオンラインで見つけたほとんどの haskell 実装は、この複雑さを達成していません。

前もって感謝します。

4

2 に答える 2

4

Map少なくとも GHC を使用している場合は、 new を作成するたびにリストがコピーされるわけではないことは正しいです (他の実装もおそらくこれを正しく行います)。これは、純粋関数型言語の利点の 1 つです。データを書き換えることができないため、命令型言語で発生する可能性のある問題を回避するためにデータ構造をコピーする必要がありません。Lisp のこのスニペットを考えてみましょう:

(setf a (list 1 2 3 4 5))
(setf b a)
; a and b are now both '(1 2 3 4 5).
(setf (cadr a) 0)
; a is now '(1 0 3 4 5).
; Careful though! a and b point to the same piece of memory,
; so b is now also '(1 0 3 4 5). This may or may not be what you expected.

Haskell では、このような変更可能な状態を持つ唯一の方法は、Stateモナド内の何かなど、明示的に変更可能なデータ構造を使用することです (そして、これは一種の偽物です (これは良いことです))。この潜在的に予期しないメモリ重複の問題は、Haskell では考えられません。なぜならa、それが特定のリストであると宣言すると、それは今も永遠にそのリストであるからです。絶対に変わらないことが保証されているので、等しいと思われるものにメモリを再利用しても危険はありません。実際、GHC はまさにこれを行います。したがって、Map同じ値で新しいを作成すると、値自体ではなく、値へのポインターのみがコピーされます。

詳細については、ボックス化されたタイプとボックス化されていないタイプの違いについてお読みください。

于 2013-09-15T12:58:43.413 に答える
0

1）Integerそれより遅いInt

2) 持っている場合[(Integer, [(Integer, Integer)])]

だけでなくData.Map、Map Integer [(Integer, Integer)]Map Integer (Map Integer Integer)

3)Intの代わりに使用Integerする場合は、少し高速なデータを使用できます - IntMapfrom Data.IntMap:IntMap (IntMap Int)

4) 各メソッドの複雑さは説明に書かれています: Data.IntMap.StrictとここではData.IntMap.Lazy :

map :: (a -> b) -> IntMap a -> IntMap b
O(n). Map a function over all values in the map.
于 2013-09-17T14:55:42.937 に答える