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 với sự trợ giúp của các ví dụ.
Bài viết này dành cho những người mới bắt đầu học thuật toán và tự hỏi nó sẽ có tác động như thế nào đến việc thúc đẩy sự nghiệp / kỹ năng lập trình của họ. Nó cũng dành cho những người thắc mắc tại sao các công ty lớn như Google, Facebook và Amazon lại 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ột cách không chính thức, một thuật toán không có gì khác ngoài việc đề cập đến các bước để giải quyết một vấn đề. Chúng thực chất là một giải pháp.
Ví dụ: một thuật toán để giải quyết vấn đề về giai thừa có thể trông giống như sau:
Bài toán: Tìm giai thừa của n
Khởi tạo fact = 1 Với mọi giá trị v trong phạm vi từ 1 đến n: Nhân fact với v fact chứa giai thừa của n
Ở đây, thuật toán được viết bằng tiếng Anh. Nếu nó được viết bằng ngôn ngữ lập trình, chúng tôi sẽ gọi nó là mã . Đây là một đoạn mã để tìm giai thừa của một số trong C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Lập trình là tất cả về cấu trúc dữ liệu và thuật toán. Cấu trúc dữ liệu được sử dụng để giữ 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) đi qua các giải pháp cho các vấn đề tiêu chuẩn một cách chi tiết và cung cấp cho bạn cái nhìn sâu sắc về mức độ hiệu quả của việc sử dụng từng vấn đề đó. Nó cũng dạy bạn khoa học về đánh giá hiệu quả của một thuật toán. Điều này cho phép bạn chọn tốt nhất trong số các lựa chọn khác nhau.
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 một bài toán đơn giản là tìm tổng của 10 11 số tự nhiên đầu tiên . Trong khi Bob đang viết thuật toán, Alice đã thực hiện nó chứng minh rằng nó đơn giản như việc chỉ trích Donald Trump.
Thuật toán (bởi Bob)
Khởi tạo sum = 0 cho mọi số tự nhiên n trong phạm vi từ 1 đến 1011 (bao gồm cả): thêm n vào tổng tổng là câu trả lời của bạn
Code (bởi Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice và Bob đang cảm thấy hưng phấn về bản thân rằng họ có thể xây dựng một cái gì đó của riêng mình trong thời gian gần như không có. 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: Hãy chạy đoạn mã này và tìm ra tổng. Bob: Tôi đã chạy đoạn mã này cách đây vài phút nhưng nó vẫn không hiển thị đầu ra. Có gì sai với nó?
Rất tiếc, đã xảy ra lỗi! Máy tính là cỗ máy xác định nhất. Quay lại và cố gắng chạy lại sẽ 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 này.
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 mã là:
Thời gian chạy mã = số lượng lệnh * thời gian để thực hiện mỗi lệnh
Số lượng 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 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
Chúng ta hãy 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 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ủa N số tự nhiên đầu tiên được cho bởi công thức:
Tổng = N * (N + 1) / 2
Chuyển nó thành mã sẽ trông giống như sau:
int sum (int N) (return N * (N + 1) / 2;)
Mã này thực thi chỉ trong một lệnh và hoàn thành nhiệm vụ bất kể giá trị là bao nhiêu. Hãy để nó lớn hơn tổng số nguyên tử trong vũ trụ. Nó 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 bom khinh khí mất 40-50 ns, 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 bom khinh khí 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ố hướng dẫn (không phải 1) để tính nhân và chia. Tôi đã nói 1 chỉ vì mục đích đơn giản.
Thông tin thêm về Khả năng mở rộng
Khả năng mở rộng là khả năng cộng với quy mô, 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 phòng học có 50 học sinh. Một trong những giải pháp đơn giản nhất là đặt phòng, lấy bảng đen, vài viên phấn và vấn đề đã được giải quyết.
Nhưng nếu quy mô của vấn đề tăng lên thì sao? Nếu số học sinh tăng lên 200 em thì sao?
Giải pháp vẫn được duy trì nhưng nó cần nhiều nguồn lực hơn. Trong trường hợp này, bạn có thể sẽ cần một căn phòng lớn hơn nhiều (có thể là rạp hát), một màn hình máy chiếu và một cây bút kỹ thuật số.
Điều gì sẽ xảy ra nếu số học sinh tăng lên 1000?
Giải pháp không thành công hoặc sử dụng nhiều tài nguyên khi quy mô 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 thì giải pháp có thể mở rộng là gì?
Consider a site like Khanacademy, millions of students can see videos, read answers at the same time and no more resources are required. So, the solution can solve the problems of larger size under resource crunch.
If you see our first solution to find the sum of first N natural numbers, it wasn't scalable. It's because it required linear growth in time with the linear growth in the size of the problem. Such algorithms are also known as linearly scalable algorithms.
Our second solution was very scalable and didn't require the use of any more time to solve a problem of larger size. These are known as constant-time algorithms.
Memory is expensive
Memory is not always available in abundance. While dealing with code/system which requires you to store or produce a lot of data, it is critical for your algorithm to save the usage of memory wherever possible. For example: While storing data about people, you can save memory by storing only their age not the date of birth. You can always calculate it on the fly using their age and current date.
Examples of an Algorithm's Efficiency
Here are some examples of what learning algorithms and data structures enable you to do:
Example 1: Age Group Problem
Problems like finding the people of a certain age group can easily be solved with a little modified version of the binary search algorithm (assuming that the data is sorted).
The naive algorithm which goes through all the persons one by one, and checks if it falls in the given age group is linearly scalable. Whereas, binary search claims itself to be a logarithmically scalable algorithm. This means that if the size of the problem is squared, the time taken to solve it is only doubled.
Suppose, it takes 1 second to find all the people at a certain age for a group of 1000. Then for a group of 1 million people,
- the binary search algorithm will take only 2 seconds to solve the problem
- the naive algorithm might take 1 million seconds, which is around 12 days
The same binary search algorithm is used to find the square root of a number.
Example 2: Rubik's Cube Problem
Imagine you are writing a program to find the solution of a Rubik's cube.
This cute looking puzzle has annoyingly 43,252,003,274,489,856,000 positions, and these are just positions! Imagine the number of paths one can take to reach the wrong positions.
Fortunately, the way to solve this problem can be represented by the graph data structure. There is a graph algorithm known as Dijkstra's algorithm which allows you to solve this problem in linear time. Yes, you heard it right. It means that it allows you to reach the solved position in a minimum number of states.
Example 3: DNA Problem
DNA is a molecule that carries genetic information. They are made up of smaller units which are represented by Roman characters A, C, T, and G.
Imagine yourself working in the field of bioinformatics. You are assigned the work of finding out the occurrence of a particular pattern in a DNA strand.
It is a famous problem in computer science academia. And, the simplest algorithm takes the time proportional to
(number of character in DNA strand) * (number of characters in pattern)
A typical DNA strand has millions of such units. Eh! worry not. KMP algorithm can get this done in time which is proportional to
(number of character in DNA strand) + (number of characters in pattern)
The * operator replaced by + makes a lot of change.
Considering that the pattern was of 100 characters, your algorithm is now 100 times faster. If your pattern was of 1000 characters, the KMP algorithm would be almost 1000 times faster. That is, if you were able to find the occurrence of pattern in 1 second, it will now take you just 1 ms. We can also put this in another way. Instead of matching 1 strand, you can match 1000 strands of similar length at the same time.
And there are infinite such stories…
Final Words
Generally, software development involves learning new technologies on a daily basis. You get to learn most of these technologies while using them in one of your projects. However, it is not the case with algorithms.
Nếu bạn không biết rõ về các thuật toán, bạn sẽ không thể xác định được liệu bạn có thể tối ưu hóa mã bạn đang viết ngay bây giờ hay không. Bạn phải biết trước về chúng và áp dụng chúng bất cứ khi nào có thể và quan trọng.
Chúng tôi đã nói cụ thể 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. Tối ưu hóa bất kỳ một trong số chúng sẽ dẫn đến một hệ thống tốt hơn.
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 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 tới nhiều máy cùng nhau, làm cho nó có thể mở rộng hơn nữa.
