Mercurial > hg > Members > tatsuki > Alice
changeset 210:214a13d5ee31 working
delete list based
| author | one |
|---|---|
| date | Wed, 27 Mar 2013 14:45:59 +0900 |
| parents | 96110f25adcc |
| children | b8f72b378f18 |
| files | .settings/org.eclipse.core.resources.prefs src/alice/test/codesegment/local/bitonicsort/DataInfo.java src/alice/test/codesegment/local/bitonicsort/DataList.java src/alice/test/codesegment/local/bitonicsort/EvenPhase.java src/alice/test/codesegment/local/bitonicsort/LocalBitonicSort.java src/alice/test/codesegment/local/bitonicsort/MakeData.java src/alice/test/codesegment/local/bitonicsort/OddPhase.java src/alice/test/codesegment/local/bitonicsort/RangeInfo.java src/alice/test/codesegment/local/bitonicsort/SetInfo.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/SortConfig.java src/alice/test/codesegment/local/bitonicsort/SortTest.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/mergesort/LocalMergeSort.java src/alice/test/codesegment/local/mergesort/MergeArray.java src/alice/test/codesegment/local/mergesort/SeparateArray.java src/alice/test/codesegment/local/mergesort/ShowResult.java src/alice/test/codesegment/local/mergesort/SortConfig.java src/alice/test/codesegment/local/mergesort/SortStart.java |
| diffstat | 29 files changed, 113 insertions(+), 953 deletions(-) [+] |
line wrap: on
line diff
--- a/.settings/org.eclipse.core.resources.prefs Tue Mar 26 17:10:38 2013 +0900 +++ b/.settings/org.eclipse.core.resources.prefs Wed Mar 27 14:45:59 2013 +0900 @@ -1,3 +1,3 @@ +#Wed Mar 27 14:38:59 JST 2013 eclipse.preferences.version=1 encoding//src/alice/test/codesegment/local/bitonicsort/SortTest.java=UTF-8 -encoding//src/alice/test/codesegment/local/bitonicsort/noarraylist/SortTest.java=UTF-8
--- a/src/alice/test/codesegment/local/bitonicsort/DataList.java Tue Mar 26 17:10:38 2013 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/DataList.java Wed Mar 27 14:45:59 2013 +0900 @@ -1,36 +1,40 @@ package alice.test.codesegment.local.bitonicsort; - -import java.util.ArrayList; -import java.util.List; -import java.util.ListIterator; - import org.msgpack.annotation.Message; @Message public class DataList { - public List<Integer> table; + public int[] table; - public DataList(){ - table = new ArrayList<Integer>(); + public DataList(int size){ + table = new int[size]; } - public DataList(int size){ - table = new ArrayList<Integer>(size); - } - - public DataList(List<Integer> numbers){ + public DataList(int[] numbers){ table = numbers; } public DataList createDataList(int start, int size){ - List<Integer> table2 = new ArrayList<Integer>(size); - ListIterator<Integer> iter = table.listIterator(start); - for (int i=start;i<(start+size);i++){ - table2.add(iter.next()); + 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/EvenPhase.java Tue Mar 26 17:10:38 2013 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java Wed Mar 27 14:45:59 2013 +0900 @@ -40,6 +40,7 @@ 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){ @@ -53,17 +54,17 @@ } else { DataList list1 = (DataList)info1.obj; DataList list2 = (DataList)info2.obj; - - DataList list3 = new DataList(); - list3.table.addAll(list1.table); - list3.table.addAll(list2.table); - if (count > sort_count){ + 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.table, 0, list3.table.size()-1); + 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);
--- a/src/alice/test/codesegment/local/bitonicsort/MakeData.java Tue Mar 26 17:10:38 2013 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/MakeData.java Wed Mar 27 14:45:59 2013 +0900 @@ -19,14 +19,12 @@ @Override public void run() { SortConfig conf = info1.asClass(SortConfig.class); - DataList list = info2.asClass(DataList.class); + DataList list = (DataList)info2.obj; int size = conf.getLength(); Random rnd = new Random(); for (int i = 0; i < size; i++){ - list.table.add(rnd.nextInt(100000)); - + list.table[i] = rnd.nextInt(100000); } - ods.update("list", list, false); } }
--- a/src/alice/test/codesegment/local/bitonicsort/OddPhase.java Tue Mar 26 17:10:38 2013 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/OddPhase.java Wed Mar 27 14:45:59 2013 +0900 @@ -46,7 +46,7 @@ ods.update("array"+info.range, list, false); return; } - Sort.quickSort(list.table,0,list.table.size()-1); + 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); @@ -69,15 +69,16 @@ DataList list1 = (DataList)info1.obj; DataList list2 = (DataList)info2.obj; - DataList list3 = new DataList(); - list3.table.addAll(list1.table); - list3.table.addAll(list2.table); + 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; } - Sort.quickSort(list3.table,0,list3.table.size()-1); + 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);
--- a/src/alice/test/codesegment/local/bitonicsort/SetInfo.java Tue Mar 26 17:10:38 2013 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/SetInfo.java Wed Mar 27 14:45:59 2013 +0900 @@ -11,8 +11,8 @@ @Override public void run() { - ods.put("local", "sortconf", conf); - ods.put("local", "data", new DataList(conf.length)); + ods.put("sortconf", conf); + ods.put("data", new DataList(conf.length), false); new MakeData(); new SetTask();
--- a/src/alice/test/codesegment/local/bitonicsort/SetTask.java Tue Mar 26 17:10:38 2013 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/SetTask.java Wed Mar 27 14:45:59 2013 +0900 @@ -10,23 +10,22 @@ private Receiver info2 = ids.create(CommandType.TAKE); SetTask(){ - info1.setKey("local","sortconf"); - info2.setKey("local","list"); + info1.setKey("sortconf"); + info2.setKey("list"); } @Override public void run() { SortConfig conf = info1.asClass(SortConfig.class); DataList list = (DataList)info2.obj; - //System.out.println(list.table); int sort_count = conf.getSplitNum(); - ods.put("local", "sort_count", sort_count*2); + ods.put("sort_count", sort_count*2); int block_num = (conf.getLength() + conf.getSplitNum() - 1 ) / sort_count; - ods.put("local", "block_num", block_num); + ods.put("block_num", block_num); int last_block_num = conf.getLength() - (conf.getSplitNum() - 1)*block_num; - ods.put("local", "last_block_num", last_block_num); + ods.put("last_block_num", last_block_num); System.out.println("sort start"); t = System.currentTimeMillis(); @@ -35,16 +34,16 @@ String key = "array"; int i = 0; for (i = 0;i< conf.getSplitNum()-1; i++){ - ods.put("local", "range"+i, new RangeInfo(i,false)); + ods.put("range"+i, new RangeInfo(i,false)); ods.update(key+i, list.createDataList(i*block_num, block_num) ,false); - ods.update("local", "count"+i, 0); + ods.update("count"+i, 0); new OddPhase("range"+i,key+i,0,"count"+i); } - ods.put("local", "range"+i, new RangeInfo(i,true)); + ods.put("range"+i, new RangeInfo(i,true)); ods.update(key+i, list.createDataList(i*block_num, last_block_num) ,false); - ods.update("local", "count"+i, 0); - ods.put("local","arraynum",i+1); + 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/ShowData.java Tue Mar 26 17:10:38 2013 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/ShowData.java Wed Mar 27 14:45:59 2013 +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; @@ -17,21 +14,32 @@ 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); + info[i].setKey("array"+i,1); - info0.setKey("local", "arraynum"); + info0.setKey("arraynum"); } @Override public void run() { System.out.println(System.currentTimeMillis() -SetTask.t +" ms"); int cnt = info0.asInteger(); - List<Integer> list = new ArrayList<Integer>(); + int size = 0; + for (int i= 0;i < cnt; i++){ DataList dlist = (DataList)info[i].obj; - list.addAll(dlist.table); + size += dlist.table.length; } - System.out.println("size check :"+ list.size()); + + 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/Sort.java Tue Mar 26 17:10:38 2013 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/Sort.java Wed Mar 27 14:45:59 2013 +0900 @@ -1,124 +1,59 @@ package alice.test.codesegment.local.bitonicsort; -import java.util.Iterator; -import java.util.ArrayList; -import java.util.List; - public class Sort { - public static List<Integer> quickSort(List<Integer> numbers){ - /* - * this method has problem. - */ - - if (numbers.size() < 1000){ - bubbleSort(numbers,0,numbers.size()-1); - return numbers; - } - - int where = numbers.size() / 2; - int pivot = numbers.get(where); - int sameAsPivot = 0; - List<Integer> lesser = new ArrayList<Integer>(); - List<Integer> greater = new ArrayList<Integer>(); - List<Integer> sorted = new ArrayList<Integer>(); - Iterator<Integer> iter = numbers.iterator(); - - while(iter.hasNext()){ - int number = iter.next(); - if (number>pivot) greater.add(number); - else if (number < pivot) lesser.add(number); - else sameAsPivot++; - } - - lesser = quickSort(lesser); - greater = quickSort(greater); - // merge - sorted.addAll(lesser); - for (int i=0;i< sameAsPivot;i++) - sorted.add(pivot); - sorted.addAll(greater); - - return sorted; - } - - public static List<Integer> quickSort(List<Integer> numbers1, List<Integer> numbers2){ - List<Integer> list = new ArrayList<Integer>(); - list.addAll(numbers1); - list.addAll(numbers2); - if ( list.size() < 1000 ){ - 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[4096]; + 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){ - /* bubble sort method is slower than quick sort method.(any number) - * so no use bubble sort. - * - if (end-begin< 400){ - bubbleSort(numbers,begin,end); + if (end-begin< 150){ + 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; } - */ - - int where = (begin+end)/2; - int pivot = numbers.get(where); - numbers.set(where, numbers.get(begin)); - int i; - p = begin; - for (i=begin+1;i<=end;i++){ - if (numbers.get(i)<pivot){ - p++; - if (i!=p)swap(numbers,p,i); - } - } - numbers.set(begin, numbers.get(p)); - numbers.set(p, pivot); - stack[sp++] = p+1; - stack[sp++] = end; - end=p-1; } if (sp==0) return; end = stack[--sp]; begin = stack[--sp]; - begin = p+1; - } - } - - 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)){ - swap(numbers,i,j); - } - } + } } - public static <T> void swap(List<T> list,int index1,int index2){ - T tmp=list.get(index1); - list.set(index1,list.get(index2)); - list.set(index2, tmp); + 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(List<Integer> numbers){ - int number1 = 0; - int number2 = 0; - Iterator<Integer> iter = numbers.iterator(); + public static void check(DataList data){ System.out.println("checking ...."); - while (iter.hasNext()){ - number1 = number2; - number2 = iter.next(); - if (number1 > number2){ - System.out.println("MISS "+ number1+" > "+number2); + 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; } }
--- a/src/alice/test/codesegment/local/bitonicsort/SortTest.java Tue Mar 26 17:10:38 2013 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/SortTest.java Wed Mar 27 14:45:59 2013 +0900 @@ -1,48 +1,34 @@ package alice.test.codesegment.local.bitonicsort; -import java.util.ArrayList; -import java.util.List; import java.util.Random; public class SortTest { public static void main(String args[]){ - int size = 100000; - int MAX = 1024; + int size = 10; + int MAX = 100; long t; - List<Integer> list = new ArrayList<Integer>(); - List<Integer> list2 = new ArrayList<Integer>(); - List<Integer> sorted; + DataList list1 = new DataList(size); + DataList list2 = new DataList(size); - for (int i = 0; i < size; i++){ - Random rnd = new Random(); - list.add(rnd.nextInt(MAX)); - } + Random rnd = new Random(); for (int i = 0; i < size; i++){ - Random rnd = new Random(); - list2.add(rnd.nextInt(MAX)); + int num = rnd.nextInt(MAX); + list1.table[i] = num; + list2.table[i] = num; } - //recursive type quicksort - t = System.currentTimeMillis(); - sorted = Sort.quickSort(list); - System.out.println("quick sort1 : "+ (System.currentTimeMillis()-t)+" ms"); - Sort.check(sorted); - - t = System.currentTimeMillis(); - sorted = Sort.quickSort(list,list2); - System.out.println("quick sort2 : "+ (System.currentTimeMillis()-t)+" ms"); - Sort.check(sorted); - // stack type quicksort t = System.currentTimeMillis(); - Sort.quickSort(list,0,list.size()-1); + Sort.quickSort(list1,0,list1.table.length-1); System.out.println("quick sort3 : "+ (System.currentTimeMillis()-t)+" ms"); - Sort.check(list); + Sort.check(list1); t = System.currentTimeMillis(); - Sort.bubbleSort(list2,0,list2.size()-1); + 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/noarraylist/DataInfo.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,16 +0,0 @@ -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; - } -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarraylist/DataList.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,40 +0,0 @@ -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(); - } - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarraylist/EvenPhase.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,84 +0,0 @@ -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){ - 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/noarraylist/LocalBitonicSort.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,13 +0,0 @@ -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(); - } -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarraylist/MakeData.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,30 +0,0 @@ -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); - } - ods.update("list", list, false); - } -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarraylist/OddPhase.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,96 +0,0 @@ -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){ - 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 { - 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; - } - - 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); - } - } - ods.update(info6.key, count+1); - } - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarraylist/RangeInfo.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,16 +0,0 @@ -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; - } - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarraylist/SetInfo.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,22 +0,0 @@ -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(); - } - - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarraylist/SetTask.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,55 +0,0 @@ -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); - - } - - - } - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarraylist/ShowData.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,48 +0,0 @@ -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); - } - - -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarraylist/Sort.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,62 +0,0 @@ -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< 150){ - 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/noarraylist/SortConfig.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,39 +0,0 @@ -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; - } - } -}
--- a/src/alice/test/codesegment/local/bitonicsort/noarraylist/SortTest.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,34 +0,0 @@ -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/mergesort/LocalMergeSort.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,13 +0,0 @@ -package alice.test.codesegment.local.mergesort; - -import alice.daemon.AliceDaemon; -import alice.daemon.Config; - -public class LocalMergeSort { - public static void main(String[] args){ - new AliceDaemon(new Config(args)).listen(); // logger off - - SortConfig conf = new SortConfig(args); - new SortStart(conf).execute(); - } -}
--- a/src/alice/test/codesegment/local/mergesort/MergeArray.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,77 +0,0 @@ -package alice.test.codesegment.local.mergesort; - -import java.util.Iterator; - -import alice.codesegment.CodeSegment; -import alice.datasegment.CommandType; -import alice.datasegment.Receiver; -import alice.test.codesegment.local.bitonicsort.DataList; - -public class MergeArray extends CodeSegment{ - - private Receiver info1 = ids.create(CommandType.TAKE); - private Receiver info2 = ids.create(CommandType.TAKE); - - int keyNum1; - int keyNum2; - - public MergeArray(int num1, int num2) { - keyNum1 = num1; - keyNum2 = num2; - String key1 = Integer.toString(num1); - String key2 = Integer.toString(num2); - info1.setKey("local", key1, 1); - info2.setKey("local", key2, 1); - - } - - @Override - public void run() { - DataList list1 = (DataList) info1.obj; - DataList list2 = (DataList) info2.obj; - DataList list3 = new DataList(); - - Iterator<Integer> iter1 = list1.table.listIterator(); - Iterator<Integer> iter2 = list2.table.listIterator(); - - int val1 = iter1.next(); - int val2 = iter2.next(); - - while(true){ - if (val1 <= val2){ - list3.table.add(val1); - if (iter1.hasNext()) { - val1 = iter1.next(); - } else { - list3.table.add(val2); - break; - } - - } else if (val1>val2) { - list3.table.add(val2); - if (iter2.hasNext()) { - val2 = iter2.next(); - } else { - list3.table.add(val1); - break; - } - } - } - - - if (iter2.hasNext()) { - while(iter2.hasNext()){ - list3.table.add(iter2.next()); - } - } else if (iter1.hasNext()) { - while(iter1.hasNext()){ - list3.table.add(iter1.next()); - } - } - - int num = (keyNum1-1)/2; - String key = Integer.toString(num); - - ods.put(key, list3, false); - } -}
--- a/src/alice/test/codesegment/local/mergesort/SeparateArray.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,50 +0,0 @@ -package alice.test.codesegment.local.mergesort; - -import alice.codesegment.CodeSegment; -import alice.datasegment.CommandType; -import alice.datasegment.Receiver; -import alice.test.codesegment.local.bitonicsort.DataList; -import alice.test.codesegment.local.bitonicsort.Sort; - -public class SeparateArray extends CodeSegment{ - - private Receiver info = ids.create(CommandType.TAKE); - int keyNum; - - public SeparateArray(int keyNum) { - this.keyNum = keyNum; - String key = Integer.toString(keyNum); - info.setKey("local", key); - } - @Override - public void run() { - DataList list = (DataList) info.obj; - if (list.table.size() > 2){ - int num = 2*keyNum + 1; - int length = list.table.size()/2; - - String key1 = Integer.toString(num); - String key2 = Integer.toString(num+1); - - ods.put(key1, list.createDataList(0, length), false); - ods.put(key2, list.createDataList(length, length),false); - - new SeparateArray(num); - new SeparateArray(num+1); - new MergeArray(num,num+1); - } else if (list.table.size()==2){ - String key = Integer.toString(keyNum); - - if (list.table.get(0)<=list.table.get(1)){ - ods.put(key, list, false); - } else { - Sort.swap(list.table, 0, 1); - ods.put(key, list,false); - } - } else { - String key = Integer.toString(keyNum); - ods.put(key, list, false); - } - } - -}
--- a/src/alice/test/codesegment/local/mergesort/ShowResult.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,29 +0,0 @@ -package alice.test.codesegment.local.mergesort; - -import alice.codesegment.CodeSegment; -import alice.datasegment.CommandType; -import alice.datasegment.Receiver; -import alice.test.codesegment.local.bitonicsort.DataList; -import alice.test.codesegment.local.bitonicsort.Sort; - -public class ShowResult extends CodeSegment{ - - private Receiver info = ids.create(CommandType.PEEK); - int keyNum; - public ShowResult(int keyNum) { - this.keyNum = keyNum; - String key = Integer.toString(keyNum); - info.setKey("local", key, 1); - - } - - @Override - public void run() { - System.out.println(System.currentTimeMillis() - SortStart.t); - DataList list = (DataList)info.obj; - System.out.println("size check :"+ list.table.size()); - Sort.check(list.table); - System.exit(0); - } - -}
--- a/src/alice/test/codesegment/local/mergesort/SortConfig.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,16 +0,0 @@ -package alice.test.codesegment.local.mergesort; - - - -public class SortConfig { - int size; - - public SortConfig(String[] args){ - for (int i=0;i<args.length; i++){ - if ("-size".equals(args[i])){ - size = Integer.parseInt(args[++i]); - } - } - } - -}
--- a/src/alice/test/codesegment/local/mergesort/SortStart.java Tue Mar 26 17:10:38 2013 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,32 +0,0 @@ -package alice.test.codesegment.local.mergesort; - -import java.util.Random; - -import alice.codesegment.CodeSegment; -import alice.test.codesegment.local.bitonicsort.DataList; - -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; - DataList list = new DataList(); - for (int i=0;i< size; i++){ - Random rnd = new Random(); - list.table.add(rnd.nextInt(1000000)); - } - - String key = Integer.toString(0); - ods.put(key, list, false); - - new SeparateArray(0); - new ShowResult(0); - t = System.currentTimeMillis(); - } - -}