Yeni problem çözme becerileri kazanmak ve Bilgisayar Bilimi bilginizi geliştirmek istiyorsanız, Scrimba'nın ücretsiz bir saatlik kursu olan The Working Developer's Guide to Algorithms'den başkasına bakmayın. Bilgisayar Bilimi konusunda geçmişi olmayan ve algoritmik düşünmeyi öğrenmekten fayda sağlayacağını düşünenler için tasarlanmıştır.
Kurs ne işe yarar?
Kılavuzumuz, altı farklı ikili arama algoritmasını nasıl oluşturacağınız konusunda size yol gösterir. Klasik Scrimba tarzında, yol boyunca bir dizi zorluk içerir, böylece bir yazılım geliştiricisi olarak becerilerinizi geliştirmek ve ileride algoritmalarla daha iyi çalışmak için ihtiyaç duyduğunuz kas hafızasını kazanacaksınız.
Öğreneceksin:
- Ikili arama
- Büyük O gösterimi
- Zorunlu kod
- Özyineleme
- Kuyruk özyineleme
- Dizi bölme
- Dizi görünümü
- Bölüm
Her algoritma üç aşamada öğretilir:
- İzlenecek yol: Jonathan algoritmayı kavramsal olarak tanıtıyor.
- Uygulama: Algoritmanın kendi versiyonlarını oluşturarak ellerimizi kirletiyoruz.
- Çözüm: Jonathan bize karşılaştırma için uygulamasını gösteriyor.
Önkoşullar
Javascript'i iyi anlıyorsanız ve ideal olarak zaten bir geliştirici olarak çalışıyorsanız veya bir Bootcamp mezunuysanız, bu kurstan en iyi şekilde yararlanacaksınız.
Henüz orada değilseniz, Scrimba'nın harika ücretsiz öğreticilerine JavaScript'e Giriş ve ES6 + Girişine bakın.
Eğitmene giriş
Jonathan Lee Martin bir yazılım geliştiricisi, web eğitimcisi, konuşmacı ve yazardır. Diğer geliştiricilerin yazma, konuşma, sürükleyici Eğitim Kampları, atölyeler ve çevrimiçi eğitimler yoluyla profesyonel ve kişisel hedeflerine ulaşmalarına yardımcı olur.
NASA ve HP gibi şirketler de dahil olmak üzere müşterilerle, sizi öğrenme yolculuğuna çıkaracak kişidir. Öyleyse başlayalım!
Ikili arama
Kursa erişmek için resme tıklayın.
İlk kastta Jonathan , üzerinde çalışacağımız algoritma olan Big-O notasyonu ve ikili arama kavramlarını tanıtıyor .
Big-O gösterimi , bir algoritmanın en kötü durum performansını tanımlamanın bir yoludur. Büyük O (O) (n), bir dizi n eleman uzunluğuna sahipse, çalışma süresinin n ile orantılı olacağını söyler. Diğer bir deyişle, yedi girişlik bir dizi, en kötü durumda 7 arama yapacak, tıpkı 7 milyon girişlik bir dizi en kötü durumda 7 milyon giriş alacak gibi. Yukarıdaki grafikte gösterildiği gibi, bu algoritmanın çalışma süresinin doğrusal olduğunu da söyleyebiliriz.
İkili arama , "Bu öğe bir listede nerede görünüyor?" Sorusunu yanıtlamak için kullanılan birkaç stratejiden biridir.
Soruyu cevaplarken iki ana yaklaşım vardır:
- Süpürücü : Doğru öğe bulunana kadar listedeki her öğeyi kontrol etme.
- Ayırıcı / İkili Arama : Listeyi ikiye bölmek, öğeyi bulmak için çok uzağa gidip gitmediğinizi kontrol etmek, sırasıyla sağ veya sol tarafta arama yapmak ve öğe bulunana kadar tekrar etmek.
Bu yaklaşımları, eski usul bir kağıt telefon rehberine bakmak açısından düşünebiliriz. Süpürücü yaklaşımı, başlangıçtan doğru olanın bulunduğu yere kadar her girişe bakmayı içerir. Ayırıcı yaklaşım, çoğu insanın kullanacağı yaklaşımdır - kitabı rastgele açmak ve giriş bulunana kadar ileri mi yoksa geri mi gitmeniz gerektiğini görmek.
İkili Arama, özellikle daha büyük listeler için süpürücü yaklaşımından daha verimlidir. Ancak yalnızca liste halihazırda sıralandığında çalışır.
Süpürme yaklaşımı doğrusal bir çalışma süresine (yukarıdaki grafiğe bakın) ve O (n) Büyük O'suna sahipken, ayırıcı yaklaşımının bir alt doğrusal çalışma süresi ve bir Büyük O O (log n) vardır.
Zorunlu
İlk meydan okuma kadrosunda Jonathan, ikili aramayı geleneksel bir tarzda uygulayarak, yani Big O of O (n) ile sabit miktarda bellek ve döngüler kullanarak elimizi kirletmemizi teşvik ediyor.
Jonathan, çözümümüzün başarılı olmasını sağlamak için kullanabileceğimiz bir test paketi sağlıyor ve uygulamasını kontrol etmeden önce bizi bu zorluğu denemeye teşvik ediyor. Burada spoiler yok, bu yüzden kendiniz denemek için oyuncu kadrosuna gidin.
Bu çözüm kısa ve ikili aramanın orijinal formülasyonuna yakın olsa da, muhtemelen çözümün yazmanın zor olduğunu ve bir yazılım ustalığı açısından en iyi çözüm olmadığını fark etmişsinizdir. Çözümü yükseltmenin yollarını öğrenmek için okumaya devam edin ...
Özyineleme
Bu kadroda, birkaç kısıtlama ile yeni bir sürümü uygulayarak ikili aramamızı geliştirmeye bakıyoruz. Çözümümüzün yine de Big O of O (n) olması gerekirken, döngüleri kullanmamalı ve özyineleme kullanmalıdır. Tüm değişkenler, değiştirilememeleri için constoperatörle başlatılmalıdır .
Jonanthan bize çözümün iskelet bir versiyonunu sunuyor ve ardından bizi bu mücadeleyi kendi başımıza denemeye teşvik ediyor:
let binarySearchWithRecursion = (array, element, compare = defaultCompare) => { return -1; }; export default binarySearchWithRecursion; Bu zorluğu tamamladıysanız, muhtemelen bu çözümün okumasının çok daha kolay, ancak oldukça ayrıntılı olduğunu görmüşsünüzdür. En kötü durumda, sonsuz özyineleme ile sonuçlanabilir. Çözümü kolaylaştırmanın yolları olup olmadığını görmek için kursa devam edin ...
Kuyruk Özyinelemesi
Bir sonraki döküm için zorluk, tekrarlamayı azaltarak önceki uygulamamızı iyileştirmektir.
Jonathan, çözümün önceki iki çözümden daha kötü görüneceği konusunda bizi uyarıyor, ancak bu bizi daha ileride bazı daha iyi optimizasyonlar için hazırlıyor. Zorluğu kendiniz denemek ve Jonathan'ın çözümünü görmek için şimdi kursa gidin.
Dizi Bölme
If you completed the previous challenge, you may have felt that we're still passing a lot of extra information into our binary search via recursion. This cast looks at a way of cleaning that up called array splitting.
We can think of array splitting in terms of our phone book example from earlier - whenever we decide that half the phone book is irrelevant, we just tear it off and throw it away. Similarly, our next solution should disregard any parts of the array which don't include our desired entry.
To help us achieve this, Jonathan starts us off with some skeleton code:
let binarySearchWithArraySplitting = ( array, element, compare = defaultCompare ) => { return -1; }; Then, as usual, he gives us free rein to try to the solution for ourselves before walking us through his own implementation.
Although this is an elegant method of binary search, because it involves making a copy of part of the array, it no longer has a Big O of O(n) and has a higher memory usage and slower run time. Continue with the course to find out whether there is a way to regain a higher performance with a similar code solution...
Array View
In this cast, we look for ways of merging the higher performance of our previous solutions with the elegance of array splitting. To do this, we create an array-like object that responds to the same methods as an array. We'll then inject this object in place of the original array.
Jonathan gets us started by initializing a function ArrayView which returns an object that expects three arguments: array, start and end. When invoked, ArrayView should return an object with four methods, length, toArray, slice and get.
export let ArrayView = ( array, start = 0, end = array.length, ) => ({ length: end - start, toArray: () => array.slice(start, end), slice: () => , get: () => , }); let binarySearchWithArrayView = (array, ...args) => binarySearchWithArraySplitting(ArrayView(array), ...args) Our challenge is to implement the slice and get methods of ArrayView without making a copy of the original array. Click through to try it out and then view Jonathan's walkthrough.
Although this solution produces better, more readable code, it is longer than some of our previous solutions. Continue with the course to find out if we can retain the benefits of ArrayView while lifting even more of the logic out of binary search code...
Array Partition
In the final challenge cast of the course, Jonathan gives us a goal of extracting some of the cryptic bounce logic in our previous version into a data structure.
For this, we need a simple data structure which returns the middle, left or right part of an array. To start us off, Jonathan sets up a function ArrayPartition:
export let ArrayPartition = (array, pivot) => ({ left: () => array.slice(0, pivot), middle: () => array.get(pivot), right: () => array.slice(pivot + 1, array.length), }); Next, Jonathan sets up a new version of binary search called binarySearchWithPartition, which has a starting signature the same as binarySearchWithArraySplitting:
let binarySearchWithPartition = (array, element, compare = defaultCompare) => { if (array.length === 0) { return -1; } const middle = Math.floor(array.length / 2); const comparison = compare(element, array.get(middle)); if (comparison === 0) { return middle; } //bounce logic const [left, right] = comparison === -1 ? [0, middle - 1] : [middle + 1, array.length]; //end of bounce logic const subIndex = binarySearchWithArraySplitting( array.slice(left, right), element, compare ); return subIndex === -1 ? -1 : left + subIndex; }; let binarySearchWithPartitionAndView = (array, ...args) => binarySearchWithPartition(ArrayView(array), ...args); Our challenge now is to rewrite binarySearchWithPartition with none of the bounce logic highlighted above, instead of creating an array partition and making calls to its left, middle and right methods.
Kendiniz için meydan okumayı denemek için şimdi kursa gidin. Jonathan'ın da belirttiği gibi, bu zorluk zor, bu yüzden çok uzun süre takılıp kalırsanız ancak kendi başınıza bir başlangıç yaparsanız çözümüne geçebilirsiniz.
Sarmak
Kursun sonuna kadar başardınız - harika iş çıkardınız! İkili aramaya yönelik, tümü kendi yararları ve dezavantajları olan birkaç yaklaşımı ele aldık ve algoritmalarla etkili bir şekilde çalışmak için harika bir kas hafızası oluşturduk.
Artık ikili aramaya altı farklı yaklaşım gördüğünüze göre, muhtemelen programlamanın birçok farklı yerinde ortaya çıktığını fark edeceksiniz.
Jonathan'ın 10 algoritma içeren tam kursu yıl sonunda çıkacak, ancak bu arada, yeni bulduğunuz ikili arama becerilerinizi iyi bir şekilde kullanabileceğinizi umuyorum.
Mutlu kodlamalar :)