我已经实现了一种类似LFU的Web缓存替换算法,该算法的工作原理如下:在每个请求中,我分配的权重为1 /(p ^ reqIndex)给定,其中p是权重因子,reqIndex是请求(第一个请求的索引) ,第二个请求等)。例如,对于p = 0.5,对于第一个请求,权重为1;对于第二个请求,权重为2;对于第三个请求,权重为4。然后,为了计算每个请求项的得分(我将其称为加权频率,weightFreq),我简单地对相应的权重求和。被请求的项目仅通过数字ID(整数)来区分,我将其称为请求ID(reqID)。例如,如果第一个请求是针对ID为7的商品,第二个请求为ID为3的商品,第三次为ID为7的商品,那么ID为7的商品的得分应为1 + 4 = 5 (第1个请求的权重+第3个请求的权重),而ID为3的商品应获得2分(第2个请求的权重)。
我使用ListMultimap(通过Google Guava库)作为权重,因为我应该能够为单个键(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方法:
/**
* 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,第二个是reqID3。在第一个请求之后,我得到:
ReqID:7,权重:[1.0]
没关系但是在第二个请求之后,我得到:
ReqID:7,权重:[1.0]
ReqID:3,权重:[1.0,2.0]
错了!正确的应该是:
ReqID:7,权重:[1.0]
ReqID:3,权重:[2.0]
因此,我获得reqID 3的分数(weightFreq)等于3(1 + 2),而不是正确的2。
请注意,我仅在过去的7个月左右的时间里学习编程,这是我第一次使用multimap(因为我需要为单个键分配多个值)。我知道了这样做的想法以及来自此处的相关信息:
http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Multimap.html
它说明了多图的几种不同实现(ListMultimap,SetMultimap等),以替代使用集合图或asMap通过Google Guava等进行相同操作的方法。
我不确定我是否了解多地图方面的问题,或者我对先前的getter方法的逻辑是否有错误。任何指导将不胜感激。
最佳答案
没有真正的想法,这是怎么回事,但有太多话要说。您一定可以修复它,只需先对其进行简化即可。考试
key == request.reqID
这很可能是错误的,因为您正在处理
Integer
而不是int
。在这种情况下,切勿依赖自动装箱并使用equals
或intValue
。您的代码过于复杂。您要处理
request.reqID
的条目,因此请获取它们:List<Double> tempWeights = weights.get(request.reqID);
删除外部循环和
if
。简化更多操作,例如,使用foreach循环
for (double d : tempWeights) sum += d;
当所有不必要的东西都消失了时,您可能会立即看到问题所在。