CODEWITHSUNDEEP
javadebuggingcollections
Oliver Funk
Oliver Funk

Reputation: 186

Strange bug when incrementing a value while iterating through a collection in Java

I recently wrote a program that does Ant Colony Optimization on a graph.

The following code has a bug in it I can't understand.

    Map<Node, Edge> nodesLinkedToCurrentNode = a.getCurrentNode().getLinkedNodes();

    TreeMap<Double, Node> probabilitiesForNodes = new TreeMap<>();
    double totalProb = 0d;

    for (Node n : graph.values()) {
        if (!a.getVisited().contains(n)) {
            //For each node that has not yet been visited
            //calculate it's weighted probabily
            double weightedProbability
                    = (Math.pow(nodesLinkedToCurrentNode.get(n).getPheremoneLevel(), RPI))
                    * (Math.pow((double) 1 / nodesLinkedToCurrentNode.get(n).getDistance(), RHI));
            totalProb += weightedProbability;

            //Map the node to its probability
            probabilitiesForNodes.put(weightedProbability, n);
        }
    }

    double testTotalProb = 0d;
    for (Double d : probabilitiesForNodes.keySet()) {
        testTotalProb += d;
    }
    if (testTotalProb != totalProb) { <----------How can this happen??
        System.out.println("Why?");
        totalProb = testTotalProb;
    }

That if statement executes all the time and I don't understand why.

I'm just incrementing a value, but for some reason, it's not being incremented properly.

I made the project open source, if you want to check it out

The java file with the code in it

I replicated the bug with the following code:

    TreeMap<Double, String> probabilitiesForNodes = new TreeMap<>();
    double totalProb = 0d;

    for (int i = 1; i < 10; i++) {
        //For each node that has not yet been visited
        //calulate it's weighted probabily
        double weightedProbability
                = (Math.pow(0.7 + 1 / i, 2))
                * (Math.pow((double) 1 / 30, i));
        totalProb += weightedProbability;

        String sudoNode = "node" + i;

        //Map the node to its probability
        probabilitiesForNodes.put(weightedProbability, sudoNode);
    }

    double testTotalProb = 0d;
    for (Double d : probabilitiesForNodes.keySet()) {
        testTotalProb += d;
    }
    if (testTotalProb != totalProb) {
        System.out.println("Why?");
        totalProb = testTotalProb;
    }

Upvotes: 3

Views: 95

Answers (1)

Marko Topolnik
Marko Topolnik

Reputation: 200168

You are working with double numbers so you should expect this. Specifically you obtain totalProb and testTotalProb by iteratively adding the same double numbers, but in different order. Since adding doubles is not an exactly associative operation, enough discrepancy occurs to make your equality test fail.

Another thing that can happen is a collision on the same Double key. There is nothing stopping two nodes from having exactly the same weighted probability. So for starters you can just check the sizes of the two collections.

Upvotes: 4

Related Questions