Mercurial > hg > Database > Alice

changeset 155:0979827c859b working

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add bitonic sort. But can not execute.
author sugi
date Mon, 10 Dec 2012 19:36:39 +0900
parents d6afa779dd49
children e0f077820d59
files src/alice/test/codesegment/local/bitonicsort/DataInfo.java src/alice/test/codesegment/local/bitonicsort/DataList.java src/alice/test/codesegment/local/bitonicsort/LocalBitonicSort.java src/alice/test/codesegment/local/bitonicsort/MakeData.java src/alice/test/codesegment/local/bitonicsort/SetInfo.java src/alice/test/codesegment/local/bitonicsort/SetTask.java src/alice/test/codesegment/local/bitonicsort/Sort.java src/alice/test/codesegment/local/bitonicsort/SortConfig.java src/alice/test/codesegment/local/mergesort/LocalMergeSort.java src/alice/test/codesegment/local/mergesort/ShowResult.java src/alice/test/codesegment/local/mergesort/SortStart.java src/alice/test/codesegment/local/mergesort/StartSort.java
diffstat 12 files changed, 294 insertions(+), 41 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/DataInfo.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,16 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import org.msgpack.annotation.Message;
+
+@Message
+public class DataInfo {
+	public int index;
+	public int ptr;
+	
+	public DataInfo(){}
+	
+	public DataInfo(int _index, int _ptr){
+		index = _index;
+		ptr = _ptr;
+	}
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/DataList.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,29 @@
+package alice.test.codesegment.local.bitonicsort;
+
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+
+import org.msgpack.annotation.Message;
+
+@Message
+public class DataList {
+
+	List<Integer> table = new LinkedList<Integer>();
+	public DataList(){};
+	public DataList(List<Integer> numbers){
+		table = numbers;
+	};
+	
+	public DataList getSubList(int start, int size){
+		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);
+	}
+	
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/LocalBitonicSort.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,8 @@
+package alice.test.codesegment.local.bitonicsort;
+
+public class LocalBitonicSort {
+	public static void main(String[] args){
+		SortConfig conf = new SortConfig(args);
+		new SetInfo(conf).execute();
+	}
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/MakeData.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,32 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import java.util.Random;
+
+import alice.codesegment.CodeSegment;
+import alice.datasegment.CommandType;
+import alice.datasegment.Receiver;
+
+public class MakeData extends CodeSegment {
+	
+	private Receiver info1 = ids.create(CommandType.PEEK);
+	private Receiver info2 = ids.create(CommandType.TAKE);
+
+	public MakeData(){
+		info1.setKey("local", "sortconf");
+		info2.setKey("local", "data");
+	}
+	
+	@Override
+	public void run() {
+		SortConfig conf = info1.asClass(SortConfig.class);
+		DataList list = info2.asClass(DataList.class);
+		int size = conf.getLength();
+		for (int i = 0;i<size;i++){
+			Random rnd = new Random();
+			//DataInfo info = new DataInfo(rnd.nextInt(Integer.MAX_VALUE),i);
+			list.table.add(rnd.nextInt(Integer.MAX_VALUE));
+		}
+		
+		ods.update("local", "list", list);
+	}
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/SetInfo.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,22 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import alice.codesegment.CodeSegment;
+
+public class SetInfo extends CodeSegment {
+
+	private SortConfig conf;
+	public SetInfo(SortConfig conf) {
+		this.conf = conf;
+	}
+
+	@Override
+	public void run() {
+		ods.put("local", "sortconf", conf);
+		ods.put("local", "data", new DataList());
+		
+		new MakeData();
+		new SetTask();
+	}
+
+	
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/SetTask.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,42 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import alice.codesegment.CodeSegment;
+import alice.datasegment.CommandType;
+import alice.datasegment.Receiver;
+
+public class SetTask extends CodeSegment {
+	
+	private Receiver info1 = ids.create(CommandType.PEEK);
+	private Receiver info2 = ids.create(CommandType.PEEK);
+	
+	SetTask(){
+		info1.setKey("local","sortconf");
+		info2.setKey("local","list");
+	}
+	
+	@Override
+	public void run() {
+		SortConfig conf = info1.asClass(SortConfig.class);
+		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数
+		int last_block_num = conf.getLength() - (conf.getSplitNum() - 1)*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);
+			}
+			// 最後のblockは端数
+			ods.update("local", key+i, list.getSubList(i*block_num, last_block_num));
+			new Sort(key+i);
+		}
+		ods.update("local", "count", sort_count-1);
+		
+	}
+
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/Sort.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,66 @@
+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;
+	}
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/SortConfig.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,38 @@
+package alice.test.codesegment.local.bitonicsort;
+
+import org.msgpack.annotation.Message;
+
+@Message
+public class SortConfig {
+	public int length = 1200;
+	public int MAX_BLOCK_SIZE = 1024;
+	public int cpu = 1;
+	
+	public SortConfig(){}
+	
+	public SortConfig(String[] args){
+		for (int i=0;i<args.length; i++){
+			if ("-l".equals(args[i])){
+				length = Integer.parseInt(args[++i]);	
+			} else if ("-b".equals(args[i])){
+				MAX_BLOCK_SIZE = Integer.parseInt(args[++i]);	
+			}
+		}
+	}
+
+	public int getLength() {
+		return length;
+	}
+
+	public int getblockSize() {
+		return MAX_BLOCK_SIZE;
+	}
+	
+	public int getSplitNum(){
+		if (length / cpu < MAX_BLOCK_SIZE){
+			return cpu;
+		} else {
+			return (length + MAX_BLOCK_SIZE -1) / MAX_BLOCK_SIZE;
+		}
+	}
+}
--- a/src/alice/test/codesegment/local/mergesort/LocalMergeSort.java	Tue Dec 04 15:58:09 2012 +0900
+++ b/src/alice/test/codesegment/local/mergesort/LocalMergeSort.java	Mon Dec 10 19:36:39 2012 +0900
@@ -3,6 +3,6 @@
 public class LocalMergeSort {
 	public static void main(String[] args){
 		SortConfig conf = new SortConfig(args);
-		new StartSort(conf).execute();
+		new SortStart(conf).execute();
 	}
 }
--- a/src/alice/test/codesegment/local/mergesort/ShowResult.java	Tue Dec 04 15:58:09 2012 +0900
+++ b/src/alice/test/codesegment/local/mergesort/ShowResult.java	Mon Dec 10 19:36:39 2012 +0900
@@ -21,7 +21,7 @@
 
 	@Override
 	public void run() {
-		System.out.println(System.currentTimeMillis() - StartSort.t);
+		System.out.println(System.currentTimeMillis() - SortStart.t);
 		List<Value> list = info.asArray();
 		for (int i =0; i+1< list.size();i++){
 			if (list.get(i).asIntegerValue().getInt()>list.get(i+1).asIntegerValue().getInt()){
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/mergesort/SortStart.java	Mon Dec 10 19:36:39 2012 +0900
@@ -0,0 +1,39 @@
+package alice.test.codesegment.local.mergesort;
+
+import java.io.IOException;
+import java.util.Random;
+
+import alice.codesegment.CodeSegment;
+import alice.codesegment.SingletonMessage;
+
+public class SortStart extends CodeSegment{
+	public static long t;
+	SortConfig conf;
+	public SortStart(SortConfig conf){
+		this.conf = conf;
+	}
+	
+	@Override
+	public void run() {
+		int size = conf.size;
+		int[] array = new int[size];
+		for (int i=0;i< size; i++){
+			Random rnd = new Random();
+			array[i] = 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);
+	
+		new SeparateArray(0);
+		new ShowResult(0);
+		t = System.currentTimeMillis();
+	}
+
+}
--- a/src/alice/test/codesegment/local/mergesort/StartSort.java	Tue Dec 04 15:58:09 2012 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,39 +0,0 @@
-package alice.test.codesegment.local.mergesort;
-
-import java.io.IOException;
-import java.util.Random;
-
-import alice.codesegment.CodeSegment;
-import alice.codesegment.SingletonMessage;
-
-public class StartSort extends CodeSegment{
-	public static long t;
-	SortConfig conf;
-	public StartSort(SortConfig conf){
-		this.conf = conf;
-	}
-	
-	@Override
-	public void run() {
-		int size = conf.size;
-		int[] array = new int[size];
-		for (int i=0;i< size; i++){
-			Random rnd = new Random();
-			array[i] = 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);
-	
-		new SeparateArray(0);
-		new ShowResult(0);
-		t = System.currentTimeMillis();
-	}
-
-}