Jaka jest złożoność czasu przejścia drzew przy użyciu plonu?

Question

Przykładem głębokości pierwszego przechodzenie drzewa:

class Node: 
    def __init__(self, value): 
     self._value = value 
     self._children = [] 

    def add_child(self, child): 
     self._children.append(child) 

    def __iter__(self): 
     return iter(self._children) 

    def depth_first(self): 
     yield self 
     for c in self: 
      yield from c.depth_first() 

Rozumiem, że yield from nie zużywa generator od razu, ale zamiast zdać yield górę do swojego rozmówcy.

Ale ten proces przechodząc nadal istnieje, a zatem yield będą przekazywane z każdego węzła całą drogę aż do nasady, a my możemy opisać czas pracy przez nawrotu (zakładamy, że jest to drzewo binarne dla uproszczenia , ale idea jest taka sama):

T (n) = 2 * T (n/2) + Θ (n)

Θ(n) istnieje, ponieważ węzeł musi przejść przez cały yield przekazane od potomstwa do rodzica. I złożoność czas pochodzi z powyższym wzorze jest:

O (nlogn)

Jednak złożoność czas przechodzenie drzewa jest tylko O(n) jeśli nie używam yield lub yield from w ogóle.

Zastanawiam się, czy źle rozumiem, jak działa yield lub po prostu nie można napisać takiego generatora rekursywnego.

Answer 1

Z oficjalnej Python 3.3 dopuszczenia do yield from: https://www.python.org/dev/peps/pep-0380/

Korzystanie składni specjalistycznego otwiera możliwości optymalizacji gdy istnieje długi łańcuch generatorów. Takie łańcuchy mogą powstać dla instancji , gdy rekursywnie przechodzą przez strukturę drzewa. Zlecenie przekazywania i uzyskiwania wartości w dół i w górę łańcucha może spowodować, że to, co powinno być operacją O (n), staje się, w najgorszym przypadku, , O (n ** 2).

Możliwą strategią jest dodanie gniazda do generatora obiektów , aby zatrzymać delegowany generator. Po wywołaniu funkcji send() w generatorze, to gniazdo jest sprawdzane jako pierwsze, a , jeśli nie jest ono puste, to generator, do którego się odwołuje, zostaje w tym przypadku wznowiony jako . Jeśli podniesie StopIteration, slot zostanie wyczyszczony i główny generator zostanie wznowiony.

Spowoduje to zmniejszenie obciążenia delegowania do wywołania funkcji C w trybie C, bez wykonywania kodu w języku Python. Możliwym wzmocnieniem byłoby przemieszczenie całego łańcucha generatorów w pętli i bezpośrednio wznowienie na końcu, chociaż obsługa tego StopIteracji jest wówczas bardziej skomplikowana.

Wygląda na to, że yield from nadal wymaga przechodzenia przez drzewo. Ale to przejście jest wykonywane przez interpreter w C zamiast w Pythonie.Technicznie jest to nadal O (n), ale nie jest tak źle, jak się wydaje.