二叉树上的并行编程

Question

我对 python 和并行编程还很陌生。我有一个看起来像这样的二叉树：

我的任务是对每个节点进行平方并替换节点中的值，但是子节点必须在父节点之前进行平方（即所有子任务都应该被执行在父任务之前 - 4、5、6 和 7 将首先进行平方，然后使用线程 2 和 3），并且同一级别的所有节点都应该并行进行平方任务。

如何在每个节点上并行应用此功能？通过并行，我的意思是使用 python.

的多处理方面

Answer 1

我假设并行只是意味着深度级别的所有节点必须在较低深度级别之前计算，即您不关心多个线程。

对二叉树的节点执行操作的标准方法是使用递归函数。但是，在这种情况下，您必须跟踪深度级别以了解您是否被允许执行该任务。

您可以使用按正确顺序执行的任务列表：遍历树，将节点附加到任务列表。该列表根据节点的深度排序。最后，您按给定顺序对排序列表的每个节点应用您的操作。

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)，但是如果你使用更好的结构来处理排序任务，比如另一个二叉树，你可以得到O(n log n)）

并不是说如果您需要来自子节点的信息来对当前节点执行操作，这将不起作用。

编辑：复杂度实际上是 O(n)：当您在调用子节点上的函数之前添加当前节点时，您确保当前深度低于所有未来深度。因此，您始终可以在列表的前面添加节点，其成本为 O(1)。

如果您在将当前节点添加到列表之前调用子节点上的函数，就不会出现这种情况。

Answer 2

这是在其父级别之前对每个级别进行平方的解决方案。它首先找到级别，然后从最低级别开始对每个级别进行平方：

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)

输出将是：

现在，如果您需要运行每个级别并行，请将 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)

并且它会打印与之前的单线程输出相同的输出。

二叉树上的并行编程

Parallel programming on Binary tree

python

algorithm

parallel-processing

binary-tree

python-multiprocessing