Mercurial > hg > Database > Alice
changeset 207:7dddff9fa7f3 working
package name renamed
| author | sugi |
|---|---|
| date | Tue, 26 Mar 2013 13:08:45 +0900 |
| parents | 5016c7e18c76 |
| children | a645cece5edc |
| files | .settings/org.eclipse.core.resources.prefs src/alice/datasegment/Command.java src/alice/test/codesegment/local/bitonicsort/noarraylist/DataInfo.java src/alice/test/codesegment/local/bitonicsort/noarraylist/DataList.java src/alice/test/codesegment/local/bitonicsort/noarraylist/EvenPhase.java src/alice/test/codesegment/local/bitonicsort/noarraylist/LocalBitonicSort.java src/alice/test/codesegment/local/bitonicsort/noarraylist/MakeData.java src/alice/test/codesegment/local/bitonicsort/noarraylist/OddPhase.java src/alice/test/codesegment/local/bitonicsort/noarraylist/RangeInfo.java src/alice/test/codesegment/local/bitonicsort/noarraylist/SetInfo.java src/alice/test/codesegment/local/bitonicsort/noarraylist/SetTask.java src/alice/test/codesegment/local/bitonicsort/noarraylist/ShowData.java src/alice/test/codesegment/local/bitonicsort/noarraylist/Sort.java src/alice/test/codesegment/local/bitonicsort/noarraylist/SortConfig.java src/alice/test/codesegment/local/bitonicsort/noarraylist/SortTest.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/DataInfo.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/DataList.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/EvenPhase.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/LocalBitonicSort.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/MakeData.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/OddPhase.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/RangeInfo.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/SetInfo.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/SetTask.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/ShowData.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/Sort.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/SortConfig.java src/alice/test/codesegment/local/bitonicsort/noarrraylist/SortTest.java |
| diffstat | 28 files changed, 557 insertions(+), 562 deletions(-) [+] |
line wrap: on
line diff
--- a/.settings/org.eclipse.core.resources.prefs Tue Mar 26 01:45:34 2013 +0900 +++ b/.settings/org.eclipse.core.resources.prefs Tue Mar 26 13:08:45 2013 +0900 @@ -1,3 +1,3 @@ eclipse.preferences.version=1 encoding//src/alice/test/codesegment/local/bitonicsort/SortTest.java=UTF-8 -encoding//src/alice/test/codesegment/local/bitonicsort/noarrraylist/SortTest.java=UTF-8 +encoding//src/alice/test/codesegment/local/bitonicsort/noarraylist/SortTest.java=UTF-8
--- a/src/alice/datasegment/Command.java Tue Mar 26 01:45:34 2013 +0900 +++ b/src/alice/datasegment/Command.java Tue Mar 26 13:08:45 2013 +0900 @@ -63,14 +63,9 @@ public void setElement(CommandType cmdType, String key, Value val, Object obj){ this.type = cmdType; - this.receiver = null; this.key = key; this.val = val; this.obj = obj; - this.index = 0; - this.seq = 0; - this.replyQueue = null; - this.cs = null; this.reverseKey = "local"; }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/DataInfo.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,16 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +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/noarraylist/DataList.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,40 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +import org.msgpack.annotation.Message; + +@Message +public class DataList { + + public int[] table; + + public DataList(int size){ + table = new int[size]; + } + + public DataList(int[] numbers){ + table = numbers; + } + + public DataList createDataList(int start, int size){ + int[] table2 = new int[size]; + for (int i=start,j=0;i<(start+size);i++,j++){ + table2[j] = table[i]; + } + return new DataList(table2); + } + + public void swap(int i, int j){ + int tmp = table[i]; + table[i] = table[j]; + table[j] = tmp; + } + + public void showData(){ + for(int i = 0;i<table.length;i++){ + System.out.print(table[i]+ " "); + + } + System.out.println(); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/EvenPhase.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,84 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +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){ + info1.flip(CommandType.UPDATE, "array"+info.range, list ,false); + return; + } + info1.flip(CommandType.PUT, info.range+"f", "dummy"); + info3.flip(CommandType.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){ + info1.flip(CommandType.UPDATE, "array"+info.range, list3 ,false); + return; + } + int block_num = info3.asInteger(); + Sort.quickSort(list3, 0, list3.table.length-1); + if (!info.lastFlag){ + info1.flip(CommandType.PUT, info.range+"f", list3.createDataList(0, block_num/2) ,false); + info2.flip(CommandType.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(); + info1.flip(CommandType.PUT, info.range+"f", list3.createDataList(0, block_num/2) ,false); + info2.flip(CommandType.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); + } + + } + info6.flip(CommandType.UPDATE, info6.key, count+1); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/LocalBitonicSort.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,13 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +import alice.daemon.AliceDaemon; +import alice.daemon.Config; + +public class LocalBitonicSort { + public static void main(String[] args){ + new AliceDaemon(new Config(args)).listen(); // logger off + + 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/noarraylist/MakeData.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,30 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +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("sortconf"); + info2.setKey("data"); + } + + @Override + public void run() { + SortConfig conf = info1.asClass(SortConfig.class); + DataList list = (DataList)info2.obj; + int size = conf.getLength(); + Random rnd = new Random(); + for (int i = 0; i < size; i++){ + list.table[i] = rnd.nextInt(100000); + } + info2.flip(CommandType.UPDATE, "list", list, false); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/OddPhase.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,96 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +import alice.codesegment.CodeSegment; +import alice.datasegment.CommandType; +import alice.datasegment.Receiver; + +public class OddPhase 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 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); + info1 = ids.create(CommandType.TAKE); + info1.setKey(key1,index); + info2 = ids.create(CommandType.TAKE); + info2.setKey(key2,index); + info3.setKey("block_num"); + info5.setKey("sort_count"); + info6.setKey(key6); + } + + @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){ + info1.flip(CommandType.UPDATE, "array"+info.range, list, false); + return; + } + Sort.quickSort(list,0,list.table.length-1); + if (!info.lastFlag){ + info1.flip(CommandType.PUT, info.range+"f", list.createDataList(0, block_num/2) ,false); + info3.flip(CommandType.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 { + info1.flip(CommandType.PUT, info.range+"f",list, false); + info3.flip(CommandType.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 { + 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){ + info1.flip(CommandType.UPDATE, "array"+info.range, list3, false); + return; + } + + Sort.quickSort(list3,0,list3.table.length-1); + info1.flip(CommandType.PUT, info.range+"f", list3.createDataList(0, block_num/2) ,false); + info2.flip(CommandType.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); + } + } + info6.flip(CommandType.UPDATE, info6.key, count+1); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/RangeInfo.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,16 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +import org.msgpack.annotation.Message; + +@Message +public class RangeInfo { + public int range; + public boolean lastFlag; + + public RangeInfo(){} + public RangeInfo(int i,boolean flag){ + range = i; + lastFlag = flag; + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/SetInfo.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,22 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +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("sortconf", conf); + ods.put("data", new DataList(conf.length), false); + + new MakeData(); + new SetTask(); + } + + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/SetTask.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,56 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +import alice.codesegment.CodeSegment; +import alice.datasegment.CommandType; +import alice.datasegment.Receiver; + +public class SetTask extends CodeSegment { + public static long t; + private Receiver info1 = ids.create(CommandType.PEEK); + private Receiver info2 = ids.create(CommandType.TAKE); + + SetTask(){ + info1.setKey("sortconf"); + info2.setKey("list"); + } + + @Override + public void run() { + SortConfig conf = info1.asClass(SortConfig.class); + DataList list = (DataList)info2.obj; + + int sort_count = conf.getSplitNum(); + ods.put("sort_count", sort_count*2); + + + int block_num = (conf.getLength() + conf.getSplitNum() - 1 ) / sort_count; + ods.put("block_num", block_num); + int last_block_num = conf.getLength() - (conf.getSplitNum() - 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); + } + + 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); + new ShowData(i+1); + + } + + + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/ShowData.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,48 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +import alice.codesegment.CodeSegment; +import alice.datasegment.CommandType; +import alice.datasegment.Receiver; + +public class ShowData extends CodeSegment{ + + private Receiver[] info; + private Receiver info0 = ids.create(CommandType.PEEK); + + public ShowData(int cnt) { + info = new Receiver[cnt]; + for (int i= 0;i < cnt; i++) + info[i] = ids.create(CommandType.PEEK); + for (int i= 0;i < cnt; i++) + info[i].setKey("array"+i,1); + + info0.setKey("arraynum"); + } + + @Override + public void run() { + System.out.println(System.currentTimeMillis() -SetTask.t +" ms"); + int cnt = info0.asInteger(); + int size = 0; + + for (int i= 0;i < cnt; i++){ + DataList dlist = (DataList)info[i].obj; + size += dlist.table.length; + } + + DataList list = new DataList(size); + + int start = 0; + for (int i= 0;i < cnt; i++){ + DataList dlist = (DataList)info[i].obj; + System.arraycopy(dlist.table, 0, list.table, start, dlist.table.length); + start += dlist.table.length; + } + + System.out.println("size check :"+ list.table.length); + Sort.check(list); + System.exit(0); + } + + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/Sort.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,62 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +public class Sort { + + // this method has "stack overflow" problem + public static void quickSort(DataList data, int begin,int end){ + int[] stack = new int[8192]; + int sp = 0; + int p = 0; + while(true){ + while(begin < end){ + if (end-begin< 200){ + bubbleSort(data,begin,end); + break; + } else { + int where = (begin+end)/2; + int pivot = data.table[where]; + data.table[where] = data.table[begin]; + p = begin; + for (int i=begin+1;i<=end;i++){ + if (data.table[i]<pivot){ + p++; + if (i!=p)data.swap(p,i); + } + } + data.table[begin] = data.table[p]; + data.table[p] = pivot; + stack[sp++] = p+1; + stack[sp++] = end; + end=p-1; + } + } + if (sp==0) return; + end = stack[--sp]; + begin = stack[--sp]; + + } + } + + public static void bubbleSort(DataList data ,int begin,int end){ + for (int i=begin;i<end;i++){ + for (int j=end;j>i;j--){ + if (data.table[i] > data.table[j]){ + data.swap(i,j); + } + } + } + + + } + + public static void check(DataList data){ + System.out.println("checking ...."); + for (int i = 0; i< data.table.length-1; i++){ + if (data.table[i] > data.table[i+1]){ + System.out.println("MISS "+data.table[i]+" > "+data.table[i+1]+" Position is "+i); + return; + } + } + System.out.println("sort is succeed"); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/SortConfig.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,39 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +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]); + } + } + if (length<MAX_BLOCK_SIZE) MAX_BLOCK_SIZE = length; + } + + 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; + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/alice/test/codesegment/local/bitonicsort/noarraylist/SortTest.java Tue Mar 26 13:08:45 2013 +0900 @@ -0,0 +1,34 @@ +package alice.test.codesegment.local.bitonicsort.noarraylist; + +import java.util.Random; + +public class SortTest { + + public static void main(String args[]){ + int size = 10; + int MAX = 100; + long t; + DataList list1 = new DataList(size); + DataList list2 = new DataList(size); + + Random rnd = new Random(); + for (int i = 0; i < size; i++){ + int num = rnd.nextInt(MAX); + list1.table[i] = num; + list2.table[i] = num; + } + + // stack type quicksort + t = System.currentTimeMillis(); + Sort.quickSort(list1,0,list1.table.length-1); + System.out.println("quick sort3 : "+ (System.currentTimeMillis()-t)+" ms"); + Sort.check(list1); + + t = System.currentTimeMillis(); + Sort.bubbleSort(list2,0,list2.table.length-1); + System.out.println("bubble sort : "+ (System.currentTimeMillis()-t)+" ms"); + Sort.check(list2); + + + } +}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/DataInfo.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,16 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -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; - } -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/DataList.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,40 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -import org.msgpack.annotation.Message; - -@Message -public class DataList { - - public int[] table; - - public DataList(int size){ - table = new int[size]; - } - - public DataList(int[] numbers){ - table = numbers; - } - - public DataList createDataList(int start, int size){ - int[] table2 = new int[size]; - for (int i=start,j=0;i<(start+size);i++,j++){ - table2[j] = table[i]; - } - return new DataList(table2); - } - - public void swap(int i, int j){ - int tmp = table[i]; - table[i] = table[j]; - table[j] = tmp; - } - - public void showData(){ - for(int i = 0;i<table.length;i++){ - System.out.print(table[i]+ " "); - - } - System.out.println(); - } - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/EvenPhase.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,84 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -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){ - info1.flip(CommandType.UPDATE, "array"+info.range, list ,false); - return; - } - info1.flip(CommandType.PUT, info.range+"f", "dummy"); - info3.flip(CommandType.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){ - info1.flip(CommandType.UPDATE, "array"+info.range, list3 ,false); - return; - } - int block_num = info3.asInteger(); - Sort.quickSort(list3, 0, list3.table.length-1); - if (!info.lastFlag){ - info1.flip(CommandType.PUT, info.range+"f", list3.createDataList(0, block_num/2) ,false); - info2.flip(CommandType.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(); - info1.flip(CommandType.PUT, info.range+"f", list3.createDataList(0, block_num/2) ,false); - info2.flip(CommandType.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); - } - - } - info6.flip(CommandType.UPDATE, info6.key, count+1); - } -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/LocalBitonicSort.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,13 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -import alice.daemon.AliceDaemon; -import alice.daemon.Config; - -public class LocalBitonicSort { - public static void main(String[] args){ - new AliceDaemon(new Config(args)).listen(); // logger off - - SortConfig conf = new SortConfig(args); - new SetInfo(conf).execute(); - } -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/MakeData.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,30 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -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("sortconf"); - info2.setKey("data"); - } - - @Override - public void run() { - SortConfig conf = info1.asClass(SortConfig.class); - DataList list = (DataList)info2.obj; - int size = conf.getLength(); - Random rnd = new Random(); - for (int i = 0; i < size; i++){ - list.table[i] = rnd.nextInt(100000); - } - info2.flip(CommandType.UPDATE, "list", list, false); - } -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/OddPhase.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,96 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -import alice.codesegment.CodeSegment; -import alice.datasegment.CommandType; -import alice.datasegment.Receiver; - -public class OddPhase 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 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); - info1 = ids.create(CommandType.TAKE); - info1.setKey(key1,index); - info2 = ids.create(CommandType.TAKE); - info2.setKey(key2,index); - info3.setKey("block_num"); - info5.setKey("sort_count"); - info6.setKey(key6); - } - - @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){ - info1.flip(CommandType.UPDATE, "array"+info.range, list, false); - return; - } - Sort.quickSort(list,0,list.table.length-1); - if (!info.lastFlag){ - info1.flip(CommandType.PUT, info.range+"f", list.createDataList(0, block_num/2) ,false); - info3.flip(CommandType.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 { - info1.flip(CommandType.PUT, info.range+"f",list, false); - info3.flip(CommandType.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 { - 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){ - info1.flip(CommandType.UPDATE, "array"+info.range, list3, false); - return; - } - - Sort.quickSort(list3,0,list3.table.length-1); - info1.flip(CommandType.PUT, info.range+"f", list3.createDataList(0, block_num/2) ,false); - info2.flip(CommandType.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); - } - } - info6.flip(CommandType.UPDATE, info6.key, count+1); - } - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/RangeInfo.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,16 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -import org.msgpack.annotation.Message; - -@Message -public class RangeInfo { - public int range; - public boolean lastFlag; - - public RangeInfo(){} - public RangeInfo(int i,boolean flag){ - range = i; - lastFlag = flag; - } - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/SetInfo.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,22 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -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("sortconf", conf); - ods.put("data", new DataList(conf.length), false); - - new MakeData(); - new SetTask(); - } - - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/SetTask.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,56 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -import alice.codesegment.CodeSegment; -import alice.datasegment.CommandType; -import alice.datasegment.Receiver; - -public class SetTask extends CodeSegment { - public static long t; - private Receiver info1 = ids.create(CommandType.PEEK); - private Receiver info2 = ids.create(CommandType.TAKE); - - SetTask(){ - info1.setKey("sortconf"); - info2.setKey("list"); - } - - @Override - public void run() { - SortConfig conf = info1.asClass(SortConfig.class); - DataList list = (DataList)info2.obj; - - int sort_count = conf.getSplitNum(); - ods.put("sort_count", sort_count*2); - - - int block_num = (conf.getLength() + conf.getSplitNum() - 1 ) / sort_count; - ods.put("block_num", block_num); - int last_block_num = conf.getLength() - (conf.getSplitNum() - 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); - } - - 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); - new ShowData(i+1); - - } - - - } - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/ShowData.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,48 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -import alice.codesegment.CodeSegment; -import alice.datasegment.CommandType; -import alice.datasegment.Receiver; - -public class ShowData extends CodeSegment{ - - private Receiver[] info; - private Receiver info0 = ids.create(CommandType.PEEK); - - public ShowData(int cnt) { - info = new Receiver[cnt]; - for (int i= 0;i < cnt; i++) - info[i] = ids.create(CommandType.PEEK); - for (int i= 0;i < cnt; i++) - info[i].setKey("array"+i,1); - - info0.setKey("arraynum"); - } - - @Override - public void run() { - System.out.println(System.currentTimeMillis() -SetTask.t +" ms"); - int cnt = info0.asInteger(); - int size = 0; - - for (int i= 0;i < cnt; i++){ - DataList dlist = (DataList)info[i].obj; - size += dlist.table.length; - } - - DataList list = new DataList(size); - - int start = 0; - for (int i= 0;i < cnt; i++){ - DataList dlist = (DataList)info[i].obj; - System.arraycopy(dlist.table, 0, list.table, start, dlist.table.length); - start += dlist.table.length; - } - - System.out.println("size check :"+ list.table.length); - Sort.check(list); - System.exit(0); - } - - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/Sort.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,62 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -public class Sort { - - // this method has "stack overflow" problem - public static void quickSort(DataList data, int begin,int end){ - int[] stack = new int[8192]; - int sp = 0; - int p = 0; - while(true){ - while(begin < end){ - if (end-begin< 200){ - bubbleSort(data,begin,end); - break; - } else { - int where = (begin+end)/2; - int pivot = data.table[where]; - data.table[where] = data.table[begin]; - p = begin; - for (int i=begin+1;i<=end;i++){ - if (data.table[i]<pivot){ - p++; - if (i!=p)data.swap(p,i); - } - } - data.table[begin] = data.table[p]; - data.table[p] = pivot; - stack[sp++] = p+1; - stack[sp++] = end; - end=p-1; - } - } - if (sp==0) return; - end = stack[--sp]; - begin = stack[--sp]; - - } - } - - public static void bubbleSort(DataList data ,int begin,int end){ - for (int i=begin;i<end;i++){ - for (int j=end;j>i;j--){ - if (data.table[i] > data.table[j]){ - data.swap(i,j); - } - } - } - - - } - - public static void check(DataList data){ - System.out.println("checking ...."); - for (int i = 0; i< data.table.length-1; i++){ - if (data.table[i] > data.table[i+1]){ - System.out.println("MISS "+data.table[i]+" > "+data.table[i+1]+" Position is "+i); - return; - } - } - System.out.println("sort is succeed"); - } -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarrraylist/SortConfig.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,39 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -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]); - } - } - if (length<MAX_BLOCK_SIZE) MAX_BLOCK_SIZE = length; - } - - 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/bitonicsort/noarrraylist/SortTest.java Tue Mar 26 01:45:34 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,34 +0,0 @@ -package alice.test.codesegment.local.bitonicsort.noarrraylist; - -import java.util.Random; - -public class SortTest { - - public static void main(String args[]){ - int size = 10; - int MAX = 100; - long t; - DataList list1 = new DataList(size); - DataList list2 = new DataList(size); - - Random rnd = new Random(); - for (int i = 0; i < size; i++){ - int num = rnd.nextInt(MAX); - list1.table[i] = num; - list2.table[i] = num; - } - - // stack type quicksort - t = System.currentTimeMillis(); - Sort.quickSort(list1,0,list1.table.length-1); - System.out.println("quick sort3 : "+ (System.currentTimeMillis()-t)+" ms"); - Sort.check(list1); - - t = System.currentTimeMillis(); - Sort.bubbleSort(list2,0,list2.table.length-1); - System.out.println("bubble sort : "+ (System.currentTimeMillis()-t)+" ms"); - Sort.check(list2); - - - } -}