Σε αυτό το άρθρο, θα μάθουμε γιατί κάθε προγραμματιστής πρέπει να μάθει δομές δεδομένων και αλγόριθμους με τη βοήθεια παραδειγμάτων.
Αυτό το άρθρο απευθύνεται σε εκείνους που μόλις άρχισαν να μαθαίνουν αλγόριθμους και αναρωτιούνται πόσο επίδραση θα είναι να ενισχύσουν τις δεξιότητες σταδιοδρομίας / προγραμματισμού τους. Είναι επίσης για όσους αναρωτιούνται γιατί μεγάλες εταιρείες όπως το Google, το Facebook και το Amazon προσλαμβάνουν προγραμματιστές που είναι εξαιρετικά καλοί στη βελτιστοποίηση των αλγορίθμων.
Τι είναι οι αλγόριθμοι;
Άτυπα, ένας αλγόριθμος δεν είναι παρά μια αναφορά βημάτων για την επίλυση ενός προβλήματος. Είναι ουσιαστικά μια λύση.
Για παράδειγμα, ένας αλγόριθμος για την επίλυση του προβλήματος των παραγόντων μπορεί να μοιάζει με αυτό:
Πρόβλημα: Βρείτε το παραγοντικό του n
Initialize fact = 1 Για κάθε τιμή v στην περιοχή 1 έως n: Πολλαπλασιάστε το γεγονός με v fact περιέχει το παραγοντικό του n
Εδώ, ο αλγόριθμος γράφεται στα Αγγλικά. Αν ήταν γραμμένο σε γλώσσα προγραμματισμού, θα το καλούσαμε αντί για κώδικα . Εδώ είναι ένας κωδικός για την εύρεση του παραγοντικού ενός αριθμού στο C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Ο προγραμματισμός αφορά αποκλειστικά τις δομές και τους αλγορίθμους δεδομένων. Οι δομές δεδομένων χρησιμοποιούνται για τη συγκράτηση δεδομένων, ενώ οι αλγόριθμοι χρησιμοποιούνται για την επίλυση του προβλήματος χρησιμοποιώντας αυτά τα δεδομένα.
Οι δομές δεδομένων και οι αλγόριθμοι (DSA) εξετάζουν λεπτομερώς λύσεις σε τυπικά προβλήματα και σας δίνουν μια εικόνα για το πόσο αποτελεσματικό είναι να χρησιμοποιείτε καθένα από αυτά. Σας διδάσκει επίσης την επιστήμη της αξιολόγησης της αποτελεσματικότητας ενός αλγορίθμου. Αυτό σας δίνει τη δυνατότητα να επιλέξετε τις καλύτερες από διάφορες επιλογές.
Χρήση δομών δεδομένων και αλγορίθμων για να κάνετε τον κώδικα σας επεκτάσιμο
Ο χρόνος είναι πολύτιμος.
Ας υποθέσουμε ότι η Άλις και ο Μπομπ προσπαθούν να λύσουν ένα απλό πρόβλημα εύρεσης του αθροίσματος των πρώτων 10 11 φυσικών αριθμών. Ενώ ο Μπομπ έγραφε τον αλγόριθμο, η Άλις τον εφάρμοσε αποδεικνύοντας ότι είναι τόσο απλό όσο η κριτική στον Ντόναλντ Τραμπ.
Αλγόριθμος (από τον Bob)
Αρχικοποιήστε το άθροισμα = 0 για κάθε φυσικό αριθμό n στην περιοχή 1 έως 1011 (συμπεριλαμβάνεται): η προσθήκη n στο άθροισμα είναι η απάντησή σας
Κωδικός (από την Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Η Αλίκη και ο Μπομπ νιώθουν ευφορία για τον εαυτό τους ότι θα μπορούσαν να φτιάξουν κάτι δικό τους σε σχεδόν καθόλου χρόνο. Ας ρίξουμε μια ματιά στον χώρο εργασίας τους και να ακούσουμε τη συνομιλία τους
Αλίκη: Ας τρέξουμε αυτόν τον κωδικό και ανακαλύψουμε το άθροισμα. Bob: Έτρεξα αυτόν τον κωδικό πίσω λίγα λεπτά αλλά εξακολουθεί να μην δείχνει την έξοδο. Ποιο ειναι το ΠΡΟΒΛΗΜΑ ΜΕ ΑΥΤΟ?
Ωχ! Κάτι πήγε στραβά! Ο υπολογιστής είναι η πιο ντετερμινιστική μηχανή. Η επιστροφή και η προσπάθεια να την εκτελέσετε ξανά δεν θα σας βοηθήσει. Ας αναλύσουμε λοιπόν τι συμβαίνει με αυτόν τον απλό κώδικα.
Δύο από τους πιο πολύτιμους πόρους για ένα πρόγραμμα υπολογιστή είναι ο χρόνος και η μνήμη .
Ο χρόνος που χρειάζεται ο υπολογιστής για την εκτέλεση του κώδικα είναι:
Χρόνος εκτέλεσης κώδικα = αριθμός οδηγιών * χρόνος εκτέλεσης κάθε εντολής
Ο αριθμός των εντολών εξαρτάται από τον κωδικό που χρησιμοποιήσατε και ο χρόνος που απαιτείται για την εκτέλεση κάθε κώδικα εξαρτάται από το μηχάνημα και τον μεταγλωττιστή σας.
Σε αυτήν την περίπτωση, ο συνολικός αριθμός των εντολών που εκτελέστηκαν (ας πούμε x) είναι , δηλαδήx = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Ας υποθέσουμε ότι ένας υπολογιστής μπορεί να εκτελέσει οδηγίες σε ένα δευτερόλεπτο (μπορεί να διαφέρει ανάλογα με τη διαμόρφωση του μηχανήματος). Ο χρόνος που απαιτείται για την εκτέλεση του παραπάνω κώδικα είναιy = 108
Χρόνος που απαιτείται για την εκτέλεση του κώδικα = x / y (μεγαλύτερο από 16 λεπτά)
Είναι δυνατόν να βελτιστοποιήσετε τον αλγόριθμο έτσι ώστε η Άλις και ο Μπομπ να μην χρειάζεται να περιμένουν για 16 λεπτά κάθε φορά που εκτελούν αυτόν τον κώδικα;
Είμαι σίγουρος ότι μαντέψατε ήδη τη σωστή μέθοδο. Το άθροισμα των πρώτων N φυσικών αριθμών δίνεται από τον τύπο:
Άθροισμα = N * (N + 1) / 2
Η μετατροπή του σε κώδικα θα μοιάζει με αυτό:
int sum (int N) (επιστροφή N * (N + 1) / 2;)
Αυτός ο κώδικας εκτελείται σε μία μόνο εντολή και ολοκληρώνει την εργασία ανεξάρτητα από την τιμή. Αφήστε το να είναι μεγαλύτερο από τον συνολικό αριθμό ατόμων στο σύμπαν. Θα βρει το αποτέλεσμα σε χρόνο μηδέν.
Ο χρόνος που απαιτείται για την επίλυση του προβλήματος, σε αυτήν την περίπτωση, είναι 1/y(δηλαδή 10 νανοδευτερόλεπτα). Παρεμπιπτόντως, η αντίδραση σύντηξης μιας βόμβας υδρογόνου διαρκεί 40-50 ns, πράγμα που σημαίνει ότι το πρόγραμμά σας θα ολοκληρωθεί με επιτυχία ακόμη και αν κάποιος ρίξει μια βόμβα υδρογόνου στον υπολογιστή σας την ίδια στιγμή που εκτελέσατε τον κωδικό σας. :)
Σημείωση: Οι υπολογιστές λαμβάνουν μερικές οδηγίες (όχι 1) για τον υπολογισμό του πολλαπλασιασμού και της διαίρεσης. Έχω πει 1 μόνο για λόγους απλότητας.
Περισσότερα για την επεκτασιμότητα
Η δυνατότητα κλιμάκωσης είναι κλίμακα συν ικανότητα, που σημαίνει την ποιότητα ενός αλγορίθμου / συστήματος που χειρίζεται το πρόβλημα μεγαλύτερου μεγέθους
Εξετάστε το πρόβλημα της δημιουργίας μιας τάξης 50 μαθητών. Μία από τις απλούστερες λύσεις είναι να κλείσετε δωμάτιο, να πάρετε έναν μαυροπίνακα, μερικές κιμωλίες και το πρόβλημα να επιλυθεί.
Τι γίνεται όμως αν το μέγεθος του προβλήματος αυξηθεί; Τι γίνεται αν ο αριθμός των μαθητών αυξηθεί σε 200;
Η λύση εξακολουθεί να ισχύει, αλλά χρειάζεται περισσότερους πόρους. Σε αυτήν την περίπτωση, πιθανότατα θα χρειαστείτε ένα πολύ μεγαλύτερο δωμάτιο (πιθανώς ένα θέατρο), μια οθόνη προβολέα και μια ψηφιακή πένα.
Τι γίνεται αν ο αριθμός των μαθητών αυξηθεί σε 1000;
Η λύση αποτυγχάνει ή χρησιμοποιεί πολλούς πόρους όταν αυξάνεται το μέγεθος του προβλήματος. Αυτό σημαίνει ότι η λύση σας δεν ήταν επεκτάσιμη.
Τι είναι μια επεκτάσιμη λύση τότε;
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.
Εάν δεν γνωρίζετε καλά τους αλγόριθμους, δεν θα μπορείτε να προσδιορίσετε εάν μπορείτε να βελτιστοποιήσετε τον κώδικα που γράφετε αυτή τη στιγμή. Αναμένεται να τα γνωρίζετε εκ των προτέρων και να τα εφαρμόσετε όπου είναι δυνατόν και κρίσιμα.
Συζητήσαμε συγκεκριμένα για την επεκτασιμότητα των αλγορίθμων. Ένα σύστημα λογισμικού αποτελείται από πολλούς τέτοιους αλγόριθμους. Η βελτιστοποίηση οποιουδήποτε από αυτά οδηγεί σε καλύτερο σύστημα.
Ωστόσο, είναι σημαντικό να σημειωθεί ότι αυτός δεν είναι ο μόνος τρόπος για να κάνετε ένα σύστημα επεκτάσιμο. Για παράδειγμα, μια τεχνική γνωστή ως κατανεμημένος υπολογιστής επιτρέπει την εκτέλεση ανεξάρτητων τμημάτων ενός προγράμματος σε πολλά μηχανήματα, καθιστώντας το ακόμη πιο επεκτάσιμο.
