Grokking Newsletter

By Grokking Vietnam

221 - Tối ưu hoá thời gian đọc S3 giúp tăng hiệu suất tác vụ xử lý dữ liệu lớn

#224・
10.1K

subscribers

227

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 cùng tìm hiểu về:
  • Cách đội ngũ Wix xây dựng quy trình phát triển để release nhanh và liên tục.
  • Cải thiện hiệu suất các tác vụ xử lý dữ liệu lớn nhờ tối ưu hoá thời gian đọc trên S3.
  • Git hoạt động như thế nào
  • Góc Lập Trình: Lời giải cho bài toán tìm số trùng trong mảng
Ngoài ra các bạn vẫn có thể tiếp tục đặt mua ấn phẩm Dijkstra tập 2 tại đây nhé.

Những bài viết hay
Góc Lập Trình
(by phucnh)
Đề ra tuần này: Linked List Cycle II
Lời giải đề bài tuần trướcFind the Duplicate Number
Bài toán yêu cầu tìm số bị lặp nhưng không được sửa đổi mảng đầu vào, và chỉ được sử dụng độ phức tạp không gian là hằng số (constrant extra space). Ta cần chú ý tới những dữ kiện sau:
1. Mảng chỉ chứa n + 1 phần tử, và các phần tử trong khoảng [1, n]
2. Mảng chỉ chứa duy nhất 1 số bị lặp
Nhằm giới hạn độ dài của bài viết, xin chỉ giới thiệu những phương pháp đáp ứng yêu cầu “không được sửa đổi mảng đầu vào” và “độ phức tạp không gian là hằng số”.
Cách tiếp cận đơn giản nhất ta có thể nghĩ tới là sử dụng 2 vòng lặp lồng nhau. Với mỗi số “curr” trong khoảng [1, n], ta duyệt mảng đầu vào và đếm phần tử “nums[i] == curr”. Nếu biến đếm là 2, ta trả lại kết quả. Giải thuật được thực hiện như sau:
Độ phức tạp về thời gian time complexity của giải thuật trên là O(n^2).
Tuy nhiên, theo điều kiện của đề bài, mảng đầu vào chỉ chứa n + 1 phần tử, và các phần tử trong khoảng [1, n]. Với mỗi số “curr” trong khoảng [1, n], ta đếm số phần tử nhỏ hơn hoặc bằng số “curr”, ta gọi biến đếm là “countOfLessThanOrEqualToCurrent”. 
Chúng ta cùng xét ví dụ sau:
nums = [1,3,4,2,2]
Ta duyệt tất cả các số “curr” trong khoảng [1, n], ta có “countOfLessThanOrEqualToCurrent” như sau:
Số bị lặp là số “2” - số nhỏ nhất có countOfLessThanOrEqualToCurrent > curr. 
Như vậy, ta hoàn toàn có thể áp dụng binary search để tìm số bị lặp như sau:
Phương pháp này có độ phức tạp về thời gian time complexity là O(nlogn).
Bài toán này còn có thể tối ưu độ phức tạp thời gian tới O(n), giải thuật tối ưu có liên quan tới bài https://leetcode.com/problems/linked-list-cycle-ii/, vì vậy xin được dành sang số sau.
Code & Tools
The Code Review Pyramid
The Code Review Pyramid
Quotes
“Remember that code is really the language in which we ultimately express the requirements. We may create languages that are closer to the requirements. We may create tools that help us parse and assemble those requirements into formal structures. But we will never eliminate necessary precision—so there will always be code.”
— Robert C. Martin
Feedback
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