Mercurial > hg > Members > tatsuki > Alice

changeset 166:a3f7f25f884b working

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
show data CS could change dynamic array
author sugi
date Fri, 14 Dec 2012 17:17:41 +0900
parents 4fd7d0caf7e3
children a55acaea1eb1
files src/alice/test/codesegment/local/bitonicsort/EvenPhase.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 src/alice/test/codesegment/local/bitonicsort/SortTest.java
diffstat 6 files changed, 45 insertions(+), 53 deletions(-) [+]
line wrap: on
line diff
--- a/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Thu Dec 13 17:26:05 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Fri Dec 14 17:17:41 2012 +0900
@@ -64,9 +64,7 @@
 				return;
 			}
 			int block_num = info3.asInteger();
-			long t1 = System.currentTimeMillis();
 			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",
 						list3.createDataList(0, block_num/2));
--- a/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Thu Dec 13 17:26:05 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Fri Dec 14 17:17:41 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;
@@ -49,14 +46,10 @@
 				ods.update("local", "array"+info.range, list);
 				return;
 			}
-			long t1 = System.currentTimeMillis();
 			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", 
-						list.createDataList(0, block_num/2));
-				ods.put("local", info.range+"b",
-						list.createDataList(block_num/2, block_num/2));
+				ods.put("local", info.range+"f", list.createDataList(0, block_num/2));
+				ods.put("local", info.range+"b", list.createDataList(block_num/2, block_num/2));
 				
 				if (info.range==0){
 					//System.out.println("next Even "+info.range+" "+info.range+"f");	
@@ -76,21 +69,17 @@
 			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);
+			DataList list3 = new DataList();
+			list3.table.addAll(list1.table);
+			list3.table.addAll(list2.table);
 			if (count > sort_count){
-				ods.update("local", "array"+info.range, new DataList(list));
+				ods.update("local", "array"+info.range, list3);
 				return;
 			}
-			long t1 = System.currentTimeMillis();
-			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",
-					list3.createDataList(0, block_num/2));
-			ods.put("local", info.range+"b",
-					list3.createDataList(block_num/2, block_num/2));
+
+			Sort.quickSort(list3.table,0,list3.table.size()-1);
+			ods.put("local", info.range+"f", list3.createDataList(0, block_num/2));
+			ods.put("local", info.range+"b", 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/SetTask.java	Thu Dec 13 17:26:05 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Fri Dec 14 17:17:41 2012 +0900
@@ -18,16 +18,16 @@
 	public void run() {
 		SortConfig conf = info1.asClass(SortConfig.class);
 		DataList list = info2.asClass(DataList.class);
-		System.out.println(list.table);
+		//System.out.println(list.table);
 		
-		 // sort完了に必要な回数?
 		int sort_count = conf.getSplitNum();
 		ods.put("local", "sort_count", sort_count*2);
-		 // 1つのタスクでsortするdata数
+	
 		int block_num = (conf.getLength() + conf.getSplitNum() - 1 ) / sort_count;
 		ods.put("local", "block_num", block_num);
 		int last_block_num = conf.getLength() - (conf.getSplitNum() - 1)*block_num;
 		ods.put("local", "last_block_num", last_block_num);
+		
 		{
 			String key = "array";
 			int i = 0;
@@ -38,14 +38,15 @@
 				new OddPhase("range"+i,key+i,0,"count"+i);
 			}
 			
-			// 最後のblockは端数
 			ods.put("local", "range"+i, new RangeInfo(i,true));
 			ods.update("local", key+i, list.createDataList(i*block_num, last_block_num));
 			ods.update("local", "count"+i, 0);
+			ods.put("local","arraynum",i);
 			new OddPhase("range"+i,key+i,0,"count"+i);
-			System.out.println(i);
 			new ShowData(i);
+			
 		}
+		System.out.println("sort start");
 		t = System.currentTimeMillis();
 	}
 
--- a/src/alice/test/codesegment/local/bitonicsort/ShowData.java	Thu Dec 13 17:26:05 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/ShowData.java	Fri Dec 14 17:17:41 2012 +0900
@@ -8,33 +8,27 @@
 import alice.datasegment.Receiver;
 
 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;
-		info0.setKey("local", "array"+0,1);
-		info1.setKey("local", "array"+1,1);
-		info2.setKey("local", "array"+2,1);
-		//info3.setKey("local", "array"+3,1);
-		
+		for (int i= 0;i<= cnt; i++)
+			info[i] = ids.create(CommandType.PEEK);
+		for (int i= 0;i<= cnt; i++)
+			info[i].setKey("local","array"+i,1);
+		info0.setKey("local", "arraynum");
 	}
+	
 	@Override
 	public void run() {
 		System.out.println(System.currentTimeMillis() -SetTask.t +" ms");
-		DataList list0 = info0.asClass(DataList.class);
-		DataList list1 = info1.asClass(DataList.class);
-		DataList list2 = info2.asClass(DataList.class);
-		//DataList list3 = info3.asClass(DataList.class);
+		int cnt = info0.asInteger();
 		List<Integer> list = new ArrayList<Integer>();
-		list.addAll(list0.table);
-		list.addAll(list1.table);
-		list.addAll(list2.table);
-		//list.addAll(list3.table);
-		
+		for (int i= 0;i<= cnt; i++){
+			list.addAll(info[i].asClass(DataList.class).table);
+		}
+		System.out.println("size check :"+ list.size());
 		Sort.check(list);
 		System.exit(0);
 	}
--- a/src/alice/test/codesegment/local/bitonicsort/Sort.java	Thu Dec 13 17:26:05 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/Sort.java	Fri Dec 14 17:17:41 2012 +0900
@@ -12,7 +12,7 @@
 		 */
 		
 		if (numbers.size() < 1000){
-			bubbleSort(numbers);	
+			bubbleSort(numbers,0,numbers.size()-1);
 			return numbers;
 		}
 		
@@ -47,18 +47,28 @@
 		list.addAll(numbers1);
 		list.addAll(numbers2);
 		if ( list.size() < 1000 ){
-			bubbleSort(list);
+			bubbleSort(list,0,list.size()-1);
 			return list;
 		}
 		return quickSort(list);
 	}
 	
+	// this method has "stack overflow" problem
 	public static void quickSort(List<Integer> numbers, int begin,int end){
-		int[] stack = new int[1024];
+		int[] stack = new int[4096];
 		int sp = 0;
 		int p = 0;
 		while(true){
 			while(begin < end){
+				/* bubble sort method is slower than quick sort method.(any number)
+				 * so no use bubble sort.
+				 * 
+				if (end-begin< 400){
+					bubbleSort(numbers,begin,end);
+					break;
+				}
+				*/
+				
 				int where = (begin+end)/2;
 				int pivot = numbers.get(where);
 				numbers.set(where, numbers.get(begin));
@@ -83,7 +93,7 @@
 		}
 	}
 	
-	public static void bubbleSort(List<Integer> numbers){
+	public static void bubbleSort(List<Integer> numbers ,int begin,int end){
 		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)){
--- a/src/alice/test/codesegment/local/bitonicsort/SortTest.java	Thu Dec 13 17:26:05 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/SortTest.java	Fri Dec 14 17:17:41 2012 +0900
@@ -41,7 +41,7 @@
 		Sort.check(list);
 		
 		t = System.currentTimeMillis();
-		Sort.bubbleSort(list2);
+		Sort.bubbleSort(list2,0,list2.size()-1);
 		System.out.println("bubble sort : "+ (System.currentTimeMillis()-t)+" ms");
 		Sort.check(list2);
 	}