Swift’de doğru veri yapısını seçmek

Belirli bir veri koleksiyonunu temsil etmek için hangi veri yapısının kullanılacağına karar vermek, göründüğünden daha zor olabilir. Her tür veri yapısı, belirli sayıda kullanım durumu için optimize edildiğinden, her veri kümesi için doğru eşleşmeyi bulmak, kodumuzun ne kadar verimli hale geldiği konusunda genellikle büyük bir etkiye sahip olabilir.

Üç ana veri yapıları ile Swift standart kütüphane gemileri – Array, Dictionaryve Set– her optimizasyonlar, artılarını ve eksilerini farklı bir dizi ile geliyor. Bu hafta, bu özelliklerin bazılarına ve ayrıca ihtiyaçlarımız için doğru veri yapısını bulmak için bazen standart kütüphanenin dışına çıkmamız gerektiğine bir göz atalım.

Dizilerin doğrusallığı

Arraytartışmasız Swift’de en sık kullanılan veri yapılarından biri ve iyi nedenlerden biri. Öğelerini sırayla tutar, öngörülebilir bir şekilde yineleme yapmak kolaydır ve yapılardan, sınıf örneklerine ve diğer koleksiyonlara kadar her türlü değeri depolayabilir.

Örneğin, burada Canvasbir çizim uygulamasının içine yerleştirilmiş bir şekiller koleksiyonu depolamak için bir dizi kullanıyoruz . Daha sonra, tuvalimizi bir görüntüye dönüştürmemiz istendiğinde, her öğeyi a DrawingContext– like kullanarak çizmek için dizimizde yinelemeliyiz :

struct Canvas {
    var shapes: [Shape]

    func render() -> Image {
        let context = DrawingContext()
        shapes.forEach(context.draw)
        return context.makeImage()
    }
}

Tüm şekillerimizi doğrusal olarak çizmeye gelince, yukarıda yaptığımız gibi, bir dizi kullanmak mükemmel bir seçimdir. Diziler, elemanlarını yalnızca çok verimli bir şekilde depolamakla kalmaz, ayrıca ek bir iş yapmadan bize öngörülebilir bir çizim düzeni sağlayan garantili bir yineleme sırasına sahiptir.

Bununla birlikte, diğer tüm veri yapıları gibi, dizilerin de dezavantajları vardır. Bizim durumumuzda, şekilleri tuvalimizden kaldırmaya başlamak istediğimizde böyle bir olumsuzlukla karşılaşmaya başlayacağız . Dizi öğeleri dizine göre depolandığından, kaldırmadan önce belirli bir şeklin hangi dizinle ilişkili olduğunu bulmamız gerekir:

extension Canvas {
    mutating func remove(_ shape: Shape) {
        guard let index = shapes.firstIndex(of: shape) else {
            return
        }

        shapes.remove(at: index)
    }
}

İlk başta, yukarıdaki kod problemli görünmeyebilir, ancak çok sayıda şekil içeren herhangi bir tuval için performans darboğazına dönüşme olasılığı çok yüksektir – çünkü zaman karmaşıklığı açısından firstIndexdoğrusaldır ( O(N)) .

Biz ise olabilir bizim kullanıyoruz yerde bu tip bir kısıtlama geçici Canvastürü – örneğin daima doğrusu değeri veya kimliğe göre değil, dizine göre şekillere bakarak – Bunu yaparken, bizim kod daha karmaşık ve daha kırılgan hem kılacak beri, daima ediyorum Çalıştığımız tuval değiştiğinde dizinlerimizin eski olmayacağından emin olmanız gerekir.

Kümelerin hızı

Bunun yerine, Canvastemel veri yapısını değiştirerek kendini optimize edip edemeyeceğimize bakalım . Yukarıdaki soruna baktığımızda, ilk fikirlerimizden biri Setyerine kullanmak olabilir Array. “Swift’deki setlerin gücü” nde göz attığımız gibi , setlerin dizilere göre en büyük avantajlarından biri, O(1)üyelerin karma değerine göre depolanmaları nedeniyle hem kesici uçların hem de sökmelerin her zaman sabit ( ) sürede gerçekleştirilebilmesidir. Dizine göre değil.

CanvasBir kümeyi kullanmak için güncelleme yapmak, şöyle görünmesini sağlar:

struct Canvas {
    var shapes: Set<Shape>

    func render() -> Image {
        let context = DrawingContext()
        shapes.forEach(context.draw)
        return context.makeImage()
    }

    mutating func remove(_ shape: Shape) {
        shapes.remove(shape)
    }
}

Yine, yukarıdaki kod doğru görünebilir ve hatta bir aksama olmadan derler. Bununla birlikte, kaldırma sorunumuzu çözerken, kararlı çizim siparişimizi de kaybettik – dizilerden farklı olarak setler bize garantili bir yineleme emri vermez – ki bu durumda başladığımız gibi kullanıcının şekillerini rastgele bir sırayla çizerek.

Endeksleme indeksleri

Denemeye devam edelim. Sonra, optimize edebilirsiniz bakalım Canvasbir tanıtarak Dictionarybize kendi kimliği temel alarak herhangi şeklin indeks aramak sağlayan o. shapesYeni bir addyöntem kullanarak elementlerin nasıl eklendiğini kontrol edebilmek için özel dizimizi oluşturarak başlayacağız – ve her yeni şekil eklendiğinde dizinini sözlüğümüze ekledik:

struct Canvas {
    private var shapes = [Shape]()
    private var indexes = [Shape.ID : Int]()

    func render() -> Image {
        let context = DrawingContext()
        shapes.forEach(context.draw)
        return context.makeImage()
    }

    mutating func add(_ shape: Shape) {
        let index = shapes.count
        indexes[shape.id] = index
        shapes.append(shape)
    }
}

Artık belirli bir şeklin hangi dizinde depolandığını her zaman bildiğimiz için, bir küme kullanırken olduğu gibi, sabit zamanda hızlıca kaldırma işlemleri gerçekleştirebiliriz:

extension Canvas {
    mutating func remove(_ shape: Shape) {
        guard let index = indexes[shape.id] else {
            return
        }

        shapes.remove(at: index)
        indexes[shape.id] = nil
    }
}

Ancak, yeni Canvasuygulamamızın oldukça ciddi bir hatası var. Bir şekli her kaldırışımızda, aslında yeni kaldırdığımızdan daha yüksek olan tüm dizinleri geçersiz kılıyoruz – çünkü bu öğelerin her biri dizinin başlangıcına doğru bir adım ilerleyecektir. Biz ise olabilir tekrar bize geri koymak istiyorum her kaldırıldıktan sonra bu endeksler, ayarlayarak söz konusu sorunu çözmek O(N)çok başlamadan beri önlemek için çalıştığım şey olan toprakları.

Son uygulamamız olsa da yararları var. Genel olarak, iki veri yapısının bir kombinasyonunu kullanmak, bu gibi durumlarda harika bir fikir olabilir – çünkü diğerlerinin zayıf yönlerini telafi etmek için bir veri yapısının güçlü yönlerini sık sık kullanabiliyoruz ve bunun tersi de geçerlidir.

Öyleyse başka bir kombinasyonla tekrar deneyelim, ancak bu sefer gerçek gereksinimlerimizi gözden geçirerek başlayalım :

• Sürekli zaman karmaşıklığına sahip olmak için hem ekleme hem de çıkarma işlemlerine ihtiyacımız var ve temel dizini bilmeden bir şekli çıkarmak mümkün olmalı.
• Sabit bir çizim sırasını korumak için garantili bir yineleme sırasına ihtiyacımız var.

Yukarıdaki şartlara baktığımızda, istikrarlı bir yineleme düzenine ihtiyaç duyarken, aslında endekslere ihtiyacımız olmadığı ortaya çıktı – bu da bağlantılı bir listeyi kullanım durumumuz için mükemmel bir seçim haline getirecek .

Bağlantılı listeler, her düğümün listedeki bir sonraki düğüme bir referans (veya bağlantı ) içerdiği , yani bir öğe kaldırıldığında herhangi bir dizin güncellemesi gerektirmeden yinelenebileceği anlamına gelen düğümlerden oluşur . Bununla birlikte, Swift standart kütüphanesi (henüz) bağlantılı bir liste türü içermez, bu yüzden bir tane kullanmak istiyorsak – önce onu yapmamız gerekir.

Bağlantılı bir liste oluşturmak

ListListemizdeki ilk ve son düğümleri takip edecek bir yapı ilan ederek başlayalım . Veri tutarlılığını sağlamak için bu özelliklerin her ikisini de türümüz dışında salt okunur hale getireceğiz:

struct List<Value> {
    private(set) var firstNode: Node?
    private(set) var lastNode: Node?
}

Ardından, Nodebir sınıf oluşturacağımız türümüzü oluşturalım , çünkü düğümlere değer yerine referans olarak başvurabilmek istiyoruz . Listemiz iki kat bağlantılı olacak , yani her bir düğüm hem bir sonraki komşusuna hem de bir öncekine bir referans içerecektir. Her düğüm ayrıca şöyle bir şey depolar Value:

extension List {
    class Node {
        var value: Value
        fileprivate(set) weak var previous: Node?
        fileprivate(set) var next: Node?

        init(value: Value) {
            self.value = value
        }
    }
}

Bu aslında bağlantılı listemizin değerleri depolamasını sağlamak için ihtiyaç duyacağımız tüm kod. Ama bu sadece bulmacanın ilk kısmı, tıpkı diğer koleksiyonlar gibi, biz de onun üzerinde yineleme yapabilmek ve içeriğini değiştirmek edebilmek istiyoruz. Swift’in protokol odaklı tasarımı sayesinde Sequence, makeIteratoryönteme uyarak ve uygulayarak kolayca uygulanabilecek yinelemelerle başlayalım :

extension List: Sequence {
    func makeIterator() -> AnyIterator<Value> {
        var node = firstNode

        return AnyIterator {
            // Iterate through all of our nodes by continuously
            // moving to the next one and extract its value:
            let value = node?.value
            node = node?.next
            return value
        }
    }
}

Yukarıdaki yinelememiz çok basit 
AnyIteratorolduğu için, özel bir yineleyici türü uygulamak zorunda kalmaktan kaçınmak 
için standart kütüphane kullanırız 
– ki bu daha gelişmiş kullanım durumlarına uyum sağlayarak yapılabilir 
IteratorProtocol.

Daha sonra, eklemelerden başlayarak, bağlantılı listemizi mutasyona geçirmek için API ekleyelim. Girilen değer için yeni bir düğüm ekleyen ve sonra şu düğümü döndüren Listbir appendyöntemle genişleteceğiz :

extension List {
    @discardableResult
    mutating func append(_ value: Value) -> Node {
        let node = Node(value: value)
        node.previous = lastNode

        lastNode?.next = node
        lastNode = node

        if firstNode == nil {
            firstNode = node
        }

        return node
    }
}

Yukarıda @discardableResult, derleyiciye, yöntemimizi çağırmanın sonucu kullanılmadığı takdirde herhangi bir uyarı oluşturmamasını söyleyen özelliği kullanırız – çünkü oluşturulan gerçek düğüme her zaman ilgi duymayabiliriz.

Bağlantılı listeler indekslere dayanmadığından, referanslar yoluyla bir değerler zincirinin korunmasına dayandığından, kaldırmaları uygulamak, kaldırılan düğümleri nextve previouskomşularını şimdi birbirlerine işaret edecek şekilde güncellemekten ibarettir:

extension List {
    mutating func remove(_ node: Node) {
        node.previous?.next = node.next
        node.next?.previous = node.previous

        // Using "triple-equals" we can compare two class
        // instances by identity, rather than by value:
        if firstNode === node {
            firstNode = node.next
        }

        if lastNode === node {
            lastNode = node.previous
        }
    }
}

Yukarıdakiler yerinde olduğunda, ilk sürümümüz Listtamamlanmıştır ve bir tur atmaya hazırız. CanvasYeni listemizi kullanmak için güncelleyelim – ayrıca belirli bir şekil kimliğine karşılık gelen hangi düğüme hızlı bir şekilde bakmamızı sağlayan bir sözlüğü – yeni veri yapıları birleşimi olarak:

struct Canvas {
    private var shapes = List<Shape>()
    private var nodes = [Shape.ID : List<Shape>.Node]()

    func render() -> Image {
        let context = DrawingContext()
        shapes.forEach(context.draw)
        return context.makeImage()
    }

    mutating func add(_ shape: Shape) {
        nodes[shape.id] = shapes.append(shape)
    }

    mutating func remove(_ shape: Shape) {
        guard let node = nodes.removeValue(forKey: shape.id) else {
            return
        }

        shapes.remove(node)
    }
}

Artık, çağrı alanına herhangi bir ek karmaşıklık eklemek zorunda kalmadan hem hızlı ekleme ve kaldırma işlemlerinin yanı sıra hem de öngörülebilir bir yineleme düzenimiz var – oldukça havalı! Ve yeni Listolanımızı tamamen genel bir tür haline getirdiğimizden , endekssiz değerleri tekrar doğrusal bir şekilde depolamamız gerektiğinde tekrar kullanabiliriz.

Sonuç

Her ne kadar veri yapıları her türlü programlama dilinde bulunabilecek kadar temel olsa da, herhangi bir durumda hangisinin kullanılacağına karar vermek, özellikle de kodumuzun verimli kalmasını istiyorsak, makul miktarda düşünme, test etme ve deneme gerektirebilir. Büyüyen bir veri kümesiyle kullanıldığı gibi.

Ayrıca, herhangi bir durum için doğru veri yapısının, gereksinimlerimiz geliştikçe zaman içerisinde değişebileceği ve bazen birden fazla veri yapısının bir kombinasyonunu kullanmanın – sadece bir tane yerine – ihtiyaç duyduğumuz performans özelliklerine ulaşmanın bir yolu olabileceği de muhtemeldir.

Gelecek makalelerdeki veri yapılarının dünyasını keşfetmeye devam edeceğiz – özellikle de standart kütüphanede henüz uygulanmayanlara göz atarak. Diğer birçok şeyde olduğu gibi, düşüncemizi Swift’in ötesine genişletmek bazen her durumda doğru veri yapısını seçmek için gerekli olan şeydir.