Dalam artikel ini, kita akan belajar mengapa setiap pengaturcara harus mempelajari struktur data dan algoritma dengan bantuan contoh.
Artikel ini adalah untuk mereka yang baru sahaja memulakan pembelajaran algoritma dan bertanya-tanya bagaimana kesannya untuk meningkatkan kemahiran kerjaya / program mereka. Juga bagi mereka yang tertanya-tanya mengapa syarikat besar seperti Google, Facebook, dan Amazon mengupah pengaturcara yang sangat pandai mengoptimumkan Algoritma.
Apa itu Algoritma?
Secara tidak rasmi, algoritma tidak lain adalah menyebut langkah-langkah untuk menyelesaikan masalah. Mereka pada dasarnya adalah penyelesaian.
Sebagai contoh, algoritma untuk menyelesaikan masalah faktorial mungkin kelihatan seperti ini:
Masalah: Cari faktor faktor n
Memulakan fakta = 1 Untuk setiap nilai v dalam julat 1 hingga n: Darabkan fakta dengan fakta v mengandungi faktorial n
Di sini, algoritma ditulis dalam bahasa Inggeris. Sekiranya ia ditulis dalam bahasa pengaturcaraan, kami akan memanggilnya sebagai kod . Berikut adalah kod untuk mencari faktorial nombor dalam C ++.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Pengaturcaraan adalah mengenai struktur data dan algoritma. Struktur data digunakan untuk menahan data sementara algoritma digunakan untuk menyelesaikan masalah menggunakan data tersebut.
Struktur dan algoritma data (DSA) melalui penyelesaian untuk masalah standard secara terperinci dan memberi anda gambaran tentang seberapa cekap penggunaan setiap kaedah tersebut. Ia juga mengajar anda ilmu menilai kecekapan algoritma. Ini membolehkan anda memilih yang terbaik dari pelbagai pilihan.
Penggunaan Struktur Data dan Algoritma untuk Membuat Kod Anda Skalabel
Masa sangat berharga.
Andaikan, Alice dan Bob berusaha menyelesaikan masalah mudah untuk mencari jumlah 10 11 nombor semula jadi yang pertama . Semasa Bob menulis algoritma, Alice menerapkannya membuktikan bahawa semudah mengkritik Donald Trump.
Algoritma (oleh Bob)
Memulakan jumlah = 0 untuk setiap nombor semula jadi n dalam julat 1 hingga 1011 (termasuk): tambah n untuk jumlah tambah adalah jawapan anda
Kod (oleh Alice)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice dan Bob merasa gembira kerana mereka dapat membina sesuatu sendiri dalam masa yang singkat. Mari menyelinap ke ruang kerja mereka dan dengar perbualan mereka.
Alice: Mari kita jalankan kod ini dan cari jumlahnya. Bob: Saya menjalankan kod ini beberapa minit yang lalu tetapi ia masih tidak menunjukkan hasilnya. Apa salahnya?
Op, ada yang tidak kena! Komputer adalah mesin yang paling menentukan. Kembali dan cuba menjalankannya lagi tidak akan membantu. Oleh itu mari kita analisis apa yang salah dengan kod ringkas ini.
Dua sumber yang paling berharga untuk program komputer adalah masa dan memori .
Masa yang diambil oleh komputer untuk menjalankan kod adalah:
Masa untuk menjalankan kod = bilangan arahan * masa untuk melaksanakan setiap arahan
Jumlah arahan bergantung pada kod yang anda gunakan, dan masa yang diperlukan untuk melaksanakan setiap kod bergantung pada mesin dan penyusun anda.
Dalam kes ini, jumlah arahan yang dilaksanakan (katakanlah x) adalah , iaitux = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Mari kita anggap bahawa komputer dapat melaksanakan arahan dalam satu saat (ia boleh berubah mengikut konfigurasi mesin). Masa yang diperlukan untuk menjalankan kod di atas adalahy = 108
Masa yang diambil untuk menjalankan kod = x / y (lebih daripada 16 minit)
Adakah mungkin untuk mengoptimumkan algoritma agar Alice dan Bob tidak perlu menunggu selama 16 minit setiap kali mereka menjalankan kod ini?
Saya pasti bahawa anda sudah meneka kaedah yang betul. Jumlah nombor semula jadi N pertama diberikan dengan formula:
Jumlah = N * (N + 1) / 2
Mengubahnya menjadi kod akan kelihatan seperti ini:
int sum (int N) (pulangan N * (N + 1) / 2;)
Kod ini dilaksanakan hanya dalam satu arahan dan menyelesaikan tugas tidak kira berapa nilainya. Biarkan ia lebih besar daripada jumlah atom di alam semesta. Ia akan menemui hasilnya dalam masa yang singkat.
Masa yang diambil untuk menyelesaikan masalah, dalam kes ini, adalah 1/y(iaitu 10 nanodetik). Omong-omong, reaksi peleburan bom hidrogen memerlukan masa 40-50 ns, yang bermaksud program anda akan berjaya diselesaikan walaupun seseorang melemparkan bom hidrogen ke komputer anda pada masa yang sama anda menggunakan kod anda. :)
Catatan: Komputer mengambil beberapa arahan (bukan 1) untuk mengira pendaraban dan pembahagian. Saya telah mengatakan 1 hanya untuk kesederhanaan.
Lebih banyak mengenai Skalabiliti
Skalabilitas adalah skala plus kemampuan, yang bermaksud kualiti algoritma / sistem untuk menangani masalah dengan ukuran yang lebih besar.
Pertimbangkan masalah penubuhan bilik darjah yang terdiri daripada 50 orang pelajar. Salah satu penyelesaian paling mudah adalah menempah bilik, mendapatkan papan tulis, beberapa kapur, dan masalahnya diselesaikan.
Tetapi bagaimana jika saiz masalah meningkat? Bagaimana jika bilangan pelajar meningkat kepada 200?
Penyelesaiannya masih ada tetapi memerlukan lebih banyak sumber. Dalam kes ini, anda mungkin memerlukan ruang yang jauh lebih besar (mungkin teater), skrin projektor dan pen digital.
Bagaimana jika bilangan pelajar meningkat kepada 1000 orang?
Penyelesaiannya gagal atau menggunakan banyak sumber ketika ukuran masalah meningkat. Ini bermaksud, penyelesaian anda tidak boleh ditingkatkan.
Apakah penyelesaian yang boleh diskalakan itu?
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.
Sekiranya anda tidak mengetahui algoritma dengan baik, anda tidak akan dapat mengenal pasti sama ada anda dapat mengoptimumkan kod yang anda tulis sekarang. Anda diharapkan dapat mengenali mereka terlebih dahulu dan menerapkannya sedapat mungkin dan kritikal.
Kami secara khusus membincangkan mengenai skalabiliti algoritma. Sistem perisian terdiri daripada banyak algoritma seperti itu. Mengoptimumkan salah satu daripadanya membawa kepada sistem yang lebih baik.
Walau bagaimanapun, penting untuk diperhatikan bahawa ini bukan satu-satunya cara untuk menjadikan sistem boleh diskalakan. Sebagai contoh, teknik yang dikenali sebagai pengkomputeran terdistribusi membolehkan bahagian bebas program berjalan ke beberapa mesin bersama-sama menjadikannya lebih terukur.
