Hallo nochmal. Bevor wir zum Wochenende abreisen, möchten wir Ihnen eine Übersetzung von Material mitteilen, das speziell für den Grundkurs „iOS Developer“ erstellt wurde .
Die Entscheidung, welche Datenstruktur zur Darstellung eines bestimmten Wertesatzes verwendet werden soll, ist oft viel schwieriger als es scheint. Da jede Art von Datenstruktur für eine bestimmte Anzahl von Anwendungsfällen optimiert ist, kann die Auswahl der richtigen Anpassung für jeden Datensatz häufig einen großen Einfluss auf die Leistung unseres Codes haben.
Die Standard-Swift-Bibliothek enthält drei Hauptdatenstrukturen:
Array ,
Dictionary und
Set , von denen jede ihre eigenen Optimierungen, Vor- und Nachteile hat. Schauen wir uns einige ihrer Merkmale sowie Fälle an, in denen wir möglicherweise über die Standardbibliothek hinausgehen müssen, um die richtige Datenstruktur für unsere Zwecke zu finden.
Array-Linearität
Array ist wahrscheinlich eine der am häufigsten verwendeten Datenstrukturen in Swift, und dafür gibt es gute Gründe. Es speichert seine Elemente nacheinander, sie sind leicht vorhersehbar zu sortieren und alle Werte können darin gespeichert werden: von Strukturen bis zu Instanzen von Klassen und anderen Sammlungen.
Hier verwenden wir beispielsweise ein Array, um eine Sammlung von Formen zu speichern, die in einer Zeichenanwendung auf einer
Canvas platziert sind. Wenn wir dann die Leinwand in ein Bild rendern müssen, gehen wir einfach durch das Array, um jedes Element mit dem
DrawingContext zu zeichnen - wie folgt:
struct Canvas { var shapes: [Shape] func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } }
Wenn es um das sequentielle Rendern aller unserer Formen geht, wie oben beschrieben, passt das Array perfekt. Arrays speichern ihre Elemente nicht nur sehr effizient, sondern verfügen auch über eine garantierte Sortierreihenfolge, die eine vorhersehbare Renderreihenfolge bietet, ohne dass zusätzliche Arbeiten erforderlich sind.
Wie alle anderen Datenstrukturen haben Arrays jedoch ihre Nachteile. In unserem Fall werden wir auf einen seiner Nachteile stoßen, wenn wir Formen von der Leinwand entfernen möchten. Da die Elemente des Arrays nach Index gespeichert sind, müssen wir immer zuerst herausfinden, welchem Index die Figur zugeordnet ist, bevor wir sie löschen können:
extension Canvas { mutating func remove(_ shape: Shape) { guard let index = shapes.firstIndex(of: shape) else { return } shapes.remove(at: index) } }
Auf den ersten
firstIndex mag der obige Code nicht so problematisch erscheinen, aber er kann zu einem Leistungsengpass für jede
firstIndex die eine große Anzahl von Formen enthält, da
firstIndex in Bezug auf die
Zeitkomplexität linear (O (N)) ist.
Obwohl wir diese Einschränkung umgehen können, wenn wir unseren Canvas-Typ verwenden. Wenn Sie sich beispielsweise immer auf Zahlen nach Index und nicht nach Wert oder ID beziehen, wird unser Code komplexer und fragiler, da wir immer sicherstellen müssen, dass unsere Indizes nicht ablaufen, wenn die Zeichenfläche verwendet wird, mit der wir arbeiten wird sich ändern.
Geschwindigkeitssätze
Lassen Sie uns stattdessen sehen, ob wir den
Canvas selbst optimieren können, indem wir die zugrunde liegende Datenstruktur ändern. In Anbetracht des obigen Problems könnte eine unserer ersten Ideen darin bestehen,
Set (Sets) anstelle von
Array . Wie wir bereits in
Die Potenz von Mengen in Swift besprochen haben, besteht einer der wesentlichen Vorteile von Mengen gegenüber Arrays darin, dass sowohl das Einfügen als auch das Löschen immer in einer konstanten (O (1)) Zeit ausgeführt werden können. da Elemente nach Hashwert und nicht nach Index gespeichert werden.
Durch die Aktualisierung von
Canvas zur Verwendung von Sets erhalten wir Folgendes:
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) } }
Auch hier kann der obige Code richtig aussehen und sogar problemlos kompiliert werden. Obwohl wir das Löschproblem gelöst haben, haben wir auch unsere stabile Renderreihenfolge verloren - da Sets im Gegensatz zu Arrays keine garantierte Sortierreihenfolge bieten -, was in dieser Situation ein Stolperstein ist, da es so aussieht, als würden wir benutzerdefinierte Formen zeichnen zufällig.
Indizierung von Indizes
Lass uns weiter experimentieren. Lassen Sie uns nun sehen, ob wir den
Canvas optimieren können, indem wir ein
Dictionary einführen, mit dem wir anhand seiner ID nach dem Index einer beliebigen Form suchen können. Zunächst ändern wir die Zugriffsebene für unser
shapes Array in "
private damit wir das Einfügen von Elementen mithilfe der neuen
add Methode steuern können. Und jedes Mal, wenn eine neue Figur hinzugefügt wird, fügen wir ihren Index auch unserem Wörterbuch hinzu:
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) } }
Da wir jetzt immer wissen, an welchem Index eine bestimmte Zahl gespeichert ist, können wir das Löschen schnell in konstanter Zeit durchführen, wie bei Verwendung eines Satzes:
extension Canvas { mutating func remove(_ shape: Shape) { guard let index = indexes[shape.id] else { return } shapes.remove(at: index) indexes[shape.id] = nil } }
Es gibt jedoch einen ziemlich schwerwiegenden Fehler in unserer neuen
Canvas Implementierung. Jedes Mal, wenn wir eine Form löschen, werden alle Indizes ungültig, die höher sind als der gerade gelöschte. Da jedes dieser Elemente einen Schritt an den Anfang des Arrays verschoben wird. Wir könnten dieses Problem lösen, indem wir diese Indizes nach jedem Löschen anpassen, aber dies würde uns wieder in das O (N) -Gebiet zurückbringen, das wir von Anfang an zu vermeiden versuchten.
Unsere neueste Implementierung hat ihre Vorzüge. Im Allgemeinen kann die Verwendung einer Kombination aus zwei Datenstrukturen in solchen Situationen eine gute Idee sein, da wir häufig die Stärken einer Datenstruktur verwenden können, um die Mängel der anderen zu kompensieren, und umgekehrt.
Versuchen wir es also noch einmal mit einer anderen Kombination, aber diesmal betrachten wir zunächst unsere
tatsächlichen Anforderungen :
- Wir brauchen sowohl Einfügungen als auch Löschungen, um eine konstante zeitliche Komplexität zu haben, und es sollte möglich sein, die Figur zu löschen, ohne ihren Basisindex zu kennen.
- Wir benötigen eine garantierte Sortierreihenfolge, um eine stabile Renderreihenfolge aufrechterhalten zu können.
Wenn man sich die oben genannten Anforderungen ansieht, stellt sich heraus, dass wir zwar eine stabile Sortierreihenfolge benötigen, aber tatsächlich keine Indizes benötigen. Dies würde die verknüpfte Liste perfekt für unseren Anwendungsfall machen.
Verknüpfte Listen bestehen aus Knoten, wobei jeder Knoten einen Link (oder Link) zum nächsten Knoten in der Liste enthält. Dies bedeutet, dass er auf vorhersehbare Weise sortiert werden kann - ohne dass Indexaktualisierungen erforderlich sind, wenn ein Element gelöscht wird. Die Swift-Standardbibliothek enthält jedoch (bisher) keinen verknüpften Listentyp. Wenn wir ihn also verwenden möchten, müssen wir ihn zuerst erstellen.
Erstellen Sie eine verknüpfte Liste
Beginnen wir mit der Deklaration einer Listenstruktur, die den ersten und den letzten Knoten in unserer Liste verfolgt. Wir werden diese beiden Eigenschaften außerhalb unseres Typs schreibgeschützt machen, um die Datenkonsistenz sicherzustellen:
struct List<Value> { private(set) var firstNode: Node? private(set) var lastNode: Node? }
Als nächstes erstellen wir unseren Knotentyp (Knoten), den wir zu einer Klasse machen, da wir in der Lage sein möchten, auf Knoten
nach Referenz und nicht nach Wert zu verweisen. Unsere Liste wird doppelt verbunden sein, was bedeutet, dass jeder Knoten eine Verknüpfung sowohl zum nächsten als auch zum vorherigen Nachbarn enthält. Jeder Knoten speichert auch einen Wert - wie folgt:
extension List { class Node { var value: Value fileprivate(set) weak var previous: Node? fileprivate(set) var next: Node? init(value: Value) { self.value = value } } }
Der Grund, warum wir die vorherige Eigenschaft schwach machen, besteht darin, die Retain-Schleifen zu vermeiden, die auftreten würden, wenn wir starke Verbindungen in beide Richtungen beibehalten würden. Weitere Informationen zum Vermeiden von Aufbewahrungszyklen finden Sie im Artikel „Speicherverwaltung“ .
Dies ist eigentlich der gesamte Code, den wir benötigen, damit Werte in unserer verknüpften Liste gespeichert werden können. Dies ist jedoch nur der erste Teil des Puzzles, wie in jeder anderen Sammlung möchten wir auch in der Lage sein, darüber zu iterieren und seinen Inhalt zu ändern. Beginnen wir mit Iterationen, die dank des sehr protokollorientierten Swift-Designs einfach implementiert werden können, indem die Einhaltung des
Sequence sichergestellt und die
makeIterator Methode implementiert wird:
extension List: Sequence { func makeIterator() -> AnyIterator<Value> { var node = firstNode return AnyIterator {
Da die obige Iteration sehr einfach ist, verwenden wir die AnyIterator Standardbibliothek, um zu vermeiden, dass ein benutzerdefinierter Iteratortyp implementiert werden muss. Für komplexere Szenarien kann es durch Hinzufügen einer Übereinstimmung zu IteratorProtocol implementiert werden.
Als nächstes fügen wir eine API hinzu, um unsere verknüpfte Liste zu ändern, beginnend mit den Einfügungen. Wir werden die
List mit der
append Methode erweitern, die einen neuen Knoten für den eingefügten Wert hinzufügt und diesen Knoten dann wie folgt zurückgibt:
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 } }
Oben verwenden wir das Attribut @discardableResult , das den Compiler @discardableResult , keine Warnungen zu generieren, wenn das Ergebnis des Aufrufs unserer Methode nicht verwendet wurde, da wir nicht immer an dem erstellten Knoten interessiert sind.
Da verknüpfte Listen nicht auf Indizes basieren, sondern auf der Aufrechterhaltung einer Wertekette über Verknüpfungen, müssen beim Implementieren von Löschungen nur die folgenden und vorherigen Nachbarn der Remote-Knoten aktualisiert werden, sodass sie stattdessen aufeinander verweisen:
extension List { mutating func remove(_ node: Node) { node.previous?.next = node.next node.next?.previous = node.previous
Auf der Grundlage des Vorstehenden ist die ursprüngliche Version unserer Liste fertiggestellt, und wir sind bereit, sie in Aktion zu überprüfen. Aktualisieren wir den Canvas-Bereich, um unsere neue Liste sowie ein Wörterbuch zu verwenden, mit dem wir schnell herausfinden können, welcher Knoten mit einer bestimmten Form-ID übereinstimmt:
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) } }
Jetzt haben wir sowohl schnelles Einfügen als auch Löschen und eine vorhersehbare Sortierreihenfolge, ohne dass der Anrufprozess noch komplexer werden muss - es ist ziemlich cool! Und da unsere neue Liste ein völlig universeller Typ ist, können wir sie jetzt verwenden, wenn wir erneut Werte ohne Index linear speichern müssen.
Fazit
Trotz der Tatsache, dass die Datenstrukturen so grundlegend sind, dass sie in allen Arten von Programmiersprachen zu finden sind, erfordert die Entscheidung, welche in jeder spezifischen Situation verwendet werden soll, möglicherweise noch viel Nachdenken, Testen und Experimentieren, insbesondere wenn wir dies möchten Damit unser Code wirksam bleibt, wenn der Datensatz wächst.
Es ist auch sehr wahrscheinlich, dass sich die geeignete Datenstruktur für jede spezifische Situation im Laufe der Zeit ändert, wenn sich unsere Anforderungen ändern, und manchmal kann die Verwendung einer Kombination aus mehreren Datenstrukturen und nicht nur einer eine Möglichkeit sein, die erforderlichen Leistungsmerkmale zu erreichen.
In den folgenden Artikeln werden wir uns weiter mit der Welt der Datenstrukturen befassen und uns auf diejenigen konzentrieren, die noch nicht in der Standardbibliothek implementiert sind. Wie bei so vielen anderen Dingen müssen wir manchmal unser Denken über Swift hinaus erweitern, um die richtige Datenstruktur für jede Situation auszuwählen.
Sie können mich
auf Twitter finden oder mir eine E-Mail senden, wenn Sie Fragen, Kommentare oder Feedback haben.
Vielen Dank für Ihre Aufmerksamkeit!