Mercurial > hg > Members > tatsuki > Alice

changeset 211:b8f72b378f18 working

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
refactor bintonic sort
author one
date Wed, 27 Mar 2013 16:39:51 +0900
parents 214a13d5ee31
children b5daccf36104 665ccc899b3b
files src/alice/codesegment/OutputDataSegment.java src/alice/test/codesegment/local/bitonicsort/DataList.java 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/SetInfo.java src/alice/test/codesegment/local/bitonicsort/SetTask.java
diffstat 7 files changed, 82 insertions(+), 151 deletions(-) [+]
line wrap: on
line diff
--- a/src/alice/codesegment/OutputDataSegment.java	Wed Mar 27 14:45:59 2013 +0900
+++ b/src/alice/codesegment/OutputDataSegment.java	Wed Mar 27 16:39:51 2013 +0900
@@ -6,8 +6,12 @@
 import org.msgpack.type.Value;
 import org.msgpack.type.ValueFactory;
 
+import alice.datasegment.Command;
+import alice.datasegment.CommandType;
 import alice.datasegment.DataSegment;
+import alice.datasegment.DataSegmentKey;
 import alice.datasegment.Receiver;
+import alice.test.codesegment.local.bitonicsort.DataList;
 
 public class OutputDataSegment {
 	
@@ -30,6 +34,12 @@
 		}
 	}
 	
+	public void flip(Receiver receiver) {
+		//DataSegment.getLocal().put(receiver.key, receiver.val,receiver.obj);
+		DataSegmentKey key = DataSegment.getLocal().getDataSegmentKey(receiver.key);
+		key.runCommand(new Command(CommandType.PUT,null,null, receiver.val,receiver.obj, 0,0,null,null, "local"));
+	}
+	
 	public void put(String key, Value val) {
 		DataSegment.getLocal().put(key, val);
 	}
@@ -164,4 +174,6 @@
 
 	
 
+	
+
 }
--- a/src/alice/test/codesegment/local/bitonicsort/DataList.java	Wed Mar 27 14:45:59 2013 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/DataList.java	Wed Mar 27 16:39:51 2013 +0900
@@ -36,5 +36,23 @@
 		}
 		System.out.println();
 	}
+
+	public static void merge(DataList list1, DataList list2) {
+		int[] t1 = list1.table; 
+		int[] t2 = list2.table; 
+		int i = 0, j= 0;
+		while (i< t1.length){
+			if (t1[i] < t2[j]) {
+				i++;
+			} else {
+				int tmp = t1[i];
+				t1[i] = t2[j];
+				t2[j] = tmp;
+				j++;
+			}
+			
+		}
+		
+	}
 	
 }
--- a/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Wed Mar 27 14:45:59 2013 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,84 +0,0 @@
-package alice.test.codesegment.local.bitonicsort;
-
-import alice.codesegment.CodeSegment;
-import alice.datasegment.CommandType;
-import alice.datasegment.Receiver;
-
-public class EvenPhase extends CodeSegment{
-	private Receiver info0 = ids.create(CommandType.PEEK); // range
-	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 info5 = ids.create(CommandType.PEEK); // sort_count
-	private Receiver info6 = ids.create(CommandType.TAKE); // count
-	
-	public EvenPhase(String key0 ,String key1 ,int index,String key6){
-		info0.setKey(key0);
-		info1 = ids.create(CommandType.TAKE);
-		info1.setKey(key1,index);
-		info3.setKey("block_num");
-		info4.setKey("last_block_num");
-		info5.setKey("sort_count");
-		info6.setKey(key6);
-	}
-	
-	public EvenPhase(String key0,String key1,String key2,int index,String key6){
-		info0.setKey(key0);
-		info1 = ids.create(CommandType.TAKE);
-		info1.setKey(key1,index);
-		info2 = ids.create(CommandType.TAKE);
-		info2.setKey(key2,index);
-		info3.setKey("block_num");
-		info4.setKey("last_block_num");
-		info5.setKey("sort_count");
-		info6.setKey(key6);
-	}
-	
-	@Override
-	public void run() {
-		RangeInfo info = info0.asClass(RangeInfo.class);
-		int sort_count = info5.asInteger();
-		int count = info6.asInteger();
-		
-		if (info2==null){
-			DataList list = (DataList)info1.obj;
-			if (count > sort_count){
-				ods.update("array"+info.range, list ,false);
-				return;
-			}
-			ods.put(info.range+"f", "dummy");
-			ods.put(info.range+"b", list, false);
-			//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 {
-			DataList list1 = (DataList)info1.obj;
-			DataList list2 = (DataList)info2.obj;
-			
-			DataList list3 = new DataList(list1.table.length+list2.table.length);
-		    System.arraycopy(list1.table, 0, list3.table, 0, list1.table.length);
-		    System.arraycopy(list2.table, 0, list3.table, list1.table.length, list2.table.length);
-			
-		    if (count > sort_count){
-				ods.update("array"+info.range, list3 ,false);
-				return;
-			}
-			int block_num = info3.asInteger();
-			Sort.quickSort(list3, 0, list3.table.length-1);
-			if (!info.lastFlag){
-				ods.put(info.range+"f",	list3.createDataList(0, block_num/2) ,false);
-				ods.put(info.range+"b",	list3.createDataList(block_num/2, block_num/2),false);
-				//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(info.range+"f", list3.createDataList(0, block_num/2) ,false);
-				ods.put(info.range+"b", list3.createDataList(block_num/2, last_block_num) ,false);
-				//System.out.println("next Odd "+info.range+" "+ info.range+"b");
-				new OddPhase(info0.key ,info.range+"b",count,info6.key);
-			}
-
-		}
-		ods.update(info6.key, count+1);
-	}
-}
--- a/src/alice/test/codesegment/local/bitonicsort/MakeData.java	Wed Mar 27 14:45:59 2013 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/MakeData.java	Wed Mar 27 16:39:51 2013 +0900
@@ -18,6 +18,7 @@
 	
 	@Override
 	public void run() {
+		// This conversion over head should be remove.
 		SortConfig conf = info1.asClass(SortConfig.class);
 		DataList list = (DataList)info2.obj;
 		int size = conf.getLength();
--- a/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Wed Mar 27 14:45:59 2013 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Wed Mar 27 16:39:51 2013 +0900
@@ -13,14 +13,6 @@
 	private Receiver info5 = ids.create(CommandType.PEEK); // sort_count
 	private Receiver info6 = ids.create(CommandType.TAKE); // count
 	
-	public OddPhase(String key0 ,String key1 ,int index,String key6){
-		info0.setKey(key0);
-		info1 = ids.create(CommandType.TAKE);
-		info1.setKey(key1,index);
-		info3.setKey("block_num");
-		info5.setKey("sort_count");
-		info6.setKey(key6);
-	}
 	
 	public OddPhase(String key0,String key1,String key2,int index,String key6){
 		info0.setKey(key0);
@@ -36,61 +28,36 @@
 	@Override
 	public void run() {
 		RangeInfo info = info0.asClass(RangeInfo.class);
-		int block_num = info3.asInteger();
 		int sort_count = info5.asInteger();
 		int count = info6.asInteger();
 		//System.out.println("count is " +count);
-		if (info2==null){
-			DataList list = (DataList)info1.obj;
-			if (count > sort_count){
-				ods.update("array"+info.range, list, false);
-				return;
-			}
-			Sort.quickSort(list,0,list.table.length-1);
-			if (!info.lastFlag){ 
-				ods.put(info.range+"f", list.createDataList(0, block_num/2) ,false);
-				ods.put(info.range+"b", list.createDataList(block_num/2, block_num/2) ,false);
-				
-				if (info.range==0){
-					//System.out.println("next Even "+info.range+" "+info.range+"f");	
-					new EvenPhase(info0.key,info.range+"f",count,info6.key);
-				} else {
-					//System.out.println("next Even "+info.range+" "+ (info.range-1)+"b"+" "+(info.range)+"f");
-					new EvenPhase(info0.key,(info.range-1)+"b",info.range+"f",count,info6.key);
-				}
-			} else {
-				ods.put(info.range+"f",list, false);
-				ods.put(info.range+"b","dummy");
-				//System.out.println("next Even "+info.range+" "+ (info.range-1)+"b"+" "+(info.range)+"f");
-				new EvenPhase(info0.key,(info.range-1)+"b",info.range+"f",count,info6.key);
-			}
-			
-		} else {
+		
+		int i = info.range;
+		if (count<sort_count){		
 			DataList list1 = (DataList)info1.obj;
 			DataList list2 = (DataList)info2.obj;
 			
-			DataList list3 = new DataList(list1.table.length+list2.table.length);
-			System.arraycopy(list1.table, 0, list3.table, 0, list1.table.length);
-			System.arraycopy(list2.table, 0, list3.table, list1.table.length, list2.table.length);
+			Sort.quickSort(list1,0,list1.table.length-1);
+			Sort.quickSort(list2,0,list2.table.length-1);
+			DataList.merge(list1,list2);
 			
-			if (count > sort_count){
-				ods.update("array"+info.range, list3, false);
-				return;
-			}
+			ods.flip(info1);
+			ods.flip(info2);
 
-			Sort.quickSort(list3,0,list3.table.length-1);
-			ods.put(info.range+"f", list3.createDataList(0, block_num/2) ,false);
-			ods.put(info.range+"b", list3.createDataList(block_num/2, block_num/2) ,false);
-
-			if (info.range==0){
-				//System.out.println("next Even2b "+info.range+" "+ info.range+"f");
-				new EvenPhase(info0.key,info.range+"f",count,info6.key);
-			} else {
-				//System.out.println("next Even2b "+info.range+" "+ (info.range-1)+"b"+" "+info.range+"f");
-				new EvenPhase(info0.key,(info.range-1)+"b",info.range+"f",count,info6.key);
+			
+			
+			if (i+2 < SetInfo.array.length){
+				String f = (count%2==1) ? SetInfo.array[i] : SetInfo.array[i+1];
+				String b = (count%2==1) ? SetInfo.array[i+1] : SetInfo.array[i+2];
+				new OddPhase(info0.key, f, b,count,info6.key);
 			}
+		} else {
+			ods.put(SetInfo.result[i*2], info1);
+			ods.put(SetInfo.result[i*2+1], info2);
 		}
 		ods.update(info6.key, count+1);
+		
+		
 	}
 	
 }
--- a/src/alice/test/codesegment/local/bitonicsort/SetInfo.java	Wed Mar 27 14:45:59 2013 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/SetInfo.java	Wed Mar 27 16:39:51 2013 +0900
@@ -5,6 +5,10 @@
 public class SetInfo extends CodeSegment {
 
 	private SortConfig conf;
+	public  static String[] range;
+	public  static String[] array;
+	public  static String[] count;
+	public static String[] result;
 	public SetInfo(SortConfig conf) {
 		this.conf = conf;
 	}
@@ -13,10 +17,26 @@
 	public void run() {
 		ods.put("sortconf", conf);
 		ods.put("data", new DataList(conf.length), false);
+		// sortconf and datasegments should be passed directory.
 		
+		create_keys();
 		new MakeData();
 		new SetTask();
 	}
 
+	private void create_keys() {
+		range = new String[conf.length*2];
+		array = new String[conf.length*2];
+		count = new String[conf.length*2];
+		result = new String[conf.length*2];
+		
+		for(int i = 0 ; i < conf.length*2 ; i++) {
+			range[i] = "range" + i;
+			array[i] = "array" + i;
+			count[i] = "count" + i;
+			result[i] = "result" + i;
+		}
+		
+	}
 	
 }
--- a/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Wed Mar 27 14:45:59 2013 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Wed Mar 27 16:39:51 2013 +0900
@@ -19,32 +19,29 @@
 		SortConfig conf = info1.asClass(SortConfig.class);
 		DataList list = (DataList)info2.obj;
 		
-		int sort_count = conf.getSplitNum();
+		int sort_count = conf.getSplitNum()*2;
 		ods.put("sort_count", sort_count*2);
 	
-		int block_num = (conf.getLength() + conf.getSplitNum() - 1 ) / sort_count;
+		int block_num = (conf.getLength() + sort_count - 1 ) / sort_count;
 		ods.put("block_num", block_num);
-		int last_block_num = conf.getLength() - (conf.getSplitNum() - 1)*block_num;
+		int last_block_num = conf.getLength() - (sort_count - 1)*block_num;
 		ods.put("last_block_num", last_block_num);
 		
 		System.out.println("sort start");
 		t = System.currentTimeMillis();
 		
 		{
-			String key = "array";
 			int i = 0;
-			for (i = 0;i< conf.getSplitNum()-1; i++){
-				ods.put("range"+i, new RangeInfo(i,false));
-				ods.update(key+i, list.createDataList(i*block_num, block_num) ,false);
-				ods.update("count"+i, 0);
-				new OddPhase("range"+i,key+i,0,"count"+i);
+			for (i = 0;i< sort_count/2; i++){
+				// anonymas datasegmaents should be used. 
+				ods.put(SetInfo.range[i], new RangeInfo(i,i==sort_count-1));
+				ods.update(SetInfo.array[i*2], list.createDataList(i*2*block_num, block_num) ,false);
+				ods.update(SetInfo.array[i*2+1], list.createDataList((i*2+1)*block_num, block_num) ,false);
+				ods.update(SetInfo.count[i], 0);
+				new OddPhase(SetInfo.range[i],SetInfo.array[i*2],SetInfo.array[i*2+1],0,SetInfo.count[i]);
 			}
-			
-			ods.put("range"+i, new RangeInfo(i,true));
-			ods.update(key+i, list.createDataList(i*block_num, last_block_num) ,false);
-			ods.update("count"+i, 0);
-			ods.put("arraynum",i+1);
-			new OddPhase("range"+i,key+i,0,"count"+i);
+		
+			ods.put("arraynum",i);
 			new ShowData(i+1);
 			
 		}