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
, Dictionary
ve 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ığı
Array
tartış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 Canvas
bir ç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 firstIndex
doğrusaldır ( O(N)
) .
Biz ise olabilir bizim kullanıyoruz yerde bu tip bir kısıtlama geçici Canvas
tü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, Canvas
temel veri yapısını değiştirerek kendini optimize edip edemeyeceğimize bakalım . Yukarıdaki soruna baktığımızda, ilk fikirlerimizden biri Set
yerine 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.
Canvas
Bir 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 Canvas
bir tanıtarak Dictionary
bize kendi kimliği temel alarak herhangi şeklin indeks aramak sağlayan o. shapes
Yeni bir add
yö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 Canvas
uygulamamı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
List
Listemizdeki 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, Node
bir 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
, makeIterator
yö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 AnyIterator
olduğ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 List
bir append
yö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 next
ve previous
komş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 List
tamamlanmıştır ve bir tur atmaya hazırız. Canvas
Yeni 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 List
olanı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.
GIPHY App Key not set. Please check settings