Kth Order Statistics/Partial ordering – Using Tournament Algorithm (optimized)

This blog entry is in continuation to my previous entries about finding 2nd Minimum and more generic Kth Order statistic in linear time (asymptotic) using dynamic programming principles and tournament algorithm in particular. Here I talk about slight variation to the tournament algorithm implementation that results in better runtime performance. Using modification to our earlier logic we can find Kth min without any need for back-tracking. We still need to build the tournament tree, but the new mechanism results in better runtime efficiency and is also simpler to implement (compared to what we did earlier).

The Idea

The idea is that if keep track of nodes a given node is compared at each level as the node progress in tournament method, we have sufficient information to deduct Kth minimum without ever back tracking the tournament tree. To find second minimum, we inspect the root node’s defeated-node-list for the minimum value. Once we have second minimum; for finding third min we combine second min node’s defeated-node-list to minimum (root) node's defeated node-list and find the third minimum from the resulting set. This method may need some additional processing while constructing tournament tree (and perhaps little more memory), but it is worth the effort as it saves us from backtracking tournament tree to find Kth min.

Details

Referring to the same sample list used previously. If we were to keep track of defeated nodes, we can obtain something like the following:

We wrap the input data into a node structure which can encapsulate the key and also the value (in typical scenario there will be some data value that these keys would be pointing to). In addition to key and value, each node contains a list (defeated-nodes linked-list) of nodes. As a node progress to next level, it appends the defeated node to its defeated-node-list.

After constructing the tournament tree and generating node-list of defeated nodes, for each node, can easily find the Kth minimum by traversing the graph from root-node.

For example, here's how we can find 2nd, 3rd and 4th min for the example above:

2nd Minimum: Looking at the node-list for root node, we can find the second minimum without any back-tracking. Since the root node must have defeated second min node on its way to last level, second min must be the minimum node in the defeated-node-list for the root node. For the case above from the node-list we can find the second minimum value as 2.

3rd Minimum: To find third minimum, we need to go to second minimum node, get its node-list and then find the third minimum from among the combined list for the minimum and second minimum. Since we already have node with value 2 in node-list of root node, we obtain its node list and find the third least from the resulting set. For the above case it will be 3 (the node with key 2 returns 14 and 5 which is larger than 3 which root node holds).

4th Minimum: Continuing the same idea, we obtain node-list for node with key 3 (found in node-list of root); combine it with node-list of min and second min, to find the 4th min from the resulting set.

In general, the root node has node-list which is log(n) size which contains the second min. From second min we can obtain its node-list and combined with node-list of min, we can obtain third min and so on. This mechanism does not require any backtracking, once we build node-list for each progressing node. 

Code

Can also be downloaded from here -  KThMinimum2.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/\*\*
 \* Copyright (c) 2010-2020 Malkit S. Bhasin. All rights reserved.
 \* 
 \* All source code and material on this Blog site is the copyright of Malkit S.
 \* Bhasin, 2010 and is protected under copyright laws of the United States. This
 \* source code may not be hosted on any other site without my express, prior,
 \* written permission. Application to host any of the material elsewhere can be
 \* made by contacting me at mbhasin at gmail dot com
 \* 
 \* I have made every effort and taken great care in making sure that the source
 \* code and other content included on my web site is technically accurate, but I
 \* disclaim any and all responsibility for any loss, damage or destruction of
 \* data or any other property which may arise from relying on it. I will in no
 \* case be liable for any monetary damages arising from such loss, damage or
 \* destruction.
 \* 
 \* I further grant you ("Licensee") a non-exclusive, royalty free, license to
 \* use, modify and redistribute this software in source and binary code form,
 \* provided that i) this copyright notice and license appear on all copies of
 \* the software;
 \* 
 \* As with any code, ensure to test this code in a development environment
 \* before attempting to run it in production.
 \* 
 \* @author Malkit S. Bhasin
 \* 
 \*/

public class KThMinimum2 {

	/\*\*
	 \* @param inputList
	 \*            unordered linked list of Node<T,X>
	 \* @param k
	 \*            order of minimum value desired
	 \* @return kth minimum Node<T,X>
	 \* @throws Exception
	 \*/
	public static Node<Integer, Object> getKthMinimum(
			List<Node<Integer, Object>> inputList, int k) throws Exception {
		return findKthMinimum(inputList, k).get(k - 1);
	}

	/\*\*
	 \* @param inputList
	 \*            unordered linked list of non-negative integers
	 \* @param k
	 \*            ordered number of minimum values
	 \* @return k ordered minimum values
	 \* @throws Exception
	 \*/
	public static List<Node<Integer, Object>> getMinimumKSortedElements(
			List<Node<Integer, Object>> inputList, int k) throws Exception {
		return findKthMinimum(inputList, k);
	}

	/\*\*
	 \* First output tree will be obtained using tournament method. During each
	 \* round, adjacent nodes are compared against, the lower of two moves to
	 \* next round. The defeated node is added to list of defeated nodes
	 \* maintained at each node.
	 \* 
	 \* Kth minimum is obtained by going through list of defeated nodes, starting
	 \* from the root node (minimum node).
	 \* 
	 \* @param inputArray
	 \* @param k
	 \* @return ordered array of k minimum elements
	 \* @throws Exception
	 \*/
	private static List<Node<Integer, Object>> findKthMinimum(
			List<Node<Integer, Object>> inputList, int k) throws Exception {
		List<List<Node<Integer, Object>>> outputTree = getOutputTree(inputList);
		// printList(outputTree);
		return getKthMin(outputTree, k);
	}

	private static List<Node<Integer, Object>> getKthMin(
			List<List<Node<Integer, Object>>> outputTree, int k)
			throws Exception {
		int size = outputTree.size();
		if (k <= 0) {
			throw new IllegalArgumentException(
					"Please provide valid integer argument k [0," + size + ")");
		}

		List<Node<Integer, Object>> orderedList = new LinkedList<Node<Integer, Object>>();
		Node<Integer, Object> rootNode = outputTree.get(size - 1).get(0);
		orderedList.add(rootNode);
		if (k == 1) {
			return orderedList;
		}

		List<Node<Integer, Object>> defeatedNodes = new LinkedList<Node<Integer, Object>>();
		defeatedNodes.addAll(rootNode.getDefeatedNodesList());
		Node<Integer, Object> ithMinNode = rootNode;

		for (int i = 1; i < k; i++) {
			ithMinNode = getIthMinNode(defeatedNodes, ithMinNode);
			defeatedNodes.addAll(ithMinNode.getDefeatedNodesList());
		}

		Node<Integer, Object> kthMinNode = rootNode;
		for (int i = 1; i < k; i++) {
			kthMinNode = getIthMinNode(defeatedNodes, kthMinNode);
			orderedList.add(kthMinNode);
		}
		return orderedList;
	}

	private static Node<Integer, Object> getIthMinNode(
			List<Node<Integer, Object>> defeatedNodes,
			Node<Integer, Object> iMinusOneTh) {
		Node<Integer, Object> ithMin = new KThMinimum2().new Node(
				Integer.MAX_VALUE, Integer.MAX_VALUE);
		for (Node<Integer, Object> n : defeatedNodes) {
			if (n.compareTo(iMinusOneTh) < 0) {
				continue;
			}
			if ((n.compareTo(iMinusOneTh) > 0) && (n.compareTo(ithMin) < 0)) {
				ithMin = n;
			}
		}
		return ithMin;
	}

	/\*\*
	 \* Takes an input array and generated a two-dimensional array whose rows are
	 \* generated by comparing adjacent elements and selecting minimum of two
	 \* elements. Thus the output is inverse triangle (root at bottom)
	 \* 
	 \* @param values
	 \* @return
	 \*/
	public static List<List<Node<Integer, Object>>> getOutputTree(
			List<Node<Integer, Object>> inputList) {
		Integer size = new Integer(inputList.size());
		double treeDepth = Math.log(size.doubleValue()) / Math.log(2);
		int intTreeDepth = (int) (Math.ceil(treeDepth)) + 1;
		List<List<Node<Integer, Object>>> outputTreeList = new ArrayList<List<Node<Integer, Object>>>();

		// first row is the input
		outputTreeList.add(inputList);
		// printRow(inputList);

		List<Node<Integer, Object>> currentRow = inputList;
		List<Node<Integer, Object>> nextRow = null;
		for (int i = 1; i < intTreeDepth; i++) {
			nextRow = getNextRow(currentRow);
			// printRow(nextRow);
			outputTreeList.add(nextRow);
			currentRow = nextRow;
		}
		return outputTreeList;
	}

	/\*\*
	 \* Compares adjacent elements (starting from index 0), and construct a new
	 \* array with elements that are smaller of the adjacent elements.
	 \* 
	 \* For even sized input, the resulting array is half the size, for odd size
	 \* array, it is half + 1.
	 \* 
	 \* @param values
	 \* @return
	 \*/
	private static List<Node<Integer, Object>> getNextRow(
			List<Node<Integer, Object>> values) {
		int rowSize = getNextRowSize(values);
		List<Node<Integer, Object>> row = new ArrayList<Node<Integer, Object>>(
				rowSize);
		int i = 0;
		for (int j = 0; j < values.size(); j++) {
			if (j == (values.size() - 1)) {
				// this is the case where there are odd number of elements
				// in the array. Hence the last loop will have only one element.
				// row[i++] = values.get(j);
				row.add(values.get(j));
			} else {
				row.add(getMin(values.get(j), values.get(++j)));
			}
		}
		return row;
	}

	/\*\*
	 \* Returns minimum of two passed in values.
	 \* 
	 \* @param num1
	 \* @param num2
	 \* @return
	 \*/
	private static Node<Integer, Object> getMin(Node<Integer, Object> node1,
			Node<Integer, Object> node2) {
		if (node1.compareTo(node2) < 0) {
			node1.addDefeatedNode(node2);
			return node1;
		} else {
			node2.addDefeatedNode(node1);
			return node2;
		}
	}

	/\*\*
	 \* following uses Math.ceil(double) to round to upper integer value..since
	 \* this function takes double value, diving an int by double results in
	 \* double.
	 \* 
	 \* Another way of achieving this is for number x divided by n would be -
	 \* (x+n-1)/n
	 \* 
	 \* @param values
	 \* @return
	 \*/
	private static int getNextRowSize(List<Node<Integer, Object>> values) {
		return (int) Math.ceil(values.size() / 2.0);
	}

	private static void printRow(List<Node<Integer, Object>> inputList) {
		for (Node<Integer, Object> n : inputList) {
			System.out.print(n.getKey() + " ");
		}
		System.out.println(" ");
	}

	private static void printList(List<List<Node<Integer, Object>>> outputTree) {
		for (List<Node<Integer, Object>> list : outputTree) {
			for (Node<Integer, Object> n : list) {
				System.out.print(n.getKey() + ": ");
				for (Node<Integer, Object> defeatedNode : n
						.getDefeatedNodesList()) {
					System.out.print(defeatedNode.getKey() + " ");
				}
				System.out.println("");
			}
		}
	}

	private static List<Node<Integer, Object>> getNodeList(int[] input) {
		List<Node<Integer, Object>> list = new ArrayList<Node<Integer, Object>>();
		Node<Integer, Object> node = null;
		for (int i : input) {
			node = new KThMinimum2().new Node<Integer, Object>(i, i);
			list.add(node);
		}
		return list;
	}

	public static void main(String args[]) throws Exception {
		int[] input = { 2, 14, 5, 13, 1, 8, 17, 10, 6, 12, 9, 4, 11, 15, 3, 16 };
		List<Node<Integer, Object>> inputList = getNodeList(input);
		System.out.println("Fifth Minimum: " + getKthMinimum(inputList, 5));
		int minimumSortedElementSize = 10;
		List<Node<Integer, Object>> tenMinimum = getMinimumKSortedElements(
				inputList, minimumSortedElementSize);
		System.out.print("Minimum " + minimumSortedElementSize + " Sorted: ");
		for (int i = 0; i < minimumSortedElementSize; i++) {
			System.out.print(tenMinimum.get(i) + " ");
		}
	}

	class Node<T extends Comparable<T>, X> implements Comparable {
		private T key;
		private X value;
		private List<Node<T, X>> list = new LinkedList<Node<T, X>>();

		public Node(T key, X value) {
			super();
			this.key = key;
			this.value = value;
		}

		public void addDefeatedNode(Node<T, X> node) {
			list.add(node);
		}

		public List<Node<T, X>> getDefeatedNodesList() {
			return list;
		}

		@Override
		public int compareTo(Object o) {
			Node<T, X> other = (Node<T, X>) o;
			return key.compareTo(other.getKey());
		}

		public T getKey() {
			return key;
		}

		public X getValue() {
			return value;
		}

		@Override
		public String toString() {
			return String.valueOf(key);
		}
	}
}

Running Time

The asymptotic running time is similar to one obtained earlier O(n + klog(n)), but this implementation require fewer comparisons compared to one done while doing back-tracking of tournament tree. The gain of course is at the cost of maintaining node-list of defeated nodes at node that progresses to next level, which is not significant.

Final Thoughts

One of the drawback of Tournament Algorithm is that it is not in place algorithm - requires additional memory (of the order of original array) to store the tournament tree. The above algorithm further require maintaining lists to nodes (for the nodes progressing to next levels), hence put some additional burden on memory requirement (the burden is minimal as only references are kept, not additional node construction), and also some additional processing. But the advantage of the ‘tweaking’ above results in improved performance and much simpler implementation.

Can we use some in-place algorithms such as Quicksort or Heapsort to find Kth min key in efficient manner? What if we are constrained by the virtual memory and the input array cannot fit into memory. Other algorithms exists which can be employed to find Kth order key in linear time such as Counting Sort and Median Order Statistics. I will talk about some of these in my upcoming entries. Stay tuned.

Comments:

I have been reading and looking for articles on the same subject since long, but happily I finally got the information from your article, but unfortunately I came across the article after my project got over.

Posted by Buy Viagra Generic on January 13, 2011 at 07:53 PM PST #

I have been reading and looking for articles on the same subject since long, but happily I finally got the information from your article, but unfortunately I came across the article after my project got over.

Posted by Viagra Generic on January 13, 2011 at 07:56 PM PST #

Post a Comment:
  • HTML Syntax: NOT allowed
About

Malkit works in software development at Oracle, Inc. working in Oracle Business Process Manager, part of Oracle Fusion Middleware. Malkit came to Oracle through Sun Microsystems acquisition, living and working in Los Angeles, California.

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today