Grokking Newsletter

By Grokking Vietnam

#218 - Ứng dụng Machine Learning vào bài toán định tuyến phương tiện

#221・
10.1K

subscribers

222

issues

Subscribe to our newsletter

By subscribing, you agree with Revue’s Terms of Service and Privacy Policy and understand that Grokking Newsletter will receive your email address.

Grokking Vietnam
Grokking Vietnam
Trong số này, chúng ta tìm hiểu về:
  • Cách time series database có thể handle lượng dữ liệu lớn như thế nào.
  • Machine Learning và bài toán định tuyến phương tiện.
  • Kỹ thuật tạo Code Coupon tại eBay.
  • Reading in Database System.
  • Bài toán House Robber và lời giải bài LRU Cache.
Mời các bạn cùng đọc.

Những bài viết hay
Góc Data
Góc Lập Trình
Đề ra tuần này: House Robber III
Lời giải đề bài tuần trướcLRU Cache
LRUCache là viết tắt của Least Recently Used Cache, đây là phương pháp phổ biến nhất để cập nhật cache bằng cách loại bỏ những giá trị ít được sử dụng gần đây nhất.
Do đây là cache, vì vậy ta cần thực hiện các thao tác “get - truy xuất dữ liệu”, “put - cập nhật dữ liệu”, nhanh nhất có thể. Cách nhanh nhất để thực hiện những việc này là sử dụng bảng băm (HashTable hoặc HashMap).
Để đảm bảo tính chất “loại bỏ những giá trị ít được sử dụng gần đây nhất” của LRUCache, ta cần biết những giá trị nào được sử dụng gần đây nhất. Ta có thể sử dụng LinkedList với quy ước: giá trị được sử dụng cuối cùng luôn ở đầu của LinkedList. Như vậy, khi ta thêm giá trị mới vào LRUCache, giá trị mới luôn nằm ở đầu của LinkedList. 
Với quy ước trên, giá trị nằm ở cuối LinkedList là giá trị ít được sử dụng gần đây nhất. Khi số lượng phần tử trong LRUCache vượt quá quy định, ta đơn giản chỉ cần xóa đi giá trị nằm ở cuối LinkedList và key tương ứng trong HashMap.
Tổng kết lại, ta có cấu trúc dữ liệu vào giải thuật như sau:
1. Ta sử dụng LinkedList để lưu trữ giá trị cache với quy ước: “giá trị được sử dụng cuối cùng luôn ở đầu của LinkedList”.
2. Ta sử dụng HashMap để lưu trữ cache key và tham chiếu tới node chứa giá trị trong LinkedList.
3. Khi hàm int get(int key) được gọi, ta kiểm tra HashMap và di chuyển node tương ứng lên đầu của LinkedList.
4. Khi hàm void put(int key, int value) được gọi, ta thêm một node mới vào đầu của LinkedList, đồng thời cập nhật HashMap. Nếu số lượng phần tử vượt quá quy định, ta xoá đi giá trị nằm ở cuối LinkedList, đồng thời xóa key tương ứng trong HashMap.
Thao tác xóa node trong Singly Linked List có độ phức tạp thời gian Time Complexity là O(n), để tối ưu xuống O(1), ta có thể sử dụng Doubly Linked List.
Giải thuật được thực hiện như sau: https://pastebin.com/z5ErNZhB
Cả hàm get và put đều có độ phức tạp thời gian Time Complexity là O(1).
(by phucnh)
Code & Tools
  • Kubeflow: Đây là công cụ giúp triển khai machine learning trên Kubernetes một cách đơn giản và dễ dàng mở rộng.
Góc Sponsors
Là một trong những siêu ứng dụng hàng đầu ở khu vực Đông Nam Á, Grab cung cấp đa dạng dịch vụ cho hơn 187 triệu người dùng tại 428 thành phố ở tám quốc gia. Tại Grab, chúng tôi tin rằng nhân tài chính là trái tim của công ty, vì vậy chúng tôi luôn cố gắng tạo ra một môi trường tuyệt vời để tối ưu hoá tiềm năng của các Grabbers.
Những lý do bạn sẽ thích làm việc ở Grab:
  • Đồng nghiệp thân thiện, chuyên môn cao.
  • Môi trường làm việc đa quốc gia, cân bằng giữa cuộc sống và công việc (work-life balance)
  • Được tham gia giải quyết các bài toán khó (high scale, high traffic), với nhiều impact (vài trăm triệu người dùng)
  • Lương tháng 13 + lương thưởng bonus theo hiệu quả công việc.
  • Rất nhiều khoá học training đào tạo nội bộ cũng như đào tạo được cung cấp bởi các đối tác như Microsoft, Amazon, ..
Hiện văn phòng R&D của Grab đang tuyển nhiều vị trí nhưBackend Developer, Frontend Developer, DevOps Engineer, Lead Software Engineer, ... Bạn có thể tham khảo tại Jobs - Grab Careers để biết thêm chi tiết.
Quotes
“Dynamic typing: The belief that you can’t explain to a computer why your code works, but you can keep track of it all in your head.”
— @chris__martin
Bạn đánh giá nội dung số newsletter này thế nào?
(1 = Rất tệ / 5 = Rất tốt)
👎 1 ——-2 —— 3 —— 4 —— 5 👍
(Việc đánh giá của các bạn là rất quan trọng, sẽ giúp chúng tôi liên tục cải thiện nội dung newsletter tốt hơn)
Did you enjoy this issue? Yes No
Grokking Vietnam
Grokking Vietnam

Cảm ơn bạn đã dành thời gian đọc newsletter kỳ này và chúng tôi hi vọng rằng bạn đã khám phá ra một số điều mới mẻ từ các bài viết trên. Các bạn có thể đọc lại các số cũ tại website newsletter.grokking.org

In order to unsubscribe, click here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.
Viet Nam