Mercurial > hg > Database > Alice

changeset 156:e0f077820d59 working

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
minor change
author sugi
date Tue, 11 Dec 2012 15:50:17 +0900
parents 0979827c859b
children 12c8be670e0f
files src/alice/test/codesegment/local/bitonicsort/DataList.java 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/Sort.java
diffstat 5 files changed, 318 insertions(+), 79 deletions(-) [+]
line wrap: on
line diff
--- a/src/alice/test/codesegment/local/bitonicsort/DataList.java	Mon Dec 10 19:36:39 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/DataList.java	Tue Dec 11 15:50:17 2012 +0900
@@ -10,20 +10,41 @@
 @Message
 public class DataList {
 
-	List<Integer> table = new LinkedList<Integer>();
+	public List<Integer> table = new LinkedList<Integer>();
+	public int num;
+	public String position;
+	
 	public DataList(){};
+	
 	public DataList(List<Integer> numbers){
 		table = numbers;
-	};
+	}
+	public DataList(List<Integer> numbers,int arrayNum){
+		table = numbers;
+		num = arrayNum;
+	}
+	public DataList(List<Integer> numbers ,int arrayNum ,String p){
+		table = numbers;
+		num = arrayNum;
+		position = p;
+	}
 	
-	public DataList getSubList(int start, int size){
+	public DataList getSubList(int start, int size, int arrayNum){
 		List<Integer> table2 = new LinkedList<Integer>();
 		ListIterator<Integer> iter = table.listIterator(start);
 		for (int i=start;i<(start+size);i++){
 			table2.add(iter.next());
 		}
 		//System.out.println(table2);
-		return new DataList(table2);
+		return new DataList(table2,arrayNum);
 	}
-	
+	public DataList createDataList(int start, int size, int arrayNum, String p){
+		List<Integer> table2 = new LinkedList<Integer>();
+		ListIterator<Integer> iter = table.listIterator(start);
+		for (int i=start;i<(start+size);i++){
+			table2.add(iter.next());
+		}
+		//System.out.println(table2);
+		return new DataList(table2,arrayNum,p);
+	}
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Tue Dec 11 15:50:17 2012 +0900
@@ -0,0 +1,139 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import java.util.LinkedList;
+import java.util.List;
+
+import alice.codesegment.CodeSegment;
+import alice.datasegment.CommandType;
+import alice.datasegment.Receiver;
+
+public class EvenPhase extends CodeSegment{
+	private Receiver info1; 
+	private Receiver info2;
+	private Receiver info3 = ids.create(CommandType.PEEK);
+	private Receiver info4 = ids.create(CommandType.PEEK);
+	
+	public EvenPhase(String key1){
+		info1 = ids.create(CommandType.TAKE);
+		info1.setKey("local",key1);
+		info3.setKey("block_num");
+		info4.setKey("last_block_num");
+	}
+	
+	public EvenPhase(String key1,String key2){
+		info1 = ids.create(CommandType.TAKE);
+		info1.setKey("local",key1);
+		info2 = ids.create(CommandType.TAKE);
+		info2.setKey("local",key2);
+		info3.setKey("block_num");
+		info4.setKey("last_block_num");
+	}
+	
+	@Override
+	public void run() {
+		
+		DataList list1 = info1.asClass(DataList.class);
+		DataList list2 = info2.asClass(DataList.class);
+		int block_num = info3.asInteger();
+
+		list2.table = quickSort(list1.table,list2.table);
+		System.out.println(list2.num+""+list2.table);
+		if (!list2.position.equals("last")){
+			ods.update("local", list2.num+"f", 
+					list2.createDataList(0, block_num/2, list2.num, "f"));
+			ods.update("local", list2.num+"b",
+					list2.createDataList(block_num/2, block_num/2, list2.num, "b"));
+			new OddPhase(list2.num+"b",(list2.num+1)+"f");
+		} else {
+			int last_block_num = info4.asInteger();
+			ods.update("local", list2.num+"f", 
+					list2.createDataList(0, block_num/2, list2.num, "f"));
+			ods.update("local", list2.num+"b", 
+					list2.createDataList(block_num/2, last_block_num, list2.num, "last"));
+			new OddPhase(list2.num+"b");
+		}
+			
+		
+		
+	}
+	
+	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 (numbers.size() < 400){ 
+			return bubbleSort(numbers);
+			
+		} */
+		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 List<Integer> bubbleSort(List<Integer> numbers){
+		List<Integer> sorted = new LinkedList<Integer>();
+		return sorted;
+	}
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Tue Dec 11 15:50:17 2012 +0900
@@ -0,0 +1,140 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import java.util.LinkedList;
+import java.util.List;
+
+import alice.codesegment.CodeSegment;
+import alice.datasegment.CommandType;
+import alice.datasegment.Receiver;
+
+public class OddPhase extends CodeSegment{
+	private Receiver info1; 
+	private Receiver info2;
+	private Receiver info3 = ids.create(CommandType.PEEK);
+	
+	public OddPhase(String key1){
+		info1 = ids.create(CommandType.TAKE);
+		info1.setKey("local",key1);
+		info3.setKey("block_num");
+	}
+	
+	public OddPhase(String key1,String key2){
+		info1 = ids.create(CommandType.TAKE);
+		info1.setKey("local",key1);
+		info2 = ids.create(CommandType.TAKE);
+		info2.setKey("local",key2);
+		info3.setKey("block_num");
+	}
+	
+	@Override
+	public void run() {
+		int block_num = info3.asInteger();
+		if (info2==null){
+			DataList list = info1.asClass(DataList.class);
+			list.table = quickSort(list.table);
+			if (!list.position.equals("last")){ //(-1b,0f)のタスクが存在する
+				/*
+				 * ソートされたlistから指定した部分をコピーしている
+				 * ソートしている最中にlistを2つ作った方がいいかも。
+				 */
+				ods.update("local", list.num+"f", 
+						list.createDataList(0, block_num/2, list.num, "f"));
+				ods.update("local", list.num+"b",
+						list.createDataList(block_num/2, block_num/2, list.num, "b"));
+				new EvenPhase((list.num-1)+"b",list.num+"f");
+			} else {
+				System.out.println("list.num "+list.num);
+				ods.update("local", list.num+"f",list);
+			}
+			
+		} else {
+			DataList list1 = info1.asClass(DataList.class);
+			DataList list2 = info2.asClass(DataList.class);
+			list2.table = quickSort(list1.table,list2.table);
+			
+			
+			System.out.println("end");
+		}
+		
+	}
+	
+	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 (numbers.size() < 400){ 
+			return bubbleSort(numbers);
+			
+		} */
+		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 List<Integer> bubbleSort(List<Integer> numbers){
+		List<Integer> sorted = new LinkedList<Integer>();
+		return sorted;
+	}
+}
--- a/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Mon Dec 10 19:36:39 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Tue Dec 11 15:50:17 2012 +0900
@@ -7,7 +7,7 @@
 public class SetTask extends CodeSegment {
 	
 	private Receiver info1 = ids.create(CommandType.PEEK);
-	private Receiver info2 = ids.create(CommandType.PEEK);
+	private Receiver info2 = ids.create(CommandType.TAKE);
 	
 	SetTask(){
 		info1.setKey("local","sortconf");
@@ -20,20 +20,25 @@
 		DataList list = info2.asClass(DataList.class);
 		System.out.println(list.table);
 		
-		int half_num = conf.getSplitNum() - 1; 
-		int sort_count = conf.getSplitNum(); // sort完了に必要な回数
-		int block_num = (conf.getLength() + half_num ) / sort_count; // 1つのタスクでsortするdata数
+		 // sort完了に必要な回数
+		int sort_count = conf.getSplitNum();
+		ods.put("local", "sort_count", sort_count);
+		 // 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;
 			for (i = 0;i< conf.getSplitNum()-1; i++){
-				ods.update("local", key+i, list.getSubList(i*block_num, block_num));
-				new Sort(key+i);
+				ods.update("local", key+i, list.createDataList(i*block_num, block_num,i,"nolast"));
+				new OddPhase(key+i);
 			}
+			
 			// 最後のblockは端数
-			ods.update("local", key+i, list.getSubList(i*block_num, last_block_num));
-			new Sort(key+i);
+			ods.update("local", key+i, list.createDataList(i*block_num, last_block_num,i,"last"));
+			new OddPhase(key+i);
 		}
 		ods.update("local", "count", sort_count-1);
 		
--- a/src/alice/test/codesegment/local/bitonicsort/Sort.java	Mon Dec 10 19:36:39 2012 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,66 +0,0 @@
-package alice.test.codesegment.local.bitonicsort;
-
-import java.util.LinkedList;
-import java.util.List;
-
-import alice.codesegment.CodeSegment;
-import alice.datasegment.CommandType;
-import alice.datasegment.Receiver;
-
-public class Sort extends CodeSegment{
-	private Receiver info1 = ids.create(CommandType.PEEK);
-	String key;
-	
-	public Sort(String key){
-		info1.setKey("local",key);
-		
-	}
-	
-	@Override
-	public void run() {
-		DataList list = info1.asClass(DataList.class);
-		if (list.table.size()<2) {ods.update("local",key,list);}
-		list.table = quickSort(list.table);
-		System.out.println(list.table);
-		//System.exit(0);
-		
-	}
-	
-	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> bubbleSort(List<Integer> numbers){
-		List<Integer> sorted = new LinkedList<Integer>();
-		return sorted;
-	}
-}