View profile

#219 - Triết lí Unix trong Apache Kafka và Samza

Grokking Vietnam
Grokking Vietnam
Trong số này, chúng ta cùng tìm hiểu về:
  • Hệ thống control plan storage Delos của Facebook
  • Triết lí Unix trong Apache Kafka và Samza
  • Các design patterns cho microservices observability
  • PACELC, một phiên bản mở rộng từ CAP theorem trong đó cân nhắc đến nhiều yếu tố hơn
  • Bài toán Merge k Sorted Lists và lời giải bài House Robber III

Những bài viết hay
Góc Data
Góc Lập Trình
Đề ra tuần này: Merge k Sorted Lists
Lời giải đề bài tuần trướcHouse Robber III
Ta có thể diễn giải đề bài toán một cách đơn giản hơn như sau, cho một cây nhị phân, tìm tập hợp các nút trong cây có tổng giá trị lớn nhất, với điều kiện không có 2 nút liên tiếp kề nhau, trả về tổng giá trị đó.
Ta có thể nhận thấy đây là một bài toán mang tính chất cấu trúc con tối ưu (optimal substructure), chính vì vậy khả năng cao có thể giải bằng quy hoạch động.
Để giải bài toán quy hoạch động, hướng suy nghĩ thường như sau:
  1. Tìm một lời giải đơn giản cho bài toán bằng đệ quy.
  2. Xác định các bước lặp trong lời giải đệ quy, ghi nhớ giá trị tại bước đệ quy đó bằng “memoization” (Nếu bạn chưa nghe đến thì nó là memoization chứ không phải memorization. Memoization là một thuật ngữ dùng trong ngành khoa học máy tính, tham khảo wiki).
Quay trở lại bài toán, với mỗi nút trong cây, ta có 2 lựa chọn:
  • Chọn nút hiện tại, và tiếp tục xét các nút con tiếp theo không liền kề nó.
  • Bỏ qua nút hiện tại, và xét 2 nút con của nó.
Giải thuật đệ quy đơn giản như sau: https://pastebin.com/HK91QfU4
Để ý rằng, các lời gọi trong trường hợp 1 sẽ bị lặp bởi các lời gọi tiếp theo ở trường hợp 2. Vì vậy nếu ta thực hiện lưu giá trị trả về của hàm traverse tại mỗi nút ở lần gọi đệ quy đầu tiên, ta sẽ tối ưu được các lệnh gọi đệ quy bị lặp lại.
Lời giải cuối cùng cho bài toán như sau: https://pastebin.com/CJxYW4ND
Vì mỗi nút mạng chỉ sẽ được xét nhiều nhất 1 lần, nên độ phức tạp thời gian là O(N)
(by ndaadn)
History
Happy birthday to Edsger Dijkstra!
Dijkstra có lẽ làm một cái tên không còn xa lạ với bất kỳ ai trong chúng ta. Ông sinh ngày 11 tháng 5 năm 1930 tại Rotterdam, mất ngày 6 tháng 8 năm 2002.
Ông được nhận giải thưởng Turing năm 1972 cho các đóng góp có tính chất nền tảng trong lĩnh vực ngôn ngữ lập trình. Ông cũng đã được nhận giải thưởng của ACM dành cho paper xuất sắc trong lĩnh vực phân tán. Sau khi ông qua đời, giải thưởng thường niên này đã được đổi tên thành giải thưởng ACM Edsger W. Dijkstra.
Các bạn sinh viên hẳn đều đã từng code thuật toán Dijkstra cho bài toán tìm đường đi ngắn nhất. Thuật toán này chỉ được thiết kế trong vòng 20 phút. Đó là vào một buổi sáng khi ông đi mua sắm ở Amsterdam cùng với vị hôn thê của mình. Khi mệt mỏi họ đã ngồi xuống uống cafe và tại đây ông đã tự hỏi liệu có thể làm được bài toán này không. Một trong những lý do khiến thuật toán này đẹp đó là nó được thiết kế mà không cần bút và giấy. Sau này ông học được rằng, một trong những lợi thế của việc thiết kế mà không cần bút và giấy đó là bạn gần như buộc phải tránh tất cả những điều phức tạp có thể tránh được.
Các bạn có thể đọc kỹ hơn bài phỏng vấn ông vào năm 2001 tại đây.
(by lpv)
Code & Tools
  • Apache Ratis - Một thư viện Java cho Raft protocol
  • GoogleTest - Một thư viện testing và mocking cho C++ của Google
Quotes
There are very different programming styles. I tend to see them as Mozart versus Beethoven. When Mozart started to write, the composition was finished. He wrote the manuscript and it was ‘aus einem Guss’ (from one cast). In beautiful handwriting, too. Beethoven was a doubter and a struggler who started writing before he finished the composition and then glued corrections onto the page. In one place he did this nine times. When they peeled them, the last version proved identical to the first one.
— Dijkstra
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