Tài liệu tham khảo số liệu và bộ nhớ cùng phân bổ

Question

Hãy xem xét các mô hình dữ liệu sau đây:

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

Bạn có thể thấy rằng Artist s được gọi từ cả Song s và Catalogue. Catalogue chứa danh sách tất cả các nghệ sĩ được đề cập đến từ Song s, vì vậy giá trị giống nhau của Artist được giới thiệu từ hai địa điểm.

Giả sử chúng tôi để tạo ra giá trị Catalogue sử dụng nhiều ứng dụng của hàm sau:

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

Đó là điều hiển nhiên rằng Catalogue sẽ được lấp đầy bởi các tham chiếu tới cùng một giá trị của Artist như Song s tham khảo, do đó tiết kiệm bộ nhớ bằng cách không lưu trữ các bản sao của các giá trị đó.

Vấn đề là khi tôi cố gắng tạo lại danh mục từ dữ liệu được tuần tự hóa bằng cách tách riêng một tập hợp các nghệ sĩ và một bộ bài hát, ứng dụng chiếm nhiều bộ nhớ hơn khi nó tạo cùng một giá trị Catalogue với insertSong. Tôi nghi ngờ rằng nó được gây ra bởi mối quan hệ bị mất giữa cùng một Artist s được gọi từ Song s và Catalogue, đó là lý do tại sao tôi nhận được bản sao của các giá trị Artist chiếm thêm bộ nhớ.

Giải pháp duy nhất tôi thấy là trước tiên deserialize bộ nghệ sĩ và sau đó để deserialize tập hợp các bài hát trong khi mạnh mẽ thay thế các giá trị của Artist với những người từ tập đầu tiên.

Vì vậy, câu hỏi của tôi là:

1. Am Tôi có ngay trong sự nghi ngờ của tôi?
2. Giải pháp tôi thấy có hoạt động không?
3. Có cách nào tốt hơn để giải quyết vấn đề này không?

Answer 1

Tôi đã vô tình vấp vào một dự án, trong đó phương pháp tiếp cận vấn đề này. Xem RefSerialize.

Answer 2

1. Điều đó nghe có vẻ hợp lý.
2. Nó sẽ hoạt động nếu được thực hiện đúng. Đặc biệt, bạn phải đảm bảo rằng tất cả mọi thứ được háo hức đánh giá, để tránh tham chiếu các giá trị văn bản cũ từ các khối.
3. Bạn có thể chọn định dạng tuần tự hóa thông minh hơn. Ví dụ: khi bạn sắp xếp các bài hát, hãy lưu trữ chỉ mục của nghệ sĩ trong danh sách nghệ sĩ thay vì tên nghệ sĩ đầy đủ. Sau đó, tìm kiếm nó trong quá trình deserialization.

Lưu ý rằng việc chia sẻ cũng sẽ bị mất nếu bạn làm bất kỳ loại tính toán trên dây của bạn (ví dụ: ngay cả khi artist1 và artist2 đều giống nhau và chia sẻ, f artist1 và f artist2 có lẽ không). Nếu điều này trở thành vấn đề, bạn cũng có thể thực hiện các thay đổi tương tự đối với cấu trúc dữ liệu của mình.

Answer 3

Một giải pháp đơn giản dường như bộ nhớ cache dữ liệu sử dụng bản đồ hơi bị thoái hóa:

{-# 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 

Sau đó chúng ta có thể truy vấn bộ nhớ cache này nếu có đã là một mục bằng thế này, và thay thế bằng các lưu trữ một:

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) 

Bằng cách này, nếu chúng tôi tải nhiều phần tử bằng loại a, chúng tôi chuyển đổi chúng thành một đĩa đơn. Điều này có thể được thực hiện trong quá trình deserialization hoặc một lần vào cuối.

---

Có lẽ nó sẽ có thể để khái quát nó xa hơn và sử dụng SYB để lập bản đồ tất cả các giá trị của một số loại nhất định trong một cấu trúc dữ liệu thông qua một bộ nhớ cache:

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) 

Sau đó, chúng ta có thể thay thế tất cả các nghệ sĩ trong một số cấu trúc dữ liệu như

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

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

Hoặc chúng ta có thể sử dụng Proxy loại phantom để tạo ra một phiên bản chung:

01.

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) 

(Disclaimer:. Tôi đã không kiểm tra bất kỳ mã ở trên)