Chiều 30 tết cuối năm, rảnh viết nốt bài để đón tết con Heo 😀
Tiếp tục là 1 bài về so sánh các thứ trong Java, cái này thi thoảng cũng gặp khi phỏng vấn nhưng bài này mình muốn giúp các bạn có thể hiểu rõ hơn về bản chất để sử dụng hợp lý hơn, đảm bảo hiệu năng tốt hơn.
Trước tiên mình muốn đề cập Array mô tả 1 cấu trúc dữ liệu mảng cơ bản từ C/C++. Array được lưu trữ trong 1 dãy các ô nhớ liền nhau trong bộ nhớ và có thể truy xuất trực tiếp đến từng phần tử thông qua số thứ tự (index) của phần tử trong mảng. Không có các tiện ích sẵn để add/get/remove… phần tử mà chỉ có thuộc tính length để lấy kích thước. Kích thước của Array là cố định và buộc phải định nghĩa khi khai báo.
Còn ArrayList LinkedList và Vector, cả 3 cái này đều là class implement List, trong đó List là 1 collection trong Java được thiết kế có đầy đủ các method cơ bản như get, add, remove, sort,… vì vậy ArrayList LinkedList và Vector implement lại List đều mang đầy đủ những tiện ích này từ List. List được lưu trữ dưới dạng các ô nhớ rải rác trong bộ nhớ trỏ đến nhau thông qua địa chỉ ô nhớ. Việc này nhằm tối ưu về bộ nhớ có thể tận dụng các ô nhớ ở các vị trí khác nhau không nhất thiết phải liền nhau, nhưng lại gây ra việc không thể truy xuất trực tiếp đến 1 phần từ bất kỳ mà phải duyệt từ đầu List để tìm.
Tìm hiểu chi tiết hơn.
LinkedList là class implement List và cũng mang đầy đủ tiện ích của List và được bổ sung thêm các tiện ích của Deque tối ưu cho các thao tác add/remove phần từ, hay các tiện ích của AbstractSequentialList giúp tối ưu khi duyệt phần tử bằng Iterator. Nhưng lại không được tối ưu cho việc truy xuất ngẫu nhiên qua số thứ tự phần tử nên ít khi được sử dụng. Kích thước danh sách là động và được tăng mỗi khi bổ sung phần tử.
ArrayList là class implement List, được mang thêm tiện ích của RandomAccess giúp tối ưu việc truy xuất ngẫu nhiên qua số thứ tự, nhưng lại không được implement Deque nên các thao tác add/remove không nhanh như LinkedList (mình sẽ có ví dụ test performce cụ thể ở dưới). Kích thước ArrayList là cố định tại 1 thời điểm, nhưng có thể resize thêm 50% mỗi khi đạt giới hạn max hiện tại nên có thể coi là kích thước động.
Vector là class implement giống hệt ArrayList nên mang đầy đủ tiện ích như ArrayList có, và hơn thế nữa được xây dựng thêm các method thao tác phần tử như addElement setElement removeElement insertElement …. và đặc biệt các method của Vector đều được cài đặt synchronized nghĩa là safe nhưng fail-fast, an toàn cho dữ liệu khi sử dụng trong đa luồng nhưng lại gây chậm xử lý. Kích thước của Vector tương tự như ArrayList chỉ khác là sẽ tăng 100% mỗi khi đạt giới hạn max hiện tại.
Các bạn có thể đọc thêm docs của java hoặc đơn giản là decompile jdk hoặc đọc trong source nén của jdk để thấy rõ hơn về những sự giống và khác biệt này.
Tổng hợp lại dưới dạng bảng từ đó rút ra cân nhắc sử dụng cái nào trong từng trường hợp cụ thể.
| Array | ArrayList | LinkedList | Vector |
| Là mảng nguyên thủy, chỉ có thuộc tính length | Là class implement List, có các method hỗ trợ get/add/remove/… | ||
| Kích thước cố định | Tăng 50% kích thước khi đạt giới hạn | Kích thước động | Tăng 100% kích thước khi đạt giới hạn |
| Lưu kiểu dữ liệu nguyên thủy và đối tượng | Chỉ lưu kiểu dữ liệu đối tượng, từ Java 5 kiểu nguyên thủy được tự động chuyển đổi thành đối tượng để lưu trữ (auto-boxing) | ||
| Tốc độ lưu trữ và truy xuất nhanh | Tốc độ truy xuất theo index nhanh | Tốc độ truy xuất theo index chậm | Tốc độ truy xuất theo index nhanh |
| Rất kém trong việc insert/remove phần tử ở giữa mảng | Tốc độ insert/remove phần tử trong mảng trung bình | Tốc độ insert/remove phần tử trong mảng nhanh | Tốc độ insert/remove phần tử trong mảng trung bình |
| Không hỗ trợ synchronized, dễ mất dữ liệu khi xử lý đa luồng nhưng nhanh | Không hỗ trợ synchronized, dễ mất dữ liệu khi xử lý đa luồng nhưng nhanh | Không hỗ trợ synchronized, dễ mất dữ liệu khi xử lý đa luồng nhưng nhanh | Hỗ trợ synchronized, an toàn dữ liệu khi xử lý đa luồng nhưng chậm |
| Thường dùng với các thao tác bổ sung vào cuối mảng và truy xuất thông thường, sử dụng khi nghiệp vụ đơn giản ít nâng cấp | Sử dụng để lưu trữ và truy xuất dữ liệu cơ bản, ít khi thay đổi | Sử dụng khi cần thao tác thay đổi dữ liệu nhiều, cho các nghiệp vụ phức tạp | Sử dụng khi cần thao tác với nhiều luồng xử lý |
Dưới đây là các đoạn test performance khi thực hiện add/get/remove trên Array/ArrayList/LinkedList để nhìn trực quan hơn về sự khác biệt. Các kết quả có thể sẽ không chính xác như ví dụ với từng lần chạy nhưng về cơ bản vẫn có độ chênh lệch có thể nhìn thấy
package net.tunghuynh.listcollection;
import org.apache.log4j.Logger;
import java.util.*;
/**
* net.tunghuynh.listcollection.Main
* by Tùng Huynh
* at 04/02/2019 13:12 AM
*/
public class Main {
static Logger logger = Logger.getLogger(Main.class);
static int n = 100000;
public static void main(String[] args) {
arrayListVsLinkedList();
}
public static void arrayListVsLinkedList() {
Integer[] array = new Integer[n];
List arrayList = new ArrayList();
List linkedList = new LinkedList();
logger.info("==== Add ====");
long start = System.nanoTime();
for (int i = 0; i < n; i++) {
array[i] = i;
}
logger.info("Array : " + (System.nanoTime() - start)/1000000.0 + " ms");
start = System.nanoTime();
for (int i = 0; i < n; i++) {
arrayList.add(i);
}
logger.info("ArrayList : " + (System.nanoTime() - start)/1000000.0 + " ms");
start = System.nanoTime();
for (int i = 0; i < n; i++) {
linkedList.add(i);
}
logger.info("LinkedList: " + (System.nanoTime() - start)/1000000.0 + " ms");
logger.info("==== Get ====");
start = System.nanoTime();
for (int i = 0; i < n; i++) {
Integer x = array[i];
}
logger.info("Array loop index : " + (System.nanoTime() - start)/1000000.0 + " ms");
start = System.nanoTime();
for (int i = 0; i < n; i++) {
arrayList.get(i);
}
logger.info("ArrayList loop index : " + (System.nanoTime() - start)/1000000.0 + " ms");
start = System.nanoTime();
for (int i = 0; i < n; i++) {
linkedList.get(i);
}
logger.info("LinkedList loop index : " + (System.nanoTime() - start)/1000000.0 + " ms");
start = System.nanoTime();
for (Object item : arrayList) {
Object x = item;
}
logger.info("ArrayList loop interator : " + (System.nanoTime() - start)/1000000.0 + " ms");
start = System.nanoTime();
for (Object item : linkedList) {
Object x = item;
}
logger.info("LinkedList loop interator: " + (System.nanoTime() - start)/1000000.0 + " ms");
logger.info("==== Remove ====");
start = System.nanoTime();
for (int i = 9999; i >=0; i--) {
arrayList.remove(i);
}
logger.info("ArrayList : " + (System.nanoTime() - start)/1000000.0 + " ms");
start = System.nanoTime();
for (int i = 9999; i >=0; i--) {
linkedList.remove(i);
}
logger.info("LinkedList: " + (System.nanoTime() - start)/1000000.0 + " ms");
}
}
Kết quả
2019-02-04 14:01:45 INFO Main:38 - ==== Add ==== 2019-02-04 14:01:45 INFO Main:40 - Array : 10.467533 ms 2019-02-04 14:01:45 INFO Main:44 - ArrayList : 31.468273 ms 2019-02-04 14:01:45 INFO Main:51 - LinkedList: 38.454655 ms 2019-02-04 14:01:45 INFO Main:53 - ==== Get ==== 2019-02-04 14:01:45 INFO Main:59 - Array loop index : 1.231587 ms 2019-02-04 14:01:45 INFO Main:59 - ArrayList loop index : 6.705990 ms 2019-02-04 14:01:56 INFO Main:66 - LinkedList loop index : 11606.559760 ms 2019-02-04 14:01:56 INFO Main:73 - ArrayList loop interator : 9.608840 ms 2019-02-04 14:01:56 INFO Main:80 - LinkedList loop interator: 9.868294 ms 2019-02-04 14:01:56 INFO Main:82 - ==== Remove ==== 2019-02-04 14:01:57 INFO Main:88 - ArrayList : 981.452304 ms 2019-02-04 14:01:57 INFO Main:95 - LinkedList: 364.362477 ms
Lưu ý, các bạn có thể sửa các đoạn logger.infor thành System.out.println để test.
Ta có thể thấy array nhanh hơn khá nhiều khi thêm và truy xuất phần tử, các bộ test sau đấy thì phải cài đặt phương thức thủ công nên mình ko đưa Array vào. Ở phần test get 1 phần tử trong mảng bằng vòng lặp for index thì LinkedList quá chậm so với ArrayList vì mỗi lần gọi get(i) là phải duyệt từ đầu danh sách theo từng con trỏ next để tìm được thứ tự phù hợp, độ phức tạp của get(i) LinkedList sẽ là O(n) trong khi của ArrayList chỉ là O(1).
Còn với test method get(i) bằng iterator thì cả ArrayList và LinkedList đều sử dụng con trỏ next implement từ List nên kết quả có thể coi là tương đương nhau.
Đến phần test remove phần tử thì ArrayList yếu thế hơn vì mỗi lần remove thì RandomAccess phải sắp xếp lại index từ vị trí remove đến cuối để được chuỗi liên tục nên thời gian xử lý tăng lên, trong khi LinkedList chỉ cần ngắt con trỏ tại ví trí remove để trỏ đến ô nhớ tiếp theo là hoàn tất.
Tiếp theo, ta thử so sánh performance giữa ArrayList và Vector trong tình huống đơn luồng
package net.tunghuynh.listcollection;
import org.apache.log4j.Logger;
import java.util.*;
/**
* net.tunghuynh.listcollection.Main
* by Tùng Huynh
* at 04/02/2019 13:12 AM
*/
public class Main {
static Logger logger = Logger.getLogger(Main.class);
static int n = 100000;
public static void main(String[] args) {
arrayListVsVectorSingle();
}
public static void arrayListVsVectorSingle(){
List arrayList = new ArrayList();
Vector vector = new Vector();
logger.info("==== Add ====");
long start = System.nanoTime();
for (int i = 0; i < n; i++) {
arrayList.add(i);
}
logger.info("ArrayList: " + (System.nanoTime() - start)/1000000.0 + " ms");
start = System.nanoTime();
for (int i = 0; i < n; i++) {
vector.add(i);
}
logger.info("Vector : " + (System.nanoTime() - start)/1000000.0 + " ms");
logger.info("==== Get ====");
start = System.nanoTime();
for (int i = 0; i < n; i++) {
arrayList.get(i);
}
logger.info("ArrayList: " + (System.nanoTime() - start)/1000000.0 + " ms");
start = System.nanoTime();
for (int i = 0; i < n; i++) {
vector.get(i);
}
logger.info("Vector : " + (System.nanoTime() - start)/1000000.0 + " ms");
}
}
Kết quả cho thấy tốc độ xử lý của cả 2 tạm coi là tương đương nhau do Vector có cài đặt giống với ArrayList. Có sai khác thì phần lớn là do môi trường và thời điểm test.
2019-02-04 14:08:24 INFO Main:21 - ==== Add ==== 2019-02-04 14:08:24 INFO Main:27 - ArrayList: 48.413265 ms 2019-02-04 14:08:24 INFO Main:34 - Vector : 31.740043 ms 2019-02-04 14:08:24 INFO Main:36 - ==== Get ==== 2019-02-04 14:08:24 INFO Main:42 - ArrayList: 21.322051 ms 2019-02-04 14:08:24 INFO Main:49 - Vector : 12.971482 ms
Nếu thử với tình huống đa luồng thì sao nhỉ
package net.tunghuynh.listcollection;
import org.apache.log4j.Logger;
import java.util.ArrayList;
import java.util.List;
import java.util.Vector;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;
/**
* net.tunghuynh.listcollection.MultiThread
* by Tùng Huynh
* at 04/02/2019 11:55 AM
*/
public class MultiThread {
static Logger logger = Logger.getLogger(MultiThread.class);
public static void main(String[] args) {
List arrayList = new ArrayList();
List vector = new Vector();
ThreadPoolExecutor executorService = (ThreadPoolExecutor) Executors.newFixedThreadPool(10);
for (int i = 0; i < 10; i++) {
executorService.execute(new CalRunnable(arrayList));
}
shutdownAndAwaitTermination(executorService);
logger.info("ArrayList: " + CalRunnable.time/1000000.0 + " ms");
executorService = (ThreadPoolExecutor) Executors.newFixedThreadPool(10);
CalRunnable.time = 0;
for (int i = 0; i < 10; i++) {
executorService.execute(new CalRunnable(vector));
}
shutdownAndAwaitTermination(executorService);
logger.info("Vector : " + CalRunnable.time/1000000.0 + " ms");
}
static void shutdownAndAwaitTermination(ExecutorService pool) {
pool.shutdown();
try {
if (!pool.awaitTermination(60, TimeUnit.SECONDS)) {
pool.shutdownNow();
if (!pool.awaitTermination(60, TimeUnit.SECONDS))
System.err.println("Pool did not terminate");
}
} catch (Exception e) {
}
}
}
class CalRunnable implements Runnable {
static long time = 0;
List lst;
public CalRunnable(List lst){
this.lst = lst;
}
@Override
public void run() {
long time = System.nanoTime();
for (int i = 0; i < 100000; i++) {
lst.add(i);
}
CalRunnable.time += (System.nanoTime() - time);
}
}
Kết quả khi thực hiện
Exception in thread "pool-1-thread-6" java.lang.ArrayIndexOutOfBoundsException: Index 310465 out of bounds for length 240097 at java.base/java.util.ArrayList.add(ArrayList.java:486) at java.base/java.util.ArrayList.add(ArrayList.java:498) at net.tunghuynh.listcollection.CalRunnable.run(MultiThread.java:68) at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128) at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628) at java.base/java.lang.Thread.run(Thread.java:835) 2019-02-04 14:51:13 INFO MultiThread:29 - ArrayList: 972.733492 ms 2019-02-04 14:51:13 INFO MultiThread:37 - Vector : 1914.403079 ms
Ta có thể thấy Vector chậm hơn khá nhiều so với ArrayList nhưng ArrayList lại xảy ra xung đột khi nhiều thread cùng truy xuất vào phần tử. Các bạn có thể thử lại với add hoặc remove để biết thêm các trường hợp khác.
Qua bài này hi vọng các bạn có thể hiểu rõ hơn bản chất của những thứ rất cơ bản nhưng ít ai để ý và có thể ứng dụng hợp lý nhất cho các đoạn code của mình giúp cho hệ thống hoạt động trơn tru hiệu quả hơn 🙂