Home » Functional Programming » Tối ưu hoá trong Scala

Tối ưu hoá trong Scala



Trong bài viết này mình sẽ liệt kê một số vấn đề thường gặp trong Scala khiến cho code chạy chậm và cách giải quyết.

Các ví dụ trong bài viết này được chạy bằng Scala trên command line, máy MacBook Pro (Retina, 15-inch, Mid 2015) bản processor 2.2 GHz. Thời gian chạy của các ví dụ trong bài viết này được đo bằng hàm:

1. For loop filtering

Ta không nên dùng hàm if ở trong for loop.

Ví dụ 1: Tốc độ xử lý của good example trung bình nhanh gấp 1.56 lần.

Ví dụ 2: Tốc độ xử lý của good example trung bình nhanh gấp 156.22 lần.

Nguyên nhân là do

tương đương với

(Bạn có thể tham khảo thêm ở docs của Scala để rõ hơn về bản chất thực sự của for-yeild trong Scala).

Khi dùng withFilter, một hàm ẩn danh mới có kiểu Function2[Object, Boolean] được tạo ra (hàm này được dùng ở đoạn lọc dữ liệu theo cond). Tham số được truyền vào hàm này sẽ bị boxed lại, vì kiểu dữ liệu đầu vào của hàm ẩn danh này là Object. Quá trình boxing/unboxing này chậm hơn rất nhiều so với việc cond được đánh giá trực tiếp ở trong thân của for loop vì lúc đó các tham số được truy cập trực tiếp chứ không cần qua boxing (Nếu bạn không rõ về khái niệm boxing/unboxing, bạn có thể đọc thêm về Functor ở trong bài viết này).

2. Tail recursion

Đệ quy đuôi là một trường hợp đặc biệt của đệ quy khi mà hàm không thực hiện tính toán thêm sau khi gọi chính nó.

Ví dụ: Tốc độ xử lý của good example trung bình nhanh gấp 2.71 lần.

Trong bad example, sau khi gọi lại chính mình, hàm còn thực hiện thêm 1 phép cộng và trả về giá trị sau tính toán, khác với good example trả về luôn giá trị mà hàm đệ quy trong trả về.

Trong hàm đệ quy bình thường, ta phải đẩy địa chỉ trả về vào một stack trước khi mà nhảy lại vào chính nó. Điều đó có nghĩa là ta cần phải có 1 stack có kích thước bằng với độ sâu của lần gọi đệ quy. Khi dùng đệ quy đuôi, hàm ở lớp ngoài sẽ trả lại giá trị ngay khi hàm ở lớp trong trả về, do đó ta không phải phải return hàng loạt mà chỉ cần return 1 lần cho lần gọi hàm lớp ngoài cùng. Điều đó giúp tiết kiệm được thời gian và bộ nhớ cho hệ thống.

3. Move code out of the loop if any

Việc tránh những đoạn code y hệt được thực hiện đi thực hiện lại trong vòng lặp là điều hiển nhiên. Tuy nhiên với Scala đôi khi hơi khó để nhận ra sự trùng lặp này.

Ví dụ: Tốc độ xử lý của good example trung bình nhanh gấp 638.96 lần.

Trong good exampke, phần s1.toSet được tách ra khỏi hàm filter khiến cho tốc độ xử lý được cải thiện rõ rệt. Vì Scala có rất nhiều hàm có sẵn cho Seq, đôi khi deverloper không nhận thức được độ phức tạp của các hàm có sẵn này.

4. Use map instead of find

Trong Scala, các collection thường được implement sẵn hàm find nhằm tìm ra phần tử tương ứng của collection thoả mãn điều kiện.

Tuy nhiên, độ phức tạp của hàm find là O(n) với n là số phần tử trong collection. Nếu hàm find này được thực hiện nhiều lần, ta nên tạo một map từ collection với key là điều kiện tìm kiếm, value là phần tử và dùng map này để tìm phần tử tương ứng. Độ phức tạp sẽ giảm xuống còn O(1).

Ví dụ: Ta cần tìm ra danh sách những học sinh kém dựa vào sequence badStudentIds:

Trong ví dụ trên, thay vì dùng hàm find để tìm student dựa vào studentId, ta tạo ra một map với key là studentId và value là student tương ứng, sau đó dùng map để get ra student tương với với studentId. Giả sử students có độ dài n, badStudentIds có độ dài là m, thì độ phức tạp của bad example là O(mn), trong khi độ phức tạp của good example là O(n + m). Việc tạo map này sẽ phát huy tác dụng tối đa khi mà việc tìm kiếm phần tử được thực hiện nhiều lần.

Hi vọng bài viết có thể giúp ích được cho bạn đọc.

Nguồn tham khảo:

https://stackoverflow.com/questions/15137360/scala-for-comprehension-performance