帶有效插入/刪除的「列表」

我正在尋找一個帶有log（N）插入/刪除索引i的「List」。我把「List」這個單詞放在引號中，因爲我並不是指它是一個真正的Haskell List，而是任何有序的容器都有一堆對象（實際上，它可能需要某種內部的樹）。我很驚訝，我還沒有找到一個很好的解決方案呢......帶有效插入/刪除的「列表」

這是我迄今爲止最好的解決方案 - 使用Data.Sequence這兩個函數。

doInsert position value seq = before >< (value <| after) 
    where 
    (before, after) = splitAt position seq 

doDelete position seq = before >< (drop 1 after) 
    where 
    (before, after) = splitAt position seq

雖然這些在技術上是所有日誌（N）的功能，那感覺就像我做了一堆額外的東西每個插入/刪除....換句話說，這種秤像K *日誌（N ）對於比它應該大的K。另外，由於我必須自己定義這些東西，所以我覺得我正在使用Sequence來處理它沒有設計的東西。

有沒有更好的方法？

這是一個相關的問題（儘管它僅使用序列的交易，我會愉快地使用別的）：Why doesn't Data.Sequence have `insert' or `insertBy', and how do I efficiently implement them?

是的，這個問題是與此相關的另一個我發佈前幾天：Massive number of XML edits

來源

2013-12-18 jamshidh

爲什麼不是[:: Data.Map.Map Int a]（http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map-Lazy.html）？ –

@ WillNess-插入將不得不更新所有'我'的值大於插入點，所以我不認爲這個工程。 – jamshidh

這個IIRC的標準數據結構解決方案是一個樹，其中節點還在其左側包含元素數量。看看http://en.wikipedia.org/wiki/T-tree是否相關。 –

如果你仔細研究預定義的Haskell列表，他們應該沒有問題。（例如，連接兩個列表時）。

如果你想找到一個列表的實現，有效的插入和刪除，AVLTree或任何種類或平衡的二叉樹將工作。例如在AVLTree中存儲元組（Int，a），其中Int是列表的索引和elem。因此，在平均複雜度上，操作對於插入和刪除是對數的。

我希望這能回答你的問題。

來源

2014-01-21 13:03:02

有可以給你O（1）連接的結構，比如catenable seqs，catenable queues等。然而，我知道的所有這樣的結構通過給你O（i）分離來擺脫這種情況。如果你想分割並加入兩者以儘可能最優化，我認爲一個fingertree（又名Sequence）是你最好的選擇。 Sequence這種方式的整個結構是確保分裂，連接等在分裂和連接等方面具有漸近不太可怕的雜耍量。

如果可以逃脫的IntMap它開始稀疏，得到了更密集，並且是偶爾「重修」當事情變得過於密集，那麼可能給你更好的性能 - 但是這真的取決於你的使用模式。

來源

2015-02-20 05:43:50 sclv

帶有效插入/刪除的「列表」

回答

相關問題