F # hiệu quả loại bỏ các mục n từ ngày kết thúc của một Set

Question

Tôi biết tôi có thể loại bỏ các yếu tố cuối cùng từ một tập:

s.Remove(s.MaximumElement) 

Nhưng nếu tôi muốn loại bỏ các yếu tố n tối đa ... Tôi chỉ thực hiện trên n lần, hoặc là có một cách nhanh hơn để làm điều đó?

Để được rõ ràng, đây là một giải pháp rõ ràng:

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

Nhưng nó liên quan đến việc tạo ra một bộ mới n lần. Có cách nào để làm điều đó và chỉ tạo ra một bộ mới một lần?

Answer 1

Nhưng nó liên quan đến việc tạo bộ mới n lần. Có cách nào để làm điều đó và chỉ tạo một bộ mới một lần?

Theo hiểu biết tốt nhất của tôi, không. Tôi muốn nói những gì bạn có một thực hiện hoàn hảo tốt, nó chạy trong O (lg n) - và ngắn gọn của nó quá :) Hầu hết các triển khai heap cung cấp cho bạn O (lg n) để xóa min anyway, vì vậy những gì bạn có là về tốt như bạn có thể nhận được nó.

Bạn có thể có thể để có được một chút tốc độ tốt hơn bằng cách lăn cây cân bằng của bạn, và thực hiện một chức năng để thả một nhánh trái hoặc phải cho tất cả các giá trị lớn hơn một giá trị nhất định. Tôi không nghĩ rằng cây AVL hay cây RB thích hợp trong bối cảnh này, vì bạn không thể thực sự duy trì các bất biến của chúng, nhưng một cây ngẫu nhiên sẽ cho bạn những kết quả mà bạn muốn.

Một TREAP làm việc tuyệt vời cho điều này, bởi vì nó sử dụng ngẫu nhiên chứ không phải là bất biến cây để giữ cho bản thân tương đối cân bằng. Không giống như cây AVL hoặc cây RB, bạn có thể chia một phần nhỏ trên một nút mà không lo lắng về việc nó không cân bằng.Dưới đây là một việc thực hiện TREAP Tôi đã viết một vài tháng trước:

http://pastebin.com/j0aV3DJQ

Tôi đã thêm một chức năng split, mà sẽ cho phép bạn lấy một cây và trở về hai cây có chứa tất cả các giá trị ít hơn và tất cả các giá trị lớn hơn một giá trị đã cho. split chạy trong O (lg n) bằng cách sử dụng một lần đi qua cây, vì vậy bạn có thể tỉa toàn bộ cành cây của mình trong một lần chụp - miễn là bạn biết giá trị nào cần chia nhỏ.

Nhưng nếu tôi muốn loại bỏ n tối đa yếu tố ... để tôi chỉ thực hiện trên lần n, hoặc là có một cách nhanh hơn để làm điều đó?

Sử dụng lớp Treap tôi:

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 chạy trong thời gian O (n + lg m) thời gian, trong đó n là chỉ số vào dãy cây và m là số lượng các mục trong cây.

Tôi không đảm bảo về độ chính xác của mã của tôi, sử dụng theo nguy cơ của riêng bạn;)

Answer 2

Đó là một giải pháp khá tốt. OCaml có chức năng split có thể chia một Set để bạn có thể tìm thấy phần tử phù hợp, sau đó bạn có thể tách Set để xóa một loạt các phần tử cùng một lúc. Ngoài ra, bạn có thể sử dụng để trích xuất Set.difference khác Set của các yếu tố.

Answer 3

Trong F #, bạn có thể sử dụng Set.partition hoặc Set.filter để tạo ra bộ phụ:

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 

Trong câu hỏi của bạn, có thể bạn không biết giá trị của số thứ i của thiết lập của bạn, vì vậy đây là một tiện dụng chức năng cho rằng:

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

Bây giờ, chúng ta có thể viết hàm 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 

và thử nghiệm nó:

removeTopN 3 s 

và chúng tôi nhận được:

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

Chú ý rằng removeTopN không làm việc cho một tập chứa nhiều giá trị giống nhau.