Bir kod parçasının zaman karmaşıklığını ölçmek, yürütme süresi açısından maliyetlerini tahmin ederek algoritmaları ve diğer işlev türlerini optimize etmek için kullanılan yaygın bir tekniktir.
Bununla birlikte, bir kod bloğunun kaç saniye sürdüğü konusunda kesin bir ölçüm yapmak yerine, zaman karmaşıklığı, girdi sayısının bir işlevin yapması gereken iş miktarını nasıl etkilediğinin sorusunu yanıtlamayı amaçlar – ve en sık anlatılan Bir algoritma ile giriş sayısı arasındaki ilişkiyi matematiksel bir fonksiyon olarak ifade etmemizi sağlayan “Big O notasyonu” kullanarak .
Örnek olarak, bir takvim uygulaması üzerinde çalıştığımızı ve temel Calendar
modelimizin belirli bir kullanıcının takviminde görünen tüm etkinliklerin bir dizisini içerdiğini varsayalım. Bu modeli, ilk etkinliğinin şu anda belirli bir tarihten sonra planlanıp programlanmadığını kontrol etmek için uygun bir API ile genişlettik:
struct Calendar {
var events: [Event]
}
extension Calendar {
func isFirstEvent(scheduledAfter date: Date) -> Bool {
guard let firstEvent = events.first else {
return false
}
return firstEvent.date > date
}
}
Yukarıdaki işlevin sürekli zaman karmaşıklığı vardır – O(1)
– yürütme süresi, çalıştırıldığı takvimdeki olayların sayısından etkilenmez. O yana sadece ilk olay bakar takvim 10, 1000 veya 10.000 olayların toplam içeriyorsa, o önemli değil – bizim yukarıdaki fonksiyon gerçekleştirmek zorundadır iş miktarını sabit kalır.
Şimdi diyelim ki, sadece ilk olaya bakmak yerine , belirli bir tarihten sonra planlanan tüm olayları, dizimizi filtreleyerek yapılabilecek – geri dönmek istediğimizi diyelim events
:
extension Calendar {
func events(scheduledAfter date: Date) -> [Event] {
return events.filter { event in
event.date > date
}
}
}
Yukarıdaki filter
işlem, events
dizideki her öğe boyunca yinelememizi gerektirdiğinden , zamanın karmaşıklığına sahiptir O(N)
– burada N
işlevimizin üzerinde çalışacağı olayların sayısını ifade eder. İşlev, giriş sayısıyla bire bir ilişki kurduğundan (2 olay 2 yineleme, 10 olay 10 yineleme vb. Gerektirir), zaman karmaşıklığı doğrusaldır .
Bir işlevin, O(N)
en kötü durum senaryosunun tüm girişlerini yinelemeyi gerektirdiği sürece (her zaman gerekli olmasa bile) doğrusal veya zaman karmaşıklığına sahip olduğu kabul edilir . Örneğin, aşağıdaki işlev bir eşleşme bulur bulmaz yinelemeyi durdurur – ancak O(N)
eşleşen öğe sonuncusu olabileceğinden hala karmaşıklığa sahip olduğu düşünülür :
extension Calendar {
func firstEvent(scheduledAfter date: Date) -> Event? {
return events.first(where: { event in
event.date > date
})
}
}
Bir işlevin zaman karmaşıklığı aynı zamanda çoklu değişkenlere de bağlı olabilir. Örneğin, burada yine tüm olayları ( O(N)
) yineliyoruz , ancak her yinelemenin bir parçası olarak bir dizi kullanıcı üzerinde de yineliyoruz (ayrıca O(N)
):
extension Calendar {
func events(createdByAnyOf users: [User]) -> [Event] {
return events.filter { event in
users.contains(event.creator)
}
}
}
Yukarıdaki fonksiyonun toplam süresi karmaşıklığı nedenle olacak number of events * number of users
kadar büyük o gösterimi kullanılarak tarif edilebilir, O(N * M)
burada – N
olayların sayısı ve M
kullanıcı sayısıdır.
Bir koleksiyon içindeki tüm unsurları yinelemek zorunda kalmak bazen kaçınılmazdır (bu durumda olduğu gibi), iç içe geçmiş yinelemelerle uğraşırken, genellikle bulunacak bir miktar optimizasyon vardır.
Bu durumda, aslında yukarıdaki fonksiyon saf verebilir O(N)
Our ileterek karmaşıklığı users
bir şekilde Set
yerine bir şeklinin dışında, Array
. Setleri onlar (sabit belirli bir değer içerip içermediğine bakabilirsiniz yana O(1)
) zaman – biz ile bitirmek istiyorum O(N * 1)
basitçe veya O(N)
bu uygulaması ile toplam karmaşıklığı içinde,:
extension Calendar {
// The only change compared to the previous code sample is that
// users is now passed as Set<User>, rather than [User].
func events(createdByAnyOf users: Set<User>) -> [Event] {
return events.filter { event in
users.contains(event.creator)
}
}
}
İç içe geçmiş yinelemeler söz konusu olduğunda, özellikle dikkat edilmesi gereken, aynı girdi kümesinin iki kez yinelenmesidir – çünkü bize ikinci dereceden zaman karmaşıklığı verir, veya O(N²)
. İşte bir başka olayla aynı tarihte planlanan tüm olayları başka bir olayla – events
diziyi ( O(N)
) filtreleyerek ve daha sonra contains
her yinelemenin içinde aynı diziyi çağırarak bulan bir işleve örnek O(N)
:
extension Calendar {
func conflictingEvents() -> [Event] {
return events.filter { event in
events.contains(where: { otherEvent in
guard event.id != otherEvent.id else {
return false
}
return event.date == otherEvent.date
})
}
}
}
Belirli bir işlev ikinci dereceden zaman karmaşıklığına ulaştığında, özellikle önemli sayıda girdiyle çalışması gerekme olasılığı varsa, bir tür performans darboğazına dönüşme olasılığı oldukça yüksektir.
Neyse ki, bu durumda, bir kez daha yapılabilecek bir optimizasyon var. events
Her yinelemenin bir parçası olarak dizimizin tamamını tekrarlamak yerine, her bir tarih için olay sayısını tanımlamak için tek bir geçiş yaparak başlayalım – ve sonra filtrelemede bu sayım koleksiyonunu kullanalım – şunun gibi:
extension Calendar {
func conflictingEvents() -> [Event] {
var eventCountsForDates = [Date : Int]()
for event in events {
eventCountsForDates[event.date, default: 0] += 1
}
return events.filter { event in
eventCountsForDates[event.date, default: 0] > 1
}
}
}
Yeni uygulamalarımızda hala iki yineleme gerçekleştirirken, bu yinelemeler tamamen birbirinden ayrılıyor – bize O(2N)
değil, bir karmaşıklık veriyor O(N²)
. Takvimlerinde 1000 etkinlik olan bir kullanıcı için bu, şu anda 1.000.000 yerine yalnızca 2.000 yineleme yaptığımız anlamına geliyor – bu oldukça büyük bir gelişme!
GIPHY App Key not set. Please check settings