F # in modo efficiente la rimozione di n elementi dalla fine di un set

Question

so di poter rimuovere l'ultimo elemento da un insieme:

s.Remove(s.MaximumElement) 

Ma se voglio rimuovere gli elementi n massimo ... posso solo eseguire i tempi di cui sopra, o c'è un modo più veloce per farlo?

Per essere chiari, questa è una soluzione ovvia:

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

Ma si tratta di creazione di un nuovo set di n volte. C'è un modo per farlo e creare un nuovo set solo una volta?

Answer 1

Ma ciò comporta la creazione di un nuovo set n volte. C'è un modo per farlo e creare solo un nuovo set una volta?

Per quanto ne so, no. Direi che hai un'implementazione perfetta, funziona in O (lg n) - e anche la sua concisa :) La maggior parte delle implementazioni di heap ti danno comunque O (lg n) per eliminare min, quindi quello che hai è circa come bene come puoi ottenerlo

Potrebbe essere possibile ottenere una velocità leggermente migliore ruotando l'albero bilanciato e implementando una funzione per rilasciare un ramo sinistro o destro per tutti i valori superiori a un determinato valore. Non credo che un albero AVL o un albero RB siano appropriati in questo contesto, dal momento che non puoi davvero mantenere i loro invarianti, ma un albero randomizzato ti darà i risultati che desideri.

Un treap funziona davvero bene per questo, perché utilizza la casualizzazione piuttosto che gli invarianti di albero per mantenersi relativamente bilanciato. A differenza di un albero AVL o di un albero RB, è possibile dividere un treap su un nodo senza preoccuparsi di essere sbilanciato.Ecco un'implementazione Treap ho scritto qualche mese fa:

http://pastebin.com/j0aV3DJQ

Ho aggiunto una funzione split, che vi permette di prendere un albero e tornare due alberi che contengono tutti i valori inferiori e tutti i valori maggiori di un dato un valore. split viene eseguito in O (lg n) utilizzando un unico passaggio attraverso l'albero, in modo da poter potare interi rami del vostro albero in un colpo solo - purché si conosca il valore da dividere su.

Ma se voglio rimuovere il n massimo elementi ... posso solo eseguire il sopra n volte, o c'è un modo più veloce per farlo?

Utilizzando la mia classe Treap:

open Treap 

let nthLargest n t = Seq.nth n (Treap.toSeqBack t) 
let removeTopN n t = 
    let largest = nthLargest n t 
    let smallerValues, wasFound, largerValues = t.Split(largest) 
    smallerValues 

let e = Treap.empty(fun (x : int) (y : int) -> x.CompareTo(y)) 
let t = [1 .. 100] |> Seq.fold (fun (acc : Treap<_>) x -> acc.Insert(x)) e 
let t' = removeTopN 10 t 

removeTopN viene eseguito in tempo O (n + lg m), dove n è l'indice nella sequenza albero e m è il numero di elementi nella struttura.

non faccio garanzie circa l'accuratezza del mio codice, usare a vostro rischio e pericolo;)

Answer 2

Questa è già una buona soluzione. OCaml ha una funzione split che può dividere un Set in modo da poter trovare l'elemento giusto, quindi è possibile dividere lo Set per rimuovere un gruppo di elementi alla volta. In alternativa, è possibile utilizzare Set.difference per estrarre un altro Set di elementi.

Answer 3

in F #, è possibile utilizzare Set.partition o Set.filter per creare set di sub:

let s = Set([1;4;6;9;100;77]) 

let a, b = Set.partition (fun x -> x <= 10) s 

let smallThan10 = Set.filter (fun x -> x < 10) s 

Nella tua domanda, forse non si conosce il valore del numero esimo del set, ecco un pratico funzione per questo:

let nth (n:int) (s:'a Set) = 
    s |> Set.toSeq |> Seq.nth n 

Ora, possiamo scrivere la funzione di rimozione-top-n:

let removeTopN n (s:'a Set) = 
    let size = s.Count 
    let m = size - n 
    let mvalue = nth m s 
    Set.filter (fun x -> x < mvalue) s 

e provarlo:

removeTopN 3 s 

e otteniamo:

val it : Set<int> = set [1; 4; 6] 

Si noti che il removeTopN non funziona per un set contenente più stessi valori.