Sıralama basit ama güçlü bir konsepttir. Düzenlenmemiş bir öğe listesini alıp bir algoritma kullanarak bunları belirli bir düzene göre sıralayabilirsin. Bu fikir basit gibi görünse de sıralama, bilgisayar biliminin her alanında birçok farklı boyutta ve biçimde karşımıza çıkar. En önemli uygulama alanlarından biri de aramayı hızlandırmaktır. Örneğin, bilgisayarın dosyaları ada ve boyuta göre sıralar, böylece ihtiyacın olan dosyayı kolayca bulabilirsin. UEFN, objeleri Anahat Düzenleyicisi’nde Türe göre sıralamana, böylece öğeleri gruplandırmana ve projeni organize etmenize olanak sağlar. Fortnite’ta oyuncular, oyun içi puan tablosunda avlamalar ve tur süreleri gibi birçok farklı istatistiğe göre sıralanır, böylece herkes kimin en üstte olduğunu bilir.
Verse koduna sıralama uygulamak, oynanış deneyimini bir üst seviyeye çıkarmana ve gelişimine yeni boyutlar katmana yardımcı olabilir. Örneğin, bir turnuvada her rauntta en az puan alan oyuncuların avlanması için oyuncular dizisini puanlarına göre sıralayabilirsin. Bu diziyi her raundun sonunda sıralayarak en düşük puan alan oyuncuları hızlıca bulabilir ve onları seyirci yapabilirsin. Diğer yandan, en iyi puana sahip oyuncuları da aynı şekilde hızla belirleyip onlara bir sonraki raunt için bonus verebilirsin. Ayrıca bu sıralanmış listeyi, oyuncuların oyun sırasında kimlere dikkat etmeleri gerektiğini bilmeleri için kalıcı yerel sıralamalar oluşturmak için de kullanabilirsin. Dahası, adanda bir listedeki kişilerin adlarını duyurmak istiyorsan kolay görüntüleme için adlarını alfabetik olarak sıralayabilirsin.
Tüm bu örneklerde sıralama farklı şekillerde kullanır ama hepsi de hedeflerine ulaşmak için arka planda bir sıralama algoritmasından yararlanır. Sıralama algoritmaları, listeleri sıralamayı sağlayan mantığı uygular ve ihtiyaçlarına göre seçebileceğin birçok farklı türü vardır. Sıralama güçlü bir araç olsa da onu projelerine entegre etmek istiyorsan nasıl çalıştığını anlaman gerekir. Bu sayfada, sıralamanın ardında yatan temel fikirler ve projen için en iyi algoritmayı nasıl seçeceğin ele alınıyor. Belirli sıralama algoritmalarının uygulamaları için bu sayfanın sonundaki bağlantıyı inceleyebilirsin.
Birleştirme Sıralaması
Birleştirme sıralaması bir böl ve yönet sıralama algoritmasıdır. Bu, sıralanması gereken elemanların daha küçük gruplara bölünmesi ve bu küçük grupların sıralanması anlamına gelir. Ardından bu küçük gruplar, zaten sıralanmış oldukları bilinerek bir araya getirilir.
Birleştirme Sıralamasını Uygulama
Aşağıdaki uygulama, bölünmüş dizileri birleştirme sıralamasını kendisi çağırır, dolayısıyla bu, yinelemeli bir fonksiyondur. Yinelemeli bir fonksiyonun olduğunda, sonsuz yinelemeyi önlemek için bir temel durum belirtmen gerekir. Bu algoritma dizileri her seferinde yarıya böldüğü için temel durum yalnızca bir elemana sahip olan dizidir, dolayısıyla dizi tek elemandan başlayacak şekilde sıralanmış kabul edilir ve başka bir tek elemanlı diziyle birleştirilebilir; bu şekilde tüm elemanları içeren diziye kadar geri dönülebilir.
Aşağıdaki uygulama, parametreleri için parametrik türler kullanan genel bir uygulamadır. Bu, elemanlar ve kendi karşılaştırma fonksiyonun için istediğin türü bağımsız değişken olarak kullanabileceğin anlamına gelir. Böylece bir tamsayı dizisini veya bir sınıf gibi daha karmaşık bir türde bir diziyi sıralayabilirsin. Compare fonksiyonu, kendi özel fonksiyonlarını iletebileceğin bir diğer parametredir. En küçükten en büyüğe veya bir sınıfın belirli alanlarına göre sıralama yapmak istiyorsan bunu, özel fonksiyonunda bu genel fonksiyon uygulamasını değiştirmeden belirtebilirsin.
Verse’te birleştirme sıralamasını uygulamak için şu adımları takip et:
-
Dizide yalnızca bir elemanın olduğu temel durumu yazarak başlayalım. Bir veya daha az eleman varsa fonksiyona iletilen Dizi bağımsız değişkenini döndür.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Dizide birden fazla eleman olduğunu doğrula, değilse temel duruma ulaşmış oluruz. else: # Temel duruma ulaştığımız için iletilen diziyi döndür. Dizi -
Ardından diziyi yarıya böl.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Dizide birden fazla eleman olduğunu doğrula, değilse temel duruma ulaşmış oluruz. Mid:int = Floor(Length / 2) # Dizinin orta dizinini al. Left:[]t = Array.Slice[0, Mid] # Diziyi yarıya böl. Bu, başlangıçtan Orta - 1 dizinine kadar olan elemanları tutar. Right:[]t = Array.Slice[Mid] # Diziyi yarıya böl. Bu, Orta dizinden dizinin sonuna kadar olan elemanları tutar. else: # Temel duruma ulaştığımız için iletilen diziyi döndür. Dizi -
Başlangıç dizisinin her iki yarısı için
MergeSortçağrısı yap ve ardından iki yarıyı birleştirmek içinMergeçağrısı yap.MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Dizide birden fazla eleman olduğunu doğrula, değilse temel duruma ulaşmış oluruz. Mid:int = Floor(Length / 2) # Dizinin orta dizinini al. Left:[]t = Array.Slice[0, Mid] # Diziyi yarıya böl. Bu, başlangıçtan Orta - 1 dizinine kadar olan elemanları tutar. Right:[]t = Array.Slice[Mid] # Diziyi yarıya böl. Bu, Orta dizinden dizinin sonuna kadar olan elemanları tutar. then: # Dizinin sol yarısında MergeSort çağrısı yap. LeftSorted:[]t = MergeSort(Left, Compare) # Dizinin sağ yarısında MergeSort çağrısı yap. RightSorted:[]t = MergeSort(Right, Compare) # İki diziyi birleştir ve sonucu döndür. Merge(LeftSorted, RightSorted, Compare) else: # Temel duruma ulaştığımız için iletilen diziyi döndür. Dizi -
İki yarıyı geri birleştirirken her dizideki elemanları karşılaştır ve her iki dizideki tüm elemanlar eklenene kadar bunları sonuçta elde edilen diziye ekle. Bunu yapmak için her bir dizideki pozisyonları takip edecek bir dizin değişkenin olsun.
Comparefonksiyonu her başarılı olduğunda sol dizi elemanı eklenmeli ve onun dizin değişkeni, dizideki bir sonraki pozisyona ilerletilmeli; aksi takdirde aynı şeyi sağ dizi elemanıyla yap. Dizilerden birindeki tüm elemanlar eklendikten sonra, diğer dizi zaten sıralanmış olduğundan kalan elemanları ekle.# Bölünmüş dizileri Compare (Karşılaştır) fonksiyonuna dayalı bir sırayla birleştiren, MergeSort için bir yardımcı fonksiyon. Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= var LeftIndex:int = 0 var RightIndex:int = 0 var MergedArray:[]t = array{} # Dizilerdeki tüm elemanları MergedArray değişkenine döngü halinde ekle. loop: if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]): # Sol yarı dizideki elemanı sağ yarı dizideki elemanla karşılaştırarak kontrol et. # Bir bağımsız değişken olarak iletilen Compare (Karşılaştır) fonksiyonunu kullanır. if (Compare[LeftElement, RightElement]): set MergedArray += array{LeftElement} set LeftIndex += 1 else: set MergedArray += array{RightElement} set RightIndex += 1 else: # Bu noktada dizilerden birinden tüm elemanları ekledik. # Şimdi birleştirilecek elemanların bulunduğu dizileri kontrol edip kalan elemanların hepsini ekle. if (LeftIndex >= Left.Length): option{set MergedArray += Right.Slice[RightIndex]} else: option{set MergedArray += Left.Slice[LeftIndex]} # Tüm elemanları eklemeyi bitirdiğimiz için döngüden çık. break # Birleştirilmiş diziyi döndür. MergedArray
Tam Kod
# Böl ve yönet mantığıyla çalışan bir sıralama algoritması diziyi ikiye böler, bölünen her diziyi kendi içinde sıralar ve ardından dizileri birleştirir.
# Bu, bölünmüş dizileri birleştirme sıralamasını fonksiyonun kendisinin çağırdığı , yinelemeli bir uygulamadır.
# Temel durum (yinelemeyi durdurma koşulu), dizinin yalnızca bir elemana sahip olmasıdır.
# Bu, parametrik türler kullanan genel bir uygulamadır, dolayısıyla kendi türünü ve kendi karşılaştırma fonksiyonunu bağımsız değişken olarak verebilirsin.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
Length:int = Array.Length
if:
Length > 1 # Dizide birden fazla eleman olduğunu doğrula, değilse temel duruma ulaşmış oluruz.
Mid:int = Floor(Length / 2) # Dizinin orta dizinini al.
Left:[]t = Array.Slice[0, Mid] # Diziyi yarıya böl. Bu, başlangıçtan Orta - 1 dizinine kadar olan elemanları tutar.
Right:[]t = Array.Slice[Mid] # Diziyi yarıya böl. Bu, Orta dizinden dizinin sonuna kadar olan elemanları tutar.
then:
# Dizinin sol yarısında MergeSort çağrısı yap.
LeftSorted:[]t = MergeSort(Left, Compare)
# Dizinin sağ yarısında MergeSort çağrısı yap.
RightSorted:[]t = MergeSort(Right, Compare)
# İki diziyi birleştir ve sonucu döndür.
Merge(LeftSorted, RightSorted, Compare)
else:
# Temel duruma ulaştığımız için iletilen diziyi döndür.
Dizi
# Bölünmüş dizileri Compare (Karşılaştır) fonksiyonuna dayalı bir sırayla birleştiren, MergeSort için bir yardımcı fonksiyon.
Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
var LeftIndex:int = 0
var RightIndex:int = 0
var MergedArray:[]t = array{}
# Dizilerdeki tüm elemanları MergedArray değişkenine döngü halinde ekle.
loop:
if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
# Sol yarı dizideki elemanı sağ yarı dizideki elemanla karşılaştırarak kontrol et.
# Bir bağımsız değişken olarak iletilen Compare (Karşılaştır) fonksiyonunu kullanır.
if (Compare[LeftElement, RightElement]):
set MergedArray += array{LeftElement}
set LeftIndex += 1
else:
set MergedArray += array{RightElement}
set RightIndex += 1
else:
# Bu noktada dizilerden birinden tüm elemanları ekledik.
# Şimdi birleştirilecek elemanların bulunduğu dizileri kontrol edip kalan elemanların hepsini ekle.
if (LeftIndex >= Left.Length):
option{set MergedArray += Right.Slice[RightIndex]}
else:
option{set MergedArray += Left.Slice[LeftIndex]}
# Tüm elemanları eklemeyi bitirdiğimiz için döngüden çık.
break
# Birleştirilmiş diziyi döndür.
MergedArray
Bir Algoritma Seçme
Birçok sıralama algoritması benzer bir mantığa sahip olmakla birlikte, onları birbirinden ayıran ve algoritmanın performansı üzerinde büyük etkisi olabilecek birkaç şey vardır.
Zaman Karmaşıklığı
Algoritmalar zaman alır ve yapmaları gereken şey ne kadar çoksa uygulanmaları o kadar uzun sürer. Algoritmanın çözmeye çalıştığı problemin karmaşıklığını etkileyen bir dizi faktör vardır ve bu problemi çözmek için gereken zamana zaman karmaşıklığı denir.
Bir algoritmanın tamamlanması için gereken kesin zaman miktarını hesaplamak, bilgisayarının donanımı, çalışan diğer kodlar veya üzerinde çalıştığın veri türü gibi çeşitli faktörler nedeniyle neredeyse imkânsız olduğundan, zaman karmaşıklığı bunun yerine işlemlerle veya bir algoritmanın tamamlanması için gerçekleştirmesi gereken eylem sayısıyla ölçülür. Her algoritma farklı olduğundan, bir veri setini işlemenin aldığı süre büyük O gösterimi kullanılarak belirtilir. Büyük O gösterimi gereken tam işlem sayısını tanımlamaz; bunun yerine, algoritmaya girdiğin listenin boyutu arttıkça bu sayının nasıl değiştiğini tanımlar.
Örneğin, bir listedeki en küçük sayıyı bulan bir algoritma yazdığını varsayalım. Listenin sıralı olup olmadığını bilmediğin için algoritman, en küçük sayı olup olmadığını anlamak için her sayıyı kontrol etmek zorundadır. Listede üç öğe varsa algoritman üç kontrol yapar; listede on öğe varsa algoritman on kontrol yapar. İşlem sayısı, listenin girdi boyutuyla doğrusal olarak arttığından, zaman karmaşıklığı doğrusaldır veya başka bir ifadeyle, n listendeki öğe sayısı olmak üzere O(n) şeklindedir. Algoritman öğe başına iki işlem yapmak zorunda olsaydı, örneğin her kontrolün ardından her öğeyi farklı bir listeye kopyalamak zorunda olsaydı işlem sayısı 2 * NumberOfItems (Öğe Sayısı) olduğundan zaman karmaşıklığı O(2n) olacaktı.
Peki, ya algoritman sadece listede hiç öğe olup olmadığını kontrol etmek istiyorsa? Algoritman girdi boyutundan bağımsız olarak yalnızca bir işlem yaptığı için zaman karmaşıklığı sabit veya O(1) olacaktır. İkinci dereceden zaman (O(n^2)) veya faktöriyel zaman (O(n!)) gibi daha birçok örnek var ama önemli olan her birinin, gerçekleştirilen işlem sayısının girdi boyutuyla nasıl arttığını tanımlamasıdır.
Sıralamada Karmaşıklık
Sıralama algoritmaların zaman karmaşıklığını ölçmesi, listenin sıralamadan önce içinde bulunabileceği farklı durumlar nedeniyle çok daha karmaşık hale gelir. Ya liste önceden sıralanmış durumdaysa? Peki ya ters sıralanmış durumdaysa? Bir sıralama algoritmasının performansı bu faktörlere bağlı olarak önemli ölçüde değişebilir, bu nedenle sıralama algoritmaları genellikle en iyi, en kötü ve ortalama durumdaki zaman karmaşıklıklarına göre ölçülür.
Örnek olarak kabarcık sıralama algoritmasına bakalım. En iyi durumda, zaten sıralanmış bir liste belirtildiyse kabarcık sıralamasının yalnızca her eleman çiftini kontrol etmesi gerekir ancak değiştirme yapmasına gerek kalmaz! Bu, en iyi durumda zaman karmaşıklığının O(n) olacağı anlamına gelir ki bu çok iyidir! Peki ya tam tersi senaryoda, yani liste geriye doğru sıralandıysa ne olacak? Bu durumda, kabarcık sıralaması n _sayıda kontrol yapmak ve listedeki her elemanı _n kez değiştirmek zorunda kalacaktır; bu da en kötü durum zaman karmaşıklığının n * n veya O(n^2) olacağı anlamına gelir. Bu, diğer sıralama algoritmalarına kıyasla yavaş kabul edilir ve hızla kontrolden çıkabilir çünkü algoritmanın on elemandan oluşan bir listeyi işlemesi için en az yüz işlem gerekir. Yüz tane elemanın kaç işlem gerektirdiğini düşünebiliyor musun? Peki ya bin eleman?
En iyi ve en kötü durum yerine, sıralama algoritmaları genellikle ortalama duruma daha yakın bir performans sergiler. Örneğin, birleştirme sıralamasının ortalama durum karmaşıklığı O(nlogn) şeklindedir. Bu, görece iyi olarak kabul edilir çünkü diğer birçok yaygın sıralama algoritmasının en iyi, en kötü ve ortalama durum karmaşıklığı bu seviyede veya bu seviyeye çok yakındır. Yukarıdaki kabarcık sıralamasının ortalama durum karmaşıklığı O(n^2)’dir, bu nedenle ortalama durumda bile görece yavaştır.
Algoritma seçerken zaman karmaşıklığını bilmek önemlidir çünkü kodunun hızlı çalışmasını ve girdi türünden bağımsız olarak benzer şekilde performans göstermesini istersin. Yaygın olarak kullanılan verimli sıralama algoritmalarına bazı örnekler için Birleştirme Sıralaması ve Hızlı Sıralama sayfalarına bakabilirsin. Her iki algoritmanın da en iyi, en kötü ve ortalama durum karmaşıklıkları O(nlogn) şeklindedir ve bu, herhangi bir sıralama durumu için iyi bir başlangıç noktasıdır.
Uzay Karmaşıklığı
Zaman karmaşıklığının yanı sıra, algoritmanın sıralamayı tamamlamak için ne kadar şey oluşturması gerektiği de hesaba katılmalıdır. Bu, algoritmanı çalıştırırken oluşturulan uzay karmaşıklığı veya ekstra veri miktarıdır. Zaman karmaşıklığı gibi uzay karmaşıklığı da algoritmalar arasında değişir ve Büyük O gösterimiyle ölçülür. Örneğin birleştirme sıralaması, bir listeyi n alt listeye böldüğü için O(n) değerinde bir uzay karmaşıklığına sahiptir. Objeleri yerinde sıralayan (yani yeni veriler oluşturmak yerine yalnızca mevcut verileri değiştiren) algoritmalar O(1) uzay karmaşıklığına sahiptir. Çok büyük listelerle çalışıyorsan algoritma seçerken alan karmaşıklığına dikkat etmen gerekebilir.
Verse bir işlevsel programlama dili olduğundan veri yapısı API işlemleri, girdi olarak iletilen orijinal öğenin değiştirilmiş sürümlerini döndürür. Örneğin, hem Insert() hem de RemoveElement() dizi fonksiyonları orijinal diziyi değiştirmez; bunun yerine, fonksiyon yürütüldükten sonra yeni bir dizi oluşturur ve döndürür. Bu durum, yeni elemanların oluşturulması için daha fazla zaman ve uzay karmaşıklığı gereksinimlerine yol açabilir.
Kararlılık
Sıralama yaparken algoritman sıklıkla çelişkilerle karşılaşacaktır. Örneğin, ikisi de beş puana sahip iki oyuncu verildiğinde algoritma onları nasıl sıralamalıdır? Bu senaryoda, bir kararlı algoritma sıralamadan sonra listede eşit elemanların görünme sırasını koruyacaktır. Yani sıralama yapılmadan önce listede birinci oyuncu ikinci oyuncudan önceyse sıralanmış listede yine birinci oyuncu ikinci oyuncudan önce yer alacaktır.
Ancak bir kararsız algoritma bu sırayı koruyamaz, yani ikinci oyuncu birinci oyuncudan önce görünebilir. Bu, kodunun bir listedeki ilk birkaç elemanı ele aldığı durumlarda, örneğin puana göre ilk üç oyuncunun sıralamada görüntülenmesini istiyorsan önemlidir. Böyle bir durumda, o puanı ilk elde eden oyuncunun sıralamada kalmasını sağlayacak kararlı bir algoritmaya ihtiyacın vardır.
Algoritmalarını Test Etme ve Profil Oluşturma
Algoritmanın zaman ve uzay karmaşıklığına bakarak nasıl çalışmasının bekleneceğini bilmek yararlı olsa da, algoritmanın gerçek girdiler üzerinde nasıl performans gösterdiğini ölçmek daha da önemlidir. Sıralama algoritmaları geliştirmek ve kodunun tüm girdiler üzerinde tutarlı bir şekilde çalışıp çalışmadığını belirlemek zor olabilir. İşte test burada gereklidir. Geliştirme sırasında bir test fonksiyonu oluşturarak kodunun doğruluğunu ölçebilir ve nasıl davrandığını belirleyebilirsin. Test ettiğin algoritmanın uygulamasını değiştirdiğinde performansta herhangi bir gerileme olup olmadığını da görebilirsin. Sıralama algoritmaların için bir test dosyası oluşturmak ve performansları hakkında veri çıktısı almak için şu adımları takip et:
-
RunArrayTestadında bir başarısız olabilir fonksiyon oluştur.# Dizileri sıralamak ve kodun profilini oluşturmak için test fonksiyonu. RunArrayTest()<decides><transacts>:void= -
Sıralamayı çalıştırmak istediğin dizi için bağımsız değişkeni ve kullanılacak karşılaştırma fonksiyonunu ekle.
# Dizileri sıralamak ve kodun profilini oluşturmak için test fonksiyonu. RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # Birleştirme sıralaması gerçekleştir ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) -
Şimdi sıralanmış diziyi beklenen sonuçla karşılaştırman gerekiyor. Sonucun doğru olduğunu doğrulamak için beklenen diziye yönelik bağımsız değişkeni sıralanmış gerçek diziyle karşılaştır.
ResultArrayiçindeki elemanlarıExpectedArrayiçindeki elemanlarla karşılaştır.RunArrayTestbaşarısız olabilir bir fonksiyondur, yani bir eleman eşleşmediğinde test fonksiyonu başarısız olur.# Dizileri sıralamak ve kodun profilini oluşturmak için test fonksiyonu. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # Birleştirme sıralaması gerçekleştir ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Testin başarılı olduğunu ve dizinin beklendiği gibi sıralandığını doğrula. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
Test başarısız olursa dizileri karşılaştırabilmen ve test ettiğin kodu nasıl düzelteceğini anlayabilmen için her adımda dizileri yazdıracak bir bağımsız değişken fonksiyonu ekle.
# Dizileri sıralamak ve kodun profilini oluşturmak için test fonksiyonu. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void= # Birleştirme sıralaması gerçekleştir ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Sorun giderme için Gerçek, Beklenen ve Sonuç dizilerini yazdır. ProjectLog("Gerçek: {ArrayToString(ActualArray)}") ProjectLog("Beklenen: {ArrayToString(ExpectedArray)}") ProjectLog("Sonuç: {ArrayToString(ResultArray)}") # Testin başarılı olduğunu ve dizinin beklendiği gibi sıralandığını doğrula. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
Test fonksiyonun, sonucun doğruluğunu kontrol eder ancak testten daha fazla da bilgi alabilirsin. Profil ifadesini kullanarak, algoritmanın tamamlanması için gereken süreyi günlüğe kaydedip algoritmalarının performansını ölçebilirsin.
Profil ifadesi, farklı sıralama algoritmalarının performansını karşılaştırmak veya algoritmalarınızın farklı girdiler verildiğinde nasıl çalıştığını test etmek istiyorsan yararlıdır. Ayrı algoritmalar, en iyi ve en kötü durum girdileri verildiğinde çok farklı performans gösterebilir ve profil oluşturma, neye dikkat etmen gerektiğini bilmek için bu durumları ortaya çıkarıp test etmene olanak sağlar. Birden fazla test yaparak algoritmanın ortalama performansını ölçebilir ve verili herhangi bir büyüklükteki girdiler üzerinde nasıl performans göstereceğini tahmin edebilirsin.
-
Testin neye odaklandığını açıklayan
Descriptionadında bir dize bağımsız değişkeni ekle. Bunu, açıklamayı zamanlanmış değerle günlüğe kaydetmek üzereprofileifadesine ekleyebilirsin.# Dizileri sıralamak ve kodun profilini oluşturmak için test fonksiyonu. RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void= # Birleştirme sıralaması gerçekleştir ve kodun profilini oluştur. ResultArray := profile(Description): SortingAlgorithms.MergeSort(ActualArray, Compare) # Sorun giderme için Gerçek, Beklenen ve Sonuç dizilerini yazdır. ProjectLog("Gerçek: {ArrayToString(ActualArray)}") ProjectLog("Beklenen: {ArrayToString(ExpectedArray)}") ProjectLog("Sonuç: {ArrayToString(ResultArray)}") # Testin başarılı olduğunu ve dizinin beklendiği gibi sıralandığını doğrula. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected
Test Durumları Yazma
Basitten yola çık. Test ettiğin şeyi yalıt. Bir tamsayı dizisini en küçük değerden en büyük değere doğru sıralamayı test et.
-
Tamsayılar için bir karşılaştırma fonksiyonu oluştur.
# Tamsayıları en küçükten en büyüğe sıralamak için bağımsız değişken olarak kullanılacak karşılaştırma fonksiyonu. IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int= Left < Right -
Bir tamsayı dizisini dizeye dönüştüren bir yardımcı fonksiyon oluştur.
# Tamsayı dizisini dizeye dönüştüren bir yardımcı fonksiyon. IntArrayToString(Array:[]int)<transacts>:string= var ConvertedToString:string = "[" for (Index -> Element : Array): set ConvertedToString += "{Element}" if (Index < Array.Length - 1): set ConvertedToString += ", " set ConvertedToString += "]" -
Testi yürütmek için bir Verse cihazı oluştur.
# Bu dosya, sıralama algoritmasının beklendiği gibi davrandığını doğrulamaya yönelik testler içerir. # Testler ayrıca algoritmanın performansını görmek için kodun profilinin oluşturulmasını da kapsar. using { /Fortnite.com/Devices } using { /UnrealEngine.com/Temporary/Diagnostics } using { /Verse.org/Simulation } using { /Verse.org/Random } my_log_channel<public> := class(log_channel): # Günlüğe sahip bir sınıfta olmayan fonksiyonlardan gelen mesajları yazdırmak için proje genelinde bir “Kaydedici”. # Günlük oluşturucu olmayan Print fonksiyonu <no_rollback> şeklindedir, bu nedenle bir <transacts> fonksiyonunda kullanılamaz. ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void= Logger := log{Channel := my_log_channel} Logger.Print(Message, ?Level := Level) # Bir bölüme yerleştirilebilen, Verse ile yazılmış bir Kreatif cihazı. # Testleri ve profil kodunu çalıştırmak için bölüme yerleştir. test_sorting := class(creative_device): # Cihaz, çalışmakta olan bir oyunda başlatıldığında çalışır OnBegin<override>()<suspends>:void= # Test için kullanılacak örnek diziler. Test1ExpectedIntArray:[]int = array{} Test1ActualIntArray:[]int = array{} # Testleri yürüt ve başarısız mı yoksa başarılı mı olduklarını bildir. if: RunArrayTest["Integer array in order from smallest to largest", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString] then: ProjectLog("Tüm testler başarılı.") else: ProjectLog("Bir veya daha fazla test başarısız.") -
Şimdi test dizilerini değerlerle doldur.
var ArrayLength:int = GetRandomInt(10, 100) Test1ExpectedIntArray:[]int = for (Count := 0..ArrayLength): Sayı Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray) -
Verse cihazını bölümüne sürükleyerek testi çalıştır.
Yürütebileceğin testlerle ilgili aşağıdaki fikirlerden de yararlanabilirsin:
* Bir tamsayı dizisini büyükten küçüğe doğru sırala.
# Tamsayıları en büyükten en küçüğe sıralamak için bağımsız değişken olarak kullanılacak karşılaştırma fonksiyonu.
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
* Tekrarlanan değerler içeren bir tamsayı dizisini sırala.
Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)
* Bir sınıfı alanlarından birine göre sırala.
# Sıralamayı test etmek için bir örnek sınıf.
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# Galibiyetleri küçükten büyüğe doğru sıralamak için bağımsız değişken olarak kullanılacak karşılaştırma fonksiyonu.
IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins < Right.Wins
Sol
# Oyuncu istatistikleri karşılaştırma değerlerini dizeye dönüştüren bir yardımcı fonksiyon.
PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element.Wins}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
Tam Kod
# Bu dosya, sıralama algoritmasının beklendiği gibi davrandığını doğrulamaya yönelik testler içerir.
# Testler ayrıca algoritmanın performansını görmek için kodun profilinin oluşturulmasını da kapsar.
using { /Fortnite.com/Devices }
using { /UnrealEngine.com/Temporary/Diagnostics }
using { /Verse.org/Simulation }
using { /Verse.org/Random }
my_log_channel<public> := class(log_channel):
# Günlüğe sahip bir sınıfta olmayan fonksiyonlardan gelen mesajları yazdırmak için proje genelinde bir “Kaydedici”.
# Günlük oluşturucu olmayan Print fonksiyonu <no_rollback> şeklindedir, bu nedenle bir <transacts> fonksiyonunda kullanılamaz.
ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
Logger := log{Channel := my_log_channel}
Logger.Print(Message, ?Level := Level)
# Bir bölüme yerleştirilebilen, Verse ile yazılmış bir Kreatif cihazı.
# Testleri ve profil kodunu çalıştırmak için bölüme yerleştir.
test_sorting := class(creative_device):
# Cihaz, çalışmakta olan bir oyunda başlatıldığında çalışır
OnBegin<override>()<suspends>:void=
# Test için kullanılacak örnek diziler.
var ArrayLength:int = GetRandomInt(10, 100)
Test1ExpectedIntArray:[]int =
for (Count := 0..ArrayLength):
Sayı
Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)
set ArrayLength = GetRandomInt(10, 100)
Test2ExpectedIntArray:[]int = for (Count := 0..ArrayLength):
ArrayLength - Count
Test2ActualIntArray:[]int = Shuffle(Test2ExpectedIntArray)
Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)
set ArrayLength = GetRandomInt(10, 100)
Test4ExpectedPlayerStats:[]player_stats = for (Count := 0..ArrayLength):
player_stats:
Wins := ArrayLength - Count
RoundsPlayed := GetRandomInt(Count, Count * 30)
Test4ActualPlayerStats:[]player_stats = Shuffle(Test4ExpectedPlayerStats)
# Testleri yürüt ve başarısız mı yoksa başarılı mı olduklarını bildir.
if:
RunArrayTest["Integer array in order from smallest to largest", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["Integer array in order from largest to smallest", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString]
RunArrayTest["Integer array in order from smallest to largest with repeats", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["Player stats array in order from largest # wins to smallest", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString]
then:
ProjectLog("Tüm testler başarılı.")
else:
ProjectLog("Bir veya daha fazla test başarısız.")
# Dizileri sıralamak ve kodun profilini oluşturmak için test fonksiyonu.
RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=
# Birleştirme sıralaması gerçekleştir ve kodun profilini oluştur.
ResultArray := profile(Description):
SortingAlgorithms.MergeSort(ActualArray, Compare)
# Sorun giderme için Gerçek, Beklenen ve Sonuç dizilerini yazdır.
ProjectLog("Gerçek: {ArrayToString(ActualArray)}")
ProjectLog("Beklenen: {ArrayToString(ExpectedArray)}")
ProjectLog("Sonuç: {ArrayToString(ResultArray)}")
# Testin başarılı olduğunu ve dizinin beklendiği gibi sıralandığını doğrula.
for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
Result = Expected
# Tamsayı dizisini dizeye dönüştüren bir yardımcı fonksiyon.
IntArrayToString(Array:[]int)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
# Oyuncu istatistikleri karşılaştırma değerlerini dizeye dönüştüren bir yardımcı fonksiyon.
PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element.Wins}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
# Tamsayıları en küçükten en büyüğe sıralamak için bağımsız değişken olarak kullanılacak karşılaştırma fonksiyonu.
IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
Left < Right
# Tamsayıları en büyükten en küçüğe sıralamak için bağımsız değişken olarak kullanılacak karşılaştırma fonksiyonu.
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
# Sıralamayı test etmek için bir örnek sınıf.
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# Galibiyetleri küçükten büyüğe doğru sıralamak için bağımsız değişken olarak kullanılacak karşılaştırma fonksiyonu.
IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins < Right.Wins
Sol
# Galibiyetleri büyükten küçüğe doğru sıralamak için bağımsız değişken olarak kullanılacak karşılaştırma fonksiyonu.
IsWinsGreaterThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins > Right.Wins
Sol
Kendi Kendine Yapabileceklerin
-
Farklı bir sıralama algoritması uygula. Başka algoritma uygulamalarını aşağıda bulabilirsin:
-
Test kodunun kapsamını genişletmek için daha fazla test durumu ekle. Test kodunun şu anda kapsamadığı uç durumlar neler olabilir? Peki ya daha karmaşık veri türleri?