Java - ошибка Google Guava Multimap

Question

Я реализовал алгоритм замены кэша, подобный LFU, который работает следующим образом: в каждом запросе я назначаю вес, заданный 1/(p^reqIndex), где p - весовой коэффициент и reqIndex является индексом запроса (1-й запрос, 2-й запрос и т. д.). Например, при p = 0,5 мы имеем вес 1 для 1-го запроса, 2 для второго, 4 для третьего и т. Д. Затем, чтобы вычислить оценку каждого запрошенного элемента (который я называю взвешенной частотой, weightFreq), я просто суммируем соответствующие веса. Запрошенные элементы различаются просто с помощью числового идентификатора (целого), который я вызываю ID запроса (reqID). Например, если первый запрос для элемента с идентификатором 7, вторым для элемента с идентификатором 3, а третий для элемента с идентификатором 7, то элемент с идентификатором 7 должен иметь оценку 1 + 4 = 5 (вес 1-го запроса + вес третьего запроса), в то время как элемент с ID 3 должен иметь счет 2 (вес 2-го запроса).

Я использую ListMultimap (через библиотеку Google Гуаву) для весов, так как я должен быть в состоянии иметь несколько значений (вес) для одного ключа (reqID):

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

я использую простую карту для оценки:

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

Вот метод геттер, где я могу вычислить и вернуть баллы запрошенных пунктов:

/** 
* 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); 

} 

Как вы можете видеть, я включил тестовую печать (список весов для каждого reqID), чтобы проверить код. Теперь посмотрим, что произойдет, когда я запустил код. Опять же пример, первый запрос для reqID 7 и 2 для reqID 3. После первого запроса я получаю:

ReqID: 7 с весами: [1,0]

, который OK. Но после 2-го запроса я получаю:

ReqID: 7 с весами: [1,0] ReqID: 3 с весами: [1,0, 2,0]

что неправильно! Правильным должно быть:

ReqID: 7 с весами: [1,0] ReqID: 3 с весами: [2,0]

Таким образом, я получаю счет (weightFreq) для reqID 3 равен 3 (1+ 2) вместо 2, который является правильным.

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

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

Это говорит о нескольких различных реализациях Multimap (ListMultimap, SetMultimap и т.д.), для альтернативного использования карты коллекций или asMap для того, чтобы делать то же самое через Google Guava и т. д.

Я не уверен, понял ли я что-то неправильно в отношении мультиплексов или если у меня есть некоторая ошибка в моей логике относительно предыдущего метода getter. Любые указания будут оценены.

Answer 1

Реальная идея, что здесь происходит, но слишком много для комментариев. Вы можете, конечно, исправить это, сначала упростите его.Тест

key == request.reqID 

, скорее всего, не так, как вы имеете дело с Integer с, а не с int с. В таких случаях никогда не полагайтесь на авто (un) бокс и используйте либо equals, либо intValue.

Ваш код является сложным. Вы хотите иметь дело с записями для request.reqID, так что получить их:

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

Отбросьте внешний контур и if.

Simplify более, например, с помощью петли Еогеасп

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

Когда все само собой материал, нет, вы, вероятно, увидеть проблему сразу.

Answer 2

Возможно, вы работаете в многопоточной среде. Похоже, что вы могли бы упростить код, сохранить память, а также сделать ваши вычисления атомного путем введения:

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){ 
     ... 
    } 
} 

И затем использовать map.putIfAbsent сделать атомные вставки пустого RequestInfo.