OCaml中

多參數功能弱memoizing結果我正在尋找一種方式來memoize的一個OCaml的功能f採用兩個參數（或更多，在一般情況）的結果。另外（這是困難的部分），如果兩個參數的任何一個值都是垃圾收集的，我希望這個過程的映射完全忘記一個結果。OCaml中

對於只需要一個參數的函數，可以通過Weak模塊及其Make函子以簡單明瞭的方式完成。爲了將其推廣到可以記憶更高級別函數的東西，一個天真的解決方案是創建一個從值元組到結果值的弱映射。但是這對於垃圾收集來說不能正確工作，因爲值的元組只存在於memoization函數的範圍內，而不是調用f的客戶端代碼。實際上，弱引用將是元組，它將在記憶後立即被垃圾收集（在最壞的情況下）。

有沒有辦法做到這一點，而不需要重新實施Weak.Make？

Hash-consing與我的要求是正交的，事實上，對於我的價值觀來說並不是真正需要的。

謝謝！

來源

2012-04-07 Nikos

而非索引的你可以有一個樹狀結構。您將有一個由第一個函數參數索引的弱表，它的條目是次級弱表。輔助表格將由第二個函數參數索引幷包含記憶結果。只要函數參數爲GCed，該結構就會忘記記憶功能結果。但是，只要第一個函數參數處於活動狀態，輔助表格本身就會保留。根據你的函數結果的大小和不同的第一個參數的分佈，這可能是一個合理的折衷。

我還沒有測試過這個。這似乎也很明顯。

來源

2012-04-07 22:19:59

我可以看到第一個參數值的垃圾回收會如何導致釋放第二個參數的相應表。然而，即使結果圖爲空，對錶中的第二個參數進行GC化也不會對其父（如果使用「Weak」模塊）執行任何操作。當然，這可以通過主動掃描地圖的內容並刪除映射到空表的第一個參數鍵來完成。 – Nikos 2012-04-08 08:20:28

正如我所說的，直到第一個參數被釋放後，輔助表纔會被收集。但是回憶價值會被收集（在我看來）。 – 2012-04-08 14:58:06

一個想法是執行你自己的垃圾收集。

爲簡單起見，我們假設所有的參數都相同類型k。

除了含有由k * k鍵入的memoized結果的主要弱表，創建包含k類型的單個參數的次級弱表。這個想法是一次掃描主表，並刪除不再需要的綁定。這是通過查找次表中的參數完成的;那麼如果它們中的任何一個都不存在，則從主表中刪除綁定。

（聲明：我沒有測試過這一點;它可能無法正常工作或有可能是更好的解決方案）的元組

來源

2012-04-07 17:00:00

好點。也許只需要一個表，其中一個具有弱引用的元組作爲關鍵字，並且每當關鍵元組中的任何弱引用消失時都會收集自定義垃圾。這可以通過終結者來完成嗎？ – Nikos 2012-04-07 17:09:25

我知道這是一個老問題，但我的同事們最近開發的增量計算庫，稱爲Adapton，可以處理這個功能。你可以找到代碼here。您可能想要使用LazySABidi仿函數（其他用於基準測試）。您可以在Applications文件夾中查找如何使用庫的示例。如果您還有其他問題，請告訴我。

來源

2013-12-16 00:42:48

回答

相關問題