2009年4月14日 星期二

computer speed of arithmetic operations 


/**
根據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);
    }
  }
}
at 沒有留言:
Labels: ,

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);
  }
}
at 沒有留言:
Labels: , , ,

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
at 沒有留言:
Labels: , , , ,

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
at 沒有留言:
Labels: , , , , , , ,
訂閱： 文章 (Atom)