Java

解決問題 Performance (2)

教學目標

初步了解 JVM 中垃圾回收器的基本概念以利解決應用程式效能的問題。

重點概念

首先當我們啟動 Java 網站應用程式時,將會透過 Java 虛擬機器 (Java Virtual Machine,JVM) 執行程式,並且每個 Java 網站應用程式皆會執行在獨立的 JVM 中,並且在啟動 JVM 時皆會配置 Heap 記憶體的大小,也就優化入門調整 -Xms 和 -Xmx 參數值設定 Heap 記憶體的大小,若記憶體夠大且有效能考量,則建議兩個參數設定一樣,以及每個 JVM 中同時執行多執行緒,其中有個執行緒稱為 GC 執行緒,它主要會將不必要的物件,也就是將不使用的物件進行回收,並且進行清除。

記憶體大小相關參數 說明
-Xms 主要設定啟動 JVM 時使用 Heap 記憶體的大小。
-Xmx 主要設定在 JVM 中使用 Heap 記憶體的最大值。

接著在 JVM 的垃圾回收皆採用分代回收的演算法,所謂分代回收主要是基於物件不同的生命周期採取不同的回收方式,以利提高垃圾回收的效率。其中主要分為三個世代,分別為:

  1. 新生代:一開始物件會建立於新生代中,並且生命週期很短。每次新生代的垃圾回收之後,只有少數的物件存活,就是所謂 Minor GC,主要透過複製演算法進行回收。
  2. 老年代:當物件在新生代中經歷多次垃圾回收之後仍然存活,就會被放至老年代中,並且生命週期較長。每次老年代的垃圾回收,將會花費較長的時間,就是所謂 Major GC,主要透過「標記/清理」或「標記/整理」演算法進行回收,至於所謂 Full GC 則是指新生代和老年代同時進行回收。
  3. 持久代:主要儲存中繼資料,像是類別、方法、…等資訊,與垃圾回收機制沒有直接相關。

此外我們能夠透過 jconsole 工具中的記憶體頁籤中觀察三個世代的使用情況。其中又可再分為 Heap 記憶體和非 Heap 記憶體,所謂 Heap 記憶體主要是代表新生代和老年代,而非 Heap 記憶體主要是代表持久代。

垃圾回收名稱 說明
Minor GC 主要發生在新生代中,發生頻率高和清理速度快。
Major GC 主要發生在老年代中,發生頻率低和清理速度慢。
Full GC 主要同時發生在新生代和老年代中,發生頻率低和清理速度慢。

再來新生代又會再分為三個區域分別為一個 Eden 區和二個 Survivor 區,大部份會在 Eden 區被建立,當 Eden 區滿時,還存活的物件將會被複製至兩個 Survivor 區之中。當 Survivor 區滿時,此區的存活物件若不滿足晉升條件時就會被複製至另一個 Survivor 區。同時當物件每經歷一次 Minor GC,則年齡加 1,直到達晉升年齡門檻值之後,就會使放至老年代中,因此晉升年齡門檻值的大小直接影響物件在 新生代中停留的時間,主要是透過 MaxTenuringThreshold 參數進行設定,預設值為 15。

新生代空間大小相關參數 說明
-XX:NewRatio 主要設定新生代和老年代配置記憶體的比例。
-XX:SurvivorRatio 主要設定 Eden 區和 Survivor 區配置記憶體的比例。
-XX:NewSize 主要設定新生代配置記憶體的大小。

最後在 JVM 中則有許多不同類型的垃圾回收器,將能夠適用於不同的情境,其中常見的垃圾回收器,分別為:

  1. Serial:主要是單執行緒的垃圾回收器,適用新生代和老年代。
  2. ParNew:主要是多執行緒的垃圾回收器,適用新生代和老年代。
  3. Parallel Scavenge:主要以輸出量優先的垃圾回收器,適用新生代。
  4. Concurrent Mark Sweep:主要以最短回應停頓時間為目標的垃圾回收器,適用老年代。
  5. G1:主要是將 Heap 記憶體分為多個相等大小的區域,按照每個區域進行垃圾回收,特點為平行處理、分代收集,不會導致空間碎片,並且能夠設定停頓時間的上限,適用新生代和老年代。

相關資源

解決問題 Performance (1)

教學目標

初步了解如何透過 Java 監控工具解決應用程式效能的問題。

重點概念

首先當我們在 Windows 平台中遇到 Java 效能問題時,像是記憶體外洩、效能瓶頸、連線未釋放、系統崩潰、…等,此時我們可以先透過工作管理員工具了解目前 Java 應用程式所使用 CPU、記憶體、輸入/輸出、執行時間、執行指令、…等效能資訊,同時查看 Java 應用程式透過 log4j 所產生的相關記錄檔,以利我們初步判斷問題的可能原因。

接著為了能夠找出隱藏在 Java 應用程式中的問題,則建議使用 JVM 監控工具深入查看更多詳細資訊,至於 JVM 監控工具有常見的有哪些,請參考下表。

工具 說明
jcmd 主要提供有關 Java 應用程式的相關資訊。
jhat 主要提供記憶體中的資訊,將有助於事後分析。
jmap 主要提供 JVM 記憶體使用的資訊,將有助於事後分析。
jinfo 主要提供 JVM 系統資訊,並且能夠動態設定一些系統屬性。
jstack 主要提供 Java 應用程式的堆疊資訊。
jstat 主要提供 GC 和類別加載活動的相關資訊。
jconsole 主要提供有關 JVM 活動的相關資訊。
jvisualvm 主要提供監視 JVM 的 GUI 工具,可以用於即時分析執行中的詳細資訊。

再來我們主要透過 jvisualvm 工具即時監控 Java 應用程式的相關資訊,也就是所謂 VisualVM。其主要是一款免費整合多個 JDK 命令列工具,以視覺化方式呈現的工具,當我們安裝 JDK 預設在 bin 資料夾中就有提供 VisualVM 工具。其主要透過 JMX 遠端連線即時能夠提供我們強大的分析能力,以利針對 Java 應用程式進行效能分析和調整優化,像是監控 CPU 使用情況、監控記憶體、監控垃圾回收機制、…等相關資訊。

最後針對 Java 應用程式進行效能分析主要是透過收集 Java 應用程式執行時的執行資料來幫助開發人員定位應用程式需要進行優化的部分,以利提高應用程式的執行速度或資源使用效率,主要有 CPU、記憶體和執行緒三種資源。此外 VisualVM 除了能夠針對 CPU、記憶體和執行緒進行即時線上分析的監控分析方式之外,更提供快照分析方式和轉儲分析方式的功能,以利我們進行離線的完整分析。

相關資源

Java 基本介紹 (6)

教學目標

初步了解 Java 程式語言中集合框架之演算法的基本概念與應用。

重點概念

在 Java 平台中提供以 Collections 框架為基礎的演算法功能,所謂 Collections 框架又稱為容器是指多個元素組合成單一物件,主要應用於儲存、檢索、操作和溝通聚合資料。一般來說在 Java 平台中清單元素皆會搭配 Collections 框架進行演算法的實作,其中演算法可以分為六大類:

  1. 排序
  2. 洗牌
  3. 搜尋
  4. 組成
  5. 例行性資料操作
  6. 尋找最大最小值

首先排序演算法主要是重新排列清單,使得清單中的元素根據排序關係按遞增排序,排序操作,主要是使用 Collections 框架中的 sort 方法,其中排序方式為優化之後的合併排序演算法 (TimSort),具有快速且穩定的特性,所謂快速是指保證在 nlog(n) 的時間內執行完成。所謂穩定是指不重新排列相等的元素,相等的元素排序之後會維持原先的先後順序。接著與排序相反的操作則是洗牌,洗牌演算法主要是破壞清單中可能存在的任何追蹤軌跡,一般來說其是基於隨機來源的輸入元素重新排列清單,主要是使用 Collections 框架中的 shuffle 方法應用於產生測試範例。

演算法 時間複雜度(最佳) 時間複雜度(平均) 時間複雜度(最差) 空間複雜度
Selection Sort Ω(n^2) Θ(n^2) O(n^2) O(1)
Bubble Sort Ω(n) Θ(n^2) O(n^2) O(1)
Insertion Sort Ω(n) Θ(n^2) O(n^2) O(1)
Tree Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(n)
Quick Sort Ω(n log(n)) Θ(n log(n)) O(n^2) O(log(n))
Merge Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(n)
Heap Sort Ω(n log(n)) Θ(n log(n)) O(n log(n)) O(1)
Tim Sort Ω(n) Θ(n log(n)) O(n log(n)) O(n)

再來搜尋演算法主要在已排序的清單中搜尋指定的元素,主要是使用 Collections 框架中的 binarySearch 方法,其中搜尋方式為以二元搜尋演算法。若清單中包含該搜尋的值,則返回其索引,若不存在,則返回值為 (-1 × 插入點-1),其中插入點是指值將新增至清單中的位置。

此外 Collections 框架中提供 frequency 方法了解清單組成的元素頻率,更進一步針對例行性資料操作提供演算法實作的方法,主要可以分為五種類型資料操作的方法,分別為:

  1. 反向(reverse): 反轉清單中所有元素的順序。
  2. 填充(fill): 覆蓋清單中具有指定值的每個元素。
  3. 複製(copy): 將來源清單複製至目的清單。
  4. 交換(swap): 交換清單中指定的元素位置。
  5. 加入全部(addAll): 將所有指定的元素新增至清單中。

最後 Collections 框架針對尋找最大最小值則提供最小值和最大值的演算法,以利取得最大和最小的元素,此外我們亦可以透過實作 Comparator 介面解決特殊情境應用的排序方式。

範例程式碼

檔案名稱

ATM.java

情境說明

在現實生活中我們透過 ATM 進行轉帳作業時會需要點選轉帳帳戶所屬的銀行代碼,此時畫面就需要顯示銀行代碼清單,並且為了讓使用者方便點選,將會進行排序處理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;
public class ATM {
public static void main(String[] args) {
String[] banks = {"004臺灣銀行"
,"008華南銀行"
,"005土地銀行"
,"006合庫商銀"
,"021花旗銀行"
,"009彰化銀行"
,"011上海銀行"
,"012台北富邦"
,"007第一銀行"
,"013國泰世華"
,"017兆豐商銀"};
List<String> list = Arrays.asList(banks);
Collections.sort(list);
System.out.println("自動提款機畫面上顯示銀行代碼:\n" + list );
}
}

執行結果

1
2
自動提款機畫面上顯示銀行代碼:
[004臺灣銀行, 005土地銀行, 006合庫商銀, 007第一銀行, 008華南銀行, 009彰化銀行, 011上海銀行, 012台北富邦, 013國泰世華, 017兆豐商銀, 021花旗銀行]

相關資源

Java 基本介紹 (5)

教學目標

初步了解 Java 程式語言中集合框架之資料結構的基本概念。

重點概念

在現實社會中我們永遠不會知道未來有多少相同類型的物件,也無法準確的知道物件的類型,為了解決上述問題,Java 程式語言則提供集合框架,又稱容器。主要常用的集和介面則為 List 、 Set 和 Map,並且根據不同的應用情境選擇適合的資料結構。

資料結構 List Set Map
Array ArrayList
Tree TreeSet TreeMap
Linked List LinkedList
Hash Table HashSet HashMap
Hash Table + Linked List LinkedHashSet LinkedHashMap

首先 List 主要有兩種資料結構進行實作,分別為:

  1. ArrayList: 主要以陣列資料結構為主的序列,任何選取的元素皆可以在常數時間內容完成隨機的存取,此外其具有擴充機制,若沒有初始化長度則預設為 10,並且當增加元素超過原始容量時,則新容量為原始容量×3/2+1。
  2. LinkedList: 主要以串列資料結構為主的序列,任何選取的元素皆需在串列上進行,若元素愈接近串列最後位置,則花費時間愈久。

接著 Set 主要有三種資料結構進行實作,分別為:

  1. HashSet: 主要是將元素儲存至雜湊表中,效能最佳,但是對於迭代的順序無法確保。此外 HashSet 的雜湊值主要是由元素的值計算,且因為雜湊值會碰撞所以兩個物件可能會有相同的雜湊值,此時就會透過 equals() 方法判斷物件是否相等。
  2. LinkedHashSet: 主要是將的元素儲存至鏈接的雜湊表中,效能良好,但是會根據被插入集合的順序確保迭代的順序。
  3. TreeSet: 主要是將元素儲存至紅黑樹中,效能中等,但是對於元素的值會進行排序,若需要使用元素的值進行排序請採用 TreeSet,此外 TreeSet 可以搭配 Comparator 自定義針對值進行排序。

再來 Map 主要有三種資料結構進行實作,分別為:

  1. HashMap: 主要是將元素中的索引 (Key) 和值 (Value) 儲存至雜湊表中,效能最佳,但是對於迭代的順序無法確保。接著 HashMap 基於雜湊的原理使用 put(key, value) 方法儲存物件至 HashMap 中,此時會介面先透過 hashCode() 方法取得雜湊值 ((h = key.hashCode()) ^ (h >>> 16)),以利計算 index 值找到正確 Bucket 位置儲存物件,物件內容包括索引和值,若當不同物件有相同雜湊值時則發生碰撞,此時會以Bucket 接串列的形式進行儲存,以及當串列的數量大於 TREEIFY_THRESHOLD 值 (預設為 8) 時就會將串列轉為紅黑樹,接著使用 get(key) 從 HashMap 中取得物件,但若是因為雜湊值相同則發生碰撞時,則會再透過 keys.equals() 方法從串列中找出正確的節點,因此物件內容必須包括索引和值才能夠進行比對索引。再來在 HashMap 有兩個重要的參數,分別為容量 (預設為 16 ) 和負載因子 (預設為 0.75),所謂容量是指 Bucket 的大小,而負載因子則是 Bucket 允許填滿的最大程度,當 Bucket 中的物件數大於容量×負載因子時就會擴增兩位 Bucket 大小,此時還會執行 resize() 方法重新調整 Map 的大小,並且將原來的物件儲存至新的 Bucket 中的過程會執行 transfer() 方法,主要會將儲存在串列中的元素順序相反,直接將元素放在首位,為了避免 Tail Traversing 導致條件競爭發生造成死結。
  2. LinkedHashMap: 主要是將的元素中的索引 (Key) 和值 (Value) 儲存至鏈接的雜湊表中,效能良好,但是會根據被插入集合的順序確保迭代的順序。
  3. TreeMap: 主要是將元素儲存至紅黑樹中,效能中等,但是對於元素的值會進行排序,若需要使用元素的索引進行排序請採用 TreeMap,此外 TreeMap 可以搭配 Comparator 自定義針對索引進行排序。

最後要如何選擇適當集合介面搭配資料結構呢? 一開始最好的方式則是先以 ArrayList 為主,接著當發現效能問題的原因為在 List 中進行過多的插入和移除動作時,才使用 LinkedList,此外當時常進行隨機存取的方法 get() 和 set() 時則是 ArrayList 優於 LinkedList。接著 HashSet 效能優於 TreeSet ,尤其是插入和搜尋,除非需要維持元素的排序狀態,否則請採用 HashSet 即可。再來 HashMap 被設計應用於快速搜尋,其效能優於 TreeMap,除非需要維持元素索引的排序狀態,否則請採用 HashMap 即可,此外 HashMap 的實作主要使用雜湊表搭配陣列和串列的方式進行實作,若不當 hashCode() 方法不當使用則會被當成 LinkedList 使用。當然我們也可以參考不同資料結構的複雜度針對不同應用情境進行最適當的選擇。

資料結構 時間複雜度(搜尋) 時間複雜度(插入) 時間複雜度(刪除) 空間複雜度
Array Θ(n) Θ(n) Θ(n) O(n)
Tree Θ(log(n)) Θ(log(n)) Θ(log(n)) O(n)
Linked List Θ(n) Θ(1) Θ(1) O(n)
Hash Table Θ(1) Θ(1) Θ(1) O(n)

相關資源

Java 基本介紹 (4)

教學目標

初步了解 Java 程式語言中集合框架的基本概念。

重點概念

我們都曾聽過資料結構和演算法是程式語言的基礎,但是在 Java 程式語言是否有針對資料結構和演算法優化的框架能夠針對不同情境進行解決方案的應用呢? 事實上在 Java 程式語言中有提供 Collections 框架應用於表示和操作集合的架構,透過 Collections 框架就能夠讓程式設計師根據不同情境應用適當的資料結構和演算法之解決方案,Collections 框架主要包括三個部分,分別為:

  1. 介面: 主要是表示集合的抽像資料類型,透過介面能夠使得集合獨立於不同表示集合的細節而被進行資料操作的應用。
  2. 實作: 主要是專注於集合介面的實作,實作之後皆是可重用的資料結構
  3. 演算法: 主要是針對實作集合介面的物件進行實用的演算法

首先 Collections 框架中核心的集合介面主要分為兩大類,第一類是以 Collection 類別為基礎的介面,第二類是以 Map 類別為基礎的介面,其中第一類主要有四種介面,分別為:

  1. List: 可包含重複元素,並且有順序的集合。
  2. Set: 不包含重複元素的集合。
  3. Queue: 被使用於之前保存多個元素,會以先進先出 (FIFO) 的方式排序元素的集合。
  4. Deque: 被使用於之前保存多個元素,會以先進先出 (FIFO) 或後進先出 (LIFO) 的方式排序元素的集合。

第二類則主要是以 Map 介面為主,主要是將索引值 (Key) 對應至值 (Value) 的集合,其中索引值不能重複,此外 Sort 和 Map 介面的集合是不進行排序,因此 Java 程式語言針對 Sort 和 Map 介面的集合提供 SortedSet 和 SortedMap 的介面進行元素和索引值的排序應用。

總結採用 Collections 框架主要有二大優點,分別為:

  1. 減少程式開發的負擔,同時增加程式品質和效能: 透過 Collections 框架所提供實用的資料結構和演算法,同時實用的資料結構和演算法皆是以高品質與高效能的方式進行實作,同時每個介面的各種資料結構和演算法實作是可以互相切換。因此我們可以針對不同情境的問題立即轉換程式中的資料結構與演算法以利程式設計師更進一步改進程式的品質和效能。
  2. 減少學習與設計新 API 的負擔,同時允許不相關的 API 之間進行協同合作: 透過 Collections 框架所提供標準介面的集合操作,就能夠減少程式設計師學習與設計新 API 所造成的負擔,同時集合所提供的資料結構與演算法是可以重複使用。

相關資源