İlk dört yazıda sürekli "dokundurulan" veri yapıları ve algoritmaların ne olduğundan bahsedeyim artık.
CS 201 - Fundamental Structures of Computer Science
(Bilgisayar Biliminde Temel Yapılar)
Bir dakika, önce pointer denen nanenin ne olduğunu öğrenmek gerekiyor. Java'da pointer yok, C, C++ gibi eski dillerde var. Dolayısıyla hocalar ikinci dönem bir anda C++ anlatmaya başlıyorlar. C++ ile Java arasındaki fark vardır ama bu farklar basit işlerle uğraşırken gözle görülebilecek düzeyde değildir, bu yazıları okurken farkı anlayamayacaksınız bile. Bu derste gösterilen ana fark pointerlar diyebiliriz hatta.
Pointerlar
Birinci yazıda GidenAraba'nın bir obje olduğundan bahsetmiştik. Java'da bir GidenAraba değişkeni tanımlandığı zaman o değişkenin içinde bir obje değil adres vardır da demiştik. Bu objede de GidenAraba'da ne tutuluyorsa onlar vardır, GidenAraba'da dört tane int vardı yani bir GidenAraba objesi dört tane int tutar, 4*4 byte = 16 byte yer kaplar diyebiliriz.
Pointer da içinde adres tutan değişken demektir. Bir integer pointerı şöyle tanımlanır:
int* elmaPointerı;
Sonra diyelim bir canım elma çekti.
int elmaSayısı = 10;
Şimdi elmaPointerımız elmaSayısına işaret etmiş olsun. Bunu şu şekilde yazarız:
int* elmaPointerı;
int elmaSayısı = 10;
elmaPointerı = &elmaSayısı
& demek "O değişkenin adresi" demek. &elmaSayısı diyince elmaSayısının içindeki 10'u değil, elmaSayısı değişkeninin hafızada bulunduğu adresi alıyoruz ve elmaPointerı'na atıyoruz.
Böylece yapınca ne oldu? elmaPointerı değişkeni de elmaSayısı değişkeninin tuttuğu değerin aynısını tutmuş oldu. Aynısı derken kopyası değil, direkt aynısı. elmaSayısı'nı değiştirirsek elmaPointerının tuttuğu adresteki değer de değişmiş olur dolayısıyla bu elmaPointerını da etkiler.
Bilgisayarınızdaki kısayollar pointerlara harika bir örnektir. Kısayolun işaret ettiği programı silerseniz kısayol çöp olur.
Aslında bu java'daki objelerin mantığının aynısı. Hani mehmetinArabası = ahmetinArabası yapınca ikisi aynı arabadan bahsetmiş oluyordu, ahmetinAraba satılınca mehmetinAraba da gitmiş oluyordu ya. Bu o onun daha genel versiyonu. C++'da bu mantık her tip değişkene uygulanabilirmiş ama Java yapımcıları sadece objelere uygulayalım kolay olsun demişler.
Burada önemli bir durum da şu, eğer bir değere veya obje işaret eden tüm pointerlar/değişkenler başka bir şeye işaret etmeye başlarsa Java garbage collector'u (çöpçü) çağırıp otomatik olarak objeyi yok ederken C++ bunu yapmamakta.
Örnek Java ve C++ kodu (ikisi için de aynı)
GidenAraba ahmetinArabası = new GidenAraba(); // Ahmete araba aldılar
GidenAraba mehmetinArabası = ahmetinArabası; // Mehmet de aynı arabayı kullanıyor.
ahmetinArabası = new GidenAraba(); // Ahmet büyüdü başka araba aldı. Mehmet'te hala Ahmet'in eski araba var.
mehmetinArabası = ahmetinArabası; // Mehmet bu sefer de Ahmet'in yeni arabaya çöreklendi.
E Ahmet'in eski arabaya ne oldu? Yazılımcı bundan bahsetmeye tenezzül etmedi. Bu durumda Java Ahmet'in eski arabayı otomatik olarak siler. C++ ise silmez. Fakat Ahmet'in eski arabaya hiçbir şekilde erişemeyiz çünkü ona işaret eden bir değişkenimiz yok. Bu şuna benziyor, bir yerde define gömülü ama bütün haritaları sobada yaktık. Buna memory leak denir çünkü silinmeyen obje hafızada boşu boşuna yer kaplamaktadır.
Silinmesi gereken objeyi "delete" komutuyla sileriz (bu java'da yoktur doğal olarak)
delete ahmetinArabası;
(Tahmin edeceğiniz gibi delete ahmetinArabası diyince ahmetin kullandığı arabayla beraber mehmetin kullandığı araba da yok oldu. Dolayısıyla bir daha delete mehmetinArabası dememize gerek yok.)
C++'da arrayler bir obje değil pointerdır. elmaSayıları arrayi aslında bir elmaSayıları için hafızada açılmış yanyana sayıların birincisine işaret eder. Array uzunluğu javadaki gibi ayrı bir yerde tutulmaz.
Koca bir arrayin adresini kaybettiğinizde oluşacak memory leak'in farkında mısınız? Hocalar buna sınavda çok dikkat ederler. Memory leak yaptıysanız bütün sorunuzu çizerler ki koca sınavda 3-4 soru bulunur puanları da 20-30-40 diye gider. O yüzden bu ders çok kolay olduğu halde kalanı çok olur.
C++'da pointerlar olduğu ve garbage collection olmadığı için C++ Java'dan daha hızlıdır. (Muhtemelen başka nedenleri de vardır.) Buradan hareketle bir programlama dili karmaşıklaştıkça, yazılımcıdan yükü alıp kendi bir şeyi yapmaya başladıkça onla yazılan programlar yavaşlar diyebiliriz. Bu mantıkla en hızlı kod machine kod veya ona birebir karşılık gelen assembly kodu diyebiliriz.
Güncelleme: Özelden şöyle bir soru geldi:
Garbage collector memory leak'lerin etkisini azaltarak kodun hızlanmasını sağlamaz mı? Pointerların C++'ı hızlandırması tamam, ama garbage collector olsa ve yazılımcının gözünden kaçan memory leak'ler de ortadan kaldırılsa bu hızlanma sağlamaz mı? Yoksa memory leak'in hıza bir etkisi yok mu?
Cevap: Garbage collector arkada çalışırken zaman yer, kodu yavaşlatır. Atıyorum ahmetinArabası = başkaAraba yazdık, hemen altına java otomatik olarak garbage Collector kodu koyar "ahmetin eski arabası çöp mu oldu sileyim mi" diye kontrol eder. Bu kontrol etme işlemi zaman yer. Halbuki iyi bir yazılımcı memory leaksiz kod yazabilir ve garbage collector'un yiyeceği zamandan da tasarruf etmiş olur. O yüzden büyük bilgisayar oyunları C++ yazılır, hızlı olsun diye. Tabii bu zamanda kimse bir bilgisayar oyununu sıfırdan yazmak, oyun motoru kullanır (yer çekimi gibi olayları kodlamaya gerek kalmaz böylece). Oyun motorlarından Unreal Engine'de ve CryEngine'de C++ kullanılmıştır mesela. (Unity C#)
Veri Yapıları
Temelde iki veri yapısı vardır: Array ve Linked List (bağlı liste). İkisinin arasındaki fark otobüs ile tren arasındaki fark gibidir; trene vagon ekleyip çıkarabilirsiniz ama otobüsü gövdesini çıkarıp şoförün önüne koyamazsınız.
İkisini bir görselle anlatalım:
Üsttekinde yani arrayde ilk elemana bir pointerımız vardır, diğer elemanlara erişmek için de "Abi arkalara doğru ilerleyelim." deriz. Arrayin elemanları birbirine zamklanmıştır. Linked listte ise vagon misali birbirine iple bağlıdır.
Bu durumda örneğin yukarıdaki örnekte arrayin baştan ikinci yani birinci çünkü hatırlarsanız saymaya sıfırdan başlıyoruz sileceğimiz zaman üzerinde bir yazan kutunun içeriğini yani A[1]'in işaret ettiği değeri sileriz ama kutu sonra bomboş kalır öyle, A[1] kaybolmaz yani. A[0]'dan A[2]'ye otomatik olarak atlayamayız.
(Aslında "ArrayinBuElemanıSilindiMi()" diye bir fonksiyon tanımlayıp A[1]'i kontrol edip A[2]'ye geçebiliriz ama bu durumda atıyorum A[7] de silinmiş olur, teknik olarak hepsi silinmiş olabilir, dolayısıyla tüm elemanları kontrol etmemiz gerekir. Bu da bize zaman kaybettirir.)
Dolayısıyla naparız, otobüsteki elemanlara "Abi şoföre doğru geri gelin buradaki eleman buharlaştı." deriz. Yani A[1] = A[2], A[2] = A[3] ... A[8] = A[9] diye ilerleriz. E A[9] ne oldu şimdi? Başta arrayimizin on elemanlı olduğunu belirtip ona göre açtığımız için bilgisayar A[9]'a dokunmaz, A[9] her zaman boş kalır, memory leak oldu.. Dolayısıyla bu problemi aslında 9 elemanlı yeni bir array açıp, A'daki elemanları yeni arraye koyup A'yı silerek çözeriz. (Not: Bu söylediğim C++ için geçerlidir, başka bir dilde A[9]'u kullanılabilir hale getirmek mümkün olabilir.)
Linked listte ise bunu yapmak çok kolaydır. 0. elemandan 1. elemana ip sarkıyor ya? O ipi al 2. elemana sarkıt. Tabii bunu yaparsan 1. elemana sarkan ip kalmaz, memory leak olur. O yüzden önce 1. elemanı delete komutuyla siler, sonra ipi sarkıtırız. Haa dur, bunu yaparsak, sildiğimiz elemanın üçüncü elemana işaret ettiği ipi de silmiş oluruz!!! Bu sefer üçüncü elemana ve dolayısıyla diğer elemanlara olan erişimimiz kaybolur ve tam bir memory leak skandalına imza atarız. Ama birincinin ipini direkt üçüncüye sarkıtırsak da ikinci elimizde kalıyor?
Burada ip dediğim şey tabii ki pointerdır!
Çözümü temiz bir şekilde yazıp anlatıyorum şimdi.
Linked listi oluşturalım:
int birinciEleman = 5;
int ikinciEleman = 10;
int üçüncüEleman = 7;
int* birinciElemanınİpi = &ikinciEleman // Birinci elemanın ipi ikinci elemanın adresine işaret etmiş oldu
int* ikinciElemanınİpi = &üçüncüEleman
(diğerlerini yazmaya gerek görmedim)
Biz ikinciEleman'ı silmek istiyoruz.
Bir tane geçici pointer tanımlayalım.
int* geçiciPointer = birinciElemanınİpi;
(aslında bu int* geçiciPointer = &ikinciEleman demek ama normalde ikinci elemanın adresi direkt elimizde olmaz, linked listi tarayarak buluruz.)
Şimdi ne oldu, artık ikinci elemana işaret eden yedek bir pointerımız olmuş oldu. Artık birinciElemanınİpi, ikinci elemana sarkan tek ip değil. Dolayısıyla birinciElemanınİpi istediğine sarkmakta özgür.
birinciElemanınİpi = ikinciElemanınİpi;
Artık ikinciElemanınİpi'nin sarktığı elemanı da biliyoruz, yani ikinciElemanınİpi'ne mecbur değiliz. O zaman ne duruyorsun? Helva yapsanaaa
delete geçiciPointer; // geçiciPointer ikinci elemana işaret ediyor, böylece ikinci elemanı silmiş olduk.
Bu örneğin silme işlemine bir örnekti, buradan ekleme işlemini de kendiniz çözebilirsiniz. Bir de bulma işlemi var. Bu üç temel işlem önemli ve işlemlerin yapılışı da hızı da farklı.
CS 202 - Fundamental Structures of Computer Science II
Algoritma Hızı ve Verimi
Nasıl farklı?
Dikkat ettiyseniz linked listte bir şey silerken sadece üç dört satır bir şey yaptık. Array'de bir şey silerken ise önce yeni array açtık, sonra da gidip tüm elemanları yeni arrayi attık, her eleman için işlem yaptık.
Yani;
Linked list:
Birinci elemanın ipini üçüncüye bağla.
Array:
Yeni array aç.
Her array elemanı için:
- o elemanı yeni arraye at.
On elemanlı bir array/linked list için aradaki fark çok belli olmasa da bir de 6 000 000 elemanlı bir array/linked list düşünün.
Bu durumda linked listte yapacağım yine bir kereye mahsus ipleri değiştirmekken array'de ise 6 000 000 iş yapmak gerekir.
Bilgisayar bilimcileri bu durumu fark etmişler ve algoritmaları hız bakımından analiz etmeye başlamışlar. Çeşitli analiz kavramları var ama en popüleri "Worst Case" dediğimiz en kötü durumdaki hızdır. Bir arrayde eleman silerken olacak en kötü durum o elemanın birinci arrayini silmektir çünkü ardından tüm elemanları beri getirmek gerekir. Bu da altı milyonluk bir arrayde altı milyon tane "küçük işlem" yapmak anlamına gelir.
Worst case Big O Notation denilen koca O notasyonu ile gösterilir. (Ağlıyordu Alan Turing, Yeter artık, bunları Türkçe'ye çevirme diyordu.) Bir veya birkaç kere yapılan işleme sabit denir. Sabit de 1 sayısı ile gösterilir. Arraydeki eleman sayısı ise N (number) dir.
Bu durumda eleman silme işlemi
Linked Listte O(1) zamanda
Array'de O(N) zamanda çalışır.
diyebiliriz.
Diyelim linked listimiz 10 saat sürecek bir işlem yapsaydı ama bu işlem elemana bağlı olarak artmasaydı, fakat array 1 saat işlem + eleman başına 1 dakika işlem yapsaydı, bu sayılar değişmezdi. Çünkü array'de eleman sayısına bağlı olarak katlanarak artarak ve belirli bir eleman sayısından sonra array'den silmek daha yavaş hale gelir.
Bu mantıkla O(n^2 + 2393n + 204802340234)'lık bir hız bulsak, bunu yuvarlar direkt O(n^2) deriz çünkü n^2 belirli bir sayıdan sonra diğerlerini geçer.
O zaman benden de size soru, 10 elemanlı bir arrayde 5. elemanı çekmek için kaç işlem yaparız, veya kısaca O notasyonunda hızınız ne olur?
Cevap:
.
.......
...................
......................................
.......................................................
......................................
......................
...........
.
Cevap soruda gizliydi:
Array'in beşinci elemanını çekmek çok basit!
int elmaSayısı = A[5]
dediğimiz anda 5. elemanı çekmiş oluyoruz zaten.
Dolayısıyla n. elemanı çekmek arrayde O(1)
Linked list'te ise işler değişir. Yukarıdaki kutular sıralı değil, birinci elemanın adresi 1. sokaksa diğerinin ki 2. sokak değil Milli İrade sokağı falan olabiliyor. Dolayısıyla bizim ip cambazlığı yapıp pointerları takip ede ede beşinciye gitmemiz gerekiyor.
Önceki problemi integer pointerı ile anlatmıştım. Burada ise Eleman objesi pointerı yaptım. Eleman objesinin Elemanınİpi pointerı var.
public class Eleman {
int elemanınDeğeri = 10;
Eleman* elemanınİpi = blabla
}
yani
Eleman* şimdikiEleman = birinciEleman;
deyip sonra aşağıdaki işlemi 4 kere tekrarlamamız gerek:
Eleman* şimdikiEleman = birinciEleman.elemanınİpi;
En kötü durumda en sondaki elemana erişmek için N elemanlı bir linked listte N işlem yaparız.
Cevap O(N)
Algoritmalar
Gelecekteki mühendislerin bu algoritma hızı bilgisini kullanarak kaplumbağa hızında yazılım yazmamaya çalışacakları beklenir. Bilgisayar tarihinde hit olmuş bazı algoritmalar öğretilerek hızlarının analizleri yapılır.
"Dizi sıralama algoritmaları"nın özellikle üzerinde duruluyor.
Örneğin şöyle bir arrayimiz var:
2 1 3 6
Bunu bana verseniz bir bakış atar sonra rasgele sayıları yerleştiririm. Bilgisayar bunları yapamaz, sayıları sıra sıra okur ve her seferinde aynı tekniği kullanır. Peki nasıl olacak bu teknik?
En basit ama yavaş teknik bu: Selection sort, yani bilgisayar arraydeki en küçük elemanı bulur, en sola koyar, sonra en küçük ikinci elemanı bulur, soldan ikinciye koyar. Tüm elemanlar için bunu tekrarlar.
Yani:
1 a) 2'yi okudum. En küçük 2
1 b) 1'i okudum. Artık en küçük 1.
1 c) 3'ü okudum. Hala en küçük 1
1 d) 6'yı okudum. Hala en küçük 1.
1 ile ilk elemanın yerini değiştir. Array şöyle oldu:
1 2 3 6.
Artık ilk elemanı doğru yerleştirdiğimizi biliyoruz, geri kalan üç sayıda da aynı işlemi uygulayacağız.
Sonuç değişmeyecek ama 2'yi de doğru yerleştirdiğimize emin olacağız. Bir daha, sonra bir daha.
N'lik bir arrayde ilk adımda N tane okuma ve bir tane swap (takas) yaparız, sonra N-1 okuma bir swap, N-2 okuma bir swap.
Okuma'ya R, Swap'e S desek.
R*(N + N-1 + N-2.....................+1) + N*S
parantezin içindekinin N*(N+1)/2 olduğunu lisedeki toplam sembolünden biliyorsunuz.
O zaman toplam işlem sayısı R*N^2/2 + R*N/2 + N*S
N^2'lar hepsini boğar. O(N^2)'de çalışır bu sıralama algoritması.
Tabii ki açgözlü amarikalılar bununla yetinmeyip daha hızlı algoritma bulmanın yollarını aramışlar ve en sonunda O(N*logN)'de çalışan fıstık gibi iki tane algoritma bulmuşlar, bunlar
Quicksort ve
Mergesort. Uzun ve şu an için gereksiz olduğu için anlatmayacağım. Merak edenler verdiğim linklerden izlesin.
Veri Yapıları:
Bu ders kalanında ve büyük bölümünde veri yapıları incelenir. Bu yapılar arraylerle veya linked listlerle kurulur. İlk önce anlatılan ikinci yazıda anlattığım "Tree"lerdir yani ağaçlar.
Bir ağacın babası iki tane dalı vardır. Babası olmayan ağaç elemanı köktür, dalı olmayan ağaç elemanına ise yaprak denir (ciddiyim) Örnek ağaç:
Ağaçlar hızlı ve verimli çalışsın diye amaca özel ağaç tipleri vardır, yani istediğiniz yaprağa eklemeye yapamazsınız. Örneğin yukarıdaki bir "Binary Search Tree" yani arama kurtarma ağacı. Bir ağaç elemanın sağ dalı elemanın tuttuğu sayıdan büyük sayı tutan elemanları içeriyor. Bu durumda 14'ü 13'ün sol dalına asamazsınız, sağ dalına asmanız gerekir. Aynı şekilde 15'in de sağ dalına asamazsanız.
AVL tree, Red-Black tree bilmemne tree anlatıldıktan sonra Hash Table, Stack, Queue falan anlatılır. Merak edenler araştırabilir.
Google Mülakatları
Yukarıda anlattığım şeyler google mülakatlarında sorulmakta. Google size "Windows mu Linux mu" karşılaştır diye nerdce şeyler sormaz, temel şeyleri sorar bakar bu adam üniversitede okuduğunu anlamış mı. Anlamışsa biz bunu eğitebiliriz der.
Örneğin
şu linkteki kardeşimize gelen sorulara bir göz atalım:
İlk bunu sormuşlar:
Why should one use merge sort over quick sort and vice-versa?
Anlamı: Neden merge sortu quick sorta tercih etmeliyiz / veya tersi?
En sonda da bunu:
You need to develop the game Snake. What data structures will you use? Code your solution.
Anlamı: Yılan oyunu yapacaksın, hangi veri yapısını kullanırsın? Kodlayarak göster.
İnternete "Google Interview Question" yazınca "Data structures, linked list, array" gibi anahtar kelimelerle karşılacaksanız. İngilizceniz varsa "Cracking The Code Interview" kitabına bir göz atın, hep bu konulardan soru geldiğini göreceksiniz.
