Đã đăng vào thg 6 2, 2017 4:23 SA 11 phút đọc

491

Scala_Collections có thể biến đổi (Mutable) và không thể biến đổi (Immutable)

Bài đăng này đã không được cập nhật trong 2 năm

Scala Collections

Overview

Collections của scala thì được phân biệt thành 2 loại là: có thể biến đổi (mutable) và không thể biến đổi (immutable). Mutable colection thì có thể ghi đè hoặc mở rộng. Có nghĩa là có thể thêm, sửa, xóa element của collection. Ngược lại, immutable collection thì không thể thay đổi. Dù có cung cấp phép tính (operations) mô phỏng thêm, sửa, xóa nhưng operations ở tất cả trường hợp thì đều trả về collection mới, collection cũ thì không thay đổi. Immutable class thì có thể sử dụng mặc định còn mutable thì phải tự import mới sử dụng được. Collections điển hình ở Java là List・Map・Set nhưng ở Scala thì là Seq・Map・Set (List của Scala thì tạo thành từ Seq) Trong collections của scala có rất nhiều method để thao tác. Điểm khác biệt với method thao tác collection của Java có lẽ là structure・feature giống như ngôn ngữ chức năng (function language).

Mutable and Immutable Collections

Toàn bộ collection class được định nghĩa trong package scala.collection hoặc là một trong số sub package mutable, immutable, generic. Hầu hết collection class cần thiết ở client code thì được định nghĩa trong 3 package (3 dạng có đặc tính khác nhau liên quan đến khả năng biến đổi) là scala.collection.immutable, scala.collection.mutable, scala.collection.

Collection của packagescala.collection.immutable thì với bất kỳ ai cũng được đảm bảo việc không thể biến đổi. Sau khi tạo thì hoàn toàn không update được. Do đó, dù có access giá trị của collection đó bao nhiêu lần ở các thời điểm khác nhau thì cũng luôn mang lại collection có cùng các element.
Collection của package scala.collection.mutablethì có operations ghi đè update collection. Thế nên việc xử lý mutable collection thì có nghĩa là cần thiết lý giải việc update collection của code nào, thời gian nào.
Collection của packagescala.collection thì có cả mutable và immutable. Ví dụ: collection.IndexedSeq[T] là supper class của collection.immutable.IndexedSeq[T] và collection.mutable.IndexedSeq[T]. Cơ bản thì root collection của package scala.collection là định nghĩa interface giống immutable collection, mutable collection trong package scala.collection.mutable thì thêm operations biến đổi theo tác dụng phụ vào immutable interface.

Điểm khác giữa root collection và immutable collection là, client của immutable collection thì đảm bảo không ai có thể thay đổi được còn client của root collection thì chỉ quy ước được là bản thân mình không thay đổi collection. Ví dụ dù cho không cung cấp operations để thay đổi collection dạng tỉnh nhưng khi thực hiện thì cũng có khả năng có mutable collection client khác có thể thêm bằng tay. Default thì Scala luôn chọn immutable collection. Ví dụ, nếu bạn viết Set mà không có prefix nào hoặc không import thì bạn nhận được tập hợp (set) immutable, và nếu bạn viết Iterable thì bạn nhận được lặp lại (iterable) immutable collection vì chúng default bindings đã import từ package scala. Để get mutable default thì bạn cần phải viết mô tả rõ ràng collection.mutable.Set hoặc là collection.mutable.Iterable. Một quy ước tiện lợi nếu bạn muốn sử dụng cả 2 versions mutable và immutable collections thì chỉ cần import package collection.mutable.

import scala.collection.mutable

Sau đó, Set không có prefix là refer đến immutable collection còn mutable.Setthì refer đến bản mutable. Package cuối cùng trong phân cấp collections là collection.generic. Package này thì bao gồm các thành phần cơ bản để implement collections. Mặc dù collection class có sự giao phó một số phép tính (operations) ở class trong generic, nhưng user của framework thì có đòi hỏi class trong generic là trường hợp ngoại lệ. Để tiện lợi và tính tương thích phía sau, một số dạng quan trọng được định nghĩa tên riêng trong package scala, không import có thể sử dụng collection bằng tên đơn giản. VD như là dạng List có thể access bằng tên bên dưới:

scala.collection.immutable.List   // định nghĩa nguồn
scala.List                        // thông qua alias của package scala
List                              // Vì package scala._ thì luôn tự động được import

Những dạng đã được alias là: Traversable, Iterable, Seq, IndexedSeq, Iterator, Stream, Vector, StringBuilder, Range.

Đặc tính hiệu suất

Các dạng collection khác nhau thì có những điểm đặc tính hiệu suất (performance characteristics) khác nhau. Để lựa chọn sử dụng class nào phù hợp với thực tế thì bạn hãy tham khảo qua các bảng tóm tắt bên dưới:

Đặc tính hiệu suất của dạng tuần tự (sequen)

Bảng 1: Đặc tính hiệu suất của dạng tuần tự (sequen) của immutable colection

	head	tail	apply	update	add to top	add to end	insert
List	constant	constant	linear	linear	constant	linear	-
Stream	constant	constant	linear	linear	constant	linear	-
Vector	real constant	real constant	real constant	real constant	real constant	real constant	-
Stack	constant	constant	linear	linear	constant	linear	-
Queue	depreciation constant	depreciation constant	linear	linear	linear	constant	-
Range	constant	constant	constant	-	-	-	-
String	constant	linear	constant	linear	linear	linear	-

Bảng 2: Đặc tính hiệu suất của dạng tuần tự (sequen) của mutable colection

	head	tail	apply	update	add to top	add to end	insert
ArrayBuffer	constant	linear	constant	constant	linear	depreciation constant	linear
ListBuffer	constant	linear	linear	linear	constant	constant	linear
StringBuilder	constant	linear	constant	constant	linear	depreciation constant	linear
MutableList	constant	linear	linear	linear	constant	linear	linear
Queue	constant	linear	linear	linear	constant	constant	linear
ArraySeq	constant	linear	constant	constant	-	-	-
Stack	constant	linear	linear	linear	constant	linear	linear
ArrayStack	constant	linear	constant	constant	depreciation constant	linear	linear
Array	constant	linear	constant	constant	-	-	-

Đặc tính hiệu suất của dạng tập hợp (set) và map

Bảng 3: Đặc tính hiệu suất của dạng tập hợp (set) và map của immutable colection

	reference	add	remove	min
HashSet/HashMap	real constant	real constant	real constant	linear
TreeSet/TreeMap	logarithm	logarithm	logarithm	logarithm
BitSet	constant	linear	linear	real constant
ListMap	linear	linear	linear	linear

Bảng 4: Đặc tính hiệu suất của dạng tập hợp (set) và map của mutable colection

	reference	add	remove	min
HashSet/HashMap	real constant	real constant	real constant	linear
WeakHashMap	real constant	real constant	real constant	linear
BitSet	constant	depreciation constant	constant	real constant

Chú thích ý nghĩa của các giá trị bên trong bảng:

constant (Hằng số) : tính toán thì tốn thời gian không đổi (nhanh)
real constant (Hằng số thực): tính toán thì tốn thời gian không đổi thực tế nhưng phụ thuộc vào giả định của độ dài vector, hash key, etc...
depreciation constant (Hằng số khấu hao): tính toán thì tốn thời gian bình quân không đổi. Có trường hợp mất nhiều thời gian gọi operation nhưng, nếu gọi nhiều thì trung bình mỗi lần tính toán thì chỉ tốn thời gian không đổi.
logarithm (Đối số): tính toán tốn thời gian tỷ lệ với đối số độ lớn của collection.
linear (tuyến tính): tính toán tốn thời gian tỷ lệ với độ lớn của collection.
-: không hổ trợ

Chú thích xử lý của header trong bảng 1, 2:

head: Chọn phần tử đầu tiên
tail: Tạo thành sequen mới gồm các phần tử đứng sau phần tử đầu tiên
apply: chỉ số dưới (Subscripting)
update : Đối với immutable sequen thì update chức năng (function), đối với mutable sequen là update tác dụng phụ (side effect)
add to top: Thêm phần tử vào đầu sequen. Đối với immutable sequen thì tạo sequen mới, đối với mutable sequen thì update sequen đang có.
add to end:Thêm phần tử vào cuối sequen. Đối với immutable sequen thì tạo sequen mới, đối với mutable sequen thì update sequen đang có.
insert: Thêm phần tử vào vị trí tùy ý của sequen. Cái này chỉ được hổ trợ trực tiếp ở mutable sequen.

Chú thích xử lý của header trong bảng 3, 4:

reference (Tham chiếu): Kiểm tra phần tử có bao gồm trong tập hợp (Set) không, hoặc là chọn giá trị gắn với key trong map.
add: Thêm giá trị vào tập hợp (Set), hoặc là thêm cả key và giá trị vào map.
remove: Xóa giá trị từ phần tử, hoặc là xóa key từ map.
min : Giá trị nhỏ nhất của tập hợp (Set), hoặc là key nhỏ nhất của map

Trait

Trait vó thể hiểu như một class, là nơi tập hợp một nhóm method mà chúng ta muốn. Những điểm trait khác class:

Một trait hoặc một class có thể kế thừa nhiều trait khác nhau. 1 class thì không thể kế thừa nhiều class được.
Không thể khởi tạo trực tiếp instance được. Muốn sử dụng bạn có thể tạo 1 class kế thừa trait rồi khởi tạo instance cho class đó hoặc là bạn tạo instance bằng cách thêm implement.
Trait không thể nhận constructor parameter như class. Để xử lý bạn có thể tạo class kế thừa và gọi new với class đó hoặc truyền thẳng paramter vào implement của trait

Các loại trait:

Traversable : Trait có thể tìm kiếm, là parent trait của tất cả collection. Trait này chỉ có phương thức trừu tượng (abstract method) foreach, nên ngoài cái này thì đều được định nghĩa bằng TraversableLike.
Iterable : Trait có thể lặp lại. Iterable là trực hệ (con) duy nhất củaTraversable. Dưới Iterable có 3 con là Seq・Map・Set
Gen～ : Ở Scala2.9 thì tăng thêm collection song song (Parallel collection). Như là phần common của collection thường và collection song song, trant có thể bắt đầu bằng Gen.
Par～ : collection song song của Scala2.9 thì trait bắt đầu bằng Par.
Seq : collection sắp xếp theo thứ tự. Gồm có : IndexedSeq・ LinearSeq・ Buffer.
IndexedSeq :

immutable	mutable	Tương đương trong Java	Giải thích
	WrappedArray ArraySeq	Array	mảng (Array)
String	StringBuilder	String・StringBuilder	chuổi ký tự
Range			Thường sử dụng nhiều「1 to 10」hoặc là「0 until 10」của dạng for. Chỉ có giá trị bắt đầu/ kết thúc (phạm vi) bằng kiểu Int
NumericRange			bản general của Range. Sử dụng Long và BigInt・BigDecimal , etc Có thể tạo NumericRange[Char] bằng 「'A' to 'Z'」 tạo NumericRange[Long] bằng「1L to 10」
Vector			Collection được triển khai ở Scala2.8.

LinearSeq :

immutable	mutable	Tương đương trong Java	Giải thích
List	LinkedList DoubleLinkedList MutableList	List LinkedList	danh sách (list)
Stream			collection có ý nghĩa nhóm giá trị liên tục vô hạn
Queue	Queue SynchronizedQueue PriorityQueue SynchronizedPriorityQueue	Queue	Hàng đợi(queue)
Stack	Stack SynchronizedStack ArrayStack	Stack	Stack

Buffer : Chỉ có mutable

mutable	Giải thích
ArrayBuffer	Buffer dễ chuyển đổi thành array
ListBuffer	Buffer dễ chuyển đổi thành list
SynchronizedBuffer

Map : collection get được giá trị nguồn của key. Gồm có : map, SortedMap

immutable	mutable	Tương đương trong Java
HashMap	HashMap	HashMap
ListMap	ListMap
	LinkedHashMap	LinkedHashMap
	WeakHashMap	WeakHashMap
	OpenHashMap
	MultiMap
	ConcurrentMap
	SynchronizedMap

SortedMap :

immutable	mutable	Tương đương trong Java
TreeMap		SortedMap・TreeMap
	TrieMap

Set : Tập hợp. Gồm có : set, SortedSet

immutable	mutable	Tương đương trong Java
HashSet	HashSet	HashSet
BitSet	BitSet	BitSet
ListSet
	LinkedHashSet

SortedSet :

immutable	Tương đương trong Java
TreeSet	SortedSet・TreeSet

Tạo collection

Tạo instance của collection thì sử dụng method apply() của companion object của collection class.

val l = List("a", "b", "c", "d")
val m = Map("a" -> 123, "b" -> 456, "c" -> 789)
val s = Set("a", "b", "c", "d")

Để sử dụng mutable collection thì cần thiết phải import class. Ở immutable class và mutable class đều có class (trait/ object) tên giống nhau nên bạn nên tạo tên khác để dễ phân biệt.

import scala.collection.mutable.{ ListBuffer, Map=>MMap, Set=>MSet }
val l = ListBuffer("a", "b", "c", "d")
val m = MMap("a" -> 123, "b" -> 456, "c" -> 789)
val s = MSet("a", "b", "c", "d")

Collection rỗng (số phần tử là 0) thì ngoài việc cố định paramater của companion object là 0 thì cũng có thể get được bằng method empty

  val list = List[Int]()
  val list = List.empty[Int]
  val list:List[Int] = List()
  val list:List[Int] = List.empty
×val list = List(1,2,3).empty

Ví dụ với List

Chúng ta cùng thử thực hành tạo 1 List gồm các thứ trong tuần rồi thử truy cập đến các phần tử trong đó nhé.

head trả về phần tử đầu tiên của list.
last trả về phần tử cuối cùng của list.
Sử dụng index chỉ rõ vị trí của phần tử muốn lấy (vị trí đầu tiên là 0).
tail trả về list gồm toàn bộ phần tử đằng sau phần tử đầu tiên.
duyệt list bằng loop.
foreach() : là 1 procedure, nó nhận vào 1 function và thực hiện với từng phần tử trong list và tất nhiên nó trả về 1 Unit.
map() : nhận vào 1 function và convert list phần tử đó thành giá trị khác hay kiểu khác.
reduce() : nhận vào 1 function có nhiệm vụ combine 2 phần tử của list thành 1 và cứ thế cho đến cuối list.