7

次のデータ モデルを検討してください。

data Artist = Artist Text
data Song = Song Artist Text
data Catalogue = Catalogue (Set Artist) (Set Song)

が とのArtist両方から参照されていることがわかります。には から参照されたすべてのアーティストのリストが含まれているため、 の同じ値が2 つの場所から参照されます。SongCatalogueCatalogueSongArtist

Catalogue次の関数の複数のアプリケーションを使用して値を生成するとします。

insertSong :: Song -> Catalogue -> Catalogue
insertSong song@(Song artist title) (Catalogue artists songs) =
  Catalogue (Set.insert artist artists) (Set.insert song songs)

s が参照するのと同じCatalogue値への参照によって が満たされることは明らかです。したがって、これらの値のコピーを保存しないことでメモリを節約できます。ArtistSong

問題は、一連のアーティストと一連の曲を個別に逆シリアル化して、シリアル化されたデータからカタログを再作成しようとすると、アプリケーションがCataloguewithの同じ値を生成したときよりも多くのメモリを占有することinsertSongです。sArtistと から参照される同じ s の間の関係が失われたことが原因であると思われます。これが、余分なメモリを占有している値のコピーを取得する理由です。SongCatalogueArtist

私が見る唯一の解決策は、最初にアーティストのセットを逆シリアル化し、次に曲のセットを逆シリアル化し、値をArtist最初のセットの値に強制的に置き換えることです。

だから私の質問は：

  1. 私の疑いは正しいですか？
  2. 私が見た解決策は機能しますか?
  3. これを解決するより良い方法はありますか？
4

3 に答える 3

6
  1. それはもっともらしいですね。
  2. 正しく行えばうまくいくはずです。特に、サンクから古い Text 値を参照しないように、すべてが積極的に評価されるようにする必要があります。
  3. よりスマートなシリアル化形式を選択できます。たとえば、曲をシリアル化するときは、完全なアーティスト名ではなく、アーティストのインデックスをアーティスト リストに保存します。次に、逆シリアル化中に調べます。

文字列に対して何らかの計算を行うと、共有も失われることに注意してください (つまり、artist1とartist2が同じで共有されていて、f artist1おそらくf artist2共有されていない場合でも)。これが問題になる場合は、データ構造にも同様の変更を加えることができます。

于 2013-07-14T22:07:59.603 に答える
3

簡単な解決策は、やや縮退されたマップを使用してデータをキャッシュするようです。

{-# LANGUAGE DeriveDataTypeable, RankNTypes #-}
import Control.Monad
import Control.Monad.State
import Data.Map (Map)
import qualified Data.Map as M

type Cache a = Map a a

次に、このキャッシュに等しいエントリが既に存在する場合は、このキャッシュをクエリし、キャッシュされたものに置き換えることができます。

cached :: (Ord a) => a -> State (Cache a) a
cached x = state $ \m ->
    case M.lookup x m of
        Just x'     -> (x', m)
        Nothing     -> (x, M.insert x x m)

このように、 type の等しい要素をいくつかロードするとa、それらを単一に変換します。これは、逆シリアル化中または最後に 1 回実行できます。

おそらく、それをさらに一般化し、SYB を使用して、キャッシュを介してデータ構造内の特定の型のすべての値をマップすることが可能になるでしょう。

import Data.Data (Data)
import Data.Generics.Aliases (mkM)
import Data.Generics.Schemes (everywhereM)
import Data.Typeable (Typeable)

replaceFromCache
    :: (Ord a, Typeable a, Data b)
    => b -> State (Cache a) b
replaceFromCache = everywhereM (mkM cached)

次に、次のようなデータ構造のすべてのアーティストを置き換えることができます

data Artist = Artist String
  deriving (Eq, Ord, Typeable)

cacheAllArtists :: (Data b) => b -> b
cacheAllArtists b = evalState (replaceFromCache b) (M.empty :: Cache Artist)

または、Proxyファントム タイプを使用して一般的なバージョンを作成することもできます。

cacheAll :: (Ord a, Typeable a, Data b)
      => Proxy a -> b -> b
cacheAll p = flip evalState (emptyOf p) . replaceFromCache
  where
    emptyOf p = asTypeOf2 M.empty p
    asTypeOf2 :: f a -> Proxy a -> f a
    asTypeOf2 = const

cacheAllArtists :: (Data b) => b -> b
cacheAllArtists = cacheAll (Proxy :: Proxy Artist)

(免責事項: 上記のコードはテストしていません。)

于 2013-07-15T00:59:13.583 に答える