Bir geliştirici olarak, dünyayı değiştirme gücüne sahipsiniz! Evet. Yeni teknolojilere olanak sağlayan programlar yazabilirsiniz. Örneğin, daha erken bir hastalık teşhisi bulmak için yazılım geliştirin. Ancak, bu tek yol değildir, dolaylı yoldan insanları daha üretken kılan ve diğer şaşırtıcı şeyleri yapma konusunda serbest zaman kazanmalarına yardımcı olan projeler oluşturarak yapabilirsiniz. Ne yaparsanız yapın, onu kullanan toplumu etkileme potansiyeli vardır.

Ancak, bu başarılar hızlı ve ölçeklenebilir bir yazılım yazmamız durumunda mümkündür. Kod performansınızı nasıl ölçeceğinizi öğrenmek bu yazının birinci amacıdır.

Algoritma analizini kullanarak kod performansınızı nasıl ölçebileceğinizi keşfedeceğiz: zaman karmaşıklığı ve büyük O notasyonu.

İlk olarak, bunun neden önemli olduğunu öğrenmek için gerçek bir hikaye görelim.

Milyonlarca insanı kurtaran algoritma

II. Dünya Savaşı sırasında Almanlar, Avrupa’daki birliklerle iletişim kurmak için AM radyo sinyallerini kullandı . AM frekansı radyosu ve bazı Mors kodu bilgisi olan herkes mesajı engelleyebilir. Ancak, bilgi okundu! Saldırı altındaki tüm ülkeler onu çözmeye çalıştı. Bazen, şanslılar ve günün sonunda birkaç mesaj anlayabiliyorlardı. Ne yazık ki, Naziler her gün kodlamayı değiştirdi!

Alan Turing adlı parlak bir matematikçi, Alman “Enigma” kodunu kırmak için İngiliz ordusuna katıldı. Hesaplamaları kalem ve kağıtla yaparlarsa asla öne geçemeyeceklerini biliyordu. Bu yüzden aylarca süren yoğun çalışmalardan sonra bir makine yaptılar. Ne yazık ki, cihazın ilk sürümü bir mesajı çözmek için uzun sürdü! Yani, çok kullanışlı değildi.

Alan’ın takımı şifreli her mesajın aynı dizeyle bittiğini öğrendi: “Heil Hitler” Aha! Algoritmayı değiştirdikten sonra, makine yayınları daha hızlı çözebildi! Savaşı daha hızlı bitirmek ve milyonlarca insanı kurtarmak için bilgiyi kullandılar!

Bir arıza olarak kapanacak olan aynı makine, canlı bir koruyucu haline geldi. Aynı şekilde, verimli kod yazarken bilgi işlem kaynaklarınızla daha fazlasını yapabilirsiniz. Bu yazı dizisinde öğreneceğimiz şey bu!

Diğer bir popüler algoritma PageRank1998 yılında Sergey Brin ve Larry Page (Google kurucuları) tarafından geliştirilmiştir. Bu algoritma, trilyonlarca web sayfasını anlamak için bir Google arama motoru tarafından kullanıldı. Google tek arama motoru değildi. Ancak, algoritmaları daha iyi sonuçlar verdiğinden, rakiplerin çoğu ortadan kayboldu. Bugün 3 milyar günlük aramanın çoğuna çok hızlı bir şekilde güç veriyor. Ölçeklendiren algoritmaların gücü budur!

Peki neden verimli algoritmalar yazmayı öğrenmelisiniz?

Birçok avantaj var; bunlar sadece bunlardan bazıları:

• Çok daha iyi bir yazılım geliştiricisi (ve daha iyi iş / gelir) elde edersiniz.
• Kod hata ayıklama, optimizasyon ve yeniden yazma daha az zaman harcayın.
• Yazılımınız aynı donanımla daha hızlı çalışacaktır (daha ucuz ölçeklendirme).
• Programlarınız hayat kurtaran keşiflere yardımcı olmak için kullanılabilir (belki?).

Daha fazla uzatmadan, oyunumuzu hızlandıralım!

Algoritma nedir?

Algoritmalar (bildiğiniz gibi), bazı işlerin nasıl yapılacağının adımlarıdır. Örneğin, yemek pişirirken, bir yemek hazırlamak için bir reçete izlersiniz. Bir oyun oynarsanız, kazanmanıza yardımcı olacak stratejiler geliştiriyorsunuz . Benzer şekilde, bilgisayarlardaki algoritmalar bir sorunu çözmek için kullanılan bir dizi talimatdır.

Algoritmalar bir görevi gerçekleştirmek için talimatlardır

“İyi” ve “Kötü” algoritmalar var. İyiler hızlı; Kötü olanlar yavaş. Yavaş algoritmalar daha fazla paraya mal olur ve ömrünüzde bazı hesaplamaları imkansız hale getirir!

Algoritmaların temel kavramlarını keşfedeceğiz. Ayrıca, “hızlı” yı “yavaş” olanlardan nasıl ayırt edeceğimizi öğreneceğiz. Daha da iyisi, algoritmalarınızın performansını “ölçebilecek” ve bunları geliştirebileceksiniz!

Kodlama becerilerinizi nasıl geliştirirsiniz?

Bir şeyi geliştirmek için ilk adım, onu ölçmektir.

Ölçüm, kontrole ve sonunda iyileşmeye yol açan ilk adımdır. Bir şeyi ölçemezseniz, anlayamazsınız. Eğer anlayamıyorsanız, kontrol edemezsiniz. Kontrol edemezseniz, iyileştiremezsiniz.

HJ Harrington

Kodunuzu nasıl ölçersiniz? Çalıştırmak için ne kadar sürdüğünü saatlerce verir misiniz? Aynı programı bir mobil aygıtta veya kuantum bilgisayarda çalıştırıyorsanız ne olur? Aynı kod size farklı sonuçlar verecektir, değil mi?

Bu soruları cevaplamak için, önce zaman karmaşıklığı gibi bazı kavramları ele almamız gerekiyor!

Zaman karmaşıklığı

Zaman karmaşıklığı (veya çalışma süresi ), bir algoritmanın çalışması için geçen süredir. Ancak, zaman karmaşıklığını saniye cinsinden ölçmezsiniz, ancak girişin bir fonksiyonu olarak. (Garip olduğunu biliyorum ama yanımda ol).

Zaman karmaşıklığı algoritması ne kadar zamanda ilgili değildir. Bunun yerine, kaç işlem yürütülür. Bir program tarafından yürütülen talimatların sayısı, girişin boyutundan ve öğelerinin nasıl düzenlendiğinden etkilenir.

Neden zaman karmaşıklığı girdilerin bir fonksiyonu olarak ifade ediliyor? Diyelim ki bir dizi diziyi sıralamak istediğinizi varsayalım. Öğeler zaten sıralanırsa, program daha az işlem gerçekleştirir. Aksine, öğeler ters sıradaysa, sıralanması için daha fazla zaman gerekir. Bu nedenle, bir programın yürütülmesi için gereken süre doğrudan girdi büyüklüğü ve elemanların nasıl düzenlendiği ile ilgilidir.

Her algoritma için aşağıdaki çalışma sürelerine sahip olduğumuzu söyleyebiliriz:

• En kötü durum zaman karmaşıklığı (örneğin, ters sırada girdi elemanları)
• En iyi durum zaman karmaşıklığı (örneğin, zaten sıralanmıştır)
• Ortalama durum zaman karmaşıklığı (örneğin, rasgele sıradaki öğeler)

Genellikle en kötü durum zaman karmaşıklığına daha çok önem veriyoruz (En iyisini umuyoruz, ancak en kötüsüne hazırlanıyoruz).

Zaman karmaşıklığını hesaplamak

İşte zaman karmaşıklığını nasıl hesaplayabileceğinizi gösteren bir kod örneği: Bir dizideki en küçük sayıyı bulun.

/ ** 
* Sayı dizisindeki en küçük sayıyı alın 
* @param {Array} n sayı dizisi 
* / 
function  getMin ( n ) { const array = Array .from (n); izin ver min;
  
  

  array.forEach ( element => { if (min === undefined || element <min) {       min = element;     }   }); min dönüş ; }

Gerçekleştirmesi gereken işlem sayısına bağlı olarak, getMingirdi boyutunun bir fonksiyonu olarak temsil edebiliriz n. Basit olması için, her kod satırının CPU’da yürütülmesi için aynı miktarda zaman aldığını varsayalım. Toplamı yapalım:

• Satır 6: 1 işlem
• Satır 7: 1 işlem
• 9-13. Satır: nkez boyut yürüten bir döngüdür
  • Satır 10: 1 işlemi
  • Satır 11: bu zor. Bir şartlı içinde. Dizinin azalan düzende sıralandığı en kötü durumu kabul edeceğiz. Koşul ( ifblok) her seferinde yürütülecektir. Böylece, 1 işlem
• Satır 14: 1 işlem

Sonuçta, 3döngü dışında ve bloğun 2içinde işlemlerimiz var forEach. Döngü boyutu için gittiğinden n, bu bizi bırakır 2(n) + 3.

Bununla birlikte, bu ifade algoritmaları onunla karşılaştırmak için çok özel ve zordur. Bu ifadeyi daha da basitleştirmek için asimptotik analizi uygulayacağız .

Asimptotik analiz

Asimptotik analiz, işlevleri yalnızca sonsuz değere yakın olan değer olarak değerlendiriyor. Önceki örneğimizde 2(n) + 3, bunu genelleştirebiliriz k(n) + c. Büyüme değeri narttıkça, caşağıdaki tabloda görebileceğiniz gibi değer daha az ve daha az önemlidir:

n (boyut)	operasyonlar	sonuç
1	2 (1) + 3	5
10	2 (10) + 3	23
100	2 (100) + 3	203
1.000	2 (1.000) + 3	2003
10.000	2 (10.000) + 3	20003

İster inanın ister inanmayın, sabit kde bir fark yaratmaz. Biz bu durumda, yüksek mertebeden eleman almak asimptotik bu tür bir analiz kullanarak: n.

Başka bir örnek yapalım, böylece bu kavramı alabiliriz. Diyelim ki aşağıdaki işlevimiz var: 3 n 2 + 2 n + 203n2+2n+20. Asimptotik analizi kullanmanın sonucu ne olurdu?

3 n 2 + 2 n + 203n2+2n+20olarak nnbüyür ve büyür; En fazla fark yaratacak terim n 2n2.

Örneğimize geri getMindönersek, bu işlevin zaman karmaşıklığı olduğunu söyleyebiliriz n. Gördüğünüz gibi, n olarak çok fazla değer katmadığından onu yaklaşık olarak değerlendirebilir 2(n)ve düşürebiliriz.+3n büyümeye devam et.

Buradaki büyük resimle ilgileniyoruz ve bu konuda bize yardımcı olmak için asimptotik analizi kullanacağız. Bu çerçeve ile algoritmaların karşılaştırılması çok daha rahat. Çalışma sürelerini en anlamlı terimleriyle karşılaştırabiliriz: n 2n2veya nnveya 2 n2n.

Big-O notasyonu ve Büyüme oranı

Big O notasyonu son iki bölümde öğrendiğimiz şeyleri en kötü durum karmaşıklığı ve asimptotik analizler ile birleştirir.

O harfiÖbir fonksiyonun sırasını ifade eder .

Big O notasyonu, algoritmaları en kötü çalışma sürelerine göre sınıflandırmak için kullanılır veya aynı zamanda bir fonksiyonun büyüme hızının üst sınırı olarak da adlandırılır.

getMinFonksiyonlu önceki örneğimizde çalışma süresi olduğunu söyleyebiliriz O(n). Çok farklı çalışma süreleri var. Bir sonraki yazıda ele alacağımız en yaygın olan ve zamanla olan ilişkilerini şöyle:

Büyüme oranlarına göre nbüyüklük:

n	O (1)	O (log n)	O (n)	O (n log n)	O (n 2 )	0 (2 n )	O (n!)
1	<1 sn	<1 sn	<1 sn	<1 sn	<1 sn	<1 sn	<1 sn
10	<1 sn	<1 sn	<1 sn	<1 sn	<1 sn	<1 sn	4 saniye
100	<1 sn	<1 sn	<1 sn	<1 sn	<1 sn	40170 trilyon yıl	> vigintillion yıl
1.000	<1 sn	<1 sn	<1 sn	<1 sn	<1 sn	> vigintillion yıl	> milyonlarca yıl
10.000	<1 sn	<1 sn	<1 sn	<1 sn	2 dakika	> milyonlarca yıl	> milyonlarca yıl
100.000	<1 sn	<1 sn	<1 sn	1 saniye	3 saat	> milyonlarca yıl	> milyonlarca yıl
1.000.000	<1 sn	<1 sn	1 saniye	20 saniye	12 gün	> milyonlarca yıl	> milyonlarca yıl

Varsayım: 1 GHz işlemci ve 1 nanosaniyede ortalama bir komut üzerinde çalışabileceğini (genellikle daha fazla zaman alır). Ayrıca, her dilin, programlama diline bağlı olarak onlarca CPU komutuna çevrilebileceğini unutmayın.

Gördüğünüz gibi, bazı algoritmalar çok zaman alıyor. 100 kadar küçük bir giriş boyutu, 1 PHz (1 milyon GHz) CPU’sumuz olsa bile hesaplanamaz! Donanım, yazılım kadar ölçeklendirilmez.