Блог

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

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

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

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

Я не уверен, какую реализацию дерева вы используете, поэтому вам следует рассматривать объект ‘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);

        }
    }

}