Arcade Türü Oyun Programlamayı
ve Bilgisayar Bilimleri ÖğreninChapter 15: Arama
Arama, bilgisayarların her zaman yaptığı önemli ve çok yaygın uygulanan bir işlemdir. Aramalar her zaman ctrl-f kullanılarak yapılır, bir öğeyi çabucak seçmeyi sağlar ya da müşterinin siparişi ile ihtiyaca göre düzenlenen bir sayfaya bilgileri çekip müşteriye göstermek için kullanılır.
Bilgiyi aramanın çok sayıda yolu vardır. Google bunun üzerine kurulmuş milyarlarca dolarlık bir şirkettir. Bu bölüm aramanın en basit iki yöntemi ile tanışmanızı sağlayacak. Bu yöntemler doğrusal ve bölerek aramalardır.
15.1 Bir Dosyadan Veri Okumak
Nasıl arama yapılacağını tartışmadan önce, bir dosyadan verinin nasıl okunacağını bilmek kullanışlı olacaktır. Bu, programın geniş veri gruplarını kolayca aramasına izin verir.
Diyelim ki süper güçlere sahip bir kötü adamın adını kolayca bulmamıza izin veren bir
program oluşturmaya ihtiyacımız var. Başlamak için, programımız süper güçlere sahip
kötü adamların veritabanına ihtiyaç duyar. Bu veri grubunu indirmek için alttaki
linke sağ tıklayın:
Süper Güçlere Sahip Kötü Adamlar
ve example_sorted_names.txt dosyasını indirin. Bunlar ne yazık ki bunlar yazılırken
yayında olmayan nine.frenchboys.net sitesi tarafından üretilmiş rastgele isimlerdir.
Bu dosyayı kaydedin ve hangi dizine kaydettiğinizi unutmayın.
Örnek isim listesinin kaydedildiği dizin ile aynı dizine alttaki Python programını oluşturun, kaydedin ve çalıştırın:
file = open("example_sorted_names.txt") for line in file: print(line)
Bu kodta yeni bir komut var. Python open isimli dahili bir fonksiyona sahiptir. Bu bir dahili (built-in) fonksiyon olduğu için, burada bir import işlemine gerek yoktur. Bu fonksiyon hakkında bütün detaylar Python dökümantasyonunda, burada, bulunabilir, fakat bu noktada bu komut için dökümantasyon çok fazla tekniktir ve bakmaya bile değmeyebilir.
Üstteki programın iki sorunu var, fakat basit bir dosya okuma örneği sağlıyor. 1 numaralı satırda dosya açılıyor ve okumaya hazır hale getiriliyor. Dosyanın adı tırnak işaretleri içerisinde yer alıyor. Yeni file değişkeni okunacak dosyayı temsil eden bir nesne görevinde bulunuyor. 3. satır normal bir for döngüsünün bir dosyayı doğrudan satır satır nasıl okuyabileceğini gösteriyor. file değişkenini (metin dosyasını) satırların bir listesi olarak düşünün. Yeni line değişkeni program döngü boyunca çalışırken bu satırların her birinin değerine atanacak.
Programı çalıştırmayı deneyin. Sorunlardan biri metnin çift aralıkla yazdırılmış olması. Bunun sebebi ise her satırın dosyadan ayrılıp saklandığı line değişkeninin satırbaşı işaretini (Ç.N "\n" içeriyor.) de stringin bir parçası olarak içermesi. print ifadesi ayrıca bir başka satırbaşı işareti ekliyor, sonuç olarak çıktıda iki aralık oluyor.
İkinci problem ise dosya açılıyor, fakat kapatılmıyor. Bu problem çift aralık sorunu kadar açık değil, fakat önemli. Windows işletim sistemi birçok dosyayı tek bir kez açabilir. Aynı zamanda, bir dosyayı aynı anda sadece tek bir program açık tutabilir. Yani bir dosyayı açık bırakmak diğer programların bu dosya ile yapabileceği işlemlere kısıtlama koyar. Bu dosyayı kapatmak ve Windows'un programın bu dosya ile artık çalışmadığını bilmesini sağlamak gereklidir. Bu durumda bu işlem çok fazla önemli değildir çünkü bir program çalışmayı bitirdiğinde, Windows otomatik olarak açık kalan programları kapatır. Fakat bunu bu şekilde yapmak kötü bir alışkanlıktır ve sonuç olarak, kod güncellenmelidir.
file = open("example_sorted_names.txt") for line in file: line=line.strip() print(line) file.close()
Yukarıdaki listeleme daha iyi çalışıyor. İki yeni eklemeye sahip. 4. satırda yer alan strip metodu her stringden sondaki boşluğu ve satırbaşı işaretlerini siler. Bu metod orijinal stringi değiştirmek yerine bir kopyasını oluşturur. Bu satır çalışmayacaktır:
line.strip()
Programcı orijinal değişkenin yeni stringi belirtmesini istiyorsa, bu metodtan dönen yeni stringi ona atamalıdır.
İkinci ekleme ise 7. satırda. Bu dosyayı işletim sisteminin daha sonra gitmek ve program bittikten sonra açık kalan dosyaları kapatmak zorunda kalmaması için kapatır.
15.2 Bir Dizinin İçerisine Okumak
Bir dosyanın içeriğini programın daha sonra üzerinde işlem yapabilmesi için bir diziye okumak kullanışlıdır. Bu Python ile alttaki kod yardımıyla kolayca yapılabilir:
# Diskten bir dosyayı oku ve onu bir dizinin içerisine koy. file = open("example_sorted_names.txt") name_list = [] for line in file: line=line.strip() name_list.append(line) file.close()
Bu, dosyanın nasıl okunacağı ile ilgili model ile birlikte önceden öğrenilen boş bir dizinin nasıl oluşturulacağı ve ona yeni veri geldikçe nasıl ekleme yapılacağını birleştiriyor. Dosyanın bir dizinin içerisine doğru şekilde okunduğunu doğrulamak için programcı dizinin uzunluğunu ekrana yazdırabilir:
print( "Bu dosyada",len(name_list),"tane isim var.")
Ya da programcı dizinin bütün içeriğini ekrana yazdırabilir:
for line in name_list: print(name)
15.3 Doğrusal Arama (Linear Search)
Program bir veri grubuna bir dizinin içerisinde sahipse, özel bir öğeyi nasıl bulabilir? Bu iki yolla yapılabilir. İlk yöntem doğrusal arama kullanmaktır. Bu ilk öğeden başlar, istenen öğeye kadar elemanları karşılaştırmaya istenen elemanı bulana kadar devam eder ya da kontrol edilecek elemanları bitirir.
# Doğrusal arama i=0 while i < len(name_list) and name_list[i] != "Morgiana the Shrew": i += 1 if i == len(name_list): print( "İsim listede bulunamadı." ) else: print( "İsmin bulunduğu pozisyon:",i)
Doğrusal arama oldukça kolaydır. 2. satırda programın bir sonraki kontrol edeceği liste elemanının tam olarak nerede olduğu takip edilsin diye bir artış değişkeni belirlenmiştir. Kontrol edilmeye ihtiyaç duyan ilk eleman sıfırıncı elemandır, bu durumda i de sıfır olarak ayarlanmıştır.
Sonraki satır biraz daha karmaşıktır. Bilgisayar iki şey gerçekleşene kadar döngüye devam edecektir. Aranan elemanı bulması ya da elemanların bitmesi. İlk karşılaştırma kontrol ettiğimiz elemanın indisi listenin uzunluğundan küçük mü diye bakıyor. Eğer küçükse, döngüye devam ediyor. İkinci karşılaştırma listedeki geçerli eleman aradığımız isme eşit mi diye bakıyor.
Programın kontrol edeceği elemanların bitip bitmediğinin kontrolü ilk önce yapılmak zorundadır. Aksi takdirde, program var olmayan bir elemanı kontrol etmeye çalışacak ve bu da bir hata oluşturacaktır.
4. satır 3. satırda belirtilen aramaya devam etme kriterleri sağlanıyorsa basitçe sonraki öğeye gidiyor.
Döngünün sonunda, program listenin sonuna erişilip erişilmediğini 6. satırda kontrol ediyor. Unutmayın, n elemanlı bir liste 0'dan n-1'e kadar numaralandırılır. Bu nedenle, eğer i, n. pozisyona(listenin uzunluğu) bakması için ayarlandıysa listenin sonuna erişilmiştir.
15.3.1 Tekrar
Programın doğrusal arama kullandığını varsayarak alttakileri cevaplayın:
- Liste n elemana sahipse, en iyi durumda bilgisayar istenen elemanı bulmadan önce kaç elemanı kontrol etmeye ihtiyaç duyar?
- Liste n eleman içeriyorsa, en kötü durumda bilgisayar istenen elemanı bulmadan önce kaç elemanı kontrol etmeye ihtiyaç duyar?
- Liste n elemandan oluşuyorsa, istenen elemanın listede olmadığını belirlemek için kaç elemanın kontrol edilmesine ihtiyaç vardır?
- Listede n eleman varsa, istenen eleman bulunmadan önce bilgisayarın kontrol etmesi gereken elemanların ortalama sayısı nedir?
- Örnek doğrusal arama kodunu alın ve onu bir fonksiyona koyun. İstenen elemanla birlikte bir liste alın. Elemanın yerini döndürün veya bulunamazsa -1 döndürün.
15.4 Bölerek Arama
Bir listede arama yapmanın daha hızlı bir yolu bölerek arama ile mümkündür. Bölerek aramadaki işlem klasik sayı tahmin oyunu olan "1 ile 100 arasında bir sayı tahmin et" örneği ile tarif edilebilir. İşlemi anlamayı daha basit hale getirmek için, oyunu "1 ile 128 arasında bir sayı tahmin edin" şekline getirelim. Sayı aralığı kapalıdır, yani hem 1 hem de 128 ihtimallere dahildir.
Eğer bir kişi doğrusal aramayı gizli bir sayıyı tahmin etmek için yöntem olarak kullanırsa, oyun oldukça uzun ve sıkıcı olurdu.
1'den 128'e kadar bir sayı tahmin et: 1 Çok az. 1'den 128'e kadar bir sayı tahmin et: 2 Çok az. 1'den 128'e kadar bir sayı tahmin et: 3 Çok az. .... 1'den 128'e kadar bir sayı tahmin et: 93 Çok az. 1'den 128'e kadar bir sayı tahmin et: 94 Doğru!
Çoğu kişi bir sayıyı bulmak için bölerek aramayı kullanacaktır. Burda bölerek arama kullanarak bu oyunu oynamanın bir örneği var:
1'den 128'e kadar bir sayı tahmin et: 64 Çok az. 1'den 128'e kadar bir sayı tahmin et: 96 Çok fazla. 1'den 128'e kadar bir sayı tahmin et: 80 Çok az. 1'den 128'e kadar bir sayı tahmin et: 88 Çok az. 1'den 128'e kadar bir sayı tahmin et: 92 Çok az. 1'den 128'e kadar bir sayı tahmin et: 94 Doğru!
Sayı tahmin oyununun her aşamasında, tahmin eden kişi problem alanının yarısını "fazla" ya da "az" olarak aldığı tahmin cevabıyla eleyebiliyor.
Bölerek aramada, cevabın olabileceği listede bir üst ve alt sınır takip etmek gereklidir. Bilgisayar veya sayı tahmin eden insan bu öğelerin orta noktasını alır. Örneğe tekrar bakalım:
Bir alt sınır 1, üst sınır 128, orta noktaları $(1+128)/2 = 64.5$.
1'den 128'e kadar bir sayı tahmin et: 64 Çok az.
Bir alt sınır 65, üst sınır 128, orta noktaları $(65+128)/2 = 96.5$.
1'den 128'e kadar bir sayı tahmin et: 96 Çok fazla.
Bir alt sınır 65, üst sınır 95, orta noktaları $(65+95)/2 = 80$.
1'den 128'e kadar bir sayı tahmin et: 80 Çok az.
Bir alt sınır 81, üst sınır 95, orta noktaları $(81+95)/2 = 88$.
1'den 128'e kadar bir sayı tahmin et: 88 Çok az.
Bir alt sınır 89, üst sınır 95, orta noktaları $(89+95)/2 = 92$.
1'den 128'e kadar bir sayı tahmin et: 92 Çok az.
Bir alt sınır 93, üst sınır 95, orta noktaları $(93+95)/2 = 94$.
1'den 128'e kadar bir sayı tahmin et: 94 Doğru!
Bölerek arama(ikili arama) önemli derecede daha az tahmin gerektirir. En kötü durumda, 1 ile 128 arasında bir sayıyı 7 kerede bulabilir. Bir deneme fazla yapmak bu limiti 256'ya çıkarır. 9 deneme ile bu sayı 1 ile 512 arasına çıkar. Sadece 32 denemede, bir kişi 1 ile 4.2 milyar arasındaki sayıyı doğru tahmin edebilir.
Bölerek aramanın kodu doğrusal aramadan biraz daha karmaşıktır:
# Bölerek arama desired_element = "Morgiana the Shrew"; lower_bound = 0 upper_bound = len(name_list)-1 found = False while lower_bound < upper_bound and found == False: middle_pos = (int) ((lower_bound+upper_bound) / 2) if name_list[middle_pos] < desired_element: lower_bound = middle_pos+1 elif name_list[middle_pos] > desired_element: upper_bound = middle_pos else: found = True if found: print( "İsmin bulunduğu indis",middle_pos) else: print( "İsim listede bulunamadı." )
Listeler sıfır indisinden başladığı için, 3. satırda alt satır sıfır olarak belirleniyor. 4. satır üst sınırı listenin uzunluğunun bir eksiği olarak belirliyor. Şimdiye kadar 100 elemandan oluşan listenin alt sınırı 0, üst sınırı 99 oluyor.
5. satırdaki mantıksal(Boolean) değişken while döngüsüne elemanın bulunduğunu söylemek için kullanılıyor.
6. satırda elemanın bulunup bulunmadığı veya bütün elemanların bitip bitmediği kontrol ediliyor. Eğer elemanlar bittiyse alt sınır üst sınıra eşitleniyor.
7. satırda orta nokta bulunuyor. 64.5 gibi bir orta nokta bulmak da mümkün. 64.5 pozisyonuna bakmak imkansız. (J.K. Rowling'in Platform $9\frac{3}{4}$'de oldukça akıllıca yaklaşmasına rağmen.) Bu nedenle sonucu (int) ile tamsayıya çevirmek gerekiyor.
Bu satırı yapmanın alternatif bir yolu // operatörünü kullanmak. Bu / operatörüne benzerdir, fakat sadece tamsayı olarak sonuç döndürür. Örneğin, 11 // 2 cevap olarak 5.5 yerine 5'i cevap olarak verecektir.
middle_pos = (lower_bound+upper_bound) // 2
8. satırdan başlayarak, program tahminin yüksek, düşük veya doğru olup olmadığını kontrol etmeye başlıyor. Eğer tahmin düşükse, alt sınır son tahminin hemen üstüne yükseltiliyor. Eğer tahmin düşükse, üst sınır tahminin hemen altına düşürülüyor. Cevap bulunduysa, found değişkenine True atanıyor ve arama bitiyor.
15.4.1 Tekrar
Alttakileri cevaplayın, programın bölerek aramayı kullandığını ve listelerin sıralı olduğunu varsayın:
- Listede n eleman varsa, en iyi durumda bilgisayar istenen elemanı bulmadan önce kaç eleman kontrol edilecektir?
- Listede n eleman varsa, en kötü durumda bilgisayar istenen elemanı bulmadan önce kaç eleman kontrol edilecektir?
- Listede n eleman varsa, bilgisayar istenen elemanın listede olmadığını belirlemek için kaç eleman kontrol edilmelidir?
- Listede n eleman varsa, durumda bilgisayar istenen elemanı bulmadan önce ortalama kaç tane eleman kontrol edilecektir?
- Doğrusal arama kodu örneğini alın ve onu bir fonksiyonun içerisine koyun. Listeyi istenen elemanla birlikte gönderin. Elemanın indisini döndürsün veya bulunamazsa -1 döndürsün.
You are not logged in. Log in here and track your progress.
English version by Paul Vincent Craven
Spanish version by Antonio Rodríguez Verdugo
Russian version by Vladimir Slav
Turkish version by Güray Yildirim
Portuguese version by Armando Marques Sobrinho and Tati Carvalho
Dutch version by Frank Waegeman
Hungarian version by Nagy Attila
Finnish version by Jouko Järvenpää
French version by Franco Rossi
Korean version by Kim Zeung-Il
Chinese version by Kai Lin