Java: алгоритм Dijkstra с ThreadPool и CountDownLatch вызывает исключение за пределами границ - PullRequest
Новая
       36

Java: алгоритм Dijkstra с ThreadPool и CountDownLatch вызывает исключение за пределами границ

0 голосов
/ 11 июля 2019

Это основано на моем предыдущем вопросе: Подождите в цикле, пока задачи ThreadPoolExecutor не будут выполнены, прежде чем продолжить

Я пытаюсь сделать алгоритм Дейкстры параллельным.Я реализовал CountDownLatch, чтобы дождаться завершения всех задач.Каждая задача смотрит на определенный набор ребер, связанных с текущим узлом в итерации.Таким образом, 8 ребер и 2 потока означают, что каждая задача будет смотреть на 4 ребра.После того, как все задачи будут выполнены, мы перейдем к следующему узлу.

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

Чтобы посмотреть на некоторые строки отладки, я добавил Thread.Sleep (100), чтобы посмотреть на вывод, и заметил, что массив не выходит за пределы, когда я замедляю работу.

Наконец, я заметил, что цикл застревает на узле 0, источнике.Это не должно быть возможным, потому что мы начинаем с этого узла и устанавливаем значение true.Я не знаю, если это из-за других ошибок или других ошибок в моем коде.

Эта функция вызывается один раз и будет проходить через все узлы на графике: 

public void apply(int numberOfThreads) {
        ThreadPoolExecutor executor = (ThreadPoolExecutor) Executors.newFixedThreadPool(numberOfThreads + 1);
        CountDownLatch cdl = new CountDownLatch(numberOfThreads);

        class DijkstraTask implements Runnable {

            private int start;
            private int end;
            private final CountDownLatch cdl;

            public DijkstraTask(int start, int end, CountDownLatch cdl) {
                this.start = start;
                this.end = end;
                this.cdl = cdl;
            }

            @Override
            public void run() {
                calculateShortestDistances(start, end, cdl);
            }
        }

        currentNode = 0;
        this.nodes[0].setDistanceFromSource(0);

        // Visit every node, in order of stored distance
        for (int i = 0; i < this.nodes.length; i++) {
            // Loop round the edges that are joined to the current node
            currentNodeEdges = this.nodes[currentNode].getEdges();

            int edgesPerThread = currentNodeEdges.size() / numberOfThreads;
            int modulo = currentNodeEdges.size() % numberOfThreads;

            System.out.println(i);

            //Add task for each node
            for (int t = 0; t < numberOfThreads; t++) {
                int start = edgesPerThread * t;
                int end = edgesPerThread * (t + 1);

                executor.execute(new DijkstraTask(start, end, cdl));
                System.out.println("Start: " + start + ". End: " + end + ". Total: " + currentNodeEdges.size());

               //If we have a modulo we will add another task to look at the remaining edges
                if (modulo > 0 && numberOfThreads == (t + 1)) {
                    start = edgesPerThread * (t + 1);
                    end = edgesPerThread * (t + 1) + modulo;

                    executor.execute(new DijkstraTask(start, end, cdl));
                    System.out.println("Modulo start: " + start + ". End: " + end + ". Total: " + currentNodeEdges.size());
                }
            }
            //wait for all threads to finish
            try {
                cdl.await();
                System.out.println("-all done-");
            } catch (InterruptedException ex) {
                ex.printStackTrace();
            }

            // All neighbours are checked so this node is now visited
            nodes[currentNode].setVisited(true);

            //Look through the results of the tasks and get the next node that is closest by
            currentNode = getNodeShortestDistanced();
        }

        executor.shutdown();
    }

Следующая задача вызывается задачей, она обрабатывает подключенные eges от начального индекса до конечного индекса: 

public void calculateShortestDistances(int start, int end, CountDownLatch cdl) {

        //Process the edges
        for (int joinedEdge = start; joinedEdge < end; joinedEdge++) {
            // Array goes out of bounds here!
            int neighbourIndex = currentNodeEdges.get(joinedEdge).getNeighbourIndex(currentNode);

            // Only interested in an unvisited neighbour
            if (!this.nodes[neighbourIndex].isVisited()) {
                // Calculate the tentative distance for the neighbour
                int tentative = this.nodes[currentNode].getDistanceFromSource() + currentNodeEdges.get(joinedEdge).getLength();
                // Overwrite if the tentative distance is less than what's currently stored
                if (tentative < nodes[neighbourIndex].getDistanceFromSource()) {
                    nodes[neighbourIndex].setDistanceFromSource(tentative);
                }
            }
        }

        cdl.countDown();
    }

Спасибо за помощь!

Редактировать: я добавилтрассировка стека: 

Exception in thread "pool-1-thread-388" java.lang.IndexOutOfBoundsException: Index: 9, Size: 9
    at java.util.ArrayList.rangeCheck(ArrayList.java:657)
    at java.util.ArrayList.get(ArrayList.java:433)
    at ThreadPool.CalculatePerVertice.calculateShortestDistances(CalculatePerVertice.java:136)
    at ThreadPool.CalculatePerVertice$1DijkstraTask.run(CalculatePerVertice.java:76)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
    at java.lang.Thread.run(Thread.java:748)
    ````
...