Обрезать многостраничное дерево - что является лучшим решением?

Question

Мне было интересно, может ли кто-нибудь предложить более упрощенное решение или усовершенствования моего кода для решения следующей проблемы.

Скажем, у нас есть дерево с ветвями, идущими на некоторую глубину "d", и мы хотели бы обрезать это дерево так, чтобы мы сохранили "n" ветвей на глубине d, а затем еще n ветвей на глубине d-1; тогда еще n разветвляется на d-2 и т.д...

В моем решении мне нужно было прибегнуть к dictionary отслеживать количество филиалов и ref переменная глубина для отслеживания и снижения уровня глубины

Было бы очень интересно узнать более простое, более элегантное решение или какие-либо советы / подсказки, чтобы улучшить то, что у меня есть

Структура данных

type MultiTree = | MNode of int * list<MultiTree>

Тестовое дерево

let Mtree2 = MNode (0,
                    [MNode (1,[MNode (2,[MNode (3,[])])]);
                    MNode (1,[MNode (2,[MNode (3,[])])]);
                    MNode (1,[MNode (2,[MNode (3,[])])]);
                    MNode (1,[MNode (2,[MNode (3,[])])]);
                    MNode (1,[MNode (2,[MNode (3,[])])]);
                    MNode (1,[MNode (2,[MNode (3,[])])])])

Обрезка дерева Функция

let trimTree noLosses depth t=
    let mlimit = ref depth
    let dict = Dictionary()

    let fn k =
        match dict.TryGetValue(k) with
        | true, l -> dict.[k] <- l + 1
        |_ -> dict.Add(k,1)
        if dict.[k] >= noLosses then mlimit := !mlimit - 1 else mlimit := !mlimit

    let rec loop d t  = 
        match t with
            | MNode(i,sub) when d > !mlimit ->  
                fn !mlimit      
                MNode(i, List.map (loop (d+1)) [])
            | MNode(i,sub) -> MNode(i, List.map (loop (d+1)) sub)
    loop 1  t


let Mtree2trimmed = Mtree2 |> trimTree 3 2

Результат

Используя функцию printTree Томаса П, это хорошо визуализируется

let printt tree =
let rec loop depth (MNode(n, sub)) =
    printfn "%s %A" depth n
    for s in sub do loop (depth + "  ") s
loop "" tree

Выход -

printt Mtree2

 0
   1
     2
       3
   1
     2
       3
   1
     2
       3
   1
     2
       3
   1
     2
       3
   1
     2
       3

Выход -

printt Mtree2trimmed

 0
   1
     2
   1
     2
   1
     2
   1
   1
   1

Так что, если вы сделали это далеко - совет?

Ура!

Answer 1

Эта проблема называется mapreduce. Основной подход заключается в следующем:

1. Пометьте свои данные дополнительной структурой данных;
2. Процесс, основанный на дополнительных данных;
3. Уменьшить, чтобы удалить те элементы, которые не должны быть в конечном результате; Кроме того, исключите дополнительные данные, поскольку они больше не нужны.

Отметим каждую ветвь дополнительными значениями:

• depth (0= самая верхняя ветвь)
• sequential (для каждого поддерева, начиная с 0)

Для этого я изменил определение вашего дерева, чтобы оно было обобщенным:

type MultiTree<'T> = | MNode of 'T * list<MultiTree<'T>>

И сейчас:

let rec mapper depth sequential = function
    | MNode(value, sub) ->
        MNode( (depth, sequential, value),
               (sub |> List.mapi (fun i value -> mapper (depth+1) i value))
             )

let tree1 = MNode (0,
                    [MNode (1,[MNode (2,[])]);
                    MNode (3,[]);])

printfn "Original data"
tree1 |> printt
printfn "Mapped data"
tree1 |> mapper 0 0 |> printt

Результат будет:

Original data
 0
   1
     2
   3
Mapped data
 (0, 0, 0)
   (1, 0, 1)
     (2, 0, 2)
   (1, 1, 3)

Теперь, когда данные помечены, мы можем применить любой фильтр, который захотим. Вот три примера, плюс немного большее дерево, чтобы продемонстрировать все возможности:

// Take only first n branches at every level
let rec filter1 n = function
    // first subtrees pass (up to "noLosses" count)
    | MNode( (depth, sequential, value), sub)
        when sequential < n
                            -> Some(MNode(value, List.choose (filter1 n) sub))
    // the rest are skipped
    | _                     -> None

// Take "d" levels of branches unchanged, at higher levels take only second branch
let rec filter2 d = function
    | MNode( (depth, sequential, value), sub)
        when depth < d      // lower depth - pass

        || sequential = 1   // at higher levels, take only the second branch (=1)
                            -> Some(MNode(value, List.choose (filter2 d) sub))
    // the rest are skipped
    | _                     -> None

// Take only first n branches at every level;
// "n" is a list to identify maximal element at each level
let rec filter3 ns ts =
    match ns, ts with
    // Empty "noLosse" list -> no value
    | [], _                      -> None
    // if the sequential order of Tree branch is less than
    // the corresponding value in "ns" list, let the value pass the filter
    | nsHead :: nsTail, MNode((_, sequential, value), sub)
        when sequential < nsHead -> Some(MNode(value, List.choose (filter3 nsTail) sub))
    // the rest are skipped
    | _, _                       -> None

printfn "Original data"
tree2 |> printt
printfn "Filter1 applied"
tree2 |> mapper 0 0 |> filter1 2 |> Option.iter printt
printfn "Filter2 applied"
tree2 |> mapper 0 0 |> filter2 2 |> Option.iter printt
printfn "Filter3 applied"
tree2 |> mapper 0 0 |> filter3 [4; 4; 2] |> Option.iter printt

Обратите внимание, нам нужно Option.iter потому что фильтр может вернуться None значение.

Выходы:

Original data
 1
   11
     111
       1111
       1112
       1113
   12
     121
       1211
     122
       1221
       1222
       1223
     123
     124
   13
     131
       1211
   14
     141
       1411
   15
     151
       1511
   16
     161
       1611
Filter1 applied
 1
   11
     111
       1111
       1112
   12
     121
       1211
     122
       1221
       1222
Filter2 applied
 1
   11
   12
     122
       1222
   13
   14
   15
   16
Filter3 applied
 1
   11
     111
   12
     121
     122
   13
     131
   14
     141

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