敗者ツリー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 ([email protected])

 * @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.2 GhzCPUのマシン上、シングルスレッドでも10秒しかかからなかった.実は、外部の列の大部分の時間はIO上、特にCPU性能の良いワークステーション、サーバーに費やされた.