Haskell可變堆結構

我想使我的堆數據結構。另外我想在STM多單元應用程序中使用它進行操作。該堆具有1000萬個元素的大小。堆上有很多操作。Haskell可變堆結構

我已經看過這個包

由於我的意思是他們兩個是持久性的。如果我們修改這個數據結構，我們得到兩個版本。對於大尺寸的堆是無效的內存。

正如我想我需要實現可變堆。

我想聽聽您的意見和建議，以得到我想要的。

謝謝。

2011-06-03 Anton

正如Ankur指出的那樣，你可能超出了Haskell的純功能方面的範圍，至少我從來沒有見過具有良好內存性能的純粹的抽取 - 最小數據結構 - 不要認爲沒有一個。你有沒有分析現有的庫以確保它們不足以滿足你的需求？（請記住，持久數據結構是否不是意味着整個數據結構都會被複制，只要發生突變，就可以有lo在不同的「版本」之間共享的版本號）。

但是，Haskell也有一個必要的一面，你可以在那邊實現一個堆。命令式Haskell的性能特徵與任何其他命令式語言的性能特徵相近，因此您可能希望將堆放在某種類型的可變數組之外。

以與STM的核心概念是TVar很好地合作的方式實現它可能會很棘手。你可以基於它的一個（甚至是不可變的）數組，但是由於每一個操作都觸及堆的根部，所以會有很多爭用，而STM的開銷會傷害你。我更傾向於使用鎖/ MVars一次將對堆的訪問序列化到一個線程。

我知道Data.Vector.Mutable是一個流行的可變數組庫。其他人會比我更瞭解如何爲你的目的推薦一個好的可變數組庫。

來源

2011-06-03 05:57:19 luqui

謝謝。對我來說還不清楚。爲什麼STM在我的情況下更接近於MVar。我將STM看作標準併發鎖定的高級抽象。你能否解釋或獲得解釋它爲什麼的鏈接？ – Anton 2011-06-03 07:27:37

這是標準的haskell STM論文：http：//research.microsoft.com/en-us/um/people/simonpj/papers/stm/stm.pdf。 STM不檢查鎖定：相反，它會臨時運行代碼，並且在事務結束之前，它會查看是否有人更改了任何可能導致事務執行不同的數據。如果不是，它將變量提交給共享內存;如果是這樣，它會中止並再次嘗試交易。因爲所有堆事務都會改變根，如果兩個同時發生，它們中的一個*必須*重試。因此，性能可能不如鎖（更糟糕的情況下） – luqui 2011-06-03 08:09:57

如果您的交易修改TVars *稀疏*，STM是一個不錯的選擇;即同時進行的交易不可能依賴於相同的變量。 – luqui 2011-06-03 08:13:40

當你開始根據「可變內存區域」和「修改該內存區域的操作」思考問題時，你會走出像Haskell這樣的Pure FP語言的界限，並且超出這個界限的東西將會需要像Monads這樣的Haskell中的一些特殊技術。在你的Mutable數據結構的情況下，你跨越了基本的邊界，我不確定是否Monad可以幫助你跨越（Monad可以幫助你將它模擬爲可變數據結構ex：state monad - 但那不會是你正在尋找什麼，因爲你希望它是「可變的」，而不僅僅是一個模擬

來源

2011-06-03 05:41:09 Ankur

Monads與可變性無關。它們只是一種通常用於安全訪問可變數據的API慣用語（等等）。允許實際可變性的基本操作由運行時系統提供，否則沒有什麼特別的。 – 2011-06-03 17:06:39

Haskell可變堆結構

回答

相關問題