Najbardziej efektywny sposób generowania wszystkich potomków wszystkich węzłów w drzewie

9

Szukam najbardziej wydajnego algorytmu do pobrania drzewa (przechowywanego jako lista krawędzi; LUB jako lista odwzorowań z węzła nadrzędnego na listę węzłów podrzędnych); i stworzyć dla KAŻDEGO węzła listę wszystkich węzłów z niego pochodzących (poziom liścia i poziom nie-liści).

Wdrożenie musi odbywać się za pomocą pętli zamiast recusion, ze względu na skalę; i idealnie powinien być O (N).

To pytanie SO obejmuje standardowe, dość oczywiste rozwiązanie, aby znaleźć odpowiedź na JEDEN węzeł w drzewie. Ale oczywiście powtarzanie tego algorytmu na każdym węźle drzewa jest wysoce nieefektywne (z góry mojej głowy, od O (NlogN) do O (N ^ 2)).

Korzeń drzewa jest znany. Drzewo ma absolutnie dowolny kształt (np. Nie jest N-nary, nie jest w żaden sposób zbalansowany, ma kształt lub formę, nie ma jednolitej głębokości) - niektóre węzły mają 1-2 dzieci, niektóre mają 30K dzieci.

Na poziomie praktycznym (choć nie powinno to wpływać na algorytm) drzewo ma ~ 100–200 000 węzłów.

DVK
źródło
Możesz symulować rekurencję za pomocą pętli i stosu, czy jest to dozwolone dla twojego rozwiązania?
Giorgio,
@Giorgio - oczywiście. To właśnie próbowałem zasugerować przez „poprzez pętle zamiast recusion”.
DVK,

Odpowiedzi:

5

Jeśli faktycznie chcesz PRODUKOWAĆ każdą listę jako różne kopie, nie możesz mieć nadziei, że w najgorszym przypadku uzyskasz miejsce większe niż n ^ 2. Jeśli potrzebujesz tylko DOSTĘPU do każdej listy:

Wykonałbym przemierzanie drzewa w kolejności zaczynając od korzenia:

http://en.wikipedia.org/wiki/Tree_traversal

Następnie dla każdego węzła w drzewie przechowuj minimalną liczbę zamówień i maksymalną liczbę zamówień w poddrzewie (można to łatwo utrzymać przez rekurencję - możesz to symulować za pomocą stosu, jeśli chcesz).

Teraz umieść wszystkie węzły w tablicy A o długości n, w której węzeł o numerze porządkowym i znajduje się w pozycji i. Następnie, gdy musisz znaleźć listę dla węzła X, spójrz na A [X.min, X.max] - zauważ, że ten przedział będzie obejmować węzeł X, który również można łatwo naprawić.

Wszystko to odbywa się w czasie O (n) i zajmuje przestrzeń O (n).

Mam nadzieję, że to pomoże.

Jesper Nielsen
źródło
2

Nieefektywną częścią nie jest przemierzanie drzewa, ale budowanie list węzłów. Wydaje się rozsądne stworzenie takiej listy:

descendants[node] = []
for child in node.childs:
    descendants[node].push(child)
    for d in descendants[child]:
        descendants[node].push(d)

Ponieważ każdy węzeł potomny jest kopiowany na listę każdego rodzica, w przypadku drzew zrównoważonych uzyskujemy średnio złożoność O (n log n) i najgorszy przypadek O (n²) w przypadku drzew zdegenerowanych, które są naprawdę połączonymi listami.

Możemy upaść na O (n) lub O (1) w zależności od tego, czy musisz przeprowadzić konfigurację, jeśli wykorzystamy sztuczkę leniwego obliczania list. Załóżmy, że mamy plik, child_iterator(node)który daje nam dzieci tego węzła. Następnie możemy w prosty sposób zdefiniować coś descendant_iterator(node)takiego:

def descendant_iterator(node):
  for child in child_iterator(node):
    yield from descendant_iterator(child)
  yield node

Rozwiązanie nierekurencyjne jest o wiele bardziej zaangażowane, ponieważ przepływ sterowania iteratorem jest trudny (coroutines!). Zaktualizuję tę odpowiedź później dzisiaj.

Ponieważ przejście do drzewa wynosi O (n), a iteracja po liście jest również liniowa, sztuczka całkowicie odracza koszt, dopóki i tak nie zostanie zapłacony. Na przykład wydruk listy potomków dla każdego węzła ma złożoność najgorszego przypadku O (n²): iteracja po wszystkich węzłach to O (n), podobnie jak iteracja po potomkach każdego węzła, niezależnie od tego, czy są one przechowywane na liście, czy obliczone ad hoc .

Oczywiście to nie zadziała, jeśli potrzebujesz rzeczywistej kolekcji do pracy.

amon
źródło
Przepraszam, -1. Głównym celem aglorytmu jest wstępne obliczenie danych. Leniwe obliczenia całkowicie pokonują powód nawet uruchomienia algo.
DVK
2
@DVK Ok, mogłem źle zrozumieć twoje wymagania. Co robisz z wynikowymi listami? Jeśli wstępne obliczanie list jest wąskim gardłem (ale nie korzysta z list), oznaczałoby to, że nie używasz wszystkich danych, które agregujesz, a leniwe obliczenia byłyby wygrane. Ale jeśli użyjesz wszystkich danych, algorytm obliczeń wstępnych jest w dużej mierze nieistotny - złożoność algorytmiczna wykorzystania danych będzie co najmniej równa złożoności tworzenia list.
amon
0

Ten krótki algorytm powinien to zrobić, spójrz na kod public void TestTreeNodeChildrenListing()

Algorytm faktycznie przechodzi kolejno przez węzły drzewa i prowadzi listę rodziców bieżącego węzła. Zgodnie z wymaganiami bieżący węzeł jest dzieckiem każdego węzła nadrzędnego, który jest dodawany do każdego z nich jako dziecko.

Ostateczny wynik jest przechowywany w słowniku.

    [TestFixture]
    public class TreeNodeChildrenListing
    {
        private TreeNode _root;

        [SetUp]
        public void SetUp()
        {
            _root = new TreeNode("root");
            int rootCount = 0;
            for (int i = 0; i < 2; i++)
            {
                int iCount = 0;
                var iNode = new TreeNode("i:" + i);
                _root.Children.Add(iNode);
                rootCount++;
                for (int j = 0; j < 2; j++)
                {
                    int jCount = 0;
                    var jNode = new TreeNode(iNode.Value + "_j:" + j);
                    iCount++;
                    rootCount++;
                    iNode.Children.Add(jNode);
                    for (int k = 0; k < 2; k++)
                    {
                        var kNode = new TreeNode(jNode.Value + "_k:" + k);
                        jNode.Children.Add(kNode);
                        iCount++;
                        rootCount++;
                        jCount++;

                    }
                    jNode.Value += " ChildCount:" + jCount;
                }
                iNode.Value += " ChildCount:" + iCount;
            }
            _root.Value += " ChildCount:" + rootCount;
        }

        [Test]
        public void TestTreeNodeChildrenListing()
        {
            var iteration = new Stack<TreeNode>();
            var parents = new List<TreeNode>();
            var dic = new Dictionary<TreeNode, IList<TreeNode>>();

            TreeNode node = _root;
            while (node != null)
            {
                if (node.Children.Count > 0)
                {
                    if (!dic.ContainsKey(node))
                        dic.Add(node,new List<TreeNode>());

                    parents.Add(node);
                    foreach (var child in node.Children)
                    {
                        foreach (var parent in parents)
                        {
                            dic[parent].Add(child);
                        }
                        iteration.Push(child);
                    }
                }

                if (iteration.Count > 0)
                    node = iteration.Pop();
                else
                    node = null;

                bool removeParents = true;
                while (removeParents)
                {
                    var lastParent = parents[parents.Count - 1];
                    if (!lastParent.Children.Contains(node)
                        && node != _root && lastParent != _root)
                    {
                        parents.Remove(lastParent);
                    }
                    else
                    {
                        removeParents = false;
                    }
                }
            }
        }
    }

    internal class TreeNode
    {
        private IList<TreeNode> _children;
        public string Value { get; set; }

        public TreeNode(string value)
        {
            _children = new List<TreeNode>();
            Value = value;
        }

        public IList<TreeNode> Children
        {
            get { return _children; }
        }
    }
}
Nisko latający pelikan
źródło
Dla mnie wygląda to bardzo podobnie do złożoności od O (n log n) do O (n²) i poprawia się tylko nieznacznie w stosunku do odpowiedzi, do której DVK podał pytanie. Więc jeśli to nie poprawa, jak to odpowiada na pytanie? Jedyną wartością dodaną przez tę odpowiedź jest przedstawienie iteracyjnego wyrażenia naiwnego algorytmu.
amon
To O (n). Jeśli przyjrzysz się algorytmowi, iteruje się raz na węzłach. Jednocześnie tworzy kolekcję węzłów potomnych dla każdego węzła macierzystego w tym samym czasie.
Low Flying Pelican
1
Pętla przechodzi przez wszystkie węzły, czyli O (n). Następnie przeglądasz wszystkie dzieci, które na razie będziemy ignorować (wyobraźmy sobie, że to jakiś stały czynnik). Następnie wykonujesz pętlę przez wszystkich rodziców bieżącego węzła. W drzewie bilansów jest to O (log n), ale w zdegenerowanym przypadku, gdy nasze drzewo jest listą połączoną, może to być O (n). Jeśli więc pomnożymy koszt zapętlania przez wszystkie węzły przez koszt zapętlania przez ich rodziców, otrzymamy złożoność czasową od O (n log n) do O (n²). Bez wielowątkowości nie ma „w tym samym czasie”.
amon
„w tym samym czasie” oznacza, że ​​tworzy kolekcję w tej samej pętli i nie ma żadnych innych pętli.
Low Flying Pelican
0

Zwykle wystarczy zastosować podejście rekurencyjne, ponieważ pozwala ono na zmianę kolejności wykonywania, dzięki czemu można obliczyć liczbę liści zaczynając od liści w górę. Ponieważ musisz użyć wyniku wywołania rekurencyjnego, aby zaktualizować bieżący węzeł, przygotowanie wersji rekurencyjnej wymagałoby specjalnego wysiłku. Jeśli nie podejmiesz tego wysiłku, to oczywiście takie podejście po prostu rozbije Twój stos dla dużego drzewa.

Biorąc pod uwagę, że zdaliśmy sobie sprawę, że główną ideą jest uzyskanie kolejności zapętlania, zaczynając od liści i wracając do korzenia, naturalną ideą, która przychodzi na myśl, jest wykonanie sortowania topologicznego na drzewie. Wynikową sekwencję węzłów można przesuwać liniowo, aby zsumować liczbę liści (zakładając, że można zweryfikować, że węzeł jest liściem w O(1)). Ogólna złożoność czasowa rodzaju topologicznego wynosi O(|V|+|E|).

Zakładam, że twoja Njest liczbą węzłów, która |V|zwykle byłaby (z nomenklatury DAG). Z Edrugiej strony wielkość zależy w dużej mierze od aromatu twojego drzewa. Na przykład drzewo binarne ma co najwyżej 2 krawędzie na węzeł, dlatego O(|E|) = O(2*|V|) = O(|V|)w takim przypadku powstałby ogólny O(|V|)algorytm. Pamiętaj, że ze względu na ogólną strukturę drzewa nie możesz mieć czegoś takiego O(|E|) = O(|V|^2). W rzeczywistości, ponieważ każdy węzeł ma unikalny element nadrzędny, możesz mieć co najwyżej jedną krawędź do zliczenia na węzeł, jeśli weźmiesz pod uwagę tylko relacje nadrzędne, więc dla drzew mamy taką gwarancję O(|E|) = O(|V|). Dlatego powyższy algorytm ma zawsze liniowy rozmiar drzewa.

Szczery
źródło