12/08/2018, 15:24

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

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ó ...

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.

Nguồn tham khảo:

http://docs.scala-lang.org/ja/overviews/collections/overview http://eed3si9n.github.io/scala-collections-doc-ja/collections_1.html http://www.tatapa.org/~takuo/scala_collections_2.8/collections_40.html http://www.ne.jp/asahi/hishidama/home/tech/scala/collection/index.html

0