NỘI DUNG BÀI VIẾT
Trong bài viết này, chúng ta sẽ tìm hiểu lý do tại sao mọi lập trình viên nên học cấu trúc dữ liệu và thuật toán thông qua các ví dụ dưới đây.
Bài viết này dành cho những người mới bắt đầu học cấu trúc dữ liệu và thuật toán và tự hỏi mình rằng nó sẽ có tác động như thế nào để thúc đẩy kỹ năng nghề nghiệp / lập trình của họ. Tất nhiên, cũng dành cho những người tự hỏi tại sao các công ty lớn như Google, Facebook và Amazon thuê các lập trình viên đặc biệt giỏi trong việc tối ưu hóa thuật toán.
Thuật toán là gì?
Mình đã giới thiệu cho các bạn Giải thuật là gì? trong bài viết trước nên mình chỉ tóm tắt lại định nghĩa:
Giải thuật (còn gọi là thuật toán) có thể được định nghĩa như là một thủ tục, công thức hay cách giải quyết vấn đề. Nó gồm một tập hợp các bước giúp đạt được lời giải.
Ví dụ, một thuật toán để giải quyết bài toán Tìm giai thừa của n (factorial) có thể trông giống như thế này:
Vấn đề: Tìm giai thừa của n
Khởi tạo fact = 1
Với mọi giá trị i trong phạm vi từ 1 đến n:
Nhân fact với i
Trả về fact
Ở đây, thuật toán được viết bằng lời. Nếu nó được viết bằng một ngôn ngữ lập trình, ta sẽ gọi nó là mã code. Dưới đây là một mã để tìm giai thừa của một số trong JavaScript.
function factorial(n) {
let fact = 1;
for (let i = 1; i <= n; i++) {
fact = fact * i;
}
return fact;
}Code language: JavaScript (javascript)Lập trình chính là cấu trúc dữ liệu và thuật toán. Cấu trúc dữ liệu được sử dụng để lưu trữ dữ liệu trong khi các thuật toán được sử dụng để giải quyết vấn đề bằng cách sử dụng dữ liệu đó.
Cấu trúc dữ liệu và thuật toán (DSA) giúp bạn có cái nhìn tổng quan về các phương pháp để giải quyết các vấn đề cơ bản nhất một cách chi tiết và cung cấp cho bạn một cái nhìn sâu sắc về hiệu quả của việc áp dụng nó. Cấu trúc dữ liệu và thuật toán cũng dạy cho bạn đánh giá hiệu quả của một thuật toán. Điều này cho phép bạn có một sự lựa chọn tốt nhất khi giải quyết vấn đề
Sử dụng cấu trúc dữ liệu và thuật toán để làm cho mã của bạn có thể mở rộng
Thời gian là quý giá
Giả sử, Alice và Bob đang cố gắng giải quyết một bài toán đơn giản như tìm kiếm tổng của 1011 số tự nhiên đầu tiên. Trong khi Bob đang viết thuật toán, Alice đã thực hiện viết mã và chứng minh rằng nó đơn giản giống như cách mà Donald Trump mắc và khỏi bệnh Covid.
Thuật toán (bởi Bob)
Khởi tạo sum = 0
Với mọi số tự nhiên i trong phạm vi từ 1 đến 1011 (bao gồm cả):
Cộng i vào sum
sum là kết quả của bài toán
Mã (bởi Alice)
function findSum() {
let sum = 0;
for (let i = 1; i <= 100000000000; i++) {
sum += i;
}
return sum;
}Code language: JavaScript (javascript)Alice và Bob đang cảm thấy phấn khích về bản thân rằng họ có thể xây dựng một cái gì đó cho riêng mình trong thời gian ngắn. Hãy lẻn vào không gian làm việc của họ và lắng nghe cuộc trò chuyện của họ.
Alice: Mày cứ chạy đoạn mã đó đi là ra kết quả ấy mà!
Bob : Tao đã chạy mã này một vài phút trước rồi nhưng nó không hiển thị kết quả.
Đoạn mã của mày có gì sai sai?
Rất tiếc, đã xảy ra lỗi! Máy tính là cỗ máy có thể tính toán kết quả nhanh và chính xác nhất. Quay lại với đoạn mã và cố gắng chạy lại những vẫn không giúp ích được gì. Vì vậy, hãy phân tích những gì sai với mã đơn giản trên.
Hai trong số những tài nguyên quý giá nhất cho một chương trình máy tính là thời gian và bộ nhớ.
Thời gian máy tính chạy đoạn mã là:
Thời gian để chạy đoạn mã = Số lượng câu lệnh * Thời gian để thực thi các câu lệnh
Số lượng câu lệnh phụ thuộc vào mã bạn sử dụng và thời gian thực hiện mỗi mã tùy thuộc vào máy tính và trình biên dịch của bạn.
Trong trường hợp này, tổng số lệnh được thực thi (giả sử x) là x = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Giả sử rằng một máy tính có thể thực hiện các lệnh trong một giây (nó có thể thay đổi tùy theo cấu hình máy). Thời gian thực hiện để chạy đoạn mã trên là y = 108
Thời gian cần thiết để chạy mã = x/y (lớn hơn 16 phút)
Có thể tối ưu hóa thuật toán để Alice và Bob không phải đợi 16 phút mỗi khi họ chạy mã này không?
Tôi chắc chắn rằng bạn đã đoán đúng phương pháp. Tổng các số tự nhiên được tính bởi công thức:
sum = N * (N + 1) / 2
Chuyển nó thành mã sẽ trông giống như sau:
function sum(N) {
return N * (N + 1) / 2;
}Code language: JavaScript (javascript)Mã này chỉ thực thi trong một câu lệnh và hoàn thành nhiệm vụ với bất kể giá trị là bao nhiêu. Dù nó có lớn hơn tổng số nguyên tử trong vũ trụ đi chăng nữa thì máy tính cũng sẽ tìm thấy kết quả ngay lập tức.
Thời gian cần thiết để giải quyết vấn đề, trong trường hợp này, là 1 / y (là 10 nano giây). Nhân tiện, phản ứng nhiệt hạch của một quả bom hydro mất 40-50ns, có nghĩa là chương trình của bạn sẽ hoàn thành thành công ngay cả khi ai đó ném một quả bom hydro vào máy tính của bạn cùng lúc bạn chạy mã của mình. 🙂
Lưu ý: Máy tính thực hiện một số câu lệnh (không phải 1) để tính phép nhân và phép chia.
Nhiều hơn về khả năng mở rộng
Khả năng mở rộng có nghĩa là chất lượng của một thuật toán / hệ thống để xử lý vấn đề có kích thước lớn hơn.
Hãy xem xét vấn đề thiết lập một lớp học của 50 sinh viên. Một trong những giải pháp đơn giản nhất là đặt phòng, lấy bảng đen, một vài viên phấn và vấn đề được giải quyết.
Nhưng điều gì sẽ xảy ra nếu kích thước của vấn đề tăng lên khi mà số lượng sinh viên tăng lên 200?
Giải pháp vẫn còn được giữ lại để sử dụng nhưng nó cần nhiều nguồn lực hơn. Trong trường hợp này, có thể bạn sẽ cần một căn phòng lớn hơn nhiều (có thể là rạp hát, rạp chiếu phim), màn hình máy chiếu và bút kỹ thuật số.
Điều gì sẽ xảy ra nếu số lượng sinh viên tăng lên 1000?
Giải pháp không thành công hoặc sử dụng rất nhiều tài nguyên khi kích thước của vấn đề tăng lên. Điều này có nghĩa là giải pháp của bạn không thể mở rộng.
Vậy giải pháp có thể mở rộng là gì?
Hãy xem xét một trang web như Khanacademy, hàng triệu sinh viên có thể xem video, đọc câu trả lời cùng một lúc và không cần thêm tài nguyên. Vì vậy, giải pháp có thể giải quyết các vấn đề có kích thước lớn hơn dưới khủng hoảng tài nguyên.
Nếu bạn thấy giải pháp đầu tiên để tìm tổng các số tự nhiên N đầu tiên, nó không thể mở rộng. Nó đòi hỏi sự tăng trưởng tuyến tính theo thời gian với sự tăng trưởng tuyến tính theo kích thước của vấn đề. Các thuật toán như vậy còn được gọi là các thuật toán có thể mở rộng tuyến tính.
Giải pháp thứ hai rất có thể mở rộng và không yêu cầu sử dụng thêm thời gian để giải quyết vấn đề có kích thước lớn hơn. Chúng được gọi là thuật toán liên tục thời gian.
Bộ nhớ đắt tiền
Bộ nhớ không phải lúc nào cũng có sẵn. Trong khi giải quyết với mã, hệ thống đòi hỏi bạn phải lưu trữ hoặc sinh ra rất nhiều dữ liệu, nó rất quan trọng cho các thuật toán của bạn để tiết kiệm việc sử dụng bộ nhớ bất cứ nơi nào có thể. Ví dụ: Trong khi lưu trữ dữ liệu về người, bạn có thể tiết kiệm bộ nhớ bằng cách chỉ lưu trữ tuổi của họ mà không cần phải lưu ngày sinh. Bạn luôn có thể tính toán nó một cách dễ dàng bằng cách sử dụng tuổi với ngày hiện tại.
Ví dụ về hiệu quả của thuật toán
Dưới đây là một số ví dụ về những gì cấu trúc dữ liệu và thuật toán cho phép bạn thực hiện:
Ví dụ 1: Vấn đề nhóm tuổi
Các vấn đề như tìm kiếm những người trong một nhóm tuổi nhất định có thể dễ dàng được giải quyết với một phiên bản sửa đổi nhỏ của thuật toán tìm kiếm nhị phân (giả sử rằng dữ liệu đã được sắp xếp).
Thuật toán tìm kiếm tuyến tính sẽ đi qua tất cả từng người một và kiểm tra xem người đó thuộc nhóm tuổi nào. Trong khi đó, tìm kiếm nhị phân tuyên bố chính nó là một thuật toán có khả năng mở rộng. Điều này có nghĩa là nếu kích thước của vấn đề được bình phương, thời gian thực hiện để giải quyết nó chỉ được tăng gấp đôi.
Giả sử, phải mất 1 giây để tìm kiếm những người ở một nhóm tuổi nhất định với một nhóm có 1000 người. Sau đó, đối với một nhóm 1 triệu người:
- Thuật toán tìm kiếm nhị phân sẽ chỉ mất 2 giây để giải quyết vấn đề
- Thuật toán tìm kiếm tuyến tính có thể mất 1 triệu giây, khoảng 12 ngày
Ví dụ 2: Vấn đề khối Rubik
Hãy tưởng tượng bạn đang viết một chương trình để tìm giải pháp của 1 khối Rubik.
Câu đố tìm kiếm dễ thương này đã gây phiền nhiễu 43.252.003.274.489.856.000 vị trí, và đây chỉ là những vị trí! Hãy tưởng tượng số lượng đường dẫn người ta có thể đi để đạt được các vị trí sai.
May mắn thay, cách để giải quyết vấn đề này có thể được giải quyết bởi cấu trúc dữ liệu đồ thị. Có một thuật toán đồ thị được gọi là thuật toán Dijkstra cho phép bạn giải quyết vấn đề này trong thời gian tuyến tính.
Ví dụ 3: Vấn đề DNA
DNA là một phân tử mang thông tin di truyền. Chúng được tạo thành từ các đơn vị nhỏ hơn được đại diện bởi các ký tự La Mã: A, C, T và G.
Hãy tưởng tượng mình làm việc trong lĩnh vực tin sinh học. Bạn được giao công việc tìm ra sự xuất hiện của một mô hình cụ thể trong một sợi DNA.
Đây là một vấn đề nổi cộm trong khoa học máy tính. Và thuật toán đơn giản nhất là:
(số ký tự trong sợi DNA) * (số ký tự trong mẫu)
Một sợi DNA điển hình có hàng triệu đơn vị như vậy. Thuật toán KMP thể thực hiện điều này trong thời gian tỷ lệ thuận với
(số ký tự trong sợi DNA) + (số ký tự trong mẫu)
Toán tử * thay thế toán tử + mang lại rất nhiều thay đổi.
Xem xét rằng mô hình có 100 ký tự, thuật toán của bạn bây giờ nhanh hơn 100 lần. Nếu mẫu của bạn có 1000 ký tự, thuật toán KMP sẽ nhanh hơn gần 1000 lần. Đó là, nếu bạn đã có thể tìm thấy sự xuất hiện của mô hình trong 1 giây, bây giờ nó sẽ đưa cho kết quả chỉ với 1 ms. Chúng ta cũng có thể giải quyết việc này theo một cách khác. Thay vì kết hợp 1 sợi, bạn có thể khớp 1000 sợi có chiều dài tương tự cùng một lúc.
Và có những câu chuyện vô hạn như vậy …
Lời kết
Nói chung, phát triển phần mềm liên quan đến việc học các công nghệ mới hàng ngày. Bạn có thể tìm hiểu hầu hết các công nghệ này trong khi sử dụng chúng ở một trong các dự án của bạn. Tuy nhiên, nó không liên quan gì với các thuật toán.
Nếu bạn không biết rõ thuật toán, bạn sẽ không thể xác định xem bạn có thể tối ưu hóa mã bạn đang viết ngay bây giờ không. Bạn phải biết trước và áp dụng chúng bất cứ khi nào có thể không.
Về khả năng mở rộng của các thuật toán, một hệ thống phần mềm bao gồm nhiều thuật toán như vậy, chỉ cần tối ưu 1 thuật toán thôi cũng đã mang lại 1 kết quả tích cực rồi.
Tuy nhiên, điều quan trọng cần lưu ý là đây không phải là cách duy nhất để làm cho một hệ thống có thể mở rộng. Ví dụ, một kỹ thuật được gọi là điện toán phân tán cho phép các phần độc lập của một chương trình chạy song song trên nhiều máy giúp gia tăng khả năng mở rộng lên rất nhiều!
Các bạn có thể tham khảo các bài viết hay về JavaScript tại đây.
Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.
