F＃不可變大小的窗口數據結構

我有一個我需要的數據結構的描述，我想用不可變的數據結構來實現它。我試圖確定......是否有一個現有的數據結構支持我在這裏要做的或者我需要創建一個 - 如果我需要創建它，那麼什麼是好的開始的地方（積木）？F＃不可變大小的窗口數據結構

我有一個穩定的輸入值的某種類型的值。我想將它們添加到持久性/不可變數據結構中以保存它們的歷史記錄，並且在每次添加時，它都會檢查歷史記錄並確定是否會刪除一個或多個最舊的項目（例如，如果歷史記錄>某個長度或某個值有一定的屬性）。

2010-08-04 mentics

不知道更多關於您的要求，我只是說一個香草Set<'a>做的不是一份足夠的工作。我寧願在'列表'上設置'設置'，因此您始終可以使用O（LG）訪問最大和最小的項目，從而允許您通過插入日期/時間來訂購您的設置，以便有效訪問最新和最舊的項目。

似乎很容易包裹一組，以便其添加/刪除方法調用你的回調：

type AwesomeSet(internalSet : Set<'a>, insertCallback : 'a -> unit, removeCallback : 'a -> unit) = 
    member this.Add(x) = 
     insertCallback(x) 
     AwesomeSet(internalSet.Add x, insertCallback, removeCallback) 

    member this.Remove(x) = 
     removeCallback(x) 
     AwesomeSet(internalSet.Remove x, insertCallback, removeCallback) 

    member this.Count = internalSet.Count 
    member this.Min = internalSet.MinimumElement 
    member this.Max = internalSet.MaximumElement

來源

2010-08-04 17:28:09 Juliet

列表是單向鏈表，對吧？因此，尾部的訪問和刪除效率非常低，所以效果不佳。我沒有真正考慮過設置，因爲我認爲它是無序的（愚蠢的我）。但是一個有序的設置......對，這可能會完成這項工作。除了每一個新的東西都會被添加到頭部。如果它使用二叉樹，那意味着它最終會成爲一個雙向鏈表，並且對於我的用例來說效率很低，因爲刪除結束將涉及複製所有節點。 – mentics 2010-08-04 18:27:18

@taotree：內部實現'Set <'a>'是一個紅黑樹，所以它支持非常高效的O（lg n）用於隨機訪問，插入和刪除。由於樹是平衡的，它不會變成鏈表，並且不需要複製整個樹。 – Juliet 2010-08-04 18:44:34

好吧，我已經看到這個： http://msdn.microsoft.com/en-us/library/ee353619.aspx 它說二叉樹，我在想，呃哦... 但後來我看到這個的最底部： http://en.wikibooks.org/wiki/F_Sharp_Programming/Sets_and_Maps 正確...紅黑樹=性能善良。微軟應該在他們的文檔中更具體。謝謝！ – mentics 2010-08-04 18:53:37

由於朱麗葉的一種信息，我已經實現了我所需要的，我把它放在這裏的情況下，任何人否則可能會發現它有用。

let rec removeLast (s : Set<'a>, num : int) : Set<'a> = 
    match num with 
    | 0 -> s 
    | _ -> removeLast(s.Remove(s.MinimumElement), num-1) 


type History<'a when 'a : comparison>(underlying : Set<'a>, removal : History<'a> -> int) = 
    member this.Add(x) = 
     History(removeLast(underlying, removal(this)).Add x, removal) 

    member this.Count = underlying.Count 
    member this.Min = underlying.MinimumElement 
    member this.Max = underlying.MaximumElement 
    member this.Under = underlying 

let maxHist = 2 
let maxCountRemover (h : History<int>) = 
    if h.Count >= maxHist 
    then h.Count - maxHist + 1 
    else 0 


let testHistory = 
    let s = History(Set.empty, r) 
    let s = s.Add(1); 
    printfn "%i: %i - %i" s.Count s.Min s.Max 
    let s = s.Add(2); 
    printfn "%i: %i - %i" s.Count s.Min s.Max 
    let s = s.Add(3); 
    printfn "%i: %i - %i" s.Count s.Min s.Max 
    let s = s.Add(4); 
    printfn "%i: %i - %i" s.Count s.Min s.Max 
    let s = s.Add(5); 
    printfn "%i: %i - %i" s.Count s.Min s.Max 
    printfn "%A" s.Under

來源

2010-08-04 21:39:24 mentics

我推薦'printfn'％i％i's.Min s.Max'和'printfn'％A's.Under'代替'System.Console.WriteLine（...）':) – Juliet 2010-08-05 01:15:47

謝謝。我想知道打印格式的規範方法。我將修復該示例代碼。 – mentics 2010-08-05 20:17:10

F＃不可變大小的窗口數據結構

回答

相關問題