Java - Google Guava Multimap Issue

Question

I have implemented a LFU-like web cache replacement algorithm that works as follows: in every request I assign a weight given by 1/(p^reqIndex), where p is a weight factor and reqIndex is the index of the request (1st request, 2nd request etc.). For example, with p = 0.5 we have a weight 1 for the 1st request, 2 for the 2nd, 4 for the 3rd etc. Then in order to calculate the score of each requested item (which I call weighted frequency, weightFreq) I simply sum the corresponding weights. The requested items are distinguished simply by a numeric ID (an integer) which I call request ID (reqID). For example, if the 1st request is for the item with ID 7, the 2nd for the item with ID 3, and the 3rd again for the item with ID 7, then the item with ID 7 should have a score 1 + 4 = 5 (weight of 1st request + weight of 3rd request) while the item with ID 3 should have a score 2 (weight of 2nd request).

I use a ListMultimap (via the Google Guava library) for the weights since I should be able to have multiple values (weights) for a single key (reqID):

/** ListMultimap of reqID (K) and weights (V) */
private ListMultimap<Integer, Double> weights;

I use a simple map for the scores:

/** Map of reqID (K) and weightFreq (V) */
private Map<Integer, Double> weightFreqs;

Here is the getter method where I calculate and return the scores of the requested items:

/**
 * Getter for weighted frequency of the requested item
 * @param   request                             The requested item
 * @param   reqIndex                            The index of the request
 * @return  this.weightFreqs.get(request.reqID) weightFreq of the req. item
 */
public double getWeightFreq(Request request, int reqIndex) {

    // initialize weightFreq
    initWeightFreqs(request);

    // calculate weight
    weight = Math.pow(1/p, reqIndex);

    // put request along with its weight to the weights ListMultimap
    weights.put(request.reqID, weight);

    // scan keys of weights list-multimap
    for(Integer key : this.weights.keySet()) {

        // if the key is the requested item
        if (key == request.reqID) {

            // list of all weights for this key (reqID)
            List<Double> tempWeights = weights.get(key);

            // test
            logger.info("List of weights for request with ID: " +   
                            request.reqID + " is: " + tempWeights);

            // sum of those weights
            int sum = 0;

            // scan the list
            for(int i = 0; i < tempWeights.size(); i++) {

                // sum the weights
                sum += tempWeights.get(i);

            }

            // assign the sum to the weightFreq value
            weightFreq = sum;

            // put reqID along with its weightFreq into weightFreqs map
            weightFreqs.put(request.reqID, weightFreq);

        }

    }

    // return weightFreq of requested item
    return this.weightFreqs.get(request.reqID);

}

As you can see, I included a test printing (list of weights for each reqID) in order to check the code. Now look what happen when I run the code. Again the same example, 1st request is for the reqID 7 and 2nd for the reqID 3. After the first request I get:

ReqID: 7 with weights: [1.0]

which is OK. But after the 2nd request I get:

ReqID: 7 with weights: [1.0] ReqID: 3 with weights: [1.0, 2.0]

which is wrong! The correct one should be:

ReqID: 7 with weights: [1.0] ReqID: 3 with weights: [2.0]

Thus, I get score (weightFreq) for reqID 3 equal to 3 (1+2) instead of 2 which is the correct one.

Note that I am learning programming only for the last 7 months or so and this is the 1st time I had to use a multimap (since I need to assign multiple values to a single key). I got the idea for doing so and the relevant info from here:

http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Multimap.html

It says about several different implementations of a multimap (ListMultimap, SetMultimap etc.), for the alternative of using a map of collections or asMap for doing the same via Google Guava etc.

I am not sure if I had understand something wrong regarding multimaps or if I have some error in my logic regarding the previous getter method. Any guidance will be appreciated.

Answer 1

No real idea what's going on here, but too much to say for a comment. You can surely fix it, just simplify it first. The test

key == request.reqID

is most probably wrong as you're dealing with Integers rather than with ints. In such cases never rely on auto(un)boxing and use either equals or intValue.

Your code is overcomplicated. You want to deal with the entries for request.reqID, so get them:

List<Double> tempWeights = weights.get(request.reqID);

Drop the outer loop and the if.

Simplify more, e.g., using the foreach loop

for (double d : tempWeights) sum += d;

When all the needless stuff is gone, you'll probably see the problem at once.

Answer 2

You might be working in a multithreaded environment. It seems like you could simplify the code, save memory and also make your computations atomic by introducing:

ConcurrentHashMap<Integer, RequestInfo> map = new ConcurrentHashMap<>();

class RequestInfo{
    double weight;
    List<Double> frequencies;  // consider using TDoubleArrayList from Trove4j
                               // for efficiency
    public synchronized addFrequency(double freq){
        ...
    }
}

And then use map.putIfAbsent to make an atomic insertion of an empty RequestInfo.