Zaman Karmaşıklığı | Swift

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 Calendarmodelimizin 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 filterişlem, eventsdizideki her öğe boyunca yinelememizi gerektirdiğinden , zamanın karmaşıklığına sahiptir O(N)– burada Niş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 userskadar büyük o gösterimi kullanılarak tarif edilebilir, O(N * M)burada – Nolayların sayısı ve Mkullanı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ığı usersbir şekilde Setyerine 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 – eventsdiziyi ( O(N)) filtreleyerek ve daha sonra containsher 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. eventsHer 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!