/**
根據speed.java四則運算時間測試結果,
整數乘/除餘運算時間約是整數加減運算時間的5/10倍以上
實數部份比較特別,乘和加減時間幾乎一樣,除法為加減法近200倍,求餘數為加減法近10倍以上.
C:\java>java speed ia is im id ip la ls lm ld lp fa fs fm fd fp da ds dm dd dp
The ia time is 438 ms, or 4.38000e-06 ms per ia
The is time is 422 ms, or 4.22000e-06 ms per is
The im time is 1906 ms, or 1.90600e-05 ms per im
The id time is 4938 ms, or 4.93800e-05 ms per id
The ip time is 5546 ms, or 5.54600e-05 ms per ip
The la time is 453 ms, or 4.53000e-06 ms per la
The ls time is 453 ms, or 4.53000e-06 ms per ls
The lm time is 2438 ms, or 2.43800e-05 ms per lm
The ld time is 7750 ms, or 7.75000e-05 ms per ld
The lp time is 7391 ms, or 7.39100e-05 ms per lp
The fa time is 328 ms, or 3.28000e-06 ms per fa
The fs time is 329 ms, or 3.29000e-06 ms per fs
The fm time is 328 ms, or 3.28000e-06 ms per fm
The fd time is 57422 ms, or 0.000574220 ms per fd
The fp time is 4860 ms, or 4.86000e-05 ms per fp
The da time is 328 ms, or 3.28000e-06 ms per da
The ds time is 328 ms, or 3.28000e-06 ms per ds
The dm time is 328 ms, or 3.28000e-06 ms per dm
The dd time is 66000 ms, or 0.000660000 ms per dd
The dp time is 4953 ms, or 4.95300e-05 ms per dp
*/
public class speed
{
public static long operation(String op, long loop)
{
int i=500, i2=100, i1=50;
long l=5000,l2=1000, l1=500;
float f=1e3f, f2=1.01f, f1=2e3f;
double d=1e6, d2=1.01, d1=2e2;
long k;
//int loop=(int) 1e6;
long start = System.currentTimeMillis();
if(op.equals("ia")) for(k=1; k<=loop; k++) i=i+i2;
else if(op.equals("is")) for(k=1; k<=loop; k++) i=i-i2;
else if(op.equals("im")) for(k=1; k<=loop; k++) i=i*i2;
else if(op.equals("id")) for(k=1; k<=loop; k++) i=i/i2;
else if(op.equals("ip")) for(k=1; k<=loop; k++) i=i%i2;
else if(op.equals("la")) for(k=1; k<=loop; k++) l=l+l2;
else if(op.equals("ls")) for(k=1; k<=loop; k++) l=l-l2;
else if(op.equals("lm")) for(k=1; k<=loop; k++) l=l*l2;
else if(op.equals("ld")) for(k=1; k<=loop; k++) l=l/l2;
else if(op.equals("lp")) for(k=1; k<=loop; k++) l=l%l2;
else if(op.equals("fa")) for(k=1; k<=loop; k++) f=f+f2;
else if(op.equals("fs")) for(k=1; k<=loop; k++) f=f-f2;
else if(op.equals("fm")) for(k=1; k<=loop; k++) f=f*f2;
else if(op.equals("fd")) for(k=1; k<=loop; k++) f=f/f2;
else if(op.equals("fp")) for(k=1; k<=loop; k++) f=f%f2;
else if(op.equals("da")) for(k=1; k<=loop; k++) d=d+d2;
else if(op.equals("ds")) for(k=1; k<=loop; k++) d=d-d2;
else if(op.equals("dm")) for(k=1; k<=loop; k++) d=d*d2;
else if(op.equals("dd")) for(k=1; k<=loop; k++) d=d/d2;
else if(op.equals("dp")) for(k=1; k<=loop; k++) d=d%d2;
long end = System.currentTimeMillis();
long time = end - start;
return time;
}
public static void main(String args[])
{
if(args.length==0)
{
System.err.println("java speed [i|l|f|d][a|s|m|d|p]");
System.exit(0);
}
for(int a=0; a < args.length; a++)
{
String op = args[a];
long loop = (long) 1e8;
long time = operation(op,loop);
System.err.printf("The %s time is %d ms, or %g ms per %s\n",
op, time, (float) time / loop, op);
}
}
}
2009年4月14日 星期二
computer speed of arithmetic operations
2009年4月10日 星期五
scanner.next and nextLine
一般用掃瞄器物件(Scanner)時,若依下法, 在讀數字後,再讀文字,會有讀不到文字情況,Scanner sc = new Scanner(System.in); int i = sc.nextInt(); // 讀數字,換行字元未讀走 String s = sc.nextLine(); // 讀換行前字串,會收到空字串這時,建議改用如下寫法,Scanner sc = new Scanner(System.in); int i = sc.nextInt(); // 讀數字,換行字元未讀走 String s = sc.nextLine(); // 故意用nextLine讀走下一換行前字串及換行字元 String s = sc.nextLine(); // 再用nextLine重新讀下一換行前字串及換行字元或Scanner sc = new Scanner(System.in); int i = sc.nextInt(); // 讀數字,換行字元未讀走 String s = sc.next(); // 讀下一個空格隔開前文字,這樣非空格文字仍可讀到如下測試範例 Test2.java 可自行試看看. ---- Test2.java -----------/* Test2.java >javac Test2.java >java Test2 input i=123 input s= input s2=456 i=123, s=, s2=456, end */ import java.util.*; public class Test2 { public static void main(String[] arg) { Scanner sc = new Scanner(System.in); System.err.printf("input i="); int i = sc.nextInt(); System.err.printf("input s="); String s = sc.nextLine(); // 前面有讀數字,後面文字會讀不到,只收到空字串 System.err.printf("\ninput s2="); String s2 = sc.nextLine(); System.err.printf("i=%d, s=%s, s2=%s, end\n",i,s, s2); } }
2009年4月8日 星期三
summary of time complexity for common data structures
常見資料結構之平均時間複雜度
=======================
運算之平均時間複雜度 新增 刪除 查詢
--限特定位置增刪查詢之線性容器--
陣列堆疊(尾入尾出) O(1) O(1) O(1)
鏈結堆疊(頭入頭出) O(1) O(1) O(1)
陣列佇列(環狀尾入頭出) O(1) O(1) O(1)
鏈結佇列(尾入頭出) O(1) O(1) O(1)
陣列雙邊佇列(環狀頭尾出入) O(1) O(1) O(1)
鏈結雙邊佇列(雙向頭尾出入) O(1) O(1) O(1)
--線性容器--
無序陣列清單 O(1) O(n) O(n)
無序鏈結清單 O(1) O(n) O(n)
有序陣列清單 O(n) O(n) O(log(n))
有序鏈結清單 O(n) O(n) O(n)
雜湊表 O(1) O(1) O(1)
--非線性容器--
二分搜索樹 O(log(n)) O(log(n)) O(log(n))
跳躍鏈結清單 O(log(n)) O(log(n)) O(log(n))
堆積(限頭才能刪除,查詢) O(log(n)) O(log(n)) O(1)
參考:
1.carrano-pie-05-data abstraction & problem solving with java
2.weiss-pie-04-data structures & problem solving using java
3.budd-awl-00-classic data structures in java
java container (jdk1.5)
java容器(since jdk1.5版) Version 0.2b, 2006/10/26
==================
各容器介面摘要(功能定義):
Collection 收藏: 放個別物件, 可重複放,無位置概念,無排序
Queue 佇列: 放個別物件, 可重複放,頭位置概念,部份排序
List 清單: 放個別物件, 可重複放,任意位置 ,無排序
Set 集合: 放個別物件,不可重複放,無位置概念,無排序
SortedSet 有序集合: 放個別物件,不可重複放,有頭尾概念,有排序
Map 映射: 放成對物件,不可重複放,無位置概念,無排序
SortedMap 有序映射: 放成對物件,不可重複放,有頭尾概念,有排序
各容器類別摘要(實作各介面的實體類別):
Collection: Vector,Stack,ArrayList,ArrayBlockingQueue,
LinkedList,PriorityQueue,HashSet,TreeSet
Queue: ArrayBlockingQueue,LinkedList,PriorityQueue
List: Vector,Stack,ArrayList,LinkedList
Set: HashSet,TreeSet
SortedSet: TreeSet
Map: HashMap,TreeMap,HashTable,Properties
SortedMap: TreeMap
--
Vector 向量,Stack 堆疊,ArrayList 陣列清單,LinkedList 鏈結清單,
ArrayBlockingQueue 陣列等候佇列,PriorityQueue 順位佇列,
HashSet 雜湊集合,TreeSet 樹狀集合,
HashMap 雜湊映射,TreeMap 樹狀映射,
HashTable 雜湊表,Properties 屬性表
容器演算法:
Collections.binarySearch/min/max/indexOfSublist/lastIndexOfSublist,
fill/copy/swap/shuffle/sort/reverse/rotate,
list/nCopies/enumeration/reverseOrder,
singleton/singletonList/singletonMap,
synchronizedCollection/synchronizedSet/synchronizedList,
synchronizedMap/synchronizedSortedSet/synchronizedSortedMap,
unmodifiableCollection/unmodifiableSet/unmodifiableList,
unmodifiableMap/unmodifiableSortedSet/unmodifiableSortedMap,
Arrays.asList/binarySearch/equals/fill/sort,
容器一般性功能須求:
新增容器,刪除容器,查詢容器元素個數,列舉容器元素,
新增元素,刪除元素,修改元素,查詢元素,擷取元素
各容器類別提供的方法:
Vector >AbstractList >AbstractCollection, 存取有同步,有元素概念,容量無限
*add/addElement/insertElementAt/addAll,
*remove/removeElement/removeElementAt,
clear/removeAllElements/removeAll/retainAll/removeRange,
*get/set/firstElement/lastElement/elementAt/setElementAt,
*indexOf/lastIndexOf,
subList/toArray/copyInto,
isEmpty/contains/containsAll/equals/hasCode,
*size/setSize/trimToSize/capacity/ensureCapacity,
toString/clone,
--
iterator/listIterartor
Stack >Vector >AbstractList >AbstractCollection, 存取有同步
*empty/push/peek/pop/search,
--
add/addElement/insertElementAt/addAll,
remove/removeElement/removeElementAt,
clear/removeAllElements/removeAll/retainAll/removeRange,
get/set/firstElement/lastElement/elementAt/setElementAt,
indexOf/lastIndexOf,
subList/toArray/copyInto,
isEmpty/equals/contains/containsAll/hasCode,
size/setSize/trimToSize/capacity/ensureCapacity,
toString/clone,
--
iterator/listIterartor
ArrayList >AbstractList >AbstractCollection, 存取無同步,容量無限
*add/addAll,
*remove/removeRange/clear,
*get/set,
*indexOf/lastIndexOf,
*isEmpty/contains,
size/trimToSize/ensureCapacity,
clone/toArray,
--
iterator/listIterartor/equals/hasCode,
--
containsAll/removeAll/retainAll/toString
ArrayBlockingQueue >AbstractQueue >AbstractCollection 存取有同步,容量有限制
clear/contains/drainTo/iterator/
offer/peek/poll/put/remove/take
remainingCapacity/size/
toArray/toString
--
add/addAll/element/remove
--
containsAll/isEmpty/removeAll/retainAll
PriorityQueue >AbstractQueue >AbstractCollection 存取無同步,容量無限
add/clear/offer/peek/poll/remove
comparator/iterator/size
--
addAll/element/remove
--
contains/containsAll/isEmpty/removeAll/retainAll
toArray/toString
LinkedList >AbstractSequentialList >AbstractList
>AbstractCollection, 存取無同步,有頭尾概念,容量無限
*add/addAll/addFirst/addLast,
*remove/removeFirst/removeLast/clear,
*get/set/getFirst/getLast,
*contains/indexOf/lastIndexOf,
size/listIterator/clone/toArray,
--
iterator
--
equals/hashCode/removeRange/subList
containsAll/isEmpty/removeAll/retainAll/toString
HashSet >AbstractSet >AbstractCollection, 存取無同步,無順序概念
*add/remove/clear,
*contains/isEmpty/size,
*iterator/clone,
--
equals/hashCode/removeAll
--
addAll/containsAll/retainAll/toArray/toString
TreeSet >AbstractSet >AbstractCollection, 存取無同步,有順序概念
*add/addAll/remove/clear,
*contains/isEmpty/size,
*iterator/clone/comparator,
*first/last,
*headSet/tailSet/subSet,
--
equals/hashCode/removeAll
--
containsAll/retainAll/toArray/toString
HashMap >AbstractMap, 存取無同步,存放成對物件,無順序概念
*get/put/putAll/remove/clear,
*isEmpty/containsKey/containsValue,
values/keySet/entrySet,
size/clone
--
equals/hashCode/toString
TreeMap >AbstractMap, 存取無同步,存放成對物件,有順序概念
*get/put/putAll/remove/clear,
*containsKey/containsValue,
*headMap,tailMap,subMap,
values/keySet/entrySet,
firstKey/lastKey,
size/clone/comparator,
--
equals/hashCode/isEmpty/toString
HashTable >Dictionaries, 存取有同步,存放成對鍵值組
*get/put/putAll/remove/clear,
*isEmpty/containsKey/containsValue/contains,
keys/elements/values/keySet/entrySet,
size/clone/equals/hasCode/rehash/toString
--
get/put/remove,
elements/keys,
size/isEmpty,
Properties >HashTable >Dictionaries, 存取有同步,存放屬性鍵值組
*getProperty/setProperty,
*load/store/list,
*propertyNames,
--
*get/put/putAll/remove/clear,
*isEmpty/containsKey/containsValue/contains,
keys/elements/values/keySet/entrySet,
size/clone/equals/hasCode/rehash/toString
各容器介面提供的方法:
Collection
add/allAll/remove/removeAll/retainAll/clear,
isEmpty/contains/containsAll/equals/hasCode/size,
iterator/toArray,
Queue >Collection 多了頭位置概念
offer/
poll/remove/
peek/element/
--
add/allAll/remove/removeAll/retainAll/clear,
isEmpty/contains/containsAll/equals/hasCode/size,
iterator/toArray,
List >Collection 多了任意位置概念
add/allAll/remove,
get/set,
indexOf/lastIndexOf,
listIterator/subList,
--
add/allAll/remove/removeAll/retainAll/clear,
isEmpty/contains/containsAll/equals/hasCode/size,
iterator/toArray,
Set >Collection 多了不重複存放概念
add/allAll/remove/removeAll/retainAll/clear,
isEmpty/contains/containsAll/equals/hasCode/size,
iterator/toArray,
SortedSet >Set >Collection 多了順序概念
first/last,
headSet/tailSet/subSet,
comparator,
--
add/allAll/remove/removeAll/retainAll/clear,
isEmpty/contains/containsAll/equals/hasCode/size,
iterator/toArray,
Map
get/put/putAll/remove/clear,
isEmpty/containsKey/containsValue,
values/keySet/entrySet,
size/equals/hasCode,
SortedMap >Map
firstKey/lastKey,
headMap/tailMap/subMap,
comparator,
--
get/put/putAll/remove/clear,
isEmpty/containsKey/containsValue,
values/keySet/entrySet,
size/equals/hasCode,
迭代列舉介面提供的方法:
Enumeration 列舉介面,不能刪除列舉物件,只能往後列舉
hasMoreElements/nextElement,
Iterator 迭代介面,可刪除列舉物件,只能往後列舉
hasNext/next/remove,
ListIterator 清單迭代介面,可往前後列舉,及增刪改物件
add/set/remove,
hasNext/hasPrevious,
next/previous,
nextIndex,previousIndex,
可比較及比較器介面提供的方法:
java.lang.Comparable 可比較介面
compareTo
java.util.Comparator 比較器介面
compare/equals
訂閱：
文章 (Atom)
