Cải thiện performance khi làm việc với các kiểu sequence

1. List
List trong Scala là một danh sách liên kết đơn.
Vì vậy khi thêm phần tử vào một list, nếu không quan tâm đến thứ tự các phần tử,
hàm prepend (nối vào đầu) sẽ thực hiện nhanh hơn hàm append (nối vào đuôi)

Đối với trường hợp thêm 1 phần tử:

val a = List.range(1, 6)
// nên
val b = 6 +: a
// nên
val c = 6 :: a
// không nên
val d = a :+ 6

Đối với trường hợp thêm một list:

val a = List.range(1, 5)
val b = List.range(5, 15)
// nên
val c = a ::: b
// không nên
val d = a ++: b
// không nên
val e = a ++ b

Nếu muốn thêm phần tử vào cuối list, ta có thể dùng một trong các cách sau:

• Khởi tạo một list mới: thêm các phần tử vào đầu list, sau đó dùng hàm reverse. Nên dùng khi số lượng phần tử của list lớn hơn 4.
• Thêm vào list có sẵn: dùng hàm reverse để đảo ngược list, thêm các phần tử vào đầu list, sau đó dùng hàm reverse một lần nữa. Nên dùng khi số lượng phần tử thêm vào ít nhất là 3 và số lượng phần tử của list lớn hơn 3.
• Dùng ListBuffer, sau đó gọi hàm toList.
• Với trường hợp list có số lượng phần tử nhỏ thì thêm trực tiếp vào cuối list sẽ nhanh hơn.

2. Vector
Việc truy cập một phần tử trong list rất tốn thời gian do nó có độ phức tạp là O(n). Vì vậy, ta có thể dùng Vector thay thế để cải thiện tốc độ.

Hàm truy cập ngẫu nhiên của Vector thực hiện nhanh hơn so với List.

val list = List.range(1, 1000000)
val vector = Vector.range(1, 1000000)
list(500000) // khoảng 30 ms
vector(500000) // khoảng 1 ms

Ngoài ra, hàm append và prepend của Vector cũng rất nhanh.

val list = List.range(1, 1000000)
val vector = Vector.range(1, 1000000)
list :+ 10 // khoảng 250 ms
vector :+ 10 // khoảng 1 ms

3. ListBuffer
Trong một số trường hợp, ta cần thêm nhiều phần tử vào cuối list. Ta có thể dùng ListBuffer và chuyển nó thành List khi cần.

Thời gian thực hiện hàm append của ListBuffer là hằng số, còn của List là tuyến tính.

val list = List.range(1, 1000000)
val listBuffer = ListBuffer.range(1, 1000000)
list :+ 10 // khoảng 200 ms
listBuffer += 10 // khoảng 1 ms

Tuy nhiên, thời gian thực hiện của các hàm khác của ListBuffer đều là tuyến tính, ví dụ như hàm truy cập ngẫu nhiên. Khi đó, ta có thể dùng ArrayBuffer thay thế.

4. ArrayBuffer
Tốc dộ thực hiện các hàm append, update, truy cập ngẫu nhiên trong ArrayBuffer đều khá nhanh.

val listBuffer = ListBuffer.range(1, 1000000)
val arrayBuffer = ArrayBuffer.range(1, 1000000)
listBuffer(500000) // khoảng 15 ms
arrayBuffer(500000) // khoảng 1 ms

Thông tin chi tiết:

Performance characteristics của các kiểu sequence:

Chú thích:

Tham khảo:

• Collections – Overview
• Collections – Performance characteristics