Weight algorithm implemented in Java (show ads by weight)

  • 2020-04-01 03:51:48
  • OfStack

The basic algorithm is described as follows:

1. Increase the weight of each advertisement
2. Sum is the weight of all matched advertisements.
3. Take the sum result as the seed of random number, and generate the random number rd between 1 and sum
4. Next, all ads are traversed, and the access order is optional. Add the weight value of the current node to the weight value of each node previously visited to be worth curWt, and judge curWt > =   Rd, returns the current node if the condition is true, and accumulates the next node if it is not. =sum so there must be curWt> = rd.
Special note:

This algorithm is independent of the order of ads


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 {

  
  @SuppressWarnings("unchecked")
  public static void main(String[] args) {
    
    List<Node> arrNodes = new ArrayList<Node>();
    Node n = new Node(10, " test 1");
    arrNodes.add(n);
    n = new Node(20, " test 2");
    arrNodes.add(n);
    n = new Node(30, " test 3");
    arrNodes.add(n);
    n = new Node(40, " test 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;
  }
}

Related articles: