Java修道之路:Java实现排名

前一篇文章《Java修道之路:MySQL排名》写了如何用SQL来实现排名,这里想用java写一下排名算法,其实主要是想了解下两种方法的耗时,因为之前有同事说SQL的耗时会比Java少,所以想测试一下。

这里先说结果,我写的方法,测出来的结果,Java会比SQL快,也许是我的SQL写得并不优导致的,但是SQL一旦成形,就可以直接套用,使用比较方便,速度呢,1万条数据耗时相差无几,10万条数据(2个字段)耗时相差也就600毫秒左右。

下面贴出代码(数据库连接代码就略了):

/**
 * Java算法生成连续重复排名
 */
public Long rankByJavaContinuousAndRepeat() throws Exception {
	
	Long start = System.currentTimeMillis();
	
	String sql = "select id, score from score order by score desc";
	
	Connection conn = getConn();
	File outFile = new File("D:/outFile1.txt");
	PrintWriter pw = new PrintWriter(new FileWriter(outFile));
	
	try {
		Statement stmt = conn.createStatement();
		ResultSet rs = stmt.executeQuery(sql);
		
		List<Score> recordList = new ArrayList<Score>();
		
		while (rs.next()) {
			recordList.add(new Score(rs.getInt("id"), rs.getInt("score")));
		}
		
		// 排序Map<Integer, List<Score>>,将list的第一个值放入Map,key为1,value为List<Score>
		// 如果list的第二个值等于key为1的value的list最后一个值,那么放入该list中,
		// 否则放入Map,key为2,以此类推,最后遍历Map,得到重复连续排名
		Map<Integer, List<Score>> rankMap = new HashMap<Integer, List<Score>>();
		int rank = 0;
		
		for (int i = 0; i < recordList.size(); i ++) {
			// 取出map中最后一名的Score列表
			List<Score> rankList = rankMap.get(rank);
			// 该名与上名比较
			if (rankList != null && recordList.get(i).getScore() == rankList.get(rankList.size() - 1).getScore()) {
				// 相等这加入到List
				rankList.add(recordList.get(i));
			} else {
				// 不相等,rank++
				rank ++;
				List<Score> newRankList = new ArrayList<Score>();
				newRankList.add(recordList.get(i));
				rankMap.put(rank, newRankList);
			}
		}
		
		pw.println("============= Java连续重复 =============");
		
		// 将名次输出到文本
		for (int i = 1; i <= rankMap.keySet().size(); i ++) {
			List<Score> rankList = rankMap.get(i);
			for (int j = 0; j < rankList.size(); j ++) {
				pw.println(rankList.get(j).getId() + "\t\t" + 
							rankList.get(j).getScore() + "\t\t" + 
							i);
			}
		}
	} finally {
		conn.close();
		pw.close();
	}
	
	return System.currentTimeMillis() - start;
}
/**
 * Java算法生成不连续重复排名
 */
public Long rankByJavaUncontinuousAndRepeat() throws Exception {
	
	Long start = System.currentTimeMillis();
	
	String sql = "select id, score from score order by score desc";
	
	Connection conn = getConn();
	File outFile = new File("D:/outFile2.txt");
	PrintWriter pw = new PrintWriter(new FileWriter(outFile));
	
	try {
		Statement stmt = conn.createStatement();
		ResultSet rs = stmt.executeQuery(sql);
		
		List<Score> recordList = new ArrayList<Score>();
		
		while (rs.next()) {
			recordList.add(new Score(rs.getInt("id"), rs.getInt("score")));
		}
		
		// 排序Map<Integer, List<Score>>,将list的第一个值放入Map,key为1,value为List<Score>
		// 如果list的第二个值等于key为1的value的list最后一个值,那么放入该list中,
		// 否则放入Map,key为1+key为1的value的List的size,以此类推,最后遍历Map,得到重复连续排名
		// 只能使用有序的Map,因为无法通过排名顺序获取Map的名次顺序
		Map<Integer, List<Score>> rankMap = new LinkedHashMap<Integer, List<Score>>();
		int rank = 0;
		
		for (int i = 0; i < recordList.size(); i ++) {
			// 取出map中最后一名的Score列表
			List<Score> rankList = rankMap.get(rank);
			// 该名与上名比较
			if (rankList != null && recordList.get(i).getScore() == rankList.get(rankList.size() - 1).getScore()) {
				// 相等这加入到List
				rankList.add(recordList.get(i));
			} else {
				// 不相等,rank加上List的size
				if (rankList != null) {
					rank += rankList.size();
				} else {
					rank ++;
				}
				List<Score> newRankList = new ArrayList<Score>();
				newRankList.add(recordList.get(i));
				rankMap.put(rank, newRankList);
			}
		}
		
		pw.println("============= Java不连续重复 =============");
		
		// 将名次输出到文本
		for (Entry<Integer, List<Score>> entry : rankMap.entrySet()) {
			for (Score score : entry.getValue()) {
				pw.println(score.getId() + "\t\t" + 
						score.getScore() + "\t\t" + 
							entry.getKey());
			}
		}
	} finally {
		conn.close();
		pw.close();
	}
	
	return System.currentTimeMillis() - start;
}
/**
 * SQL生成连续重复排名
 */
public Long rankBySQLContinuousAndRepeat() throws Exception {

	Long start = System.currentTimeMillis();
	
	String sql = 
		"select  " + 
		"	BASE.id,  " + 
		"	BASE.score,  " + 
		//"	-- 如果score等于上一行的score那么名次和上一行相同,否则+1 " + 
		"	if ( " + 
		"		BASE.score = ( " + 
		"			select LASTROW.score from ( " + 
		"				select T.*, @row := @row + 1 as row " + 
		"				from  " + 
		"					(select * from score order by score desc, id) as T, " +  
		"					(select @row := 0) as ROW " + 
		"			) as LASTROW " + 
		"			where LASTROW.row = BASE.row - 1 " +  
		"		), " + 
		"		@rank, " + 
		"		@rank := @rank + 1 " + 
		"	) as rank  " + 
		"from  " + 
		"	( " + 
		"		select T.*, @row := @row + 1 as row " + 
		"		from  " + 
		"			(select * from score order by score desc, id) as T, " +  
		"			(select @row := 0) as ROW " + 
		"	) as BASE, " + 
		"	(select @rank := 0) as RANK";
	
	Connection conn = getConn();
	File outFile = new File("D:/outFile3.txt");
	PrintWriter pw = new PrintWriter(new FileWriter(outFile));
	
	try {
		Statement stmt = conn.createStatement();
		ResultSet rs = stmt.executeQuery(sql);
		
		pw.println("============= Java不连续重复 =============");
		
		while (rs.next()) {
			// 将名次输出到文本
			pw.println(rs.getInt("id") + "\t\t" + 
					rs.getInt("score") + "\t\t" + 
					rs.getInt("rank"));
		}
		
	} finally {
		conn.close();
		pw.close();
	}
	
	return System.currentTimeMillis() - start;
	
}
/**
 * SQL生成不连续重复排名
 */
public Long testRankUnContinuousAndRepeat() throws Exception {

	Long start = System.currentTimeMillis();
	
	String sql = 
		"select  " + 
		"	BASE.id,  " + 
		"	BASE.score,  " + 
		//"	-- 如果score等于上一行的score那么名次和上一行相同, " + 
		//"	-- 否则等于连续不重复排序出来的名次 " + 
		"	if ( " + 
		"		BASE.score = ( " + 
		"			select LASTROW.score from ( " + 
		"				select T.*, @row := @row + 1 as row " + 
		"				from  " + 
		"					(select * from score order by score desc, id) as T, " +  
		"					(select @row := 0) as ROW " + 
		"			) as LASTROW " + 
		"			where LASTROW.row = BASE.row - 1 " +  
		"		), " + 
		//"		-- 如果是相等的score, 那么rank就是BASE中该score的第一个row " + 
		//"		-- (不等的时候会对@rank进行赋值,就是赋值为第一个row) " + 
		"		@rank, " + 
		//"		-- 如果不是相等的,那么rank就是BASE中的第一个row " + 
		"		@rank := BASE.row " + 
		"	) as rank  " + 
		"from  " + 
		"	( " + 
		"		select T.*, @row := @row + 1 as row " + 
		"		from  " + 
		"			(select * from score order by score desc, id) as T, " +  
		"			(select @row := 0) as ROW " + 
		"	) as BASE, " + 
		"	(select @rank := 0) as RANK";

	
	Connection conn = getConn();
	File outFile = new File("D:/outFile4.txt");
	PrintWriter pw = new PrintWriter(new FileWriter(outFile));
	
	try {
		Statement stmt = conn.createStatement();
		ResultSet rs = stmt.executeQuery(sql);
		
		pw.println("============= Java不连续重复 =============");
		
		while (rs.next()) {
			// 将名次输出到文本
			pw.println(rs.getInt("id") + "\t\t" + 
					rs.getInt("score") + "\t\t" + 
					rs.getInt("rank"));
		}
		
	} finally {
		conn.close();
		pw.close();
	}
	
	return System.currentTimeMillis() - start;
	
}
// 测试代码
@Test
// 648
// 988
public void test1() throws Exception {
	System.out.println("Java连续重复:" + rankByJavaContinuousAndRepeat() + "ms");
}

@Test
// 616
// 998
public void test2() throws Exception {
	System.out.println("Java不连续重复:" + rankByJavaUncontinuousAndRepeat() + "ms");
}

@Test
// 696
// 1563
public void test3() throws Exception {
	System.out.println("SQL连续重复:" + rankBySQLContinuousAndRepeat() + "ms");
}

@Test
// 698
// 1580
public void test4() throws Exception {
	System.out.println("SQL不连续重复:" + testRankUnContinuousAndRepeat() + "ms");
}

测试代码上面注释的数字分别是,1万条数据和10万条数据的耗时,供参考。

PS:之前测试4个方法是写在一个测试方法中的,但是发现貌似方法之间会互相影响,比如第一个方法执行了700+ms,第二个方法单独测试应该在700ms左右,却只耗时110+ms,把两个方法顺序调换,结果相同,就很莫名其妙的了….估计和数据库连接有关吧,以后慢慢再研究。

本文《Java修道之路:Java实现排名》来自 www.juwends.com ,欢迎转载或CV操作,但请注明出处,谢谢!