Mercurial > hg > Members > tatsuki > Alice

changeset 164:9c28131e814f working

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove LinkedList and use ArrayList
author sugi
date Thu, 13 Dec 2012 11:05:24 +0900
parents db1bae5db5d2
children 4fd7d0caf7e3
files src/alice/test/codesegment/local/bitonicsort/DataList.java src/alice/test/codesegment/local/bitonicsort/EvenPhase.java src/alice/test/codesegment/local/bitonicsort/MakeData.java src/alice/test/codesegment/local/bitonicsort/OddPhase.java src/alice/test/codesegment/local/bitonicsort/ShowData.java src/alice/test/codesegment/local/bitonicsort/Sort.java src/alice/test/codesegment/local/bitonicsort/SortTest.java
diffstat 7 files changed, 61 insertions(+), 20 deletions(-) [+]
line wrap: on
line diff
--- a/src/alice/test/codesegment/local/bitonicsort/DataList.java	Wed Dec 12 21:17:35 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/DataList.java	Thu Dec 13 11:05:24 2012 +0900
@@ -1,7 +1,7 @@
 package alice.test.codesegment.local.bitonicsort;
 
 
-import java.util.LinkedList;
+import java.util.ArrayList;
 import java.util.List;
 import java.util.ListIterator;
 
@@ -10,7 +10,7 @@
 @Message
 public class DataList {
 
-	public List<Integer> table = new LinkedList<Integer>();
+	public List<Integer> table = new ArrayList<Integer>();
 	
 	public DataList(){};
 	
@@ -19,7 +19,7 @@
 	}
 	
 	public DataList createDataList(int start, int size){
-		List<Integer> table2 = new LinkedList<Integer>();
+		List<Integer> table2 = new ArrayList<Integer>();
 		ListIterator<Integer> iter = table.listIterator(start);
 		for (int i=start;i<(start+size);i++){
 			table2.add(iter.next());
--- a/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Wed Dec 12 21:17:35 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/EvenPhase.java	Thu Dec 13 11:05:24 2012 +0900
@@ -1,6 +1,6 @@
 package alice.test.codesegment.local.bitonicsort;
 
-import java.util.LinkedList;
+import java.util.ArrayList;
 import java.util.List;
 
 import alice.codesegment.CodeSegment;
@@ -58,7 +58,7 @@
 			DataList list1 = info1.asClass(DataList.class);
 			DataList list2 = info2.asClass(DataList.class);
 			if (count > sort_count){
-				List<Integer> list = new LinkedList<Integer>();
+				List<Integer> list = new ArrayList<Integer>();
 				list.addAll(list1.table);
 				list.addAll(list2.table);
 				ods.update("local", "array"+info.range, new DataList(list));
--- a/src/alice/test/codesegment/local/bitonicsort/MakeData.java	Wed Dec 12 21:17:35 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/MakeData.java	Thu Dec 13 11:05:24 2012 +0900
@@ -23,7 +23,7 @@
 		int size = conf.getLength();
 		for (int i = 0; i < size; i++){
 			Random rnd = new Random();
-			list.table.add(rnd.nextInt(Integer.MAX_VALUE));
+			list.table.add(rnd.nextInt(100000));
 		}
 		
 		ods.update("local", "list", list);
--- a/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Wed Dec 12 21:17:35 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/OddPhase.java	Thu Dec 13 11:05:24 2012 +0900
@@ -1,6 +1,6 @@
 package alice.test.codesegment.local.bitonicsort;
 
-import java.util.LinkedList;
+import java.util.ArrayList;
 import java.util.List;
 
 import alice.codesegment.CodeSegment;
@@ -76,7 +76,7 @@
 			DataList list1 = info1.asClass(DataList.class);
 			DataList list2 = info2.asClass(DataList.class);
 			if (count > sort_count){
-				List<Integer> list = new LinkedList<Integer>();
+				List<Integer> list = new ArrayList<Integer>();
 				list.addAll(list1.table);
 				list.addAll(list2.table);
 				ods.update("local", "array"+info.range, new DataList(list));
--- a/src/alice/test/codesegment/local/bitonicsort/ShowData.java	Wed Dec 12 21:17:35 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/ShowData.java	Thu Dec 13 11:05:24 2012 +0900
@@ -1,6 +1,6 @@
 package alice.test.codesegment.local.bitonicsort;
 
-import java.util.LinkedList;
+import java.util.ArrayList;
 import java.util.List;
 
 import alice.codesegment.CodeSegment;
@@ -29,7 +29,7 @@
 		DataList list1 = info1.asClass(DataList.class);
 		DataList list2 = info2.asClass(DataList.class);
 		//DataList list3 = info3.asClass(DataList.class);
-		List<Integer> list = new LinkedList<Integer>();
+		List<Integer> list = new ArrayList<Integer>();
 		list.addAll(list0.table);
 		list.addAll(list1.table);
 		list.addAll(list2.table);
--- a/src/alice/test/codesegment/local/bitonicsort/Sort.java	Wed Dec 12 21:17:35 2012 +0900
+++ b/src/alice/test/codesegment/local/bitonicsort/Sort.java	Thu Dec 13 11:05:24 2012 +0900
@@ -1,7 +1,7 @@
 package alice.test.codesegment.local.bitonicsort;
 
 import java.util.Iterator;
-import java.util.LinkedList;
+import java.util.ArrayList;
 import java.util.List;
 
 public class Sort {
@@ -10,7 +10,7 @@
 	 */
 	
 	public static List<Integer> quickSort(List<Integer> numbers){		
-		if (numbers.size() < 400){
+		if (numbers.size() < 1000){
 			bubbleSort(numbers);	
 			return numbers;
 		}
@@ -18,9 +18,9 @@
 		int where = numbers.size() / 2;
 		int pivot = numbers.get(where);
 		int sameAsPivot = 0;
-		List<Integer> lesser = new LinkedList<Integer>();
-		List<Integer> greater = new LinkedList<Integer>();
-		List<Integer> sorted = new LinkedList<Integer>();
+		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()){
@@ -42,10 +42,10 @@
 	}
 	
 	public static List<Integer> quickSort(List<Integer> numbers1, List<Integer> numbers2){
-		List<Integer> list = new LinkedList<Integer>();
+		List<Integer> list = new ArrayList<Integer>();
 		list.addAll(numbers1);
 		list.addAll(numbers2);
-		if ( list.size() < 400 ){
+		if ( list.size() < 1000 ){
 			bubbleSort(list);
 			return list;
 		}
@@ -53,9 +53,9 @@
 		int where = list.size() / 2;
 		int pivot = list.get(where);
 		int sameAsPivot = 0;
-		List<Integer> lesser = new LinkedList<Integer>();
-		List<Integer> greater = new LinkedList<Integer>();
-		List<Integer> sorted = new LinkedList<Integer>();
+		List<Integer> lesser = new ArrayList<Integer>();
+		List<Integer> greater = new ArrayList<Integer>();
+		List<Integer> sorted = new ArrayList<Integer>();
 		Iterator<Integer> iter = list.iterator();
 		
 		while(iter.hasNext()){
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/alice/test/codesegment/local/bitonicsort/SortTest.java	Thu Dec 13 11:05:24 2012 +0900
@@ -0,0 +1,41 @@
+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 = 10000;
+		int MAX = 100000;
+		long t;
+		List<Integer> list = new ArrayList<Integer>();
+		List<Integer> list2 = new ArrayList<Integer>();
+		List<Integer> list3;
+		
+		for (int i = 0; i < size; i++){
+			Random rnd = new Random();
+			list.add(rnd.nextInt(MAX));
+		}
+		for (int i = 0; i < size; i++){
+			Random rnd = new Random();
+			list.add(rnd.nextInt(MAX));
+		}
+		t = System.currentTimeMillis();
+		list3 = Sort.quickSort(list);
+		System.out.println("quick sort1 : "+ (System.currentTimeMillis()-t)+" ms");
+		Sort.check(list3);
+		
+		t = System.currentTimeMillis();
+		list3 = Sort.quickSort(list,list2);
+		System.out.println("quick sort2 : "+ (System.currentTimeMillis()-t)+" ms");
+		Sort.check(list3);
+		
+		t = System.currentTimeMillis();
+		Sort.bubbleSort(list);
+		System.out.println("bubble sort : "+ (System.currentTimeMillis()-t)+" ms");
+		Sort.check(list);
+
+	}
+}