F # eliminar eficazmente n elementos a partir del final de un Conjunto

Question

Sé que puedo eliminar el último elemento de un conjunto:

s.Remove(s.MaximumElement) 

Pero si quiero eliminar los elementos n máximas ... No acabo de ejecutar las n veces anteriores, o hay una forma más rápida de hacerlo?

Para que quede claro, esto es una solución obvia:

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

Pero implica la creación de una nueva serie n veces. ¿Hay alguna manera de hacerlo y solo crear un nuevo conjunto una vez?

Answer 1

Pero se trata de crear un nuevo conjunto n veces. ¿Hay alguna manera de hacerlo y solo crear un nuevo conjunto una vez?

Según mi leal saber y entender, no. Diría que tiene una implementación perfectamente correcta, se ejecuta en O (lg n) y también es concisa :) La mayoría de las implementaciones de montón le dan O (lg n) para eliminar min de todos modos, entonces lo que tiene se trata de tan bueno como puedas conseguirlo.

Es posible que pueda obtener un poco mejor velocidad rodando su árbol equilibrado, y la implementación de una función para colocar una rama izquierda o derecha para todos los valores superiores a un cierto valor. No creo que un árbol AVL o RB sea apropiado en este contexto, ya que no puedes mantener sus invariantes, pero un árbol con asignación aleatoria te dará los resultados que deseas.

Una corrección funciona de maravilla para esto, porque usa aleatorización en lugar de invariantes de árbol para mantenerse relativamente equilibrado. A diferencia de un árbol AVL o un árbol RB, puede dividir un ataque en un nodo sin preocuparse de que esté desequilibrado.He aquí una aplicación Treap que escribí hace unos meses:

http://pastebin.com/j0aV3DJQ

He añadido una función split, lo que le permite tener un árbol y devolver dos árboles que contienen todos los valores menores y todos los valores mayor que una valor dado split se ejecuta en O (lg n) utilizando un solo pase a través del árbol, por lo que puede podar ramas enteras de su árbol de una sola vez, siempre que sepa en qué valor se divide.

Pero si quiero quitar el máximo n elementos ... puedo sólo hay que ejecutar el por encima de n veces, o hay una manera más rápida de hacer eso?

Usando mi clase 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 carreras en tiempo O (n + lg m), donde n es el índice en la secuencia de árbol y m es el número de elementos en el árbol.

que no ofrecen ninguna garantía sobre la exactitud de mi código, utilice a su propio riesgo;)

Answer 2

Eso ya es una solución bastante buena. OCaml tiene una función split que puede dividir un Set para que pueda encontrar el elemento correcto y luego puede dividir el Set para eliminar un grupo de elementos a la vez. Alternativamente, puede usar Set.difference para extraer otro Set de elementos.

Answer 3

En F #, puede utilizar Set.partition o Set.filter para crear subconjuntos:

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 

En su pregunta, tal vez usted no sabe el valor del número i de su conjunto, por lo que aquí es un práctico función para la que:

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

Ahora, podemos escribir la función Remove-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 

y probarlo:

removeTopN 3 s 

y obtenemos:

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

en cuenta que la removeTopN no funciona para un conjunto que contiene múltiples mismos valores.