MyException - 我的异常网
当前位置:我的异常网» 数据库 » 败者树的Java兑现

败者树的Java兑现

www.myexceptions.net  网友分享于:2015-08-26  浏览:3次
败者树的Java实现

败者树在数据结构的课本上就有,它可以直接获得k个记录中的最小值/最大值,并且调整的时间复杂度为log(k),因此可以在多路归并排序中用来加速多个多并段中最小值/最大值的查找,从而提高归并的速度。

败者树的Java代码如下,其中的Result是待排记录的抽象:

/*
 * ResultSet.java     0.0.1 2013/04/04 
 * Copyright(C) 2013 db-iir RUC. All rights reserved. 
 */
import java.util.ArrayList;

/** 
 * This Class implements the loser tree algorithm.
 * 
 * @author  Hank Bian (bianhaoqiong@163.com)
 * @version 0.0.1, 2013/04/04
 */
public class LoserTree
{
	private int[] tree = null;// 以顺序存储方式保存所有非叶子结点
	private int size = 0;
	private ArrayList<Result> leaves = null;// 叶子节点

	public LoserTree(ArrayList<Result> initResults)
	{
		this.leaves = initResults;
		this.size = initResults.size();
		this.tree = new int[size];
		for (int i = 0; i < size; ++i)
		{
			tree[i] = -1;
		}
		for (int i = size - 1; i >= 0; --i)
		{
			adjust(i);
		}
	}

	public void del(int s)
	{
		leaves.remove(s);
		size--;
		tree = new int[size];
		for (int i = 0; i < size; ++i)
		{
			tree[i] = -1;
		}
		for (int i = size - 1; i >= 0; --i)
		{
			adjust(i);
		}
	}

	public void add(Result leaf, int s)
	{
		leaves.set(s, leaf);// 调整叶子结点
		adjust(s);// 调整非叶子结点
	}

	public Result getLeaf(int i)
	{
		return leaves.get(i);
	}

	public int getWinner()
	{
		return tree[0];
	}

	private void adjust(int s)
	{
		// s指向当前的值最小的叶子结点(胜者)
		int t = (s + size) / 2;// t是s的双亲

		while (t > 0)
		{
			if (s >= 0
					&& (tree[t] == -1 || leaves.get(s).compareTo(
							leaves.get(tree[t])) > 0))
			{
				// 将树中的当前结点指向其子树中值最小的叶子
				int tmp = s;
				s = tree[t];
				tree[t] = tmp;
			}
			t /= 2;
		}
		tree[0] = s;// 树根指向胜者
	}
}

在产生初始归并段时,使用ArrayList和Collections.sort()就可以了,这个是一种改进的归并内部排序算法,我试验过,效率很高的,给13个100万条的字符串列表(每个字符串约10个字符、有重复)排序,在四核3.2GhzCPU的机器上、单线程也只用了十秒钟而已。其实外排很大一部分的时间消耗在IO上,特别是对于CPU性能好的工作站、服务器。

文章评论

每天工作4小时的程序员
每天工作4小时的程序员
 程序员的样子
程序员的样子
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
我的丈夫是个程序员
我的丈夫是个程序员
为什么程序员都是夜猫子
为什么程序员都是夜猫子
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员应该关注的一些事儿
程序员应该关注的一些事儿
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
如何成为一名黑客
如何成为一名黑客
那些争议最大的编程观点
那些争议最大的编程观点
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
旅行,写作,编程
旅行,写作,编程
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
10个调试和排错的小建议
10个调试和排错的小建议
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
总结2014中国互联网十大段子
总结2014中国互联网十大段子
编程语言是女人
编程语言是女人
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
程序员必看的十大电影
程序员必看的十大电影
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
鲜为人知的编程真相
鲜为人知的编程真相
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
一个程序员的时间管理
一个程序员的时间管理
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
中美印日四国程序员比较
中美印日四国程序员比较
我是如何打败拖延症的
我是如何打败拖延症的
漫画:程序员的工作
漫画:程序员的工作
Java程序员必看电影
Java程序员必看电影
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
代码女神横空出世
代码女神横空出世
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有