4

私のアプリケーションには大量の配列操作 (log(1)インデックス作成など) が含まれているため、 Data.VectorとData.Vector.UnboxedがData.Listよりも優先されます。また、Data.Vector によって提供されない多くのセット操作 (intersectBy など) も含まれます。

これらの各関数は、Data.List のように 3 ～ 4 行で実装できます。それらがすべて Data.Vector で実装されていない理由はありますか? 推測することしかできません。パフォーマンス上の理由から、Data.Vector での集合演算は推奨されないかもしれません。つまり、intersectBy は最初にリスト内包表記を介して共通部分を生成し、次にリストを Data.Vector に変換しますか?

4

1 に答える 1

7

ソートされていない不変の配列の交差には、Ω(n*m)追加のスペースを使用せずに最悪の場合の実行時間が必要でありData.Vector、パフォーマンスが最適化されているため、欠落していると思います。ただし、必要に応じて、その関数を自分で作成できます。

import Data.Vector as V

intersect :: Eq a => V.Vector a -> V.Vector a -> V.Vector a
intersect x = V.filter (`V.elem` x)

または、一時的なセットのデータ構造を使用して、予想されるO(n + m)複雑さを実現します。

import Data.HashSet as HS

intersect :: (Hashable a, Eq a) => V.Vector a -> V.Vector a -> V.Vector a
intersect x = V.filter (`HS.member` set)
    where set = HS.fromList $ V.toList x

追加のメモリ使用量に余裕がある場合は、データにある種の集計タイプを使用できます。たとえば、高速ランダム アクセス用の配列や、Data.HashSet高速メンバーシップ チェック用のハッシュ トライなど、両方のコンテナーを常に最新の状態に保つことができます。そうすれば、交差点の漸近的な複雑さを次のように減らすことができますO(min(n, m))

于 2013-03-29T19:05:18.243 に答える