F # Неизменяемая структура данных окна переменного размера - PullRequest
Новая
       29

F # Неизменяемая структура данных окна переменного размера

3 голосов
/ 04 августа 2010

Ниже приведено описание нужной мне структуры данных, и я хочу реализовать ее с использованием неизменяемых структур данных.Я пытаюсь определить ... существует ли существующая структура данных, которая будет поддерживать то, что я пытаюсь сделать здесь, или мне нужно ее создать - и если мне нужно ее создать, что было бы хорошоместо для начала (строительные блоки)?

У меня есть постоянный поток входящих значений определенного типа.Я хочу добавить их в постоянную / неизменную структуру данных для хранения истории их, и при каждом добавлении он будет просматривать историю и определять, будет ли удален один или несколько самых старых элементов (например, если историяопределенная длина или значение имеет определенное свойство).

Ответы [ 2 ]

3 голосов
/ 04 августа 2010

Не зная больше о ваших требованиях, я бы сказал, что ваниль Set<'a> делает более чем адекватную работу.Я бы предпочел «Set», а не «List», чтобы у вас всегда был O (lg n) доступ к самым большим и самым маленьким элементам, что позволяет вам упорядочить свой набор по дате / времени вставки для эффективного доступа к самым новым и самым старым элементам.

Кажется, что обернуть набор так легко, что его методы Add / Remove вызывают ваши обратные вызовы: 

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
1 голос
/ 05 августа 2010

Благодаря любезной информации Джульетты, я реализовал то, что мне нужно, и разместил ее здесь на случай, если кто-то еще может найти это полезным. 

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
...