简介
需求： 在权重随机中需要去重处理。
主体思想：
- 使用遮罩来确定某个元素是否已经被随机出来了。
- 笔者认为使用遮罩比起使用一个新的列表的好处是会减少GC的压力。
主要内容
实现语言采取Java， 以下代码仅做示意使用。
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
@Data
public class WeightObject<T> {
private T obj;
private int weight;
}
public final class Util {
public static int mask(int v, int i) {
return v | (1 << i);
}
public static boolean isMask(int v, int i) {
return (v & (1 << i)) != 0;
}
/**
* 计算总权重
*/
public static<T> int totalWeight(List<WeightObject<T>> list, int mask){
int total = 0;
for (int i = 0; i < list.size(); i++) {
if (isMask(mask, i)) {
continue;
}
total += list.get(i).getWeight();
}
return total;
}
public static int random(int max) {
return 0; // 省略
}
public static<T> List<T> weightRandomDistinct(List<WeightObject<T>> list, int count) {
int mask = 0;
if(list.size() >= 32) {
// 此处可以考虑使用 long类型， 或者使用 BitSet, 或者回归var tmp = new ArrayList(list); tmp.remove(j) 的形式。
throw new IllegalArgumentException("size must be less than 32");
}
var result = new ArrayList<T>(count);
for (int i = 0; i < count; i++) {
var total = totalWeight(list, mask);
var randomWeight = random(total);
var currentWeight = 0;
for (int j = 0; j < list.size(); j++) {
if (isMask(mask, j)) {
continue;
}
var element = list.get(j);
currentWeight += element.getWeight();
if (currentWeight >= randomWeight) {
mask = mask(mask, j);
result.add(element.getObj());
break;
}
}
}
return result;
}
}
|
核心思想就是计算总权重的时候使用遮罩去除某些元素， 在遍历元素的时候， 也使用遮罩去除某些元素。
如果使用 var tmp = new ArrayList(list); tmp.remove(j) 的形式， 每次进行权重随机的时候都需要创建一个新的 ArrayList ， 使用之后就抛弃， 应该会产生较大的GC压力。 比如 16随3， 30 随3 的情况下， 使用遮罩之后，GC方面应该就会好很多。
