Проблемы с Java HashMaps и методом putAll ()

Question

Привет всем, Я пишу программу, которая сравнивает время выполнения различных реализаций Дейкстры. Я анализирую соответствующую информацию из текстового файла и записываю ее в хеш-таблицу. В моей текущей реализации у меня есть «главная» хеш-таблица, которая содержит информацию об узле, и эта информация копируется во временную хеш-таблицу, которая затем передается в различные классы Dijkstra.

public class Router
{
    public static Map <Integer, Node> nodes = new HashMap<Integer, Node>();
    public static Map <Integer, Node> temp = new HashMap<Integer, Node>();
    public static int target = 2;
    public static int start = 0;

    public static void main(String[] args) throws IOException
    {
        Parser p3 = new Parser(args[0], nodes, p);
        temp.putAll(nodes);

        // Test 1
        DijkstraFib fb = new DijkstraFib(temp, start, target, p);
        temp.clear();
        temp.putAll(nodes);

        //Test 2
        DijkstraBinary d = new DijkstraBinary(temp, start, target, p);
        temp.clear();
        temp.putAll(nodes);

        // Test 3
        Dijkstra b = new Dijkstra(temp, start, target, p);
    }

}

Поэтому вместо того, чтобы трижды вызывать анализатор для каждого класса Dijkstra, я просто хочу скопировать все значения из таблицы nodes в temp, поскольку temp изменяется во время выполнения метода. Первые два теста работают нормально, но третий тест не пройден. Если я поменяю местами Тест 2 и Тест 3, то Тест 2 не пройден; в основном, какой бы тест ни выполнялся последним, он терпит неудачу. Вот мой метод Дейкстры:

void route(Map <Integer, Node> nodes, int source)
{
    Node start = nodes.get(source);
    start.distance = 0;
    unsettledNodes.add(start);

    while(!unsettledNodes.isEmpty())
    {
        Node n = extractMin();
        visited.put(n.name, n);
        relax_neighbours(n, nodes);
    }
}

void relax_neighbours(Node n, Map <Integer, Node> nodes)
{
    for (int i = 0; i < n.outgoing.size(); i++)
    {
        Edge edge = n.outgoing.get(i);
        Node v = nodes.get(edge.node);

        if (isSettled(v))
        {
            continue;
        }

        double shortDist = n.distance + edge.length;
        if (shortDist < v.distance)
        {
            unsettledNodes.remove(v);
            v.distance = shortDist;
            v.previous = n;
            unsettledNodes.add(v);
        }
    }
}

и вот мой метод, который печатает путь, начиная с целевого узла:

 void print_path(Map <Integer, Node> visited, int i)
{
    ArrayList<Node> path = new ArrayList<Node>();

    for (Node target = visited.get(i); target != null; target = target.previous)
    {
        path.add(target);
    }
    System.out.println("Simple Dijkstra took " + this.time_taken + " ms");
    System.out.print("Min dist from " + this.source + " to " + this.target + " = " + path.get(0).distance + " : ");

    Collections.reverse(path);

    System.out.print(path.get(0).name);
    p.append(Integer.toString(path.get(0).name));
    for (int k = 1; k < path.size(); k++)
    {
        System.out.print(" -> " + path.get(k).name);
    }
    System.out.println();
}

и вот вывод консоли:

Edges: 948464
Fibonacci Dijkstra took 340 ms
Min dist from 0 to 2 = 89.0 : 0 -> 195 -> 5523 -> 5504 -> 5870 -> 5835 -> 3076 -> 15319 -> 5588 -> 5911 -> 2

Binary Dijkstra took 302292 ms
Min dist from 0 to 2 = 89.0 : 0 -> 195 -> 5523 -> 5504 -> 5870 -> 5835 -> 3076 -> 15319 -> 5588 -> 5911 -> 2

Simple Dijkstra took 0 ms
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
   at java.util.ArrayList.rangeCheck(ArrayList.java:571)
   at java.util.ArrayList.get(ArrayList.java:349)
   at Dijkstra.print_path(Dijkstra.java:115)
   at Dijkstra.<init>(Dijkstra.java:25)
   at Router.main(Router.java:33)

Answer 1

Не видя больше вашего кода, я не могу сказать наверняка, но похоже, что вы передаете одни и те же объекты, когда помещаете все в новые карты. То есть те же узлы ссылаются из вызова в вызов, и temp является , а не копией значений в узлах. Если ваши методы изменяют веса пути для алгоритмов кратчайшего пути (то есть, если Node является изменяемым), вы столкнетесь с проблемами.

Один из вариантов - написать метод глубокого копирования для вашего узла, создав новый узел и заполнив всю необходимую информацию. Тогда у вас будет «свежая» копия узла для каждого нового запуска алгоритма

Answer 2

Исключение (java.lang.IndexOutOfBoundsException) означает, что вы пытаетесь получить элемент, выходящий за пределы диапазона в вашем массиве.

Проблема в 115 строке в методе print_path:

at Dijkstra.print_path(Dijkstra.java:115)

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

edited: Проблема в том, что когда вы вызываете putAll (), выпоместите ссылки на ваши основные узлы, после этого ваш алгоритм модифицирует узлы (на самом деле в ваших узлах HashMap ), и это будет распространено в следующих тестах.