匯合持久性的實際應用

我只是讀Brodal等人的Purely Functional Worst Case Constant Time Catenable Sorted Lists。他們介紹了數據結構的背景下，不同類型的持久性給我留下了一個明顯的問題：匯合持久性的實際應用

合流持久性：所有的版本都可以更新，查詢，此外，兩個版本可以組合產生一個新的版本。請注意，在這種情況下，可以通過反覆將其與本身連接在一起，以多項式形式創建指數規模的結構。

能夠通過反覆與自身連接創建「指數規模」結構的多項式時間的實際應用是什麼？

來源

2012-06-15 Jon Harrop

我沒有閱讀論文，但通過查看您提供的Confluent Persistence的定義，我可以將其與數據結構相關聯，如Binomial Heap，其中合併操作是對數運行時間，非常適合設置聯合類型算法。隨着樹木呈指數級增長並考慮二項堆，我們可能會有幾個，並且它們中的每一個都可以在多項式時間內合併。進行聯合操作將是我對這種數據結構以及多項式時間的最佳應用。

來源

2012-06-15 09:13:53 Yavar

我最初有一個類似的想法，但我不認爲set union可以引入共享，因爲它刪除了重複，即集合A與它自己的聯合不會比A大。 –

你的問題表明你閱讀這篇文章時說這個屬性是展現這種類型持久性的數據結構的一個優點。看這篇論文，我不認爲這就是作者所期望的 - 這只是這種數據結構的一些有點違反直覺的特性，他們想指出讀者的樂趣和樂趣。作爲進一步的說明，作者所談論的指數大小，我認爲是「數學」大小（抽象意義上的節點數），而不是內存中的大小 - 這是不可能的在多項式時間內訪問或寫入指數數量的內存位置！

來源

2012-06-15 20:20:21

下面是一個示例用例。設想一個通用的「序列」數據類型在數組期望稀疏的情況下（即，大多數元素將包含相同的值，相對較少的點設置爲某個其他值）使用的通用「序列」數據類型。如果序列數據類型具有此屬性，則可以使用您提到的技術構建（可能非常大）的數組，並且在此用法下它仍然具有合理的空間和時間效率。

當然，您可以爲稀疏數組創建一個特殊用途的數據類型，它可能會比通用數據類型多一點空間和時間效率，但重要的是通用數據類型會優雅地適應足以滿足這種使用模式，您甚至可能甚至不需要製作特殊用途數據類型。（不可否認，這個例子大體上是關於匯合持久性的，而不是關於論文的「排序列表」，然後再一次在論文中，他們提出了關於匯合持久性的一般問題的評論，並不是特別關注他們自己的數據結構）

來源

2012-06-16 12:02:18

匯合持久性的實際應用

回答

相關問題