пройти неупорядоченное двоичное дерево

Question

У меня есть ситуация, когда мне нужно получить доступ к дереву параллельно. Как это возможно? Я не могу думать ни о чем на деревьях без рекурсии.

Answer 1

Не уверен, если вы все еще ищете ответ на этот вопрос, но я подумал, что другие люди могли бы извлечь выгоду.

Вы все еще можете использовать рекурсию, но вам нужно заблокировать ветви дерева и позволить другим потокам «пропустить» эти ветви, потому что они уже обрабатываются (или уже были обработаны).

ДляНапример, предположим, что вы обрабатываете дерево, выполняя первый обход в ширину, поэтому при каждом запуске рекурсивного метода вы просматриваете дочерние элементы текущего узла.Каждый поток должен перебирать дочерние узлы текущего узла и пытаться заблокировать каждый дочерний узел, пропуская его, если он уже заблокирован.

Я не уверен, какую реализацию дерева вы используете, поэтому вам следует обработать 'Объект Node 'в следующем примере кода является псевдокодом, но остальное - правильный Java.

В приведенном ниже примере выбрана предопределенная глубина для применения блокировки в - это гарантирует, что потоки не просто блокируются вкорень дерева и сериализация доступа ко всему дереву.

Выбор правильной глубины будет зависеть от формы вашего конкретного дерева.Например, если это бинарное дерево, то ваше дерево может иметь до 8 ветвей на глубине 3, что, скорее всего, будет хорошо для пары потоков, но если вы выполняете 20 потоков, вам нужно будет выбрать точку сериализациименьшая глубина, чтобы все потоки могли обрабатывать некоторые ветви.

Вы также можете использовать какой-то другой метод принятия решения о том, когда блокировать (например, если узел мог бы эффективно сообщать о том, сколько у него было конечных узлов, вы могли бы установить порог для этого), важно то, что все потоки используюттот же код для принятия решения заблокировать или не блокировать.

Object master_LOCK = new Object();
HashMap locks = new HashMap();
int DEPTH = 5;

public boolean lockNode(Object nodeID) {
    synchronized(master_LOCK) {
        Object node_LOCK = (Object)locks.get(nodeID);
        if (node_LOCK == null) {
            //we can lock this node
            locks.put(nodeID,new Object());
            return true;
        } else {
            //node already locked
            return false;
        }
    }
}

public void traverseBreadhFirst(Node node) {    
    locks.clear();
    traverseBreadthFirst(node,0);
}

public void traverseBreadthFirst(Node node, int currentDepth) {
    currentDepth++;

    //Process the current node here


    //Iterate through children, locking to force serialised access only at a predetermined depth
    List children = node.getChildren();

    for (int i = 0; i < children.size(); i++) {

        Node child = (Node)children.get(i);

        //If we are a certain depth in the tree we start serialising access from that point on
        //This ensures that there are enough branches at this point to roughly evenly distribute them 
        //to all available threads.

        if (currentDepth < DEPTH ) {
            //All threads are to go to depth N
            traverseBreadthFirst(node,currentDepth);

        } else if (currentDepth == DEPTH ) {
            //At depth N we lock all branches we intend to process
            if (lockNode(child.getID())) {
                //We have locked this child node so we should process it
                traverseBreadthFirst(node,currentDepth);
            } else {
                //This child has been locked for processing already so we skip it
            }

        } else {
            //We are deeper than depth N so we can traverse our locked branch without locking further
            traverseBreadthFirst(node,currentDepth);

        }
    }

}