Bu yazıda her programcının neden veri yapılarını ve algoritmaları öğrenmesi gerektiğini örnekler yardımıyla öğreneceğiz.
Bu makale, algoritmaları öğrenmeye yeni başlayanlar ve kariyerlerini / programlama becerilerini geliştirmenin ne kadar etkili olacağını merak edenler içindir. Ayrıca, Google, Facebook ve Amazon gibi büyük şirketlerin neden Algoritmaları optimize etmede son derece başarılı programcıları işe aldığını merak edenler için de geçerli.
Algoritmalar nedir?
Gayri resmi olarak, bir algoritma, bir sorunu çözme adımlarından başka bir şey değildir. Esasen bir çözümdür.
Örneğin, faktöriyel problemini çözmek için bir algoritma şunun gibi görünebilir:
Problem: n'nin faktöriyelini bulun
Initialize fact = 1 1'den n'ye kadar olan her v değeri için: olguyu v ile çarpın fact, n'nin faktöriyelini içerir
Burada algoritma İngilizce olarak yazılmıştır. Bir programlama dilinde yazılmış olsaydı, onu kodlamak için çağırırdık. C ++ 'da bir sayının faktöriyelini bulmak için bir kod.
int factorial(int n) ( int fact = 1; for (int v = 1; v <= n; v++) ( fact = fact * v; ) return fact; )
Programlama tamamen veri yapıları ve algoritmalarla ilgilidir. Veri yapıları verileri tutmak için kullanılırken, bu verileri kullanarak problemi çözmek için algoritmalar kullanılır.
Veri yapıları ve algoritmalar (DSA), standart sorunların çözümlerini ayrıntılı olarak inceler ve her birini kullanmanın ne kadar verimli olduğu konusunda size bir fikir verir. Aynı zamanda size bir algoritmanın verimliliğini değerlendirme bilimini de öğretir. Bu, çeşitli seçeneklerden en iyisini seçmenize olanak tanır.
Kodunuzu Ölçeklenebilir Hale Getirmek İçin Veri Yapılarının ve Algoritmaların Kullanımı
Zaman degerlidir.
Diyelim ki Alice ve Bob, ilk 10 11 doğal sayının toplamını bulmaya ilişkin basit bir problemi çözmeye çalışıyorlar . Bob algoritmayı yazarken, Alice bunu Donald Trump'ı eleştirmek kadar basit olduğunu kanıtlayarak uyguladı.
Algoritma (Bob tarafından)
1 ila 1011 (dahil) arasındaki her doğal sayı için toplam = 0'ı başlatın: cevabınız toplamına n ekleyin
Kod (Alice tarafından)
int findSum() ( int sum = 0; for (int v = 1; v <= 100000000000; v++) ( sum += v; ) return sum; )
Alice ve Bob, neredeyse hiç zaman kaybetmeden kendi başlarına bir şey inşa edebilecekleri için kendilerini şevkle hissediyorlar. Çalışma alanlarına gizlice girelim ve konuşmalarını dinleyelim.
Alice: Hadi bu kodu çalıştıralım ve toplamı bulalım. Bob: Bu kodu birkaç dakika önce çalıştırdım ama yine de çıktıyı göstermiyor. Bunun nesi var?
Hoop! Birşeyler yanlış gitti! Bilgisayar en belirleyici makinedir. Geri dönüp tekrar çalıştırmaya çalışmanın bir faydası olmaz. Öyleyse bu basit kodda neyin yanlış olduğunu analiz edelim.
Bir bilgisayar programı için en değerli kaynaklardan ikisi zaman ve bellektir .
Bilgisayarın kodu çalıştırmak için harcadığı süre:
Kodu çalıştırma süresi = talimat sayısı * her bir talimatı yürütme süresi
Talimatların sayısı kullandığınız koda bağlıdır ve her bir kodu çalıştırmak için geçen süre makinenize ve derleyicinize bağlıdır.
Bu durumda, yürütülen toplam komut sayısı (diyelim ki x) ,x = 1 + (1011 + 1) + (1011) + 1x = 2 * 1011 + 3
Bir bilgisayarın komutları bir saniyede yürütebileceğini varsayalım (makine yapılandırmasına bağlı olarak değişebilir). Yukarıdaki kodu çalıştırmak için geçen sürey = 108
Kodu çalıştırmak için geçen süre = x / y (16 dakikadan fazla)
Algoritmayı, Alice ve Bob'un bu kodu her çalıştırdıklarında 16 dakika beklemek zorunda kalmaması için optimize etmek mümkün müdür?
Eminim doğru yöntemi zaten tahmin etmişsinizdir. İlk N doğal sayının toplamı aşağıdaki formülle verilir:
Toplam = N * (N + 1) / 2
Bunu koda dönüştürmek şuna benzer:
int sum (int N) (dönüş N * (N + 1) / 2;)
Bu kod sadece bir komutta çalışır ve değeri ne olursa olsun görevi yerine getirir. Evrendeki toplam atom sayısından daha büyük olsun. Sonucu anında bulacaktır.
Bu durumda problemi çözmek için geçen süre 1/y(10 nanosaniye). Bu arada, bir hidrojen bombasının füzyon reaksiyonu 40-50 ns sürer, bu da sizin kodunuzu çalıştırdığınız sırada birisi bilgisayarınıza bir hidrojen bombası atsa bile programınızın başarıyla tamamlanacağı anlamına gelir. :)
Not: Bilgisayarlar, çarpma ve bölmeyi hesaplamak için birkaç talimat alır (1 değil). Sadece basitlik uğruna 1 dedim.
Ölçeklenebilirlik hakkında daha fazla bilgi
Ölçeklenebilirlik, ölçek artı kabiliyettir; bu, bir algoritmanın / sistemin kalitesinin daha büyük boyuttaki sorunu ele alması anlamına gelir.
50 öğrencilik bir sınıf kurma sorununu düşünün. En basit çözümlerden biri, bir oda ayırtmak, bir kara tahta, birkaç tebeşir almaktır ve sorun çözülür.
Peki ya sorunun boyutu büyürse? Öğrenci sayısı 200'e çıkarsa ne olur?
Çözüm hala geçerli ama daha fazla kaynağa ihtiyacı var. Bu durumda, muhtemelen çok daha büyük bir odaya (muhtemelen bir tiyatro), bir projektör ekranına ve bir dijital kaleme ihtiyacınız olacak.
Öğrenci sayısı 1000'e çıkarsa ne olur?
Sorunun boyutu arttığında çözüm başarısız olur veya çok fazla kaynak kullanır. Bu, çözümünüzün ölçeklenebilir olmadığı anlamına gelir.
O halde ölçeklenebilir çözüm nedir?
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.
Algoritmaları iyi bilmiyorsanız, şu anda yazdığınız kodu optimize edip edemeyeceğinizi belirleyemezsiniz. Bunları önceden bilmeniz ve mümkün ve kritik olan her yerde uygulamanız beklenmektedir.
Özellikle algoritmaların ölçeklenebilirliğinden bahsettik. Bir yazılım sistemi bu tür birçok algoritmadan oluşur. Bunlardan herhangi birini optimize etmek daha iyi bir sistem sağlar.
Ancak, bir sistemi ölçeklenebilir hale getirmenin tek yolunun bu olmadığına dikkat etmek önemlidir. Örneğin, dağıtılmış hesaplama olarak bilinen bir teknik, bir programın bağımsız bölümlerinin birden çok makinede birlikte çalışmasını sağlayarak onu daha da ölçeklenebilir hale getirir.
