# 072. 基于 storm 完成 LRUMap 中 topn 热门商品列表的算法讲解与编写
# top n 简易算法
public static void main(String[] args) {
/**
* top n 简易算法：手写思路
* top 3 列表： 5、3、1
* 比如来一个 6，那么比 5 大，把 5 所在位置往后移位。最后把 6 放到 第一位，
* 变成：6、5、3
*/
int n = 10;
int[] topn = new int[n];
// 循环 n 次，模拟有这么多数据需要计算
for (int i = 0; i < 100; i++) {
int randomNum = RandomUtils.nextInt(100);
// int randomNum = i;
// 每次都从第一个开始比较
for (int j = 0; j < topn.length; j++) {
int target = topn[j];
if (randomNum > target) {
// 从当前位置往后移动一位
System.arraycopy(topn, j, topn, j + 1, n - (j + 1));
topn[j] = randomNum;
break;
}
}
}
// 某一次的输出结果 [99, 99, 99, 99, 99, 96, 93, 93, 91, 91]
System.out.println(Arrays.toString(topn));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 商品列表计算 top n
public class ProductCountBolt extends BaseRichBolt {
private LRUMap<Long, Long> countMap = new LRUMap(100);
@Override
public void prepare(Map stormConf, TopologyContext context, OutputCollector collector) {
// 启动一个线程，1 分钟计算一次
new Thread(new Runnable() {
@Override
public void run() {
int n = 3;
Map.Entry<Long, Long>[] top = new Map.Entry[n];
while (true) {
Arrays.fill(top, null);
Utils.sleep(6000);
for (Map.Entry<Long, Long> entry : countMap.entrySet()) {
long value = entry.getValue();
for (int i = 0; i < top.length; i++) {
Map.Entry<Long, Long> targetObj = top[i];
if (targetObj == null) {
top[i] = entry;
break;
}
long target = targetObj.getValue();
if (value > target) {
// 使用数组 + 系统原生 copy ，性能很棒
// 而且 top n 不大的话，更快
System.arraycopy(top, i, top, i + 1, n - (i + 1));
top[i] = entry;
break;
}
}
}
System.out.println(Thread.currentThread().getName() + "：" + Arrays.toString(top));
}
}
}).start();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
启动 storm 后，来测试统计是否正确
访问：http://eshop-cache03/product?method=product&productId=11&shopId=1
这里为了能让商品 id 能落到同一个 task 上，选择了商品 id：2、5、8、11 总共 4个进行访问次数测试
统计输出如下
商品 5,次数 1
商品 2,次数 1
Thread-41：[null, null, null]
Thread-40：[null, null, null]
Thread-39：[5=1, 2=1, null]
// 后面的非 39 线程的我就删除了，为了看着清晰一点
商品 2,次数 2
Thread-39：[2=2, 5=1, null]
Thread-39：[2=2, 5=1, null]
Thread-39：[2=2, 5=1, null]
Thread-39：[2=2, 5=1, null]
Thread-39：[2=2, 5=1, null]
Thread-39：[2=2, 5=1, null]
商品 8,次数 1
Thread-39：[2=2, 5=1, 8=1] // top 列表中 3 个都满了
Thread-39：[2=2, 5=1, 8=1]
商品 11,次数 1 // 再来一个 11 ，看看效果
Thread-39：[2=2, 5=1, 8=1] // 结果没有看到 11，这个很正常，访问次数都不比现在的大，所以没有入围
商品 11,次数 2
Thread-39：[2=2, 11=2, 5=1] // 当访问两次后，商品 8 被挤掉了
商品 11,次数 3
Thread-39：[11=3, 2=2, 5=1]
Thread-39：[11=3, 2=2, 5=1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
从日志测试来看，这个算法是没有问题的
# 另外一种简单的 top n 算法
这种 topn 算法没有那么麻烦，思路也很清晰
public static void topn() {
int n = 10;
int[] topn = new int[n];
// 循环 n 次，模拟有这么多数据需要计算
for (int i = 0; i < 100; i++) {
int randomNum = RandomUtils.nextInt(100);
// int randomNum = i;
for (int j = 0; j < topn.length; j++) {
int target = topn[j];
if (randomNum >= target) {
topn[j] = randomNum;
randomNum = target;
}
}
}
System.out.println(Arrays.toString(topn));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18