バイナリツリーの並列プログラミング

Question

私はPythonと並列プログラミングにはかなり新しいです。私はこのようになりますバイナリツリーがあります。

を私のタスクは、各ノードを二乗し、ノードの値を置き換えますが、子ノードが前に親ノードを乗しなければならないことです（つまり、すべての子どもたちの作業親タスク - 4,5,6 & 7が最初に2乗され、次いでスレッドを使用して2 & 3になる）の前に実行されなければならず、同じレベルのすべてのノードは2乗タスクを並列に受けるべきである。

各ノードでこの機能を並列に適用するにはどうすればよいですか？ 並行して、私はPythonのマルチプロセッシングの側面を使用することを意味します。

Answer 1

これは、親レベルの前に各レベルを四角形にするソリューションです。これは、最初のレベルを発見し、各レベルを正方形に最低レベルから開始します。

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) 

出力は次のようになります。

今

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

あなたが並行して、各レベルの実行に必要がある場合は、交換してくださいsquare_level関数を並列実装します。

ので、マルチスレッド・バージョンは、この希望：

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) 

をそして、それは以前のシングルスレッドのような同じ出力を表示します。

Answer 2

これは、深さレベルのすべてのノードを低い深度レベルより前に計算する必要があるということです。つまり、複数のスレッドを気にしないということです。

バイナリツリーのノードで操作を実行する標準的な方法は、再帰関数を使用することです。ただし、この場合は、タスクを実行することが許可されているかどうかを判断するために深度レベルを把握する必要があります。

タスクのリストを正しい順序で実行することができます。タスクのリストにノードを追加してツリーを通過します。このリストは、ノードの深さに応じてソートされます。最後に、並べ替えられたリストの各ノードに対して、指定した順序で操作を適用します。

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) 

次に、リストのすべてのノードにsquare（）を適用します。

（これは。複雑さはO（n^2）の擬似コードですが、あなたがそのような別のバイナリツリーとしてソートされたタスクを処理するために、より良い構造を使用する場合は（N Nをログ）Oを得ることができます）

現在のノードで操作を実行するために子ノードからの情報が必要な場合、これは機能しません。

EDIT：複雑さは実際にはO（n）です：子ノードで関数を呼び出す前に現在のノードを追加すると、現在の深度がすべての将来のものよりも低いことが保証されます。したがって、リストの先頭にノードを追加することはできますが、O（1）のコストがかかります。

現在のノードをリストに追加する前に子ノードで関数を呼び出していた場合、これは当てはまりません。