基本算法描述如下:
1、每個廣告增加權重
2、將所有匹配廣告的權重相加sum，
3、以相加結果為隨機數的種子，生成1~sum之間的隨機數rd
4、.接著遍歷所有廣告，訪問順序可以隨意.將當前節點的權重值加上前面訪問的各節點權重值得curWt,判斷curWt >= rd,如果條件成立則返回當前節點,如果不是則繼續累加下一節點. 直到符合上面的條件,由于rd<=sum 因此一定存在curWt>=rd。
特別說明：
此算法和廣告的順序無關
|
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.LinkedHashMap;import java.util.List;import java.util.Map;public class Test { /** * @param args */ @SuppressWarnings("unchecked") public static void main(String[] args) { List<Node> arrNodes = new ArrayList<Node>(); Node n = new Node(10, "測試1"); arrNodes.add(n); n = new Node(20, "測試2"); arrNodes.add(n); n = new Node(30, "測試3"); arrNodes.add(n); n = new Node(40, "測試4"); arrNodes.add(n); //Collections.sort(arrNodes, new Node()); Map<String, Integer> showMap = null; int sum = getSum(arrNodes); int random = 0; Node kw = null; for(int k = 0; k < 20; k++) { showMap = new LinkedHashMap<String, Integer>(); for(int i = 0; i < 100; i++) { random = getRandom(sum); kw = getKW(arrNodes, random); if(showMap.containsKey(kw.kw)) { showMap.put(kw.kw, showMap.get(kw.kw) + 1); } else { showMap.put(kw.kw, 1); } //System.out.println(i + " " +random + " " + getKW(arrNodes, random)); } System.out.print(k + " "); System.out.println(showMap); } } public static Node getKW(List<Node> nodes, int rd) { Node ret = null; int curWt = 0; for(Node n : nodes){ curWt += n.weight; if(curWt >= rd) { ret = n; break; } } return ret; } public static int getSum(List<Node> nodes) { int sum = 0; for(Node n : nodes) sum += n.weight; return sum; } public static int getRandom(int seed) { return (int)Math.round(Math.random() * seed); }}class Node implements Comparator{ int weight = 0; String kw = ""; public Node() {} public Node(int wt, String kw) { this.weight = wt; this.kw = kw; } public String toString(){ StringBuilder sbBuilder = new StringBuilder(); sbBuilder.append(" weight=").append(weight); sbBuilder.append(" kw").append(kw); return sbBuilder.toString(); } public int compare(Object o1, Object o2) { Node n1 = (Node)o1; Node n2 = (Node)o2; if(n1.weight > n2.weight) return 1; else return 0; }} |
