Kết quả bộ nhớ đệm Haskell của hàm

Question

Tôi có một hàm lấy tham số và tạo kết quả. Thật không may, phải mất khá nhiều thời gian để hàm tạo ra kết quả. Hàm này được gọi khá thường xuyên với cùng một đầu vào, đó là lý do tại sao nó sẽ thuận tiện nếu tôi có thể lưu trữ kết quả. Một cái gì đó như

let cachedFunction = createCache slowFunction 
in (cachedFunction 3.1) + (cachedFunction 4.2) + (cachedFunction 3.1) 

Tôi đã xem xét Data.Array và mặc dù mảng là lười, tôi cần phải khởi tạo nó với một danh sách các cặp (sử dụng listArray) - đó là không thực tế. Nếu 'khóa' là ví dụ: kiểu 'Double', tôi không thể khởi tạo nó, và thậm chí nếu tôi có thể gán một Integer cho mọi đầu vào có thể, tôi có vài chục nghìn đầu vào có thể và tôi chỉ sử dụng một số ít. Tôi sẽ cần phải khởi tạo các mảng (hoặc, tốt nhất là một bảng băm, như là chỉ một số ít các resutls sẽ được sử dụng) bằng cách sử dụng một chức năng thay vì một danh sách.

Cập nhật: Tôi đang đọc các bài viết ghi nhớ và theo như tôi hiểu thì MemoTrie có thể hoạt động theo cách tôi muốn. Có lẽ. Ai đó có thể thử tạo ra 'cachedFunction'? Ưu tiên cho một hàm chậm có 2 đối số đôi? Hoặc, cách khác, phải mất một đối số Int trong một miền của ~ [0,1 tỷ] mà sẽ không ăn tất cả bộ nhớ?

Answer 1

Vâng, có Data.HashTable. Các bảng băm không có xu hướng chơi độc đáo với dữ liệu bất biến và tính minh bạch tham chiếu, vì vậy tôi không nghĩ rằng nó thấy rất nhiều sử dụng.

Đối với một số lượng nhỏ giá trị, việc đánh dấu chúng trong một cây tìm kiếm (chẳng hạn như Data.Map) có thể sẽ đủ nhanh. Nếu bạn có thể tạo ra một số xoài của Double s, một giải pháp mạnh mẽ hơn sẽ là sử dụng cấu trúc giống như trie, chẳng hạn như Data.IntMap; chúng có thời gian tra cứu tỷ lệ chủ yếu với chiều dài khóa và gần như không đổi trong kích thước bộ sưu tập. Nếu Int quá hạn chế, bạn có thể tìm hiểu về Hackage để tìm thư viện trie linh hoạt hơn trong loại khóa được sử dụng.

Để biết cách lưu vào bộ nhớ cache kết quả, tôi nghĩ những gì bạn muốn thường được gọi là "memoization". Nếu bạn muốn tính toán và ghi nhớ kết quả theo yêu cầu, ý chính của kỹ thuật là xác định cấu trúc dữ liệu được lập chỉ mục có chứa tất cả các kết quả có thể là, theo cách bạn yêu cầu một kết quả cụ thể. câu trả lời bạn muốn. Các ví dụ phổ biến thường liên quan đến việc lập chỉ mục vào một danh sách, nhưng cùng một nguyên tắc nên áp dụng cho bất kỳ cấu trúc dữ liệu không nghiêm ngặt nào. Theo quy tắc chung, các giá trị không hoạt động (bao gồm các cấu trúc dữ liệu đệ quy vô hạn) sẽ thường được lưu vào bộ nhớ cache theo thời gian chạy, nhưng không phải là kết quả hàm, do đó, mẹo là bao bọc tất cả các tính toán của bạn bên trong định nghĩa cấp cao nhất phụ thuộc vào bất kỳ đối số nào.

Chỉnh sửa: Ví dụ về MemoTrie ahoy!

Đây là bằng chứng khái niệm nhanh và bẩn; cách tiếp cận tốt hơn có thể tồn tại.

{-# LANGUAGE TypeFamilies #-} 
{-# LANGUAGE TypeOperators #-} 
import Data.MemoTrie 
import Data.Binary 
import Data.ByteString.Lazy hiding (map) 

mangle :: Double -> [Int] 
mangle = map fromIntegral . unpack . encode 

unmangle :: [Int] -> Double 
unmangle = decode . pack . map fromIntegral 

instance HasTrie Double where 
    data Double :->: a = DoubleTrie ([Int] :->: a) 
    trie f = DoubleTrie $ trie $ f . unmangle 
    untrie (DoubleTrie t) = untrie t . mangle 

slow x 
    | x < 1 = 1 
    | otherwise = slow (x/2) + slow (x/3) 

memoSlow :: Double -> Integer 
memoSlow = memo slow 

Lưu ý các phần mở rộng GHC được sử dụng bởi gói MemoTrie; hy vọng đó không phải là một vấn đề. Tải nó lên trong GHCi và thử gọi slow so với memoSlow bằng thứ gì đó như (10^6) hoặc (10^7) để xem nó hoạt động.

Việc tổng hợp việc này thành các hàm lấy nhiều đối số hoặc không nên đơn giản. Để biết thêm chi tiết về cách sử dụng MemoTrie, bạn có thể tìm thấy this blog post by its author hữu ích.

Answer 2

Xem memoization

Answer 3

Tôi không biết haskell cụ thể, nhưng làm thế nào về việc giữ câu trả lời hiện có trong một số cơ sở hạ tầng băm (có thể được gọi là từ điển, hoặc hashmap)? Bạn có thể bọc chức năng chậm của bạn trong một chức năng khác mà trước tiên hãy kiểm tra bản đồ và chỉ gọi hàm chậm nếu nó không tìm thấy câu trả lời.

Bạn có thể làm cho nó trở nên lạ mắt bằng cách giới hạn kích thước của bản đồ với một kích thước nhất định và khi nó đạt đến điều đó, hãy ném ra mục nhập ít được sử dụng gần đây nhất. Đối với điều này, bạn cũng cần phải giữ một bản đồ của ánh xạ key-to-timestamp.

Answer 4

Bạn có thể viết hàm chậm làm hàm bậc cao hơn, trả về một hàm. Do đó bạn có thể thực hiện tất cả tiền xử lý bên trong hàm chậm và phần khác nhau trong mỗi phép tính trong hàm trả về (hy vọng nhanh). Một ví dụ có thể trông như thế này: (mã SML, nhưng ý tưởng phải rõ ràng)

fun computeComplicatedThing (x:float) (y:float) = (* ... some very complicated computation *) 
fun computeComplicatedThingFast = computeComplicatedThing 3.14 (* provide x, do computation that needs only x *) 
val result1 = computeComplicatedThingFast 2.71 (* provide y, do computation that needs x and y *) 
val result2 = computeComplicatedThingFast 2.81 
val result3 = computeComplicatedThingFast 2.91 

Answer 5

Tôi có vài chục ngàn đầu vào có thể và tôi chỉ thực sự sử dụng một số ít. Tôi sẽ cần phải khởi tạo mảng ... bằng cách sử dụng một hàm thay vì một danh sách.

Tôi muốn đi với listArray (start, end) (map func [start..end])

• func không thực sự được gọi trên. Haskell là lười biếng và tạo ra các khối sẽ được đánh giá khi giá trị thực sự được yêu cầu.
• Khi sử dụng mảng thông thường, bạn luôn cần phải khởi tạo giá trị của nó. Vì vậy, công việc cần thiết để tạo ra những khối này là cần thiết dù sao đi nữa.
• Hàng chục nghìn cách xa rất nhiều. Nếu bạn có hàng nghìn tỷ thì tôi khuyên bạn nên sử dụng bảng băm yada yada

Answer 6

Tôi sẽ thêm giải pháp của riêng mình, điều này có vẻ khá chậm. Tham số đầu tiên là một hàm trả về Int32 - là định danh duy nhất của tham số. Nếu bạn muốn xác định duy nhất nó bằng các phương tiện khác nhau (ví dụ: bằng 'id'), bạn phải thay đổi tham số thứ hai trong H.new thành hàm băm khác. Tôi sẽ cố gắng tìm hiểu cách sử dụng Data.Map và kiểm tra xem tôi có nhận được kết quả nhanh hơn không.

import qualified Data.HashTable as H 
import Data.Int 
import System.IO.Unsafe 

cache :: (a -> Int32) -> (a -> b) -> (a -> b) 
cache ident f = unsafePerformIO $ createfunc 
    where 
     createfunc = do 
      storage <- H.new (==) id 
      return (doit storage) 

     doit storage = unsafePerformIO . comp 
      where 
       comp x = do 
        look <- H.lookup storage (ident x) 

        case look of 
         Just res -> return res 
         Nothing -> do 
          result <- return (f x) 
          H.insert storage (ident x) result 
          return result 

Answer 7

Có một số công cụ trong hệ thống thời gian chạy của GHC một cách rõ ràng để hỗ trợ ghi nhớ.

Thật không may, ghi nhớ không thực sự là một kích thước phù hợp với mọi chuyện, vì vậy có một số cách tiếp cận khác nhau mà chúng tôi cần hỗ trợ để đối phó với các nhu cầu khác nhau của người dùng.

Bạn có thể tìm thấy năm 1999 writeup gốc hữu ích vì nó bao gồm một số triển khai như ví dụ:

Stretching the Storage Manager: Weak Pointers and Stable Names in Haskell bởi Simon Peyton Jones, Simon Marlow, và Conal Elliott