海量用户积分排名算法探讨

看到一篇文章介绍用户排名算法，自己对其中的一个实现了下， 背景介绍： 某海量用户网站，用户拥有积分，积分可能会在使用过程中随时更新。现在要为该网站设计一种算法，在每次用户登录时显示其当前积分排名。用户最大规模为2亿；积分为非负整数，且小于100万 算法： 仔细观察一下积分变化对排名的具体影响，可以发现某用户的积分从s变为s+n，积分小于s或者大于等于s+n的其他用户排名实际上并不会受到影响，只有积分在[s,s+n)区间内的用户排名会下降1位。我们可以用于一个大小为100,000,000的数组表示积分和排名的对应关系，其中rank[s]表示积分s所对应的排名。初始化时，rank数组可以由user_score表在O(n)的复杂度内计算而来。用户排名的查询和更新基于这个数组来进行。查询积分s所对应的排名直接返回rank[s]即可，复杂度为O(1)；当用户积分从s变为s+n，只需要把rank[s+1]到rank[s+n]这n个元素的值减少1即可，复杂度为O(n)。 算法特点 优点：积分排名数组比区间树更简单，易于实现；排名查询复杂度为O(1)；排名更新复杂度O(n)，在积分变化不大的情况下非常高效。 缺点：当n比较大时，需要更新大量元素， 其中发现隐含的问题是，一个积分可能是没有人使用的，因此需要存储一个积分的使用人数，实现如下：

package name.codeboy.rank;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class RankCheck {
	private int maxScore;
	private int[] rankes;
	private int[] scoreCount;
	
	public RankCheck(int maxScore) {
		super();
		this.maxScore = maxScore;
		this.rankes = new int[this.maxScore];
		scoreCount = new int[this.maxScore];
		Arrays.fill(this.rankes, 0, this.rankes.length-1, -1);
	}
	
	public void initData() {
		for (int i=0; i=maxScore || dest<0 || dest>=maxScore) {
			throw new IllegalArgumentException("change from " + src + "to dest " + dest + " not ellegal");
		}
		if (scoreCount[src] == 0) {
			throw new IllegalArgumentException("score " + src + " is not in db");
		}
		for (int i=src+1; i<=dest; i++) {
			if (rankes[i] > 0) {
				rankes[i]--;
			}
		}
		scoreCount[src]--;
		scoreCount[dest]++;
	}
	
	public void addScore(int score) {
		if ( score >= maxScore || score < 0) {
			throw new IllegalArgumentException("score " + score + "not illegal");
		}
		scoreCount[score]++;
		for (int i=score+1; i= maxScore || score < 0) {
			throw new IllegalArgumentException("score " + score + "not illegal");
		}
		if (scoreCount[score] == 0) {
			throw new IllegalArgumentException("score " + score + " not in db");
		}
		scoreCount[score]--;
		for (int i=score+1; i= maxScore || score < 0) {
			throw new IllegalArgumentException("score " + score + "not illegal");
		}
		if (scoreCount[score] == 0) {
			throw new IllegalArgumentException("score " + score + "is not in db");
		}
		return rankes[score];
	}
	public int getScoreCount(int score) {
		if ( score >= maxScore || score < 0) {
			throw new IllegalArgumentException("score " + score + "not illegal");
		}
		return scoreCount[score];
	}
	
	public List getAllScore() {
		List result = new LinkedList();
		for (int i=0; i allScore) {
		for (Integer t : allScore) {
			System.out.print(t);
			System.out.print("\t");
		}
		System.out.print("\n");
		
		
	}

}

原文算法链接