Параллельное программирование на двоичном дереве

Question

Я довольно новичок в python и параллельном программировании. У меня есть бинарное дерево, которое выглядит следующим образом:

Моя задача состоит в том, чтобы умиротворять каждый узел и заменить значение в узле, но дочерние узлы должны быть в квадрате перед тем родительские узлы (т.е. все дети задачи должен выполняться перед родительскими задачами - 4,5,6 & 7 сначала будет квадратным, затем 2 & 3, используя потоки), и все узлы того же уровня должны проходить параллельную параллельную задачу.

Как применить эту функцию на каждом узле параллельно? Параллельно я хочу использовать многопроцессорный аспект 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), но вы можете получить O (N журнал N), если вы используете более удобную структуру для обработки отсортированные задач, таких как другой бинарное дерево)

Не то, чтобы это не сработало, если вам нужна информация из дочерних узлов для выполнения операции над текущим узлом.

EDIT: сложность на самом деле O (n): при добавлении текущего узла перед вызовом функции на дочернем узле вы убедитесь, что текущая глубина ниже всех будущих. Поэтому вы всегда можете добавить узел в начале списка, который стоит O (1).

Это не так, если бы вы вызывали функцию на дочерних узлах, прежде чем добавлять текущий список в список.