W tym artykule dowiemy się, dlaczego każdy programista powinien uczyć się struktur danych i algorytmów na przykładach.
Ten artykuł jest przeznaczony dla tych, którzy dopiero zaczęli uczyć się algorytmów i zastanawiali się, jak znaczące będzie ich rozwinięcie umiejętności zawodowych / programistycznych. To także propozycja dla tych, którzy zastanawiają się, dlaczego duże firmy, takie jak Google, Facebook czy Amazon, zatrudniają programistów, którzy są wyjątkowo dobrzy w optymalizacji algorytmów.
Co to są algorytmy?
Nieformalnie algorytm to nic innego jak wzmianka o krokach prowadzących do rozwiązania problemu. Zasadniczo są rozwiązaniem.
Na przykład algorytm do rozwiązania problemu silni może wyglądać mniej więcej tak:
Problem: Znajdź silnię liczby n
Zainicjuj fakt = 1 Dla każdej wartości v w zakresie od 1 do n: Pomnóż fakt przez v fakt zawiera silnię n
Tutaj algorytm jest napisany w języku angielskim. Gdyby został napisany w języku programowania, nazwalibyśmy go zamiast tego kodem . Oto kod do znajdowania silni liczby w C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
W programowaniu chodzi o struktury danych i algorytmy. Struktury danych są używane do przechowywania danych, podczas gdy algorytmy są używane do rozwiązania problemu przy użyciu tych danych.
Struktury danych i algorytmy (DSA) szczegółowo analizują rozwiązania standardowych problemów i dają wgląd w to, jak efektywne jest wykorzystanie każdego z nich. Uczy także nauki oceniania skuteczności algorytmu. Umożliwia to wybór najlepszych z różnych opcji.
Wykorzystanie struktur danych i algorytmów do skalowania kodu
Czas jest cenny.
Załóżmy, że Alicja i Bob próbują rozwiązać prosty problem polegający na znalezieniu sumy pierwszych 10 11 liczb naturalnych. Podczas gdy Bob pisał algorytm, Alice zaimplementowała go, udowadniając, że jest to tak proste, jak krytykowanie Donalda Trumpa.
Algorytm (autor: Bob)
Zainicjuj sumę = 0 dla każdej liczby naturalnej n z zakresu od 1 do 1011 (włącznie): dodaj n do sumy suma to twoja odpowiedź
Kod (Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice i Bob odczuwają euforię, że mogą zbudować coś własnego w prawie krótkim czasie. Zakradnijmy się do ich miejsca pracy i posłuchajmy ich rozmowy.
Alice: Uruchommy ten kod i sprawdźmy sumę. Bob: Uruchomiłem ten kod kilka minut wstecz, ale nadal nie wyświetla danych wyjściowych. Co jest z tym nie tak?
Ups! Coś poszło nie tak! Komputer jest najbardziej deterministyczną maszyną. Powrót i ponowna próba uruchomienia go nie pomogą. Przeanalizujmy więc, co jest nie tak z tym prostym kodem.
Dwa najbardziej wartościowe zasoby programu komputerowego to czas i pamięć .
Czas potrzebny komputerowi do uruchomienia kodu to:
Czas wykonania kodu = liczba instrukcji * czas wykonania każdej instrukcji
Liczba instrukcji zależy od użytego kodu, a czas potrzebny do wykonania każdego kodu zależy od maszyny i kompilatora.
W tym przypadku całkowita liczba wykonanych instrukcji (powiedzmy x) wynosi , czylix = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Załóżmy, że komputer może wykonać instrukcje w ciągu jednej sekundy (może się to różnić w zależności od konfiguracji maszyny). Czas potrzebny do uruchomienia powyższego kodu toy = 108
Czas potrzebny do uruchomienia kodu = x / y (większy niż 16 minut)
Czy można zoptymalizować algorytm, aby Alicja i Bob nie musieli czekać 16 minut za każdym razem, gdy uruchamiają ten kod?
Jestem pewien, że już odgadłeś właściwą metodę. Suma pierwszych N liczb naturalnych jest określona wzorem:
Suma = N * (N + 1) / 2
Przekształcenie go w kod będzie wyglądać mniej więcej tak:
int sum (int N) (return N * (N + 1) / 2;)
Ten kod jest wykonywany w jednej instrukcji i wykonuje zadanie bez względu na wartość. Niech będzie większa niż całkowita liczba atomów we wszechświecie. Wynik znajdzie w mgnieniu oka.
W tym przypadku czas potrzebny do rozwiązania problemu wynosi 1/y(czyli 10 nanosekund). Nawiasem mówiąc, reakcja fuzji bomby wodorowej trwa 40-50 ns, co oznacza, że twój program zakończy się pomyślnie, nawet jeśli ktoś rzuci bombę wodorową na twój komputer w tym samym czasie, gdy uruchomisz kod. :)
Uwaga: komputery wykonują kilka instrukcji (nie 1), aby obliczyć mnożenie i dzielenie. Powiedziałem 1 tylko dla uproszczenia.
Więcej o skalowalności
Skalowalność to skala plus zdolność, co oznacza jakość algorytmu / systemu do obsługi problemu o większej skali.
Rozważmy problem utworzenia klasy liczącej 50 uczniów. Jednym z najprostszych rozwiązań jest zarezerwowanie pokoju, zdobycie tablicy, kilku kred i problem zostanie rozwiązany.
Ale co, jeśli rozmiar problemu się zwiększy? A co, jeśli liczba uczniów wzrośnie do 200?
Rozwiązanie nadal działa, ale wymaga więcej zasobów. W takim przypadku prawdopodobnie będziesz potrzebować znacznie większego pomieszczenia (prawdopodobnie kina), ekranu projektora i cyfrowego pióra.
A jeśli liczba uczniów wzrośnie do 1000?
Rozwiązanie zawodzi lub zużywa dużo zasobów, gdy rozmiar problemu rośnie. Oznacza to, że Twoje rozwiązanie nie było skalowalne.
Czym jest zatem rozwiązanie skalowalne?
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.
Jeśli nie znasz dobrze algorytmów, nie będziesz w stanie określić, czy możesz zoptymalizować kod, który właśnie piszesz. Oczekuje się, że znasz je z wyprzedzeniem i stosujesz je tam, gdzie jest to możliwe i krytyczne.
Mówiliśmy konkretnie o skalowalności algorytmów. System oprogramowania składa się z wielu takich algorytmów. Optymalizacja dowolnego z nich prowadzi do lepszego systemu.
Należy jednak pamiętać, że nie jest to jedyny sposób na skalowanie systemu. Na przykład technika znana jako przetwarzanie rozproszone umożliwia niezależne części programu uruchamianie na wielu komputerach jednocześnie, co czyni go jeszcze bardziej skalowalnym.
