F # Эффективное удаление n предметов из конца набора - PullRequest
Новая
       31

F # Эффективное удаление n предметов из конца набора

5 голосов
/ 05 августа 2010

Я знаю, что могу удалить последний элемент из набора: 

s.Remove(s.MaximumElement)

Но если я хочу удалить максимум n элементов ... я могу просто выполнить вышеупомянутые n раз или естьболее быстрый способ сделать это?

Для ясности, это очевидное решение: 

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

Но это включает в себя создание нового набора n раз.Есть ли способ сделать это и создать новый набор только один раз?

Ответы [ 3 ]

1 голос
/ 06 августа 2010

Но это включает создание нового набора n раз. Есть ли способ сделать это и создать новый набор только один раз?

Насколько мне известно, нет. Я бы сказал, что у вас есть отличная реализация, она работает в O (LG N) - и это тоже сжато :) Большинство реализаций кучи в любом случае дают O (LG N) для удаления min, так что у вас есть примерно хорошо, как вы можете это получить.

Возможно, вам удастся получить немного лучшую скорость, развернув сбалансированное дерево и внедрив функцию отбрасывания левой или правой ветви для всех значений, превышающих определенное значение. Я не думаю, что дерево AVL или дерево RB подходят в этом контексте, так как вы не можете реально поддерживать их инварианты, но случайное дерево даст вам желаемые результаты.

Трэп работает потрясающе для этого, потому что он использует рандомизацию, а не древовидные инварианты, чтобы сохранять себя относительно сбалансированным. В отличие от дерева AVL или дерева RB, вы можете разделить трэп на узле, не беспокоясь о его несбалансированности. Вот реализация трэпа, которую я написал несколько месяцев назад:

http://pastebin.com/j0aV3DJQ

Я добавил функцию split, которая позволит вам взять дерево и вернуть два дерева, содержащие все значения, меньшие чем, и все значения, превышающие данное значение. split работает в O (LG N), используя один проход через дерево, так что вы можете обрезать все ветви вашего дерева за один выстрел - при условии, что вы знаете, на какое значение делить.

Но если я хочу убрать п максимум элементы ... я просто выполнить выше п раз, или там быстрее способ сделать это?

Используя мой 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 выполняется за время O (n + lg m), где n - индекс последовательности дерева, а m - количество элементов в дереве.

Я не даю никаких гарантий относительно точности моего кода, используйте на свой страх и риск;)

0 голосов
/ 05 августа 2010

В F # вы можете использовать Set.partition или Set.filter для создания подмножеств: 

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

В вашем вопросе, может быть, вы не знаете значение i-го номера вашего набора, поэтому вот удобная функция для этого: 

let nth (n:int) (s:'a Set) = 
    s |> Set.toSeq |> Seq.nth 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

и протестируйте его: 

removeTopN 3 s

и мы получаем: 

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

Обратите внимание, что removeTopN не работает для набора, содержащего несколько одинаковых значений.

0 голосов
/ 05 августа 2010

Это уже довольно хорошее решение.OCaml имеет функцию split, которая может разделить Set, поэтому вы можете найти нужный элемент, а затем разделить Set, чтобы удалить кучу элементов за раз.Кроме того, вы можете использовать Set.difference для извлечения еще одного Set элементов.

...