Mercurial > hg > Members > tatsuki > Alice

changeset 165:4fd7d0caf7e3 working

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add no recursive type quick sort
author sugi
date Thu, 13 Dec 2012 17:26:05 +0900
parents 9c28131e814f
children a3f7f25f884b
files src/alice/test/codesegment/local/bitonicsort/EvenPhase.java src/alice/test/codesegment/local/bitonicsort/OddPhase.java src/alice/test/codesegment/local/bitonicsort/Sort.java src/alice/test/codesegment/local/bitonicsort/SortTest.java src/alice/test/codesegment/local/mergesort/MergeArray.java src/alice/test/codesegment/local/mergesort/SeparateArray.java src/alice/test/codesegment/local/mergesort/SortConfig.java src/alice/test/codesegment/local/mergesort/SortStart.java
diffstat 8 files changed, 127 insertions(+), 178 deletions(-) [+]
line wrap: on
line diff
--- a/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Thu Dec 13 11:05:24 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Thu Dec 13 17:26:05 2012 +0900
@@ -1,8 +1,5 @@
 package alice.test.codesegment.local.bitonicsort;
 
-import java.util.ArrayList;
-import java.util.List;
-
 import alice.codesegment.CodeSegment;
 import alice.datasegment.CommandType;
 import alice.datasegment.Receiver;
@@ -57,30 +54,32 @@
 		} else {
 			DataList list1 = info1.asClass(DataList.class);
 			DataList list2 = info2.asClass(DataList.class);
+
+			DataList list3 = new DataList();
+			list3.table.addAll(list1.table);
+			list3.table.addAll(list2.table);
+			
 			if (count > sort_count){
-				List<Integer> list = new ArrayList<Integer>();
-				list.addAll(list1.table);
-				list.addAll(list2.table);
-				ods.update("local", "array"+info.range, new DataList(list));
+				ods.update("local", "array"+info.range, list3);
 				return;
 			}
 			int block_num = info3.asInteger();
 			long t1 = System.currentTimeMillis();
-			list2.table = Sort.quickSort(list1.table,list2.table);
+			Sort.quickSort(list3.table, 0, list3.table.size()-1);
 			System.out.println(list2.table.size()+" : "+(System.currentTimeMillis()- t1));
 			if (!info.lastFlag){
 				ods.put("local", info.range+"f",
-						list2.createDataList(0, block_num/2));
+						list3.createDataList(0, block_num/2));
 				ods.put("local", info.range+"b",
-						list2.createDataList(block_num/2, block_num/2));
+						list3.createDataList(block_num/2, block_num/2));
 				//System.out.println("next Odd "+info.range+" "+ info.range+"b"+" "+(info.range+1)+"f");
 				new OddPhase(info0.key,info.range+"b",(info.range+1)+"f",count,info6.key);
 			} else {
 				int last_block_num = info4.asInteger();
 				ods.put("local", info.range+"f", 
-						list2.createDataList(0, block_num/2));
+						list3.createDataList(0, block_num/2));
 				ods.put("local", info.range+"b", 
-						list2.createDataList(block_num/2, last_block_num));
+						list3.createDataList(block_num/2, last_block_num));
 				//System.out.println("next Odd "+info.range+" "+ info.range+"b");
 				new OddPhase(info0.key ,info.range+"b",count,info6.key);
 			}
--- a/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Thu Dec 13 11:05:24 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Thu Dec 13 17:26:05 2012 +0900
@@ -50,7 +50,7 @@
 				return;
 			}
 			long t1 = System.currentTimeMillis();
-			list.table = Sort.quickSort(list.table);
+			Sort.quickSort(list.table,0,list.table.size()-1);
 			System.out.println(list.table.size()+" : "+(System.currentTimeMillis()- t1));
 			if (!info.lastFlag){ 
 				ods.put("local", info.range+"f", 
@@ -75,21 +75,22 @@
 		} else {
 			DataList list1 = info1.asClass(DataList.class);
 			DataList list2 = info2.asClass(DataList.class);
+			
+			List<Integer> list = new ArrayList<Integer>();
+			list.addAll(list1.table);
+			list.addAll(list2.table);
 			if (count > sort_count){
-				List<Integer> list = new ArrayList<Integer>();
-				list.addAll(list1.table);
-				list.addAll(list2.table);
 				ods.update("local", "array"+info.range, new DataList(list));
 				return;
 			}
 			long t1 = System.currentTimeMillis();
-			list2.table = Sort.quickSort(list1.table,list2.table);
+			Sort.quickSort(list,0,list.size()-1);
 			System.out.println(list2.table.size()+" : "+(System.currentTimeMillis()- t1));
-			
+			DataList list3 = new DataList(list);
 			ods.put("local", info.range+"f",
-					list2.createDataList(0, block_num/2));
+					list3.createDataList(0, block_num/2));
 			ods.put("local", info.range+"b",
-					list2.createDataList(block_num/2, block_num/2));
+					list3.createDataList(block_num/2, block_num/2));
 
 			if (info.range==0){
 				//System.out.println("next Even2b "+info.range+" "+ info.range+"f");
--- a/src/alice/test/codesegment/local/bitonicsort/Sort.java	Thu Dec 13 11:05:24 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/Sort.java	Thu Dec 13 17:26:05 2012 +0900
@@ -5,11 +5,12 @@
 import java.util.List;
 
 public class Sort {
-	/*
-	 * quick method has problem. 
-	 */
 	
-	public static List<Integer> quickSort(List<Integer> numbers){		
+	public static List<Integer> quickSort(List<Integer> numbers){
+		/*
+		 * this method has problem. 
+		 */
+		
 		if (numbers.size() < 1000){
 			bubbleSort(numbers);	
 			return numbers;
@@ -49,31 +50,37 @@
 			bubbleSort(list);
 			return list;
 		}
-		
-		int where = list.size() / 2;
-		int pivot = list.get(where);
-		int sameAsPivot = 0;
-		List<Integer> lesser = new ArrayList<Integer>();
-		List<Integer> greater = new ArrayList<Integer>();
-		List<Integer> sorted = new ArrayList<Integer>();
-		Iterator<Integer> iter = list.iterator();
-		
-		while(iter.hasNext()){
-			int number = iter.next();
-			if (number>pivot) greater.add(number);
-			else if (number < pivot) lesser.add(number);
-			else sameAsPivot++;
+		return quickSort(list);
+	}
+	
+	public static void quickSort(List<Integer> numbers, int begin,int end){
+		int[] stack = new int[1024];
+		int sp = 0;
+		int p = 0;
+		while(true){
+			while(begin < end){
+				int where = (begin+end)/2;
+				int pivot = numbers.get(where);
+				numbers.set(where, numbers.get(begin));
+				int i;
+				p = begin;
+				for (i=begin+1;i<=end;i++){
+					if (numbers.get(i)<pivot){
+						p++;
+						if (i!=p)swap(numbers,p,i);
+					}
+				}
+				numbers.set(begin, numbers.get(p));
+				numbers.set(p, pivot);
+				stack[sp++] = p+1;
+				stack[sp++] = end;
+				end=p-1;
+			}
+			if (sp==0) return;
+			end = stack[--sp];
+			begin = stack[--sp];
+			begin = p+1; 
 		}
-
-		lesser = quickSort(lesser);
-		greater = quickSort(greater);
-
-		// merge
-		sorted.addAll(lesser);
-		for (int i=0;i< sameAsPivot;i++)
-			sorted.add(pivot);
-		sorted.addAll(greater);
-		return sorted;
 	}
 	
 	public static void bubbleSort(List<Integer> numbers){
@@ -96,7 +103,6 @@
 		int number1 = 0;
 		int number2 = 0;
 		Iterator<Integer> iter = numbers.iterator();
-		
 		System.out.println("checking ....");
 		while (iter.hasNext()){
 			number1 = number2;
--- a/src/alice/test/codesegment/local/bitonicsort/SortTest.java	Thu Dec 13 11:05:24 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/SortTest.java	Thu Dec 13 17:26:05 2012 +0900
@@ -12,7 +12,7 @@
 		long t;
 		List<Integer> list = new ArrayList<Integer>();
 		List<Integer> list2 = new ArrayList<Integer>();
-		List<Integer> list3;
+		List<Integer> sorted;
 		
 		for (int i = 0; i < size; i++){
 			Random rnd = new Random();
@@ -20,22 +20,29 @@
 		}
 		for (int i = 0; i < size; i++){
 			Random rnd = new Random();
-			list.add(rnd.nextInt(MAX));
+			list2.add(rnd.nextInt(MAX));
 		}
+		
+		//recursive type quicksort
 		t = System.currentTimeMillis();
-		list3 = Sort.quickSort(list);
+		sorted = Sort.quickSort(list);
 		System.out.println("quick sort1 : "+ (System.currentTimeMillis()-t)+" ms");
-		Sort.check(list3);
+		Sort.check(sorted);
 		
 		t = System.currentTimeMillis();
-		list3 = Sort.quickSort(list,list2);
+		sorted = Sort.quickSort(list,list2);
 		System.out.println("quick sort2 : "+ (System.currentTimeMillis()-t)+" ms");
-		Sort.check(list3);
+		Sort.check(sorted);
+		
+		// stack type quicksort
+		t = System.currentTimeMillis();
+		Sort.quickSort(list,0,list.size()-1);
+		System.out.println("quick sort3 : "+ (System.currentTimeMillis()-t)+" ms");
+		Sort.check(list);
 		
 		t = System.currentTimeMillis();
-		Sort.bubbleSort(list);
+		Sort.bubbleSort(list2);
 		System.out.println("bubble sort : "+ (System.currentTimeMillis()-t)+" ms");
-		Sort.check(list);
-
+		Sort.check(list2);
 	}
 }
--- a/src/alice/test/codesegment/local/mergesort/MergeArray.java	Thu Dec 13 11:05:24 2012 +0900
+++ b/src/alice/test/codesegment/local/mergesort/MergeArray.java	Thu Dec 13 17:26:05 2012 +0900
@@ -1,13 +1,11 @@
 package alice.test.codesegment.local.mergesort;
 
 import java.util.Iterator;
-import java.util.List;
-
-import org.msgpack.type.Value;
 
 import alice.codesegment.CodeSegment;
 import alice.datasegment.CommandType;
 import alice.datasegment.Receiver;
+import alice.test.codesegment.local.bitonicsort.DataList;
 
 public class MergeArray extends CodeSegment{
 	
@@ -29,84 +27,52 @@
 
 	@Override
 	public void run() {
-		List<Value> list1 = info1.asArray();
-		List<Value> list2 = info2.asArray();
-
-		//System.out.println(list1);
-		//System.out.println(list2);
 		
-		int length = list1.size() + list2.size();
-		int[] array = new int[length];
+		DataList list1 = info1.asClass(DataList.class);
+		DataList list2 = info2.asClass(DataList.class);
+		DataList list3 = new DataList();
 		
-		Iterator<Value> iter1 = list1.listIterator();
-		Iterator<Value> iter2 = list2.listIterator();
+		Iterator<Integer> iter1 = list1.table.listIterator();
+		Iterator<Integer> iter2 = list2.table.listIterator();
 		
-		int val1 = iter1.next().asIntegerValue().getInt();//0
-		int val2 = iter2.next().asIntegerValue().getInt();//0
+		int val1 = iter1.next();
+		int val2 = iter2.next();
 
-		int i;
-		for (i=0;i<length;i++){
+		while(true){
 			if (val1 <= val2){
-				array[i] = val1;
-				if (!iter1.hasNext()) {
-					array[i+1] = val2; 
-					break;
-				}
-				val1 = iter1.next().asIntegerValue().getInt();
-			} else if (val1>val2) {
-				array[i] = val2;
-				if (!iter2.hasNext()) {
-					array[i+1] = val1; 
+				list3.table.add(val1);
+				if (iter1.hasNext()) {
+					val1 = iter1.next();
+				} else {
+					list3.table.add(val2);
 					break;
 				}
-				val2 = iter2.next().asIntegerValue().getInt();
-			}
-		}
-		
-		if (iter2.hasNext()) {
-			for (i=i+2 ;i<length;i++){
-				array[i] = iter2.next().asIntegerValue().getInt();
-			}
-		} else if (iter1.hasNext()) {
-			for (i=i+2;iter1.hasNext();i++){
-				array[i] = iter1.next().asIntegerValue().getInt();
-			}
-		}
-		
-		/*
-		for (int i=0,k=0,j=0;i<length;i++){
-			int array1 = list1.get(j).asIntegerValue().getInt();
-			int array2 = list2.get(k).asIntegerValue().getInt();
-			
-			if (array1<=array2){
-				array[i]=array1;
-				j++;
-				if (j == list1.size()){
-					for (i=i+1;i<length;i++,k++){
-						array[i]=list2.get(k).asIntegerValue().getInt();
-					}
-					break;
-				}
-			} else if (array1>array2){
-				array[i]=array2;
-				k++;
-				if (k == list2.size()){
-					for (i=i+1;i<length;i++,j++){
-						array[i]=list1.get(j).asIntegerValue().getInt();
-					}
+				
+			} else if (val1>val2) {
+				list3.table.add(val2);
+				if (iter2.hasNext()) {
+					val2 = iter2.next();
+				} else {
+					list3.table.add(val1);
 					break;
 				}
 			}
 		}
-		*/
-		/*
-		for (int i = 0;i<length;i++){
-			System.out.println(array[i]);
+		
+		
+		if (iter2.hasNext()) {
+			while(iter2.hasNext()){
+				list3.table.add(iter2.next());
+			}
+		} else if (iter1.hasNext()) {
+			while(iter1.hasNext()){
+				list3.table.add(iter1.next());
+			}	
 		}
-		*/
+		
 		int num = (keyNum1-1)/2;
 		String key = Integer.toString(num);
 		
-		ods.put("local", key, array);
+		ods.put("local", key, list3);
 	}
 }
--- a/src/alice/test/codesegment/local/mergesort/SeparateArray.java	Thu Dec 13 11:05:24 2012 +0900
+++ b/src/alice/test/codesegment/local/mergesort/SeparateArray.java	Thu Dec 13 17:26:05 2012 +0900
@@ -1,13 +1,10 @@
 package alice.test.codesegment.local.mergesort;
 
-import java.util.Iterator;
-import java.util.List;
-
-import org.msgpack.type.Value;
-
 import alice.codesegment.CodeSegment;
 import alice.datasegment.CommandType;
 import alice.datasegment.Receiver;
+import alice.test.codesegment.local.bitonicsort.DataList;
+import alice.test.codesegment.local.bitonicsort.Sort;
 
 public class SeparateArray extends CodeSegment{
 
@@ -21,50 +18,32 @@
 	}
 	@Override
 	public void run() {
-		List<Value> list = info.asArray();
-		//System.out.println(list);
-		if (list.size() > 2){
+		DataList list = info.asClass(DataList.class);
+		if (list.table.size() > 2){
 			int num = 2*keyNum + 1;
-			int length = list.size()/2;
-			int[] array1 = new int[length];
-			int[] array2 = new int[length];
-			/*
-			for (int i = 0;i<length;i++){
-				array1[i] = list.get(i).asIntegerValue().getInt();
-				array2[i] = list.get(i+length).asIntegerValue().getInt();
-			}
-			*/
+			int length = list.table.size()/2;
 			
-			Iterator<Value> iter = list.listIterator();
-			Iterator<Value> iter1 = list.listIterator(length);
-			
-			for (int i = 0;i<length;i++){
-				array1[i] = iter.next().asIntegerValue().getInt();
-				array2[i] = iter1.next().asIntegerValue().getInt();				
-			}
 			String key1 = Integer.toString(num);
 			String key2 = Integer.toString(num+1);
 
-			ods.put("local", key1, array1);
-			ods.put("local", key2, array2);			
+			ods.put("local", key1, list.createDataList(0, length));
+			ods.put("local", key2, list.createDataList(length, length));			
 			
 			new SeparateArray(num);
 			new SeparateArray(num+1);
 			new MergeArray(num,num+1);
+		} else if (list.table.size()==2){
+			String key = Integer.toString(keyNum);
+			
+			if (list.table.get(0)<=list.table.get(1)){
+				ods.put("local",key, list);
+			} else {
+				Sort.swap(list.table, 0, 1);
+				ods.put("local",key, list);
+			}
 		} else {
 			String key = Integer.toString(keyNum);
-			int array[] = new int[2];
-			int array1 = list.get(0).asIntegerValue().getInt();
-			int array2 = list.get(1).asIntegerValue().getInt();
-			if (array1<=array2){
-				array[0] = array1;
-				array[1] = array2;
-				ods.put("local",key, array);
-			} else {
-				array[0] = array2;
-				array[1] = array1;			
-				ods.put("local",key, array);
-			}
+			ods.put("local",key, list);
 		}
 	}
 
--- a/src/alice/test/codesegment/local/mergesort/SortConfig.java	Thu Dec 13 11:05:24 2012 +0900
+++ b/src/alice/test/codesegment/local/mergesort/SortConfig.java	Thu Dec 13 17:26:05 2012 +0900
@@ -4,13 +4,11 @@
 
 public class SortConfig {
 	int size;
-	boolean flag;
+	
 	public SortConfig(String[] args){
 		for (int i=0;i<args.length; i++){
 			if ("-size".equals(args[i])){
 				size = Integer.parseInt(args[++i]);	
-			} else if ("-show".equals(args[i])){
-				flag = true;	
 			}
 		}
 	}
--- a/src/alice/test/codesegment/local/mergesort/SortStart.java	Thu Dec 13 11:05:24 2012 +0900
+++ b/src/alice/test/codesegment/local/mergesort/SortStart.java	Thu Dec 13 17:26:05 2012 +0900
@@ -1,10 +1,9 @@
 package alice.test.codesegment.local.mergesort;
 
-import java.io.IOException;
 import java.util.Random;
 
 import alice.codesegment.CodeSegment;
-import alice.codesegment.SingletonMessage;
+import alice.test.codesegment.local.bitonicsort.DataList;
 
 public class SortStart extends CodeSegment{
 	public static long t;
@@ -16,20 +15,14 @@
 	@Override
 	public void run() {
 		int size = conf.size;
-		int[] array = new int[size];
+		DataList list = new DataList();
 		for (int i=0;i< size; i++){
 			Random rnd = new Random();
-			array[i] = rnd.nextInt(Integer.MAX_VALUE);
+			list.table.add(rnd.nextInt(Integer.MAX_VALUE));
 		}
-		if (conf.flag){
-			try {
-				System.out.println(SingletonMessage.getInstance().unconvert(array));
-			} catch (IOException e) {
-				e.printStackTrace();
-			}
-		}
+		
 		String key = Integer.toString(0);
-		ods.put("local", key, array);
+		ods.put("local", key, list);
 	
 		new SeparateArray(0);
 		new ShowResult(0);