The basic algorithm is described as follows.
1. Each advertisement increases weight
2. sum the weights of all matching ads sum.
3. Use the sum result as the seed of the random number to generate a random number between 1 and sum rd
4.. Then traverse all the advertisements, the order of visit can be arbitrary . The weight value of the current node plus the weight value of the nodes visited before curWt, determine curWt >= rd, if the condition is established then return to the current node, if not then continue to add the next node. Until the above conditions are met, because rd<=sum so there must be curWt>=rd.
Special Notes:
This algorithm has nothing to do with the order of the ads
import ;
import ;
import ;
import ;
import ;
import ;
public class Test {
/**
* @param args
*/
@SuppressWarnings("unchecked")
public static void main(String[] args) {
List<Node> arrNodes = new ArrayList<Node>();
Node n = new Node(10, "Test 1");
(n);
n = new Node(20, "Test 2");
(n);
n = new Node(30, "Test 3");
(n);
n = new Node(40, "Test 4");
(n);
//(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(()) {
(, () + 1);
} else {
(, 1);
}
//(i + " " +random + " " + getKW(arrNodes, random));
}
(k + " ");
(showMap);
}
}
public static Node getKW(List<Node> nodes, int rd) {
Node ret = null;
int curWt = 0;
for(Node n : nodes){
curWt += ;
if(curWt >= rd) {
ret = n;
break;
}
}
return ret;
}
public static int getSum(List<Node> nodes) {
int sum = 0;
for(Node n : nodes)
sum += ;
return sum;
}
public static int getRandom(int seed) {
return (int)(() * seed);
}
}
class Node implements Comparator{
int weight = 0;
String kw = "";
public Node() {}
public Node(int wt, String kw) {
= wt;
= kw;
}
public String toString(){
StringBuilder sbBuilder = new StringBuilder();
(" weight=").append(weight);
(" kw").append(kw);
return ();
}
public int compare(Object o1, Object o2) {
Node n1 = (Node)o1;
Node n2 = (Node)o2;
if( > )
return 1;
else
return 0;
}
}