# HG changeset patch # User sugi # Date 1355387165 -32400 # Node ID 4fd7d0caf7e35dba66bee53189846c9be14b3c14 # Parent 9c28131e814f8b5691598aa16b58aa785db68234 add no recursive type quick sort diff -r 9c28131e814f -r 4fd7d0caf7e3 src/alice/test/codesegment/local/bitonicsort/EvenPhase.java --- a/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java Thu Dec 13 11:05:24 2012 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java Thu Dec 13 17:26:05 2012 +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; @@ -57,30 +54,32 @@ } else { DataList list1 = info1.asClass(DataList.class); DataList list2 = info2.asClass(DataList.class); + + DataList list3 = new DataList(); + list3.table.addAll(list1.table); + list3.table.addAll(list2.table); + if (count > sort_count){ - List list = new ArrayList(); - list.addAll(list1.table); - list.addAll(list2.table); - ods.update("local", "array"+info.range, new DataList(list)); + ods.update("local", "array"+info.range, list3); return; } int block_num = info3.asInteger(); long t1 = System.currentTimeMillis(); - list2.table = Sort.quickSort(list1.table,list2.table); + Sort.quickSort(list3.table, 0, list3.table.size()-1); System.out.println(list2.table.size()+" : "+(System.currentTimeMillis()- t1)); if (!info.lastFlag){ ods.put("local", info.range+"f", - list2.createDataList(0, block_num/2)); + list3.createDataList(0, block_num/2)); ods.put("local", info.range+"b", - list2.createDataList(block_num/2, block_num/2)); + list3.createDataList(block_num/2, block_num/2)); //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("local", info.range+"f", - list2.createDataList(0, block_num/2)); + list3.createDataList(0, block_num/2)); ods.put("local", info.range+"b", - list2.createDataList(block_num/2, last_block_num)); + list3.createDataList(block_num/2, last_block_num)); //System.out.println("next Odd "+info.range+" "+ info.range+"b"); new OddPhase(info0.key ,info.range+"b",count,info6.key); } diff -r 9c28131e814f -r 4fd7d0caf7e3 src/alice/test/codesegment/local/bitonicsort/OddPhase.java --- a/src/alice/test/codesegment/local/bitonicsort/OddPhase.java Thu Dec 13 11:05:24 2012 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/OddPhase.java Thu Dec 13 17:26:05 2012 +0900 @@ -50,7 +50,7 @@ return; } long t1 = System.currentTimeMillis(); - list.table = Sort.quickSort(list.table); + Sort.quickSort(list.table,0,list.table.size()-1); System.out.println(list.table.size()+" : "+(System.currentTimeMillis()- t1)); if (!info.lastFlag){ ods.put("local", info.range+"f", @@ -75,21 +75,22 @@ } else { DataList list1 = info1.asClass(DataList.class); DataList list2 = info2.asClass(DataList.class); + + List list = new ArrayList(); + list.addAll(list1.table); + list.addAll(list2.table); if (count > sort_count){ - List list = new ArrayList(); - list.addAll(list1.table); - list.addAll(list2.table); ods.update("local", "array"+info.range, new DataList(list)); return; } long t1 = System.currentTimeMillis(); - list2.table = Sort.quickSort(list1.table,list2.table); + Sort.quickSort(list,0,list.size()-1); System.out.println(list2.table.size()+" : "+(System.currentTimeMillis()- t1)); - + DataList list3 = new DataList(list); ods.put("local", info.range+"f", - list2.createDataList(0, block_num/2)); + list3.createDataList(0, block_num/2)); ods.put("local", info.range+"b", - list2.createDataList(block_num/2, block_num/2)); + list3.createDataList(block_num/2, block_num/2)); if (info.range==0){ //System.out.println("next Even2b "+info.range+" "+ info.range+"f"); diff -r 9c28131e814f -r 4fd7d0caf7e3 src/alice/test/codesegment/local/bitonicsort/Sort.java --- a/src/alice/test/codesegment/local/bitonicsort/Sort.java Thu Dec 13 11:05:24 2012 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/Sort.java Thu Dec 13 17:26:05 2012 +0900 @@ -5,11 +5,12 @@ import java.util.List; public class Sort { - /* - * quick method has problem. - */ - public static List quickSort(List numbers){ + public static List quickSort(List numbers){ + /* + * this method has problem. + */ + if (numbers.size() < 1000){ bubbleSort(numbers); return numbers; @@ -49,31 +50,37 @@ bubbleSort(list); return list; } - - int where = list.size() / 2; - int pivot = list.get(where); - int sameAsPivot = 0; - List lesser = new ArrayList(); - List greater = new ArrayList(); - List sorted = new ArrayList(); - Iterator iter = list.iterator(); - - while(iter.hasNext()){ - int number = iter.next(); - if (number>pivot) greater.add(number); - else if (number < pivot) lesser.add(number); - else sameAsPivot++; + return quickSort(list); + } + + public static void quickSort(List numbers, int begin,int end){ + int[] stack = new int[1024]; + int sp = 0; + int p = 0; + while(true){ + while(begin < end){ + 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) numbers){ @@ -96,7 +103,6 @@ int number1 = 0; int number2 = 0; Iterator iter = numbers.iterator(); - System.out.println("checking ...."); while (iter.hasNext()){ number1 = number2; diff -r 9c28131e814f -r 4fd7d0caf7e3 src/alice/test/codesegment/local/bitonicsort/SortTest.java --- a/src/alice/test/codesegment/local/bitonicsort/SortTest.java Thu Dec 13 11:05:24 2012 +0900 +++ b/src/alice/test/codesegment/local/bitonicsort/SortTest.java Thu Dec 13 17:26:05 2012 +0900 @@ -12,7 +12,7 @@ long t; List list = new ArrayList(); List list2 = new ArrayList(); - List list3; + List sorted; for (int i = 0; i < size; i++){ Random rnd = new Random(); @@ -20,22 +20,29 @@ } for (int i = 0; i < size; i++){ Random rnd = new Random(); - list.add(rnd.nextInt(MAX)); + list2.add(rnd.nextInt(MAX)); } + + //recursive type quicksort t = System.currentTimeMillis(); - list3 = Sort.quickSort(list); + sorted = Sort.quickSort(list); System.out.println("quick sort1 : "+ (System.currentTimeMillis()-t)+" ms"); - Sort.check(list3); + Sort.check(sorted); t = System.currentTimeMillis(); - list3 = Sort.quickSort(list,list2); + sorted = Sort.quickSort(list,list2); System.out.println("quick sort2 : "+ (System.currentTimeMillis()-t)+" ms"); - Sort.check(list3); + Sort.check(sorted); + + // stack type quicksort + t = System.currentTimeMillis(); + Sort.quickSort(list,0,list.size()-1); + System.out.println("quick sort3 : "+ (System.currentTimeMillis()-t)+" ms"); + Sort.check(list); t = System.currentTimeMillis(); - Sort.bubbleSort(list); + Sort.bubbleSort(list2); System.out.println("bubble sort : "+ (System.currentTimeMillis()-t)+" ms"); - Sort.check(list); - + Sort.check(list2); } } diff -r 9c28131e814f -r 4fd7d0caf7e3 src/alice/test/codesegment/local/mergesort/MergeArray.java --- a/src/alice/test/codesegment/local/mergesort/MergeArray.java Thu Dec 13 11:05:24 2012 +0900 +++ b/src/alice/test/codesegment/local/mergesort/MergeArray.java Thu Dec 13 17:26:05 2012 +0900 @@ -1,13 +1,11 @@ package alice.test.codesegment.local.mergesort; import java.util.Iterator; -import java.util.List; - -import org.msgpack.type.Value; import alice.codesegment.CodeSegment; import alice.datasegment.CommandType; import alice.datasegment.Receiver; +import alice.test.codesegment.local.bitonicsort.DataList; public class MergeArray extends CodeSegment{ @@ -29,84 +27,52 @@ @Override public void run() { - List list1 = info1.asArray(); - List list2 = info2.asArray(); - - //System.out.println(list1); - //System.out.println(list2); - int length = list1.size() + list2.size(); - int[] array = new int[length]; + DataList list1 = info1.asClass(DataList.class); + DataList list2 = info2.asClass(DataList.class); + DataList list3 = new DataList(); - Iterator iter1 = list1.listIterator(); - Iterator iter2 = list2.listIterator(); + Iterator iter1 = list1.table.listIterator(); + Iterator iter2 = list2.table.listIterator(); - int val1 = iter1.next().asIntegerValue().getInt();//0 - int val2 = iter2.next().asIntegerValue().getInt();//0 + int val1 = iter1.next(); + int val2 = iter2.next(); - int i; - for (i=0;ival2) { - array[i] = val2; - if (!iter2.hasNext()) { - array[i+1] = val1; + list3.table.add(val1); + if (iter1.hasNext()) { + val1 = iter1.next(); + } else { + list3.table.add(val2); break; } - val2 = iter2.next().asIntegerValue().getInt(); - } - } - - if (iter2.hasNext()) { - for (i=i+2 ;iarray2){ - array[i]=array2; - k++; - if (k == list2.size()){ - for (i=i+1;ival2) { + list3.table.add(val2); + if (iter2.hasNext()) { + val2 = iter2.next(); + } else { + list3.table.add(val1); break; } } } - */ - /* - for (int i = 0;i list = info.asArray(); - //System.out.println(list); - if (list.size() > 2){ + DataList list = info.asClass(DataList.class); + if (list.table.size() > 2){ int num = 2*keyNum + 1; - int length = list.size()/2; - int[] array1 = new int[length]; - int[] array2 = new int[length]; - /* - for (int i = 0;i iter = list.listIterator(); - Iterator iter1 = list.listIterator(length); - - for (int i = 0;i