Parallele Programmierung auf Binärbaum

Question

Ich bin ziemlich neu in Python und parallel Programmierung. Ich habe einen binären Baum, der wie folgt aussieht:

Meine Aufgabe ist es, jeden Knoten zu quadrieren und den Wert im Knoten ersetzen, aber die Kinder-Knoten müssen vor die übergeordneten Knoten quadriert werden (dh die alle Kinder Aufgaben sollte ausgeführt werden, bevor die übergeordneten Aufgaben - 4,5,6 & 7 werden zuerst quadriert dann 2 & 3 mit Threads), und alle Knoten der gleichen Ebene sollten die Quadrierung Aufgabe parallel durchlaufen.

Wie kann ich diese Funktion auf jedem Knoten parallel anwenden? Parallel dazu möchte ich den Multiprozessor-Aspekt von Python verwenden.

Answer 1

Hier ist die Lösung, die jede Ebene vor den übergeordneten Ebenen quadriert. Es findet zuerst die Stufen und beginnt dann von der untersten Ebene auf jeder Ebene Quadrat:

from Queue import Queue 

class Node: 
    def __init__(self, value): 
     self.v = value 
     self.l = None 
     self.r = None 

    def __repr__(self): 
     return str(self.v) 

def square(node): 
    level = [node] 
    levels = [level] 
    while level: 
     new_level = [] 
     for n in level: 
      if n.l: 
       new_level.append(n.l) 
      if n.r: 
       new_level.append(n.r)  
     if new_level: 
      levels.append(new_level) 
     level = new_level 
    #print levels 

    for level in reversed(levels): 
     #print level 
     square_level(level) 

def square_level(level): 
    for node in level: 
     node.v *= node.v 

def print_tree(node): 
    q = Queue() 
    q.put(node) 
    while not q.empty(): 
     n = q.get() 
     print n 
     if n.l: 
      q.put(n.l) 
     if n.r: 
      q.put(n.r) 

n1 = Node(1) 
n2 = Node(2) 
n3 = Node(3) 
n4 = Node(4) 
n5 = Node(5) 
n6 = Node(6) 
n7 = Node(7) 

n1.l = n2 
n1.r = n3 
n2.l = n4 
n2.r = n5 
n3.l = n6 
n3.r = n7 

print_tree(n1)   
square(n1) 
print "squared:" 
print_tree(n1) 

Der Ausgang wird sein:

1 
2 
3 
4 
5 
6 
7 
squared: 
1 
4 
9 
16 
25 
36 
49 

Nun, wenn Sie jede Ebene parallel ausgeführt werden müssen, ersetzen die Funktion square_level mit der parallelisierten Implementierung.

So ist die Multi-Thread-Version möchte dies:

from Queue import Queue 
from threading import Thread 

class Node: 
    def __init__(self, value): 
     self.v = value 
     self.l = None 
     self.r = None 

    def __repr__(self): 
     return str(self.v) 

def square(node): 

    # find levels 
    level = [node] 
    levels = [level] 
    while level: 
     new_level = [] 
     for n in level: 
      if n.l: 
       new_level.append(n.l) 
      if n.r: 
       new_level.append(n.r)  
     if new_level: 
      levels.append(new_level) 
     level = new_level 
    #print levels 

    # square each level, starting with the lowest level first 
    for level in reversed(levels): 
     #print level 
     square_level(level) 

def square_level(level): 
    for node in level: 
     q.put(node) 
    q.join() 

def print_tree(node): 
    q = Queue() 
    q.put(node) 
    while not q.empty(): 
     n = q.get() 
     print n 
     if n.l: 
      q.put(n.l) 
     if n.r: 
      q.put(n.r) 

q = Queue() 
def worker(): 
    while True: 
     node = q.get() 
     node.v *= node.v 
     q.task_done() 

for i in range(0, 3): 
    t = Thread(target=worker) 
    t.daemon = True 
    t.start() 

n1 = Node(1) 
n2 = Node(2) 
n3 = Node(3) 
n4 = Node(4) 
n5 = Node(5) 
n6 = Node(6) 
n7 = Node(7) 

n1.l = n2 
n1.r = n3 
n2.l = n4 
n2.r = n5 
n3.l = n6 
n3.r = n7 

print_tree(n1)   
square(n1) 
print "squared:" 
print_tree(n1) 

Und es wird die gleiche Leistung wie die vorherigen Single-Threaded einer drucken.

Answer 2

Ich nehme an, dass Sie parallel meinen, dass alle Knoten eines Tiefenlevels vor einem niedrigeren Tiefenlevel berechnet werden müssen, d. H. Dass Sie sich nicht um mehrere Threads kümmern.

Die Standardmethode zum Ausführen einer Operation an den Knoten eines Binärbaums besteht in der Verwendung einer rekursiven Funktion. In diesem Fall müssen Sie jedoch die Tiefenstufe verfolgen, um zu wissen, ob Sie die Aufgabe ausführen dürfen.

Sie könnten eine Liste von Aufgaben verwenden, die in der richtigen Reihenfolge ausgeführt werden: Sie gehen durch Ihren Baum und hängen die Knoten an die Aufgabenliste an. Diese Liste ist nach der Tiefe der Knoten sortiert. Am Ende wenden Sie Ihre Operation auf jeden Knoten der sortierten Liste in der angegebenen Reihenfolge an.

def fill_list(node, depth): 
    list.add_in_sorted_list(node, depth) 

    if(node.has_left_child()) 
     fill_list(node.left_child, depth+1) 

    if(node.has_right_child()) 
     fill_list(node.right_child, depth+1) 

Dann gelten Sie für alle Knoten der Liste Quadrat().

(dies ist Pseudocode. Komplexität O (n^2), aber Sie können O erhalten (n log n), wenn Sie eine bessere Struktur verwenden, um die sortierten Aufgaben, wie zum Beispiel eines anderen binären Baum zu handhaben)

Nicht, dass dies nicht funktioniert, wenn Sie Informationen von den untergeordneten Knoten benötigen, um die Operation auf dem aktuellen Knoten auszuführen.

BEARBEITEN: Die Komplexität ist tatsächlich O (n): Wenn Sie den aktuellen Knoten hinzufügen, bevor Sie die Funktion auf dem untergeordneten Knoten aufrufen, stellen Sie sicher, dass die aktuelle Tiefe niedriger ist als alle zukünftigen. Daher können Sie immer den Knoten an der Vorderseite der Liste hinzufügen, der O (1) kostet.

Dies ist nicht der Fall, wenn Sie die Funktion auf den untergeordneten Knoten aufgerufen haben, bevor Sie den aktuellen Knoten zur Liste hinzugefügt haben.