Mercurial > hg > Database > Alice

changeset 162:7f8a3680a35c working

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add static class for Sorting and checking. remove "list.get()" and use Iterator
author sugi
date Wed, 12 Dec 2012 21:09:21 +0900
parents 1a84834ba33a
children db1bae5db5d2
files src/alice/test/codesegment/local/bitonicsort/EvenPhase.java src/alice/test/codesegment/local/bitonicsort/MakeData.java src/alice/test/codesegment/local/bitonicsort/OddPhase.java src/alice/test/codesegment/local/bitonicsort/SetTask.java src/alice/test/codesegment/local/bitonicsort/ShowData.java src/alice/test/codesegment/local/bitonicsort/Sort.java
diffstat 6 files changed, 141 insertions(+), 239 deletions(-) [+]
line wrap: on
line diff
--- a/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Wed Dec 12 16:23:39 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Wed Dec 12 21:09:21 2012 +0900
@@ -43,12 +43,10 @@
 		RangeInfo info = info0.asClass(RangeInfo.class);
 		int sort_count = info5.asInteger();
 		int count = info6.asInteger();
-		//System.out.println("count is " +count);
 		
 		if (info2==null){
 			DataList list = info1.asClass(DataList.class);
 			if (count > sort_count){
-				//check(list.table);
 				ods.update("local", "array"+info.range, list);
 				return;
 			}
@@ -63,13 +61,13 @@
 				List<Integer> list = new LinkedList<Integer>();
 				list.addAll(list1.table);
 				list.addAll(list2.table);
-				//check(list);
 				ods.update("local", "array"+info.range, new DataList(list));
 				return;
 			}
 			int block_num = info3.asInteger();
-			list2.table = quickSort(list1.table,list2.table);
-
+			long t1 = System.currentTimeMillis();
+			list2.table = Sort.quickSort(list1.table,list2.table);
+			System.out.println(list2.table.size()+" : "+(System.currentTimeMillis()- t1));
 			if (!info.lastFlag){
 				ods.put("local", info.range+"f",
 						list2.createDataList(0, block_num/2));
@@ -90,102 +88,4 @@
 		}
 		ods.update("local", info6.key, count+1);
 	}
-	public void check(List<Integer> numbers){
-		for (int i=0 ;i+1<numbers.size();i++){
-			if (numbers.get(i)>numbers.get(i+1)){
-				System.out.println("MISS "+ numbers.get(i)+" > "+numbers.get(i+1));
-				return;
-			}
-		}
-		//System.out.println(numbers);
-	}
-	
-	public List<Integer> quickSort(List<Integer> numbers){
-		//if (numbers.size() < 1) return numbers;
-		if (numbers.size() < 400){
-			bubbleSort(numbers);	
-			return numbers;
-		}
-		int pivot = numbers.size() / 2;
-		List<Integer> lesser = new LinkedList<Integer>();
-		List<Integer> greater = new LinkedList<Integer>();
-		int sameAsPivot = 0;
-		
-		for (int number : numbers){
-			if (number>numbers.get(pivot))
-				greater.add(number);
-			else if (number < numbers.get(pivot))
-				lesser.add(number);
-			else
-				sameAsPivot++;
-		}
-		// size check bubble < quick
-		lesser = quickSort(lesser);
-		greater = quickSort(greater);
-		List<Integer> sorted = new LinkedList<Integer>();
-		for (int number: lesser)
-			sorted.add(number);
-		for (int i=0;i< sameAsPivot;i++)
-			sorted.add(numbers.get(pivot));
-		for (int number: greater)
-			sorted.add(number);
-		return sorted;
-	}
-	
-	public List<Integer> quickSort(List<Integer> numbers1,List<Integer> numbers2){
-		//if (numbers1.size() < 1) return numbers1;
-		if (numbers1.size() + numbers2.size()< 400){
-			numbers1.addAll(numbers2);
-			bubbleSort(numbers1);
-			return numbers1;
-		}
-		int pivot = numbers1.size() / 2;
-		List<Integer> lesser = new LinkedList<Integer>();
-		List<Integer> greater = new LinkedList<Integer>();
-		int sameAsPivot = 0;
-		
-		for (int number : numbers1){
-			if (number>numbers1.get(pivot))
-				greater.add(number);
-			else if (number < numbers1.get(pivot))
-				lesser.add(number);
-			else
-				sameAsPivot++;
-		}
-		for (int number : numbers2){
-			if (number>numbers1.get(pivot))
-				greater.add(number);
-			else if (number < numbers1.get(pivot))
-				lesser.add(number);
-			else
-				sameAsPivot++;
-		}
-		// size check bubble < quick
-		lesser = quickSort(lesser);
-		greater = quickSort(greater);
-		List<Integer> sorted = new LinkedList<Integer>();
-		for (int number: lesser)
-			sorted.add(number);
-		for (int i=0;i< sameAsPivot;i++)
-			sorted.add(numbers1.get(pivot));
-		for (int number: greater)
-			sorted.add(number);
-		return sorted;
-	}
-	
-	public void bubbleSort(List<Integer> numbers){
-		for (int i=0;i<numbers.size()-1;i++){
-			for (int j=numbers.size()-1;j>i;j--){
-				if (numbers.get(i) > numbers.get(j)){
-					swap(numbers,i,j);
-				}
-			}
-		}
-	}
-	
-	public <T> void swap(List<T> list,int index1,int index2){
-		T tmp=list.get(index1);
-		list.set(index1,list.get(index2));
-		list.set(index2, tmp);
-	}
 }
--- a/src/alice/test/codesegment/local/bitonicsort/MakeData.java	Wed Dec 12 16:23:39 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/MakeData.java	Wed Dec 12 21:09:21 2012 +0900
@@ -21,14 +21,10 @@
 		SortConfig conf = info1.asClass(SortConfig.class);
 		DataList list = info2.asClass(DataList.class);
 		int size = conf.getLength();
-		for (int i = 0;i<size;i++){
+		for (int i = 0; i < size; i++){
 			Random rnd = new Random();
 			list.table.add(rnd.nextInt(Integer.MAX_VALUE));
 		}
-		/*
-		for (int i = 16;i>0;i--){
-			list.table.add(i);
-		}*/
 		
 		ods.update("local", "list", list);
 	}
--- a/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Wed Dec 12 16:23:39 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Wed Dec 12 21:09:21 2012 +0900
@@ -12,7 +12,7 @@
 	private Receiver info1; 							   // Array1
 	private Receiver info2; 							   // Array2
 	private Receiver info3 = ids.create(CommandType.PEEK); // block_num
-	private Receiver info4 = ids.create(CommandType.PEEK); // last_block_num
+	//private Receiver info4 = ids.create(CommandType.PEEK); // last_block_num
 	private Receiver info5 = ids.create(CommandType.PEEK); // sort_count
 	private Receiver info6 = ids.create(CommandType.TAKE); // count
 	
@@ -21,7 +21,6 @@
 		info1 = ids.create(CommandType.TAKE);
 		info1.setKey("local",key1,index);
 		info3.setKey("block_num");
-		info4.setKey("last_block_num");
 		info5.setKey("sort_count");
 		info6.setKey(key6);
 	}
@@ -33,7 +32,6 @@
 		info2 = ids.create(CommandType.TAKE);
 		info2.setKey("local",key2,index);
 		info3.setKey("block_num");
-		info4.setKey("last_block_num");
 		info5.setKey("sort_count");
 		info6.setKey(key6);
 	}
@@ -48,17 +46,13 @@
 		if (info2==null){
 			DataList list = info1.asClass(DataList.class);
 			if (count > sort_count){
-				//check(list.table);
 				ods.update("local", "array"+info.range, list);
 				return;
 			}
-			list.table = quickSort(list.table);
+			long t1 = System.currentTimeMillis();
+			list.table = Sort.quickSort(list.table);
+			System.out.println(list.table.size()+" : "+(System.currentTimeMillis()- t1));
 			if (!info.lastFlag){ 
-				/*
-				 * ソートされたlistから指定した部分をコピーしている
-				 * ソートしている最中にlistを2つ作った方がいいかも。
-				 */
-				
 				ods.put("local", info.range+"f", 
 						list.createDataList(0, block_num/2));
 				ods.put("local", info.range+"b",
@@ -85,12 +79,13 @@
 				List<Integer> list = new LinkedList<Integer>();
 				list.addAll(list1.table);
 				list.addAll(list2.table);
-				//check(list);
 				ods.update("local", "array"+info.range, new DataList(list));
 				return;
 			}
-			list2.table = quickSort(list1.table,list2.table);
-				
+			long t1 = System.currentTimeMillis();
+			list2.table = Sort.quickSort(list1.table,list2.table);
+			System.out.println(list2.table.size()+" : "+(System.currentTimeMillis()- t1));
+			
 			ods.put("local", info.range+"f",
 					list2.createDataList(0, block_num/2));
 			ods.put("local", info.range+"b",
@@ -106,103 +101,5 @@
 		}
 		ods.update("local", info6.key, count+1);
 	}
-	public void check(List<Integer> numbers){
-		for (int i=0 ;i+1<numbers.size();i++){
-			if (numbers.get(i)>numbers.get(i+1)){
-				System.out.println("MISS "+ numbers.get(i)+" > "+numbers.get(i+1));
-				return;
-			}
-		}
-		//System.out.println(numbers);
-	}
 	
-	public List<Integer> quickSort(List<Integer> numbers){
-		if (numbers.size() < 1) 
-			return numbers;
-		/*if (numbers.size() < 400){ 
-			return bubbleSort(numbers);
-			
-		} */
-		int pivot = numbers.size() / 2;
-		List<Integer> lesser = new LinkedList<Integer>();
-		List<Integer> greater = new LinkedList<Integer>();
-		int sameAsPivot = 0;
-		
-		for (int number : numbers){
-			if (number>numbers.get(pivot))
-				greater.add(number);
-			else if (number < numbers.get(pivot))
-				lesser.add(number);
-			else
-				sameAsPivot++;
-		}
-		// size check bubble < quick
-		lesser = quickSort(lesser);
-		greater = quickSort(greater);
-		List<Integer> sorted = new LinkedList<Integer>();
-		for (int number: lesser)
-			sorted.add(number);
-		for (int i=0;i< sameAsPivot;i++)
-			sorted.add(numbers.get(pivot));
-		for (int number: greater)
-			sorted.add(number);
-		return sorted;
-	}
-	
-	public List<Integer> quickSort(List<Integer> numbers1, List<Integer> numbers2){
-		//if (numbers1.size() < 1) return numbers1;
-		if (numbers1.size() + numbers2.size()< 400){
-			numbers1.addAll(numbers2);
-			bubbleSort(numbers1);
-			return numbers1;
-		}
-		int pivot = numbers1.size() / 2;
-		List<Integer> lesser = new LinkedList<Integer>();
-		List<Integer> greater = new LinkedList<Integer>();
-		int sameAsPivot = 0;
-		
-		for (int number : numbers1){
-			if (number>numbers1.get(pivot))
-				greater.add(number);
-			else if (number < numbers1.get(pivot))
-				lesser.add(number);
-			else
-				sameAsPivot++;
-		}
-		for (int number : numbers2){
-			if (number>numbers1.get(pivot))
-				greater.add(number);
-			else if (number < numbers1.get(pivot))
-				lesser.add(number);
-			else
-				sameAsPivot++;
-		}
-		// size check bubble < quick
-		lesser = quickSort(lesser);
-		greater = quickSort(greater);
-		List<Integer> sorted = new LinkedList<Integer>();
-		for (int number: lesser)
-			sorted.add(number);
-		for (int i=0;i< sameAsPivot;i++)
-			sorted.add(numbers1.get(pivot));
-		for (int number: greater)
-			sorted.add(number);
-		return sorted;
-	}
-	
-	public void bubbleSort(List<Integer> numbers){
-		for (int i=0;i<numbers.size()-1;i++){
-			for (int j=numbers.size()-1;j>i;j--){
-				if (numbers.get(i) > numbers.get(j)){
-					swap(numbers,i,j);
-				}
-			}
-		}
-	}
-	
-	public <T> void swap(List<T> list,int index1,int index2){
-		T tmp=list.get(index1);
-		list.set(index1,list.get(index2));
-		list.set(index2, tmp);
-	}
 }
--- a/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Wed Dec 12 16:23:39 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Wed Dec 12 21:09:21 2012 +0900
@@ -20,7 +20,7 @@
 		DataList list = info2.asClass(DataList.class);
 		System.out.println(list.table);
 		
-		 // sort完了に必要な回数
+		 // sort完了に必要な回数?
 		int sort_count = conf.getSplitNum();
 		ods.put("local", "sort_count", sort_count*2);
 		 // 1つのタスクでsortするdata数
--- a/src/alice/test/codesegment/local/bitonicsort/ShowData.java	Wed Dec 12 16:23:39 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/ShowData.java	Wed Dec 12 21:09:21 2012 +0900
@@ -9,32 +9,34 @@
 
 public class ShowData extends CodeSegment{
 
-	private Receiver[] info = new Receiver[10];
+	private Receiver info0 = ids.create(CommandType.PEEK);
+	private Receiver info1 = ids.create(CommandType.PEEK);
+	private Receiver info2 = ids.create(CommandType.PEEK);
+	//private Receiver info3 = ids.create(CommandType.PEEK);
 	int cnt;
 	public ShowData(int cnt) {
 		this.cnt = cnt;
-		for (int i=0;i<cnt;i++){
-			info[i] = ids.create(CommandType.PEEK);
-			info[i].setKey("local", "array"+i,1);
-		}
+		info0.setKey("local", "array"+0,1);
+		info1.setKey("local", "array"+1,1);
+		info2.setKey("local", "array"+2,1);
+		//info3.setKey("local", "array"+3,1);
+		
 	}
-
 	@Override
 	public void run() {
-		
+		System.out.println(System.currentTimeMillis() -SetTask.t);
+		DataList list0 = info0.asClass(DataList.class);
+		DataList list1 = info1.asClass(DataList.class);
+		DataList list2 = info2.asClass(DataList.class);
+		//DataList list3 = info3.asClass(DataList.class);
 		List<Integer> list = new LinkedList<Integer>();
-		for (int i=0;i<cnt;i++){
-			list.addAll(info[i].asClass(DataList.class).table);
-		}
-		for (int i=0 ;i+1<list.size();i++){
-			if (list.get(i)>list.get(i+1)){
-				System.out.println("MISS "+ list.get(i)+" > "+list.get(i+1));
-				return;
-			}
-		}
-		System.out.println("OK");
-		System.out.println(list);
-			
+		list.addAll(list0.table);
+		list.addAll(list1.table);
+		list.addAll(list2.table);
+		//list.addAll(list3.table);
+		
+		Sort.check(list);
+		System.exit(0);
 	}
 	
 	
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/Sort.java	Wed Dec 12 21:09:21 2012 +0900
@@ -0,0 +1,107 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+
+public class Sort {
+	public static void check(List<Integer> numbers){
+		int number1 = 0;
+		int number2 = 0;
+		Iterator<Integer> iter = numbers.iterator();
+		
+		System.out.println("checking ....");
+		while (iter.hasNext()){
+			number1 = number2;
+			number2 = iter.next();
+			if (number1 > number2){
+				System.out.println("MISS "+ number1+" > "+number2);
+				return;
+			}
+		}
+		System.out.println("sort is succeed");
+	}
+	
+	public static List<Integer> quickSort(List<Integer> numbers){		
+		if (numbers.size() < 400){
+			bubbleSort(numbers);	
+			return numbers;
+		}
+		
+		int where = numbers.size() / 2;
+		int pivot = numbers.get(where);
+		int sameAsPivot = 0;
+		List<Integer> lesser = new LinkedList<Integer>();
+		List<Integer> greater = new LinkedList<Integer>();
+		List<Integer> sorted = new LinkedList<Integer>();
+		Iterator<Integer> iter = numbers.iterator();
+		
+		while(iter.hasNext()){
+			int number = iter.next();
+			if (number>pivot) greater.add(number);
+			else if (number < pivot) lesser.add(number);
+			else sameAsPivot++;
+		}
+		
+		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 List<Integer> quickSort(List<Integer> numbers1, List<Integer> numbers2){
+		List<Integer> list = new LinkedList<Integer>();
+		list.addAll(numbers1);
+		list.addAll(numbers2);
+		if ( list.size() < 400 ){
+			bubbleSort(list);
+			return list;
+		}
+		
+		int where = list.size() / 2;
+		int pivot = list.get(where);
+		int sameAsPivot = 0;
+		List<Integer> lesser = new LinkedList<Integer>();
+		List<Integer> greater = new LinkedList<Integer>();
+		List<Integer> sorted = new LinkedList<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++;
+		}
+
+		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){
+		for (int i=0;i<numbers.size()-1;i++){
+			for (int j=numbers.size()-1;j>i;j--){
+				if (numbers.get(i) > numbers.get(j)){
+					swap(numbers,i,j);
+				}
+			}
+		}
+	}
+	
+	public static <T> void swap(List<T> list,int index1,int index2){
+		T tmp=list.get(index1);
+		list.set(index1,list.get(index2));
+		list.set(index2, tmp);
+	}
+}