Algorithmen und Datenstrukturen in Swift 5 - Gelingt in deinem Job Interview für den Softwareentwickler! | Karoly Nyisztor | Skillshare

Playback-Geschwindigkeit


  • 0.5x
  • 1x (normal)
  • 1.25x
  • 1.5x
  • 2x

Algorithmen und Datenstrukturen in Swift 5 - Gelingt in deinem Job Interview für den Softwareentwickler!

teacher avatar Karoly Nyisztor, Senior Software Engineer, Instructor

Schau dir diesen Kurs und Tausende anderer Kurse an

Erhalte unbegrenzten Zugang zu jedem Kurs
Lerne von Branchenführern, Ikonen und erfahrenen Experten
Eine Vielzahl von Themen, wie Illustration, Design, Fotografie, Animation und mehr

Schau dir diesen Kurs und Tausende anderer Kurse an

Erhalte unbegrenzten Zugang zu jedem Kurs
Lerne von Branchenführern, Ikonen und erfahrenen Experten
Eine Vielzahl von Themen, wie Illustration, Design, Fotografie, Animation und mehr

Einheiten dieses Kurses

49 Einheiten (2 Std. 2 Min.)
    • 1. Algorithmen und Datenstrukturen in Swift 5

      2:46
    • 2. Abschnitt 1: Übersicht

      2:40
    • 3. Ist dieser Kurs für dich?

      1:05
    • 4. Warum solltest du Algorithmen lernen?

      1:14
    • 5. Voraussetzungen

      1:02
    • 6. Abschnitt 2: Große O-Notation

      2:31
    • 7. Konstante Zeit - O(1)

      5:40
    • 8. Lineare Zeit - O(n)

      4:17
    • 9. Quadratische Zeit - O(n2)

      3:53
    • 10. Hinweise für Polynome O(n^k) Komplexität

      1:32
    • 11. Logarithmische Zeit - O(log n)

      1:56
    • 12. Big O Zusammenfassung

      1:30
    • 13. Abschnitt 3: Rekursion

      0:40
    • 14. Was ist Recursion?

      2:38
    • 15. Wie funktioniert Recursion ?

      4:45
    • 16. Rekursion Fallstricke

      2:37
    • 17. Wie vermeide ich unendliche Rekursion?

      1:51
    • 18. Abschnitt 4: Die Macht der Algorithmen

      1:28
    • 19. Sum(N) berechnen

      3:04
    • 20. Pair Herausforderung

      4:17
    • 21. Finde den Equilibrium Index

      3:51
    • 22. Die Macht der Algorithmen - Zusammenfassung

      1:49
    • 23. Abschnitt 5: Generika

      0:55
    • 24. Warum Generika?

      1:24
    • 25. Generische Typen

      1:56
    • 26. Generische Funktionen

      3:47
    • 27. Abschnitt 6: Schnelles Sammeln

      0:55
    • 28. Das Array

      2:08
    • 29. Zugriff auf das Array

      1:09
    • 30. Array verändern

      2:43
    • 31. Das Set

      2:27
    • 32. Zugriff und Änderung des Satzes

      1:48
    • 33. Festlegen von Operationen

      1:10
    • 34. Das Hashable Protokoll

      4:40
    • 35. Das Wörterbuch

      2:33
    • 36. Zugriff auf und Ändern des Textes

      1:35
    • 37. Abschnitt 7: Grundlegende Sortierung

      2:12
    • 38. Auswahl Sortieren

      5:33
    • 39. Auswahl Sortieren - Zusammenfassung

      0:49
    • 40. Sortieren

      7:58
    • 41. Sortieren - Zusammenfassung

      1:03
    • 42. Bubble Sortieren

      5:05
    • 43. Bubble Sortieren - Zusammenfassung

      1:01
    • 44. Abschnitt 8: Erweitertes Sortieren

      0:51
    • 45. Sortieren nach

      3:46
    • 46. Sortieren zusammenführen - Zusammenfassung

      0:55
    • 47. Quicksort

      3:28
    • 48. Quicksort - Zusammenfassung

      0:57
    • 49. Abschnitt 9: Endliche Gedanken und nützliche Ressourcen

      2:30
  • --
  • Anfänger-Niveau
  • Fortgeschrittenes Niveau
  • Fortgeschrittenes Niveau
  • Alle Niveaus

Von der Community generiert

Das Niveau wird anhand der mehrheitlichen Meinung der Teilnehmer:innen bestimmt, die diesen Kurs bewertet haben. Bis das Feedback von mindestens 5 Teilnehmer:innen eingegangen ist, wird die Empfehlung der Kursleiter:innen angezeigt.

294

Teilnehmer:innen

--

Projekte

Über diesen Kurs

Werfen Sie einen genaueren Blick auf Algorithmen und Datenstrukturen und lernen Sie, wie du mit ihnen zusammenarbeiten kannst, um mit Swift die Softwareentwicklung effizienter anzugehen. "Einführung in Algorithmen und Datenstrukturen in Swift 5" ist ein einfacher Leitfaden zur effizienteren Lösung von Algorithms

In diesem umfangreichen Kurs hilft der Autor Károly Nyisztor dabei, sich mit algorithmischen Denk- und code vertraut zu machen. Er erläutert jedes Konzept anhand von einfach verständlichen Beispielen. Er konzentriert sich auf die praktische Anwendung und verwendet praktische hands-on für die Referenz und Praxis.

Obwohl die Demos in Swift implementiert sind, können die Kurse auf jede Programmiersprache angewendet werden.

Während des Kurses führt dich Károly durch mehrere Demo-Anwendungen, um die Macht der Algorithmen und die Bedeutung der Auswahl der richtigen Lösung zu demonstrieren.

Themen sind:

  • Algorithmisches Denken

  • Die große O-Notation

  • Konstante, lineare, polynome und logarithmische Zeitkomplexität

  • Rekursion verstehen und Fallen vermeiden

  • Fallstudien zum Finden schnellerer Lösungen

  • Generika

  • Eingebaute Built-in

  • Wann verwende ich ein Set, ein Array oder ein Wörterbuch?

  • Implementing Implementing und Implementing implementieren

  • Erweiterte Sortierung: sorting: und Zusammenführen

Das Studium der Algorithmen und Datenstrukturen ist für jeden Programmierer von grundlegender Bedeutung, der Software-Systeme entwickeln will, die skalierbar und performant sind.
"Einführung in Algorithmen und Datenstrukturen in Swift 5" ist der perfekte Kurs für dich, wenn du daran interessiert bist, deine Swift auf die nächste Stufe zu bringen.

-------------

Um die Übungen in diesem Buch zu implementieren, brauchst du einen Mac mit macOS 10.14.3 (Mojave) oder höher. Du brauchst auch Xcode 10.2.1 oder neuer. Du kannst Xcode kostenlos im Mac App Store herunterladen.

Wir werden Swift 5 verwenden, um den Quellcode in diesem Kurs zu implementieren.

Alle Muster sind mit der neuesten Swift kompatibel. Ich werde den Quellcode aktualisieren, da es Änderungen in der Sprache erforderlich machen.

Die Projekte stehen auf Github zur Verfügung, und du kannst sie aus dem folgenden Repository herunterladen: https://github.com/nyisztor/swift-algorithms.

Triff deine:n Kursleiter:in

Teacher Profile Image

Karoly Nyisztor

Senior Software Engineer, Instructor

Kursleiter:in

My passion is helping people through online courses. So far, I've inspired over 50,000 students worldwide.

Hi there, my name is Károly Nyisztor. I'm a software engineer, online instructor, and book author. You can find my courses and books on all major platforms including Udemy, LinkedIn Learning, Lynda and Pluralsight.

I've worked with companies such as Apple, Siemens, SAP, Zen Studios, and many more. 
I've designed and built several enterprise frameworks, and I hold twelve patents related to inventions in the field of mobile computing.

I've developed over a dozen iOS apps and games- Libra Balance, My Travel Assistant, Travel Mate, iSyslog, GiftShopper, Zombie Run, to name a few.
Most of these apps have been featured by Apple(New a... Vollständiges Profil ansehen

Kursbewertungen

Erwartungen erfüllt?
    Voll und ganz!
  • 0%
  • Ja
  • 0%
  • Teils teils
  • 0%
  • Eher nicht
  • 0%
Bewertungsarchiv

Im Oktober 2018 haben wir unser Bewertungssystem aktualisiert, um das Verfahren unserer Feedback-Erhebung zu verbessern. Nachfolgend die Bewertungen, die vor diesem Update verfasst wurden.

Warum lohnt sich eine Mitgliedschaft bei Skillshare?

Nimm an prämierten Skillshare Original-Kursen teil

Jeder Kurs setzt sich aus kurzen Einheiten und praktischen Übungsprojekten zusammen

Mit deiner Mitgliedschaft unterstützt du die Kursleiter:innen bei Skillshare

Lerne von überall aus

Ob auf dem Weg zur Arbeit, zur Uni oder im Flieger - streame oder lade Kurse herunter mit der Skillshare-App und lerne, wo auch immer du möchtest.

Transkripte

1. Algorithmen und Datenstrukturen in Swift 5: Algorithmen sind im Wesentlichen in der Informatik. Sie sind buchstäblich überall, auch wenn Sie sie noch nicht bemerkt haben. Wenn Sie Ihre Reise planen, verwendet das GPS Routensuche Algorithmen. Und wenn Sie sich ein 4K-Video auf YouTube ansehen, spielt es dank Audio- und Videokompressionsalgorithmen fehlerfrei. Wie wäre es mit den erstaunlichen 3D-Spielszenen? Ohne ausgeklügelte Rendering-Algorithmen wären sie nicht möglich. Sind Sie ein Softwareentwickler? Was wäre, wenn Sie besseren, schnelleren Code schreiben könnten? Vielleicht erwägen Sie eine Karriere in der Softwareentwicklung. Wäre es nicht toll, das Vorstellungsgespräch mit Bravour zu bestehen. Hi, ich bin Carter. Wenn Sie speichern, bin ich Software-Ingenieur, MOOC-Autor und Dozent. Ich freue mich, Sie zu meinem Kurs, Einführung in Algorithmen und Datenstrukturen in Swift fünf begrüßen zu dürfen. In diesem Kurs lehre ich Ihnen, wie Sie die zeitliche Komplexität einer Funktion herausfinden können. Sie werden verstehen, wie integrierte Container funktionieren und Sie werden in der Lage sein , mit Zuversicht zu erklären, warum Quicksort besser ist als Blasensortierung. Wenn Sie über Algorithmen und Datenstrukturen wissen, können Sie besseren Code schreiben. Ihre Programme werden schneller ausgeführt, indem Sie den richtigen Algorithmus anwenden. Ich werde alles durch das Leben demonstrieren. Swift-Codierung führt Leistungstests durch, um die Laufzeiten verschiedener Lösungen mit dem gleichen Problem zu vergleichen. Sie werden etwas über die Big O-Notation lernen. Dies wird Ihnen helfen, die Komplexität von Funktionen und Algorithmen herauszufinden. Dann zeige ich Ihnen die Macht der Generika. Generische stehen im Kern der schnellen Standardbibliothek, werden Generika in Aktion sehen und Sie werden sich schnell mit ihnen vertraut machen. Als nächstes werden wir über die integrierten Swift-Sammlungstypen sprechen. Ich zeige Ihnen, wie Sie einige der grundlegenden Datenstrukturen mit Swift implementieren. Dann werden wir uns mit den Sortieralgorithmen von Basic bis Advanced beschäftigen. Ich werde die Auswahlsortierung, Einfügesortierung, Blasensortierung, Merge-Sortierungund den berühmten QuickSort Algorithmus erklären und implementieren Einfügesortierung, Blasensortierung, Merge-Sortierung . Ich verwende Visualisierungstechniken während des Kurses. Und ich zerteile komplexe Konzepte in einfache, leicht verständliche Stücke. Am Ende dieses Kurses werden Sie wissen, wie Sie schnellere und bessere Programme implementieren können. Sie werden auch verstehen, wie die gängigsten Datenstrukturen und Sortieralgorithmen funktionieren. Sie lernen, wie Sie effizienteren Code zusammen mit den Best Practices für die Swift-Programmierung implementieren , die Sie sofort in Ihren Apps anwenden können. Diskurse entlang der Zeitinvestition. Wir sehen uns in der ersten Lektion. 2. Abschnitt 1: Übersicht: Hallo, ich bin Fracht im Laden und willkommen zu Einführung in Algorithmen und Datenstrukturen in Swift. Ich habe diesen Kurs erstellt, um Ihnen zu helfen, besseren, leistungsfähigeren Code zu schreiben . Sie werden einige der häufig verwendeten Algorithmen und Datenstrukturen kennen lernen . Wir beginnen damit, zu lernen, wie man die Effizienz von Algorithmen analysiert. Zuerst werden wir über die große O-Notation sprechen, die ein mathematisches Modell zum Messen und Klassifizieren von Algorithmen ist. Es schätzte die Zeiteffizienz der Ausführung eines Algorithmus als Funktion der Eingangsgröße. Wir werden über konstante Zeit, lineare Zeit, Polynomzeit und logarithmische Zeit sprechen. Um diese Konzepte zu verstehen, werden wir verschiedene Algorithmen implementieren, analysieren und vergleichen. Dann sprechen wir über Rekursion und wie man das Problem der unendlichen Rekursion vermeidet. Viele Algorithmen und Datenstrukturen verlassen sich auf Rekursion. Daher ist es zwingend notwendig zu verstehen, wie Rekursion funktioniert. Wir zeigen nun die praktischen Vorteile der Verwendung von Algorithmen. Wir vergleichen nicht optimierte Samples mit denen, die auf Algorithmen angewiesen sind. Wenn Sie Zweifel an der Bedeutung von Algorithmen hatten, werden diese Beispiele Sie überzeugen. Als nächstes tauchten wir in Generika. Sie müssen Generika verstehen, bevor wir mit dem Studium von Datenstrukturen und Algorithmen beginnen. Dann sprechen wir über die eingebauten Datenstrukturen. Sie erfahren mehr über das Array, die Menge und das Wörterbuch, bevor Sie zu den Sortieralgorithmen übergehen. Als nächstes untersuchen und implementieren wir die Auswahlsortierung, Einfügesortierung und die Blasensortierung. Wir werden die Effizienz jedes dieser Sortieralgorithmen analysieren und sie visuell darstellen. Wir werden mit zwei fortschrittlicheren Sortieralgorithmen fortfahren. Wir implementieren die Merge-Sort und die QuickSort in Swift. Schließlich werde ich einige nützliche Online-Ressourcen teilen , die Ihnen helfen, Ihre Programmier- und Problemlösungsfähigkeiten zu schärfen. Nachdem Sie diesen Kurs abgeschlossen haben, werden Sie alle grundlegenden Konzepte im Zusammenhang mit Algorithmen und Datenstrukturen kennen. Sie werden ein gutes Verständnis von Konzepten wie Rekursion und Generika haben. Sie werden sehen, wie die beliebten Sortieralgorithmen funktionieren und wie sie mit Swift als ersten Teil einer Serie zur Swift-Programmierung implementiert werden können . Dieser Kurs ist ein wesentlicher Schritt, um tiefer in Algorithmen, Datenstrukturen und generelle Programmierung zu vertiefen. 3. Ist dieser Kurs für dich?: Mal sehen, ob dies der richtige Kurs für dich ist. Obwohl ich fast jede Codezeile erklärt habe, die ich in diesem Kurs schreibe, sollten Sie die Grundlagen der Programmierung kennen. Dinge wie Methoden, Schleifen oder Bedingungen sollten Ihnen vertraut sein. Es ist kein Problem, wenn Sie relativ neu in der Programmierung sind. Mach dir keine Sorgen. Wenn Sie noch nicht gehört haben, sagen Sie die große O-Notation, Rekursion oder Generika. Ich werde jedes Konzept von Anfang an erklären. Bist du neu bei Swift? Kein Problem. Haben Sie mit einer anderen Programmiersprache wie Java, C-Sharp oder sogar Flugzeugen C gearbeitet ? In diesem Fall werden Sie in der Lage sein, mit mir zu folgen. Sie können diesen Kurs auch dann nützlich finden, wenn Sie eine andere Programmiersprache verwenden. Erhalten Sie Einblicke in Swift und lernen Sie, wie Sie Ihren Code optimieren können, erhöhen Sie Ihre Karriere und Ihre beruflichen Fähigkeiten. Nun, beschreibt dies Sie, wenn ja, das ist die perfekte Punktzahl, um über Datenstrukturen und Algorithmen in Swift zu lernen. 4. Warum solltest du Algorithmen lernen?: Warum sollten Sie also in erster Linie Algorithmen studieren? Sobald wir die grundlegenden Hallo Welt Anfängeranwendungen vorbei sind, beginnen wir zu erkennen, dass die Implementierung komplexer Softwaresysteme einen anderen Ansatz erfordert. Die Software, die während unserer Tests gut funktionierte, wird unglaublich langsam und stürzt häufig in der Produktion ab. Wir haben auf die harte Art und Weise gelernt, dass wir unser System nicht für den Einsatz im wirklichen Leben vorbereitet haben. Obwohl es ohne Probleme mit den Testdaten lief, scheitert es kläglich, wenn die Realität tritt n. Computeralgorithmen wurden in den letzten paar Jahrzehnten entwickelt und verfeinert. Die Untersuchung von Algorithmen und Datenstrukturen ist für jeden Programmierer von grundlegender Bedeutung , der skalierbare und leistungsfähige Softwaresysteme entwickeln möchte. Algorithmen sind unverzichtbar, um Software zu entwickeln, die große Datenmengen verwalten oder komplexe Probleme lösen kann . Und Datenstrukturen ermöglichen es uns, effizient auf die Daten zuzugreifen und diese zu speichern. Wir können Datenstrukturen beim Studieren von Algorithmen nicht vermeiden. Außerdem werden Sie bei Vorstellungsgesprächen Fragen zu Algorithmen und Datenstrukturen begegnen . 5. Voraussetzungen: Bevor wir nun anfangen, in Algorithmen und Datenstrukturen zu graben, wir einen kurzen Blick auf das, was Sie wissen sollten. Dieser Kurs ist anfängerfreundlich. Einige grundlegende Programmiererfahrung ist erforderlich, aber Sie müssen nicht wirklich mit Swift selbst gearbeitet haben. Um die Übungen in diesem Kurs umzusetzen, benötigen Sie einen Mac mit macOS Catalina oder Big Sur und Xcode 12 oder neuer. Sie können Xcode kostenlos im Mac App Store herunterladen. Wir werden 55 verwenden, um den Quellcode in diesem Kurs zu implementieren. Sind die Beispiele mit der neuesten Swift-Version kompatibel? Ich werde den Quellcode aktualisieren, da Änderungen in der Sprache es notwendig machen. Die Projekte sind auf GitHub verfügbar und Sie können sie aus dem folgenden Repository herunterladen. Die Sprache Swift ist als Open Source verfügbar. Besuchen Sie Swift.org für alles, was fünfte verwandt ist. Und ohne das gesagt, lasst uns eintauchen. 6. Abschnitt 2: Große O-Notation: Willkommen im zweiten Abschnitt dieses Kurses über Algorithmen in Swift. In diesem Abschnitt werden wir über Rechenkomplexität sprechen. Die Beagle-Notation ist ein mathematisches Modell, das Informatik verwendet, um die Effizienz von Algorithmen als Funktion ihrer Eingangsgröße zu beschreiben . Der beste Weg, das Big O gründlich zu verstehen, ist über Codebeispiele. Daher veranschaulichen wir jedes Konzept mit einer schnellen Codierung hier als die üblichen Ordnungen des Wachstums oder Komplexität, über die wir sprechen werden. In diesem Abschnitt beschreibt Constant Time einen Algorithmus, der unabhängig von der Eingabegröße immer in der gleichen Zeit ausgeführt wird. Linear Time beschreibt einen Algorithmus, dessen Leistung linear und in direktem Verhältnis zur Größe des Importdatensatzes zunimmt. Quadratische Zeit stellt einen Algorithmus dar, dessen Leistung direkt proportional zum Quadrat der Größe des Eingabedatensatzes ist. Dieses Verhalten ist typisch für Algorithmen, die verschachtelte Iterationen über den Datensatz umfassten . Tiefer verschachtelte Iterationen führen zu kubischer Zeit, aquatische Zeit und schlechtere logarithmische Zeit logarithmische Zeit repräsentiert ah, hocheffizienten Algorithmus. Zum Beispiel, die beliebte binäre Suchtechnik führt in logarithmischer Zeit wissen, dass wir nur die Grundlagen der großen abdecken Oh, dieses Wissen ist ausreichend, um die Effizienz der Sortieralgorithmen vorgestellt in den Partituren. Diese Grafik visualisieren ist die Laufzeiten einiger der beliebtesten Sortieralgorithmen. die Eingangsgröße zunimmt, werden die Leistungsunterschiede immer häufiger, wenn der Input County klein alle Algorithmen fast gleich funktionieren. Tatsächlich beim Testen mit kleinen Datensätzen vielleicht sogar den Eindruck, haben wir beim Testen mit kleinen Datensätzen vielleicht sogar den Eindruck,dass der Algorithmus mit der logarithmischen Komplexität die schlechtesten Darsteller hat . Allerdings, wie die Größe der Daten sagt wächst deutlich die Unterschiede in den nächsten Videos zu sehen. Wir werden die verschiedenen Algorithmus-Komplexitäten anhand praktischer, nach Beispielen analysieren . Wir beginnen damit, die konstante Zeit zu präsentieren und werden diesen Abschnitt mit der logarithmischen Zeit enden . 7. Konstante Zeit - O(1): konstante Zeit beschreibt einen Algorithmus, der unabhängig von der Eingabegröße die gleiche Zeit für die Ausführung benötigt . Hier ist, was wir bekommen Wenn wir die Laufzeit eines Algorithmus visualisieren, der in konstanter Zeit ausgeführt wird,wirkt sich konstanter Zeit ausgeführt wird, die Eingabegröße nicht auf die Ausführungszeit aus. Mit anderen Worten, die Ausführungszeit bleibt konstant auf Algorithmus, der eine konstante Zeit hat. Komplexität läuft für die gleiche Zeit. Ob es auf einem oder mehreren 1000 oder 1.000.000 Einträge in der folgenden Demo arbeitet, waren verschwunden. Implementieren Sie einige Beispiele, dass die Ausführung konstanter Zeit Nein, dass wir auf schnelle Spielplätze in den Partituren verlassen werden, wird eine Utility-Klasse für die Messung implementieren . Die Darsteller werden sich auf diese Utility-Klasse verlassen, um Messungen in der aktuellen Demo und in einigen anderen kommenden Projekten durchzuführen. Um die konstante Zeit zu veranschaulichen, Komplexität wird eine Funktion erstellen, die Formen Check Honoree waren. Das zweite Beispiel basiert auf Hash-Map. Schauen Sie nach oben. Wir werden die Zeiten messen, die erforderlich sind, um Werte basierend auf ihren Schlüsseln aus Steve-Wörterbüchern unterschiedlicher Größe abzurufen . Wenn sie korrekt implementiert ist, sollte die Hash-Map-Nachschlagestellung in konstanter Zeit erfolgen. In Ordnung, wechseln wir zu Ex Corde, wenn du mir folgen willst. Laden Sie das Repository von Get Hub geöffnet den größeren Spielplatz von der großen alten SRC. Des Weiteren finden Sie den Quellcode für diese Demo in der Constant Time Playground Seite. Zuerst implementieren wir das Benchmarking-Dienstprogramm. Die Bench-Timer-Klasse verfügt über eine einzige Methode namens Measure-Block. Die Measureblock-Typmethode verfügt über ein Close-Argument. Der Measurecode wird 10 mal ausgeführt und wir speichern die einzelnen Laufzeiten. In Honore. Wir verlassen uns auf die Kern-Frameworks von Quarts. Sehen Sie sich eine aktuelle Medienzeitfunktion an, um die aktuelle absolute Zeit abzurufen. Im Gegensatz zu jedem Nachlass oder CF. Absolute Zeit. Holen Sie sich den aktuellen. Sehen Sie die aktuelle Medienzeit ist zuverlässig, da sie keinen Änderungen in der externen Zeitreferenz unterliegt , wird der gemessene Rock zwischen der Erstellung der Startzeit und der Endzeit ausgeführt. Wir speichern die Ausführungszeit im Array der Ausführungszeiten. Nach 10 Iterationen berechneten wir die durchschnittliche Ausführungszeit, die reduzierte oder eine Funktionsursache der Schließungen schließlich auf alle Array-Elemente, die in unserem Fall alle Elemente in der Theorie zusammenfassen. Schließlich teilen wir das Ergebnis durch die Anzahl der Iterationen, was uns die durchschnittliche Ausführungszeit gibt. Als nächstes implementieren wir eine Funktion, die ein Array nimmt und prüft. Gibt an, ob das erste Element Null ist. Die einfache Funktion wird in konstanter Zeit ausgeführt. Da ist die Hinrichtung. Die Zeit sollte unabhängig von der Größe der in Töpferei gleich sein. Nun lassen Sie uns beweisen, dass unsere Theorie wirklich die Beginne mit Null-Funktion mit drei Arrays aufruft, die erste Rate hat nur drei Elemente. Die 2. 1 hat 10.000 Einträge und das dritte Array ist riesig mit einer Million Items. Unser Benchmark zeigt, dass die Größe der Eingabe eine Rate die Ausführungszeit nicht beeinflusst. Es gibt nur vernachlässigbare Unterschiede in der Reihenfolge der Mikrosekunden. Ein anderer Algorithmus , der in konstanter Zeit ausgeführt wird, ist die Hash-Map. Schauen Sie nach oben. Wir verlassen uns auf die Generierung dicked Helfer Funktion Zehe. Große benutzerdefinierte Wörterbücher generieren dicked nimmt auf Import-Argument namens Größe. Dieses Argument gibt die Größe des generierten Wörterbuchs an. Die Funktion gibt ein Wörterbuch mit Schlüsseln vom Typ string und Werte vom Typ integer zurück. Für uns erstellen wir auf leeres Wörterbuch. Als nächstes validiere ich den Größeneingabeparameter mit der guards-Anweisung. Wenn die Größe nicht größer als Null ist, haben wir das Anti-Wörterbuch zurückgegeben. Ansonsten generieren wir die Schlüssel und die Werte. Ich benutze eine for in Schleife toe literate von Null bis zu, aber ohne die Größe variiert. Wir entweder es von Null zu Größe minus eins. Der Schlüssel ist die Zeichenfolgendarstellung des Indexes. Dann sagten wir den Wert für den gegebenen Schlüssel, der der Index selbst ist. Am Ende erhalten wir ein Wörterbuchfeld mit Schlüsselwertpaaren in der Form String Integer. Lassen Sie uns nun Wörterbücher unterschiedlicher Größe erstellen. Die 1. 1 genannt Small Dictionary, enthält nur drei Schlüsselwertpaare. Medium dicked hat 500 riesige Schwanz enthält 100.000 Schlüssel und Werte. Wir verlassen uns auf die Messzeit- oder Messblockmethode, um die Ausführungszeit des Wörterbuchs herauszufinden . Suchen Sie nach dem Ausführen der Demo nach. Wir sehen tatsächlich, dass die Zeit, die es braucht, um ein Element zu finden, nicht von der Größe des Wörterbuchs abhängt . Unser Test zeigt, dass die Wörterbuchsuche eine konstante zeitliche Komplexität hat. Die Unterschiede in den Ausführungszeiten liegen unter der Mikrosekunde. Frische Welt. Konstante Zeitalgorithmen sind ideal, da sie nicht von der Größe der Eingabe beeinflusst werden. Leider ist es nicht immer möglich, eine Lösung zu finden, die in konstanter Zeit läuft. 8. Lineare Zeit - O(n): in diesem Vortrag werden wir über die lineare Zeitkomplexität sprechen. Linear Time beschreibt einen Algorithmus, dessen Leistung linear und in direktem Verhältnis zur Größe des Eingabedatensatzes zunimmt. Dieses Diagramm stellt die Laufzeit eines Algorithmus dar, der in linearer Zeit ausgeführt wird. Es gibt eine 1 zu 1 Korrelation zwischen Eingabegröße und Ausführungszeit. Der Ausführungszeit-Ofen-Algorithmus mit linearer Zeitkomplexität steigt mit der gleichen Geschwindigkeit wie die Importdaten, die gesagt wachsen. zum Beispiel Wennzum Beispiel1000 Einträge eine Sekunde dauern, als 10.000 10 Mal so viel benötigen, das 10 Sekunden. 100.000 Einträge würden in 100 Sekunden verarbeitet werden und so weiter. Wie die Importdaten gesagt wachsen, erhöht sich auch unsere Algorithmen Verarbeitungszeit auf Deshalb wird es lineare Zeit genannt. Als nächstes werden einige Beispiele implementiert, die in linearer Zeit ausgeführt werden. Zuerst werde ich Ihnen eine Funktion zeigen, die die Elemente von Honore zusammenfasst. Die nächste Funktion, die wir implementieren, gibt die Anzahl der sollte und sogar ganze Zahlen von Honore zurück, beide Funktionen lesen durch die gesamte Ari. Daher hängt die Berechnungszeit direkt mit der Größe der Theorie zusammen. Wir haben lineare Komplexität in beiden Fällen für Leistungsmessungen werden auf der Tisch-Timer angewiesen . Wir sind es in der vorherigen Lektion. Wenn Sie mir folgen möchten, laden Sie das Repository von Get Hub herunter. Öffnen Sie den großen alten Spielplatz aus dem großen O SRC Weiter, Sie können den Quellcode für diese Demo in der linearen Zeit Spielplatz Seite finden, Ich werde sagen, die lineare Zeitkomplexität wird eine Erhöhung der verschiedenen Größen benötigen. Lassen Sie uns also die Implementierung der Funktion erzwingen, die benutzerdefinierte Größe der Strahlen mit zufälligem Inhalt erzeugt. Die Funktion „Rendern Marie generieren“ nimmt zwei Argumente Größe, die die Größe des generierten Dorie und den maximalen Wert gibt, der den größten zulässigen Wert für die Elemente bereitstellt. Wir benutzen unsere für Ende, ähm, Uniformen zu großen zufälligen Inhalten für die Theorie. Als nächstes erstellen wir eine Funktion, die die Elemente der Eingabe zusammenfasst. Tory. Diese Funktion interessiert sich durch die Elemente der Imperatori. Die einige der Elemente werden in der Variablen namens Ergebnis gespeichert. Schließlich gibt die Funktion die Summe aller Ganzzahlen aus deran Keramik wissen, dass wir die Reduzierung oder eine Funktion Zehe verwenden könnten , berechnen Sie die Summe. Aber die Implementierung der benutzerdefinierten Lösung macht es offensichtlich, dass wir über die gesamte Ari wiederholen , wir werden die einige Funktion mit drei Arrays unterschiedlicher Größe testen. Der erste Ray hat 100 Gegenstände, der nächste hat 1000 und der letzte hat 10.000 Elemente. Nach der Durchführung unserer Tests die im Rat angezeigten Leistungsmesswerte, dass die Ausführungszeit linear ist, die Summenfunktion Analphabeten durch alle Elemente des Arrays. Daher ist es normal, dass die Ausführungszeit proportional zur Größe des Arrays zunimmt. Hier ist eine andere Funktion, die durch alle Elemente der Eingabeliste iteriert werden muss . Die Anzahl sind sogar Funktion überprüft jedes Element, um herauszufinden, ob es ungerade oder gerade ist. Ich habe den Moduloperator verwendet, um zu überprüfen, ob es einen Rest gibt, wenn die Zahl durch zwei geteilt . Die Zahl ist auch, wenn der Rest Null. Andernfalls ist die Zahl ungerade. Unsere Tests haben bestätigt, dass kontered sogar tatsächlich eine Funktion ist, die in linearer Zeit läuft. Die Ausführungszeit erhöht sich mit der gleichen Geschwindigkeit wie die Eingabedaten, die gesagt wachsen. Wir stoßen sehr häufig auf lineare Zeitalgorithmen. Mehr Daten bedeuten in der Regel mehr Verarbeitungszeit, die Reduzierung der Zeitkomplexität eines Algorithmus von linearer auf konstante Zeit ist keine leichte Aufgabe und ist möglicherweise nicht einmal in allen Fällen möglich. Aber wie Sie in den kommenden Vorträgen sehen werden, gibt es noch schlimmere Zeitkomplexitäten. 9. Quadratische Zeit - O(n2): Könnte. Ruhezeit stellt einen Algorithmus dar, dessen Leistung direkt proportional zum Quadrat der Größe des Eingabedatensatzes ist. Wie Sie in diesem Diagramm sehen können, erhöht sich die Laufzeit deutlich schneller als diean Put-Größen. Die Laufzeit eines Algorithmus mit quadratischer Zeitkomplexität wird als Quadrat der Importdatensätze Größe quadratische kubische und quadratische Zeit Komplexitäten sind das Ergebnis verschachtelter Operationen auf Datensatz. Sie sollten versuchen, sie zu vermeiden, wenn möglich aufgrund der negativen Auswirkungen auf die Gesamtleistung . Nehmen wir an, Ihr quadratischer Zeitalgorithmus verarbeitet 100 Einträge in 100 Millisekunden. Bei 2000 Einträgen würde der Algorithmus 40 Sekunden lang ausgeführt und 4000 Einträge würden in etwas mehr als 26 Minuten verarbeitet werden . Die Laufzeit stieg mit der Importgröße bei kubischer oder aquatischer Zeitkomplexität noch stärker an. In der folgenden Demo werden wir eine Funktion bauen, die große Multiplikationstabellen. Die Funktion wird zwei verschachtelte Schleifen wegen der verschachtelten Iterationen verwenden. Dieser Algorithmus hat eine quadratische Zeitkomplexität. Wenn Sie mit mir folgen möchten, laden Sie das Repository von get up geöffnet den Big O Spielplatz aus dem Big O SRC Ordner. Den Quellcode für diese Demo finden Sie auf der quadratischen Zeitspielplatz-Seite. Jetzt erreichen wir zwei x erzielte. Zuerst implementieren wir eine nützliche Ergänzung. Toe sind Benchmarking-Dienstprogramm. Wir hatten eine formatierte Zeiteigenschaft für den CF-Zeitintervall Typ. Diese Eigenschaft stellt eine prägnante Zeichenfolgendarstellung des Zeitintervallwerts bereit, der auch die richtigen Zeiteinheiten umfasst, die von neun Sekunden bis Sekunde reichen. Als nächstes wird eine Funktion implementieren, um die quadratische Zeitkomplexität zu demonstrieren. Die Meine Tabellenfunktion nimmt ein ganzzahliges Argument, das die Größe des Arrays angibt, die positive ganze Zahlen im Bereich eins bis Größe enthält. Die Funktion gibt die Ergebnisse der Multiplikation jedes Elements in der Theorie mit jedem anderen Wert zurück. Wir verwenden zwei Schleifen, um das Ergebnis zu berechnen. Die äußere Schleife interessiert sich durch die Indizes der Theorie. Die interne Schleife nimmt den Wert am äußeren Index gefunden und multipliziert ihn mit jedem Element aus demselben Array. Der L-Putt ist eine Multiplikationstabelle. Schauen wir uns an, was wir für den Eingabewert erhalten. 10. Lassen Sie uns nun analysieren, wie die beiden verschachtelten Schleifen die Verarbeitungszeit für eine zwei elementare beeinflussen . Die äußere Schleife iterierte zweimal die innere Schleife Analphabeten für jede äußere Isolierung. Dies gibt uns vier Iterationen insgesamt für eine drei elementare. Die Gesamtzahl der Befreiungen beträgt drei Mal drei. Es gibt neun für 10 Elemente. Die Funktion wird 100 mal aussehen. Die Anzahl der Iterationen geht nach oben ist ein Quadrat der Eingabedatengröße. Lassen Sie uns einige Leistungstests durchführen, um zu beweisen, dass unsere Funktion eine quadratische Zeitkomplexität hat . Wir nannten die marktfähige Funktion mit den Strahlen unterschiedlicher Größe, und wir lieben die Ausführungszeiten. Also der Rat, die Zahlen sind überzeugend. Wir können die quadratischen Sprünge in der Ausführungszeit deutlich sehen. Jetzt möchte ich hinzufügen, dass, insbesondere für kleinere Eingaben, die Messungen möglicherweise nicht immer die quadratische Zeitkomplexität reflektieren, weil unter der Haube Compiler und Hardware-Optimierung. 10. Hinweise für Polynome O(n^k) Komplexität: verschachtelte Schleifen innerhalb der Methode oder Funktion sollten immer ein Warnzeichen sein, und Sie sollten sie um jeden Preis vermeiden. Wann immer Sie auf zwei oder mehr Schleifen stoßen, die russischen Schachtelpuppen ähneln, fragen Sie sich, ob die Nachrichteniterationen wirklich erforderlich sind, um dieses Problem zu lösen . zuerst Dokumentieren Siezuerstden fragwürdigen Code mit dedizierten Commons oder noch besser bei einer Warnung, wenn sie vom gegebenen Compiler unterstützt wird. Implementieren Sie dann Komponententests. Zehe Ich habe, wie das Performance-Problem, das durch die verschachtelten Schleifen verursacht wird, schließlich versucht, das Problem zu lösen, indem ich die notwendigen Dauern durch einen effizienteren Algorithmus ersetzt habe. Polynom-Zeitkomplexität ist normalerweise das Ergebnis von übereilten Codierungen, die von Entwicklern produziert werden die Zeit oder Fachwissen mögen, oder vielleicht beides. Meistens finden Sie im Abschnitt „The Power of Algorithms“ eine bessere Lösung, die Beispiele für den Austausch ineffizienter Ansätze durch Lösungen enthält, die enorme Leistungssteigerungen bringen . Manchmal gibt es wirklich keinen besseren Weg, ein bestimmtes Problem zu lösen, und Sie können die verschachtelten Schleifen in solchen Fällen loswerden. Dokumentieren Sie die betroffenen Gerichtsteile gründlich und beschreiben Sie, warum es so funktioniert. Beschreiben Sie auch die Performance-Probleme, die bei größeren Datensätzen auftreten können 11. Logarithmische Zeit - O(log n): erweiterte Algorithmen wie die binäre Suchtechnik werden in logarithmischer Zeit ausgeführt. Logarithmische Zeit bedeutet, dass die Ausführungszeit linear ansteigt, während die Eingabedatengröße exponentiell wächst. beispielsweise eine Millisekunde dauert, Wenn esbeispielsweise eine Millisekunde dauert,um 10 Elemente zu berechnen, dauert es bis zu Millisekunden 100 Elemente drei Millisekunden zu berechnen, um 1000 Elemente zu berechnen usw. Kauf einer Forschung schnelle Sortierung und Teilung eroberten Art von Algorithmen in der Regel in logarithmischer Zeit laufen . zuerst Schauen wir unszuerstden luxuriösen Daumen genauer an. In der Mathematik. Der Algorithmus ist die umgekehrte Operation, um NC-ation zu erklären. Der Logarithmus von X zu Basis B ist die eindeutige reelle Zahl. Warum solcher, dass B zur Macht? Warum ist X zum Beispiel ein Luxus? Sie von 1000 Basis 10 ist drei als 10 zur Macht drei ist 1000. Die Basis für längere sie von 16 ist zu, als vier auf die Macht zu ist 16. Die Basis drei Logarithmen von 27 ist drei wie drei auf die Macht drei ist 27 und die Basis zwei Logarithmen von 1024 ist 10. Was die Macht betrifft, ist 10 1024. Mit anderen Worten, der Algorithmus einer Zahl ist die Exponentenspitze, die eine andere feste Zahl, die Basis, angehoben werden muss, um diese Zahl in der Informatik zu erzeugen, wenn die Leistung von Algorithmen, die Basis der Logarithmen nicht angegeben, da das Ergebnis Onley ändert sich um einen konstanten Faktor, wenn wir eine andere Basis verwenden. Daher wird in der Regel ein konstanter Faktor bei der Analyse von Algorithmen ignoriert. 12. Big O Zusammenfassung: mit dedizierten diesem gesamten Abschnitt toe die größere Notation. Das Verständnis der Zeitkomplexität ebnet die Arbeit mit Algorithmen. Wir haben über konstante Zeitkomplexität gesprochen, bei der die Ausführungszeit konstant ist und nicht von der Importgröße abhängt. Das Überprüfen des ersten Elements eines Arrays oder das Abrufen eines Elements aus einem Wörterbuch sind gute Beispiele für die konstante Zeitkomplexität. lineare Zeitkomplexität beschreibt einen Algorithmus, dessen Ausführungszeit in direktem Verhältnis zur Größe der Eingabe wächst . Zum Beispiel, Aufzählung durch die Elemente der Ehrenwerke in linearer Zeit, die Ausführungszeiten von quadratischen Zeitalgorithmen steigen als ein Quadrat der Importdaten, die Größe quadratische Zeitkomplexität wird durch eine Schleife erzeugt verschachtelt in eine andere Schleife, wie wir in unserer Multiplikationstabelle gesehen haben. Beispiel. Versuchen Sie, polynomiale Zeitkomplexität wie quadratisch, aquatisch oder kubisch zu vermeiden , da es zu einem enormen Leistungsengpass werden kann. Logarithmische Zeit beschreibt komplexe Algorithmen wie die schnelle Sortierung und zeigt ihre Vorteile bei der Arbeit mit größeren Datensätzen in. Die kommenden Abschnitte ohne in die Welt der Algorithmen werden den Unterschied zwischen dem naiven Brute-Force-Ansatz und dem, den wir mit Blick auf Effizienz implementieren, exportieren . 13. Abschnitt 3: Rekursion: in der Programmierung. Wiederholung kann mit Schleifen wie der Four Loop oder der While Loop beschrieben werden. Eine andere Möglichkeit besteht darin, Riker Shin zu verwenden. Wir begegnen Rikers selten. Warum? Studieren von Algorithmen und Datenstrukturen. Daher ist es wichtig zu verstehen, was Rickerson ist. Ich werde Ihnen zeigen, wie Incursion durch Lebenscodierungsbeispiele funktioniert. Rickerson ist eine nützliche Technik, aber es kommt nicht ohne Fallstricke. Ich denke, es ist dieser Abschnitt, indem Sie zeigen, wie Sie häufige Probleme vermeiden können, wenn Sie Rikers bei seinen fünften Projekten verwenden . 14. Was ist Recursion?: Lassen Sie uns klarstellen, was Ryker-Version ist. Per Definition ist die Aufzeichnung eine Möglichkeit, ein wieder auftretendes Problem zu lösen. Meine wiederholte Lösung ähnlicher Unterprobleme in der Programmierung können wir rekursive Funktionen haben. Die Funktion ist rekursiv. Wenn es sich selbst verursacht, kann das Auto direkt passieren, wie in diesem Fall oder indirekt. Wenn die Funktion eine andere Funktion verursachen, die wiederum die erste Funktion gut aufruft, stoßen oft rekursive Datenstrukturen zu einer Datenstruktur rekursiv ist, wenn Sie sie in Bezug auf sich selbst beschreiben können . beispielsweise Eine verknüpfte Liste kannbeispielsweiseals Listenknoten beschrieben werden, gefolgt von einer verknüpften Liste. In Ordnung, lassen Sie uns eine rekursive Datenstruktur implementieren. Also hier ist ein einfaches Notizglas. Jede Notiz kann über die nächste Eigenschaft mit dem nächsten Knoten verknüpft werden. Die Notiz auch, wer einen Wert vom Typ string hat. Schließlich biete ich eine anfängliche Isar an, die den Wert Eigenschaft festlegt. Nun, da wir keinen Typ haben, lassen Sie uns eine der verknüpften Liste sein. Zuerst erstelle ich jede Note und weise ihr einen Wert zu, der ihrem Namen entspricht. Dann sagte ich, die nächste Eigenschaft jeder Notiz, um eine Link-Liste zu bilden. Die nächste Notiz für Knoten 1 ist Nein zu für Nein zur nächsten Note wird Nein sein. Drei. Und schließlich beende ich die verknüpfte Liste, indem ich die nächste Notiz für Note 3 zum Knien setze. Lassen Sie uns nun die Funktion implementieren, die die verknüpfte Liste umkehrt und den Wert in jedem Knoten prinzen . Ich werde die Funktion Parse-Knoten aufrufen, die persönliche. Seine Funktion nimmt einen Parameter vom Typ Knoten. Wenn der Eingang Nein, diese Neil Ich verlasse die Funktion. Andernfalls drucke ich den Wert des angegebenen Knotens aus. Als nächstes nannte ich das Personal seine Funktion rekursiv Lee, indem ich den nächsten Knoten übergebe. Schließlich rufe ich die Balkennotenfunktion mit der ersten Note als Eingabeparameter auf, der Konsul zeigt die erwarteten Werte an. Da die Datenstruktur rekursiv ist, konnte ich Riker Schienbeinzehe mit einer rekursiven Funktion iteriert verwenden. Datensätze in erzeugen nicht notwendigerweise schnelleren oder effizienteren Code, aber es bietet normalerweise eine elegante Alternative zu beiden. Dave nähert sich und benötigt weniger Codezeilen 15. Wie funktioniert Recursion ?: Bisher haben wir einige Beispiele für rekursive Funktionen und Datenstrukturen gesehen. Jetzt schauen wir uns an, wie Rikers in der Arbeit. Ich werde die Faktorial von einer positiven Ganzzahl berechnen. Und das ist ein Problem, das mit Ryker Shin gelöst werden kann, da die Fakultät als das Produkt von den ganzen Zahlen von eins bis Ende definiert ist. Hier ist also eine schnelle faktorielle Funktion, die die faktorielle einer positiven Ganzzahl berechnet. Die Funktion übernimmt vorzeichenlose Ganzzahl als Argument. Wenn der Eingabeparameter kleiner ist als die Funktion gibt einen zurück. Andernfalls die Funktion das Produkt aus der Eingabe zurück und das Ergebnis aus Aufruf der Funktion mit einem Argument, das um eins kleiner ist. Die rekursiven Kosten werden fortgesetzt, bis die Funktion mit einem Wert aufgerufen wird, der kleiner als zwei ist . Um zu verstehen, wie Datensätze in funktioniert, hier ist eine grafische Darstellung, was bei der Berechnung des Faktors von drei vor sich geht. Immer wenn ein verschachtelter Aufruf stattfindet, wird die Ausführung des früheren Aufrufs angehalten und sein Status gespeichert. Der Snapshot seines Kontexts, das heißt, es sind gute Eingabeparameter und lokale Variablen wird beibehalten. All diese Informationen werden in einer Struktur gespeichert, die als Caustic oder Execution Pake bekannt ist. Der Caustic ist eine Stapelstruktur, die das Wrack von dem Punkt abhält, an dem die Kontrolle zurückgegeben werden soll , nachdem ein Unterprogramm seine Ausführung beendet hat. Wenn die Ausführung des verschachtelten Aufrufs abgeschlossen ist, wird sein Kontext zerstört und das Steuerelement wird an den Kragen zurückgegeben. Schließlich kommen wir zurück zum allerersten Funktionsaufruf. Bis dahin werden alle verschachtelten Kontexte zerstört, und das Endergebnis wird an den Kragen zurückgegeben. Jetzt wechseln wir zu Ex Corde. Ich habe ein Spielplatzprojekt abgestuft. Beginnen wir mit der Implementierung einer Funktion, die cock die faktorielle einer positiven Ganzzahl ist, und die Funktion nimmt eine 64-Bit-Ganzzahl ohne Vorzeichen als Argument, und es gibt auch diesen Typ zurück. Dieses Problem kann mithilfe von Aufzeichnungs-Sees gelöst werden. Die Fakultät ist definiert als das Produkt aus den Inter Juroren von einem Zehenende, die faktorielle off one und null ist eins, also drehen wir eins für die Eingabe. Klüger als zu. Andernfalls die Funktion das Produkt aus der Eingabe zurück und das Ergebnis aus Aufruf der Funktion mit einem Argument, das um eins kleiner ist. In Ordnung, lasst uns unsere Funktion ausprobieren. Und in der Tat, faktorial off drei ist sechs. Jetzt versuchen wir es mit einer größeren Zahl. Sagen wir dann, Ordnung, jetzt, versuchen wir es mit 20. Und wie wär's mit 30? Hoppla, wir haben einen Fehler. Dies liegt daran, dass das Ergebnis größer wäre als der Maximalwert, der dargestellt werden kann. Mit vorzeichenloser 64-Bit-Ganzzahl drucke ich vor Ort in 64 Max toe den Rat aus. Dies ist also die größte Zahl, die wir mit einer 64-Bit-Ganzzahl ohne Vorzeichen darstellen können, und die Faktorial von 21 ist bereits größer als das. Jetzt gibt es keine Unterstützung für große ganze Zahlen in Swift. Dennoch gibt es einen großen Prototyp im offiziellen Swift-Repository. Sie können es in der Master-Suite finden. Rep. Oh, unter Testprototypen wähle ich falsch aus und speicherte dann die Seite als schnelle Quelldatei. Als nächstes werde ich es zu unserem Spielplatzprojekt hinzufügen. Wir brauchen diesen Import nicht, und ich werde auch die Tests außer diesen Typ-Alias loswerden. Jetzt kann ich den großen Intertype benutzen. Also lassen Sie uns Reflektor r faktorielle Funktion. Ich werde begin für das Eingabeargument verwenden. Beginnen Sie auch für den Rückgabetyp. Lassen Sie uns nun unsere neue Funktion ausprobieren. Es funktioniert bereits mit 30, so dass wir sogar die sehr weiter erhöhen können und das Ergebnis wird eine große Anzahl sein , wie Sie im Moment sehen werden. Hoffentlich werden wir den Anfangstyp bald in der offiziellen Sift Library sehen. Bis dahin können Sie es benutzen, aber es ist auf eigenes Risiko. 16. Rekursion Fallstricke: Rickerson ist großartig, aber es kommt nicht ohne Beat. Für uns ist das größte Problem unendlich. Ryker Shin. Ich werde es illustrieren. Mit Exco Playground Project implementiere ich eine Funktion, die einige von den ersten und positiven Ganzzahlen berechnet. Ich nenne die Funktion schlecht. Einige Zehe machen deutlich, dass es nicht der richtige Ansatz ist, um dieses Problem zu lösen. Ich habe Ihnen die richtige Lösung gesehen, die auf einer einfachen Formel in einer kommenden Lektion beruht, so dass einige, außer auf Eingabeparameter und Off-Typ int und Rückgaben auf Integer, einen rekursiven Ansatz verwenden. Die Funktion gibt zurück, die einige aus dem Eingabeparameter und das Ergebnis aus, das sich mit einem Argument aufruft, das um eins kleiner ist . In Ordnung jetzt, lassen Sie es uns mit, sagen wir, drei schließlich Laufzeitfehler versuchen sagen wir, . Natürlich, um die Ursache zu verstehen, lassen Sie uns schnell zusammenfassen, wie Rickerson funktioniert. Jedes Mal, wenn belästigt Anruf tritt eine Aufzeichnung aus. Der aktuelle Kontext wird erstellt und als neuer Stick Frame an der Spitze des Stapels hinzugefügt, und jedes Mal, wenn ein Auto zurückkehrt, wird der obere Stickrahmen entfernt. Der Stack ist ein besonderer Teil des Speichers, der für schnelle statische Zuweisungen verwendet wird. Jede Anwendung hat einen Stack, und Moody s Kreditanträge haben einen Stack pro Thread. Der Stapel hat eine endliche Größe. also Wenn wiralsoverschachtelte Funktionen aufrufen und keine dieser Funktionen zurückgeben, wurde der verfügbare Stack-Speicherplatz leer. Wenn der verfügbare Speicher für den Caustic überschritten wird, stürzt der Athlet mit einem Stapelüberlauffehler ab. Lassen Sie uns unser Bestes untersuchen. Irgendwelche Funktion. Es gibt keine Bedingung, die die Ausführung des verschachtelten Aufrufs immer und immer wieder verhindert. Ich werde das Gericht leicht ändern, um den Wert vom Eingabeargument zu drucken, wenn wir die Funktion aufrufen. Jetzt können wir deutlich sehen, dass die Ausführung nach zwei rekursiven Kursen nicht stoppt, wie es sollte. Das bedeutet, dass der häusliche Kontext nicht zerstört wird und die Stack-Frames nicht entfernt werden. Wir weisen Speicher auf dem Stapel zu, ohne ihn zuzuweisen, was schließlich durch den Stapel führt. Überlauf-Ausnahme 17. Wie vermeide ich unendliche Rekursion?: , um unendliche Ryker Shin zu vermeiden. Jede rekursive Funktion muss mindestens eine Bedingung haben, die die verschachtelten Kosten für sich selbst verhindert . Dieser Zustand ist auf Gott basierter Fall. Gehen wir also zurück zur besten Funktion und fügen Sie den fehlenden Basisfall hinzu. Das Problem ist, dass Wette einige Ursache selbst, wie wir weiter abnehmen, Thean legte Argument und wir brauchen den Basisfall hier. Das ist eine Bedingung, die die Funktion zurückgibt, ohne einen weiteren rekursiven Aufruf auszuführen . Wir sind nur an den einigen positiven Ganzzahlen interessiert. Also, wenn das Eingabeargument Null ist, können wir einfach Null zurückgeben. Wenn ich die Funktion nach dieser Änderung ausführe, erzeugt sie das erwartete Ergebnis. Aber funktioniert diese Überprüfung wirklich für alle Eingabewerte? Lasst es uns mit Verstand überprüfen, Swan. Nein, da ich die Funktion nur nach Null überprüfe, da Laufzeitabsturz für negative Eingaben abstürzt, müssen wir auch sicherstellen, dass die Funktion tatsächlich in Richtung des Basisfalls vorschreitet. Ich muss den Basisfall so ändern, dass er nicht nur den Wert Null, sondern auch negative Werte abkühlt. Jetzt wird diese bedingte Aussage funktionieren. Dennoch ist eine Guards-Anweisung besser geeignet, weil sie uns zwingt, die Funktion zu verlassen, die ich weiß , dass einige Programmiersprachen Überprüfungen eingebaut haben, um Stapelüberläufe zu verhindern. Erinnere dich an diese Regeln. Wenn Sie rekursive Lösungen in Swift und Jack implementieren, rekursive Funktionen gründlich durch Komponententests, die auch Edge-Fälle cower. 18. Abschnitt 4: Die Macht der Algorithmen: in diesem Abschnitt werden wir einen genaueren Blick auf die Bedeutung und die Vorteile von Algorithmen und algorithmischem Denken, das wir über die große oder Notation im vorherigen Abschnitt gesprochen haben. Wir haben gesehen, dass unsere Wahl, ein Problem zu implementieren, einen großen Unterschied machen kann, wenn es um die Leistung und die Skalierbarkeit geht. Unsere Lösung ist schrecklich. Denken ist die Fähigkeit, sich einem Problem zu nähern und die effizienteste Technik zu finden, um es zu lösen. Um die Macht von Algorithmen zu demonstrieren, werden wir die folgenden Probleme lösen. Wir berechnen die einige der ersten und natürlichen Zahlen. Dann werden wir die Funktion implementieren, die, gegeben ein Array und der Wert gibt die Indizes aus zwei verschiedenen Elementen, deren einige gleich dem Zielwert ist. Schließlich werden wir die Berechnung des Gleichgewichtsindex von Honoree gehen. Der Gleichgewichts- oder Balance-Index stellt den Index dar, der die Arrays so aufteilt, dass die Summe der Elemente, die niedrigere Indizes gleich der Summe der Elemente an höher ist in diesem ist, werden wir zuerst einen naiven Ansatz verwenden, dann wird implementieren Sie eine Lösung mit Blick auf Effizienz. Ich werde Ihnen zeigen, wie einige grundlegende Mathematik und das Wissen über sift Sprachfunktionen und Datenstrukturen uns helfen können, sauberere und leistungsstärkere Lösung zu implementieren. 19. Sum(N) berechnen: Unsere erste Aufgabe ist es, die Funktion zu implementieren, die einige der ersten und natürlichen Zahlen berechnet. Wir fangen mit dem naiven Ansatz an. Dann werden wir einen effizienteren Weg implementieren, um dieses Problem zu lösen, indem wir eine Formel verwenden, die mehr als 2000 Jahre alt ist. In Ordnung, also wechseln wir zu unserem ausschließlichen Spielplatzprojekt. Ich finde eine Funktion namens einige, die ein einzelnes Argument benötigt. Dieses Argument stellt die Anzahl der natürlichen Zahlen, die einige wollen wir die funktionalen Rückgaben berechnen , eine vorzeichenlose Ganzzahl, die den einigen gibt, die wir eine sehr einfache Logik implementieren. Wir fassen alle Zahlen zusammen, beginnend mit einer bis zum Wert des Eingabeparameters. Und aufgrund dieser Schleife hat unsere Funktion eine lineare Zeitkomplexität. Wir können dies bestätigen, indem wir die Sonnenfunktion mit stetig zunehmender und Werte die Ursache aufrufen. Ein Protokoll zeigt, dass die Ausführungszeit linear mit der Eingabe zunimmt. Obwohl Dysfunktion die Aufgabe erledigt, gibt es eine bessere Möglichkeit, die Summe aus den ersten und natürlichen Zahlen zu berechnen. Wir werden uns auf eine einfache Formel verlassen. Carl Friedrich Gauß soll diese Beziehung in seiner frühen Erde gefunden haben. Allerdings war er nicht der erste, der diese Formel entdeckt hat. Es ist wahrscheinlich, dass sein Ursprung auf die Kategorien zurückgeht, und es war bereits im sechsten Jahrhundert bekannt. Vor Christus. Die Vorteile der Verwendung dieser Formel werden deutlich. Wenn Sie sich einige Beispiele ansehen, um die einige der ersten 3 natürlichen Zahlen zu berechnen, können wir sie einfach hinzufügen. Zusammen erhalten wir die gleichen Ergebnisse mit der neuen Formel. Wenn die Zahl zunimmt, wird offensichtlich, dass die Formel eine sauberere und kürzere Lösung gibt. Also lassen Sie es uns umsetzen. Mit Swift arbeitet die summenoptimierte Funktion in konstanter Zeit. Die Ausführungszeit hängt nicht von der Eingabe ab. Lassen Sie uns die gleichen Leistungstests ausführen, wie wir es für die einige Funktion getan haben. Die Ergebnisse belegen, dass die Ausführungszeiten nicht. Sehr. Unabhängig von der Importgröße. Es gibt nur einige geringfügige, vernachlässigbare Unterschiede im Bereich der Mikrosekunden, aber kein großer Vorteil. Aus dem linearen Algorithmus ist seine Leistung. Lassen Sie uns die beiden Methoden vergleichen, die einige optimieren, effizienter, auch für kleinere Werte, und der Unterschied wächst nur mit der Eingabe. Diese Diagramme visualisieren ist die Laufzeiten aus den beiden Funktionen. Die optimierte konstante Zeitfunktion hängt nicht von der Eingabe ab, im Gegensatz zu einer Funktion, die in linearer Zeit ausgeführt wird. Durch die Anwendung dieser cleveren Formel gelang es uns, eine Lösung mit der optimalsten Zeitkomplexität zu implementieren. In der nächsten Vorlesung werden wir ein schwierigeres Problem lösen. 20. Pair Herausforderung: hier ist unsere nächste Herausforderung. Unsere Aufgabe ist es, eine Funktion zu schreiben, die angesichts eines Arrays und des Zielwerts null basierende Indizes von zwei verschiedenen Elementen zurückgibt, die einige gleich dem Ziel sind. Etwas. Wenn solche Elemente nicht vorhanden sind, sollte die Funktion zurückgeben. Neil, zum Beispiel, für den Bereich der Zahlen 12234 Und der Zielwert für unsere Funktion sollte die Abstürzen Indizes 12 oder 03 zurückgeben Zuerst werden wir die Lösung implementieren, die auf sauren Iterationen beruht, weil der bösen Wiederholungen. Dieser Algorithmus hat eine quadratische Zeitkomplexität. Dann werden wir einen Algorithmus entwickeln, der in der Lena-Zeit statt quadratischer Zeit arbeitet . In Ordnung, Zeit, etwas zu programmieren. Wie üblich setzen wir den Brute-Force-Ansatz um. Zuerst gingen wir durch das Array und überprüfen jeden Wert Ausgehend vom äußeren Index haben wir den Rest des Arrays gescannt. Wenn wir eine Zahl finden, so dass die beiden Zahlen addieren sich zum Ziel, wir haben den Topper zurückgegeben. Wie wir fortfahren durch die Saberi zu iterieren. Dieser Algorithmus verwendet zwei verschachtelte Schleifen, was quadratische Zeitkomplexität bedeutet. Um genau zu sein. Diese Funktion hat eine schlechteste Zeitkomplexität aus und quadriert, plus und geteilt durch zwei. Wo N ist die Größe aus dem Impuls? Drei. Es ist nicht n Quadrat, da Vienna Look nicht durch das gesamte Array iteriert. Lassen Sie uns durch die Schritte gehen, um diese Formel zu finden. Die äußere Schleife iterierte durch das gesamte Array, was eine it orations die inneren Schleifengastronomie und minus einmal Kraft als l minus zwei Mal und so weiter gibt . Wenn der äußere Loop Richard der vorletzte Index, die innere Schleife auf wiederholt, die Summe herausfinden will, die sie in der inneren Schleife durchführen , müssen wir die Summe von der ersten und minus eine Zahl berechnen. Wir können die Formel verwenden, die wir in der vorherigen Vorlesungsspitze gelernt haben. Berechnen Sie die innere Schleifenzählung, die ein Minus einmal und minus eins plus 1/2 ist, was n minus ein Mal und über jetzt zusammen Gesamtzahl davon ergibt. Wir müssen die Anzahl der äußeren Schleifen hinzufügen, damit unsere Funktion eine Zeitkomplexität aus und quadriert hat , plus und oder zwei. Lassen Sie uns nun eine Lösung implementieren, die sich nicht auf verschachtelte Schleifen stützt. Mit anderen Worten, wir werden vermeiden, die Rate klug zu erschrecken, um Zahlen zu finden, die sich auf den Zielwert summieren . Wir werden eine einzige Schleife verwenden, um Restaurants durch den gesamten Weg. Für jede Zahl prüfen wir, ob die Differenz zwischen dem Sollwert und der gegebenen Zahl im Suchtdatensatz gefunden werden kann . Wenn der Unterschied gefunden wird, haben wir unsere zwei Zahlen und wir haben die Spitze mit den Indizes zurückgegeben, während wir den aktuellen Index speichern , der Unterschied ist der Schlüssel und wir essen es weiter nein, dass beide Wörterbuch Einfügung und Suche geschieht konstante Zeit. Daher wirken sich diese Operationen nicht auf die Zeitkomplexität unserer Funktion aus. Wir haben es geschafft, die Zeitkomplexität zu reduzieren, um zu bestellen, und weil wir nur einmal durch das Array Analphabeten, lassen Sie uns jetzt die Leistung der beiden Funktionen vergleichen . Zuerst führen wir unseren Test mit einem Array aus, das 10 zufällige Einführen enthält. Die optimierte Funktion funktioniert in der Regel besser als die mit quadratischer Zeitkomplexität . Doch der Geschwindigkeitsunterschied ist nicht so überzeugt Singer. Für 50 Artikel beginnen wir spürbare Unterschiede zu sehen. Die Vorteile der linearen Zeitkomplexität liegen auf der Hand. Die Ergebnisse sprechen für sich selbst, da wir die Größe des Arrays weiter erhöhen. In der nächsten Vorlesung werden wir ein weiteres interessantes Problem lösen, genannt den Equilibrium Index 21. Finde den Equilibrium Index: in der folgenden Demo werden wir eine Funktion Toe zu bauen, Finden Sie die Gleichgewichtsindizes von Honore. Der Equilibrium Index von Honore ist ein Index, so dass die Summe der Elemente bei niedrigeren Indizes gleich der Summe der Elemente bei höheren Indizes ist. Zum Beispiel in Honore A mit den Zahlen minus drei bis minus 21 und minus zwei eins ein Gleichgewichtsindex, weil das Element, das Index Null gleich der Summe der Elemente ist, die zwei und drei und vier zwei indiziert , auch auf Gleichgewichtsindex. Da die Summe der Elemente, die in dieser Null und eins gleich der Summe aus Elementen ist, die in diesem drei und vier ist, werden wir die Funktion implementieren, die Honore gegeben Theokoles, Librium-Indizes oder Neil zurückgibt , wenn der Bereich keine Gleichgewichtsindex. Zuerst werden wir eine Lösung implementieren, die zwei verschachtelte Schleifen verwendet. Dann werde ich Ihnen eine Möglichkeit zeigen, unseren Algorithmus zu optimieren, indem Sie einige grundlegende Mathematik anwenden, wird mit einem Algorithmus kommen, der in linearer Zeit ausgeführt wird. Jetzt wechseln wir zum X-Gericht. Die Gleichgewichtsfunktion verwendet drei Schleifen die äußere Schleife Restaurants zu allen Elementen aus Theorie, wir müssen innere Schleifen, um herauszufinden, ob der aktuelle Index groß durch die äußere Schleife ist ein Gleichgewichtsindex oder nicht. Die erste in der Schleife verfolgt einige der Elemente bei niedrigeren Indizes. Die zweite innere Schleife hält den Überblick über einige Off-Items bei höheren Indizes. Mit anderen Worten, mit der Plädotheorie an der Position außerhalb des äußeren Index, dann vergleichen wir einige der Elemente von den beiden Sabri. Wenn die Summen gleich sind, haben wir einen Gleichgewichtsindex gefunden, und wir haben zur Theorie der Indizes hinzugefügt, während wir weiter iterieren, die schlimmste Zeitkomplexität dieser Lösung ist quadratisch. Die Aktualisierung der linken und rechten Summen mit inneren Schleifen ist ein einfacher, aber auch sehr ineffizienter Ansatz. Lassen Sie uns versuchen, eine Lösung zu finden, die keine verschachtelten Schleifen erfordert. Die Idee ist zusammen erzählt uns ein Teil des Arrays. Zuerst verwenden wir die reduzierte oder eine Methode, um die Summe aller Elemente in der Theorie zu berechnen, dann wir Italien, durch das gesamte Array der linken. Einige sind ursprünglich auf Null initialisiert. Wir aktualisieren die linke, einige, indem wir T-Elemente hinzufügen, während wir durch das Array iterierten, können wir einige der Elemente der rechten Zusammenfassung erhalten , indem wir die Elemente eins nach dem anderen von der Gesamtsumme subtrahieren. Mit diesem Algorithmus müssen wir nur einmal durch das Array schauen. Diese Funktion hat eine lineare Zeitkomplexität, die wegen der reduzierten Funktion und der Schleife zum Ende angeordnet ist. Lassen Sie uns jetzt unsere armen vier Monate laufen, Tess für fünf Dinge. Die optimierte Variante funktioniert etwa zweimal besser und über 20-mal besser für 50 Artikel bei Verletzungen ab 200 Artikeln. Die Gleichgewichtsoptimierte Funktion läuft etwa 1000 Mal schneller als die Funktion, die verschachtelte Schleifen verwendet. Der Unterschied wächst schnell mit der Eingabegröße für größere Arrays. Finden von Thea-gruseligen um-Indizes mit der Optimierungsvariante nimmt einen Bruchteil von der Laufzeit aus dem Brute-Force-Ansatz, wie wir erwartet haben, die Funktion mit quadratischer Zeitkomplexität ist empfindlicher für Importdatengrößen als die Funktion mit linearer Zeitkomplexität. Dies ist ein weiteres Beispiel, das zeigt, wie wichtig es ist, den richtigen Algorithmus zu finden 22. Die Macht der Algorithmen - Zusammenfassung: in diesem Abschnitt haben wir einige praktische Beispiele zur Lösung von Problemen mit zwei verschiedenen Ansätzen gesehen. Die Messerimplementierungen führten zu den richtigen Ergebnissen. jedoch, Sie beginnenjedoch,ihre Schwächen zu zeigen, wenn die Eingabegröße größer wird. Durch effizientere Techniken reduzieren wir Zeit, Komplexität und damit die Ausführungszeit unserer Lösungen erheblich. den optimalen Algorithmus zu entwickeln, erfordert Forschung und tieferes Verständnis für das Problem. Wir versuchen, Meth Gears zu lösen und die Fähigkeit, die Funktionen aus der gegebenen Programmiersprache anzuwenden , wird glücklicher bei der Erstellung effizienterer Algorithmen. Die Dime-Komplexität oft Algorithmus, ist entscheidend, wenn es um die Leistung geht. Tun Sie Ihr Bestes, um polynomiale und schlechteste Zeit Komplexitäten zu vermeiden. Nassib-Schleifen sollten immer ein Warnzeichen sein, wenn Sie ihnen begegnen. Denken Sie an andere Alternativen, um dieses spezielle Problem zu lösen. Um zusammenzufassen, sollten Sie die Leistungsengpässe hervorheben. Mit dedizierten Kommentaren, Implementierung von Komponenten- und Leistungstests, wurden sie aufgetaucht. Die Probleme, die sonst verborgen bleiben, versuchen schließlich, das Problem zu lösen, ohne möglichst auf die Wiederholungen der NASA verlassen zu müssen. Jetzt wissen wir, worum es bei der größeren Notation geht. Wir sind uns auch bewusst von den Vorteilen von Algorithmen und algorithmischem Denken Lassen Sie uns weiter mit der Studie von Algorithmen im nächsten Abschnitt fortfahren , wir werden einen genaueren Blick auf die beliebtesten grundlegenden Sortieralgorithmen werfen. Wir werden analysieren, wie die Sortieralgorithmen funktionieren, und wir werden sie von Grund auf mit Swift implementieren. 23. Abschnitt 5: Generika: bevor wir tiefer in Algorithmen eintauchen, ist es wichtig, über das verwandte Thema Datenstrukturen zu sprechen. Datenstrukturen sind Container, die die in unseren Programmen verwendeten Daten enthalten. Die Effizienz dieser Datenstrukturen wirkt sich auf das gesamte Softwaresystem aus, daher ist es wichtig zu verstehen, wie sie funktionieren und welche für die jeweilige Aufgabe zu wählen ist. In diesem Abschnitt werden wir über Generika und das Gebäude sprechen. Swift Sammlungstypen Generika sind die Mittel, um nicht nur nützlichen, sondern auch wiederverwendbaren Code zu schreiben . Es wurde auch verwendet, um Datenstrukturen zu implementieren, die nicht nur auf einen Datentyp beschränkt sind . Dann werfen wir einen genaueren Blick auf die fünften Sammlungstypen des Gebäudes. Wir werden über das Array, die Menge und den Wörterbuchtyp sprechen. 24. Warum Generika?: Generika stehen im Kern der schnellen Standardbibliothek. Sie sind so tief in der Sprache verwurzelt, dass man sie nicht vermeiden kann. In den meisten Fällen werden Sie nicht einmal bemerken, dass Sie Generika verwenden. Um die Nützlichkeit von Generika zu veranschaulichen. Wir versuchen, ein einfaches Problem zu lösen. Nehmen wir an, wir müssen Typen erstellen, die Paare von verschiedenen Werten halten. Angenommen, wir brauchen einen Paartyp, der zwei Strings enthält, könnten wir eine Struktur wie diese erstellen. Als nächstes brauchen wir ein Paar, das sich an Inter-Werte hält. Also deklarieren wir unsere in Ersatztyp. Dann brauchen wir auch den DYP, der schweben muss. Los geht's. Wie wäre es mit einem Paar, das Dateneigenschaften hat? Wir begrüßen noch eine weitere Paarstruktur namens Datenpaar. Und wenn wir das String-Doppelpaar brauchen, erstellen wir den entsprechenden Typ, richtig? Könnte es einfacher sein? Wir können jetzt unsere neu erstellten Typen verwenden, wann immer wir sie brauchen. Wir dürfen uns nur an ihre Namen erinnern. Wann immer wir einen neuen Paartyp brauchen, haben wir einfach erstellt. Ist das wirklich der Weg zu gehen? Definitiv nicht. Wir müssen die Explosion stoppen, bevor sie aus der Hand kommt. 25. Generische Typen: Würde es nicht? Weil Zehe nur einen Typ haben, der mit einem beliebigen Wert arbeiten kann. Generische Typen kommen zur Rettung. Mit Generika können wir eine Paarstruktur definieren, die mit jedem Typ verwendet werden kann, den wir Ort Wetter anstelle von konkreten Typen für die Eigenschaften in der Struktur T eins und T zwei R Polizeiaufträge , die überall innerhalb der Typen verwendet werden können -Definition. Außerdem nennen wir einfach unser geschlagenes Paar. Da es sich um einen generischen Typ handelt, müssen wir die unterstützten Typen nicht im Namen unserer Struktur angeben. Jetzt können wir Paare von jedem Typ mit der folgenden Syntax erstellen. Wir können sogar den Ort überspringen, wo es Typen gibt. Der Compiler ist intelligent genug, um den Typ basierend auf dem Argumenttyp herauszufinden. Die Inferenz funktioniert, indem die bereitgestellten Werte untersucht werden. Warum das Gericht zusammenstellen? In Swift können wir unsere genetischen Klassen, Strukturen oder Enumeration genauso einfach definieren . Alles klar, lassen Sie uns, was nicht erzielt hat. Ich werde die Vorteile der Gen-Typen noch deutlicher machen. Dies war also unser erster naiver Versuch, die Paartypen zu erstellen. Eine Menge redundanter Code. Im Moment deklarieren wir die generische Version mit der Paarstruktur. Wir können alle spezifischen Paarstrukturen löschen. Jetzt, da sie weg sind, erhalten wir einen Compilerfehler. können wir, nicht wahr? Reparieren Sie das. Ich werde alle Verweise auf die alten Typen durch das generische Gegenstück ersetzen, das es generische Typen hat, das die Typexplosion gestoppt hat. Unser Code wurde nicht nur kürzer, sondern er ist auch wieder sichtbar. Als nächstes werden wir über generische Funktionen sprechen. 26. Generische Funktionen: generische Funktionen und Methoden sind ein weiteres leistungsfähiges Feature aus der schnellen Sprache. Eine generische Funktion oder Methode kann mit jedem Typ arbeiten, der Duplikationen und richtigen saubereren Code vermeiden kann . Beginnen wir mit der Programmierherausforderung, die wir brauchen, um eine Methode zu implementieren, die tut, ob Werte gleich sind. Zuerst haben wir die einfache Gleichheitsfunktion für Strings ziemlich unkompliziert definiert. Dann brauchen wir das gleiche Feature für Doppeltypen, keine große Sache. Was ist mit Dates? Zum Glück wird das auch nicht zu lange dauern, um zu implementieren. Dann müssen wir auch sagen, ob Dateninstanzen sind gleich getan jetzt. Du siehst wahrscheinlich, wohin das geht. Und wenn Sie die Lektion über Typenexplosion waren, wissen Sie, was ich sagen werde. Das ist nicht der richtige Weg. Die Implementierung einer neuen Funktion für jeden neuen Typ führt zu einer Menge von redundantem Code. Solch eine Gerichtsbasis ist schwer, die Nachrichten aufrechtzuerhalten. Wir sollten immer Code-Wiederholungen und Generika vermeiden. Helfen Sie uns auch, dieses Problem zu lösen . In Ordnung, lassen Sie uns das generische ist gleich Funktion erstellen. Die Syntax zum Schreiben einer generischen Funktion ähnelt dem, was wir verwendet haben, um generische Typen zu deklarieren . Wir geben den Ort an, an dem sie Typ zwischen Wut Klammern sind. Nach dem Funktions- oder Methodennamen können wir auf diesen Ort verweisen, wo es das Argument gibt, am wenigsten oder irgendwo im Funktionskörper. Wenn wir unseren Code so kompilieren, wie er jetzt ist, erhalten wir einen Fehler. Dies liegt daran, dass der Compiler nicht weiß, wie man zwei Instanzen außerhalb des Ortes vergleicht. Ob Typ, wir müssen sicherstellen, dass der Typ den Gleichheitsoperator implementiert, der da ist. Um das Äquator Rechnung Protokoll übernehmen muss die Gleichheit zu Operator implementieren, so müssen wir eine Typeinschränkung erzwingen. Typeinschränkungen angegeben, dass der Typ einem bestimmten Protokoll entsprechen oder von einer bestimmten Klasse erben muss . Lassen Sie uns die gerechte Typeinschränkung hinzufügen. Dies schränkt die Typen ein, die als Argumente in unserer Funktion verwendet werden können. Wir haben den Compilerfehler beseitigt. Jetzt kann die genetische Leichtigkeit Gleichheitsfunktion nur Instanzen von Typen akzeptieren, die das gerechte Protokoll übernehmen . Kontakt ist Hindernis, das nicht mit dem Äquator übereinstimmt, wo Protokoll unser Code nicht kompiliert, wenn wir versuchen. Es war die einfache Kernfunktion mit Instanzen zu kontaktieren. Also lassen Sie uns die gerechte Protokollkonformität hinzufügen, um den Äquator zu übernehmen, wo Protokoll wir den gleichen tow-Operator als statisches Mitglied implementieren müssen. Die Implementierung ist einfach. Wir prüfen, ob die Eigenschaften aus den beiden Argumenten übereinstimmen. Das Equitable Protocol definiert auch den ungleichen Operator. Wir müssen es nicht implementieren, obwohl die Standardbibliothek die vierte Implementierung bereitstellt. Dies verursachte den benutzerdefinierten Gleichwert-Operator und die Schwule. Das Ergebnis. Wir können Typbeschränkungen anwenden, auch Zehe generische Typen. Vielleicht erinnern Sie sich an das generische Paar, das wir in der vorherigen Lektion implementiert haben. Nehmen wir an, wir wollen die Typen auf diejenigen beschränken, die das vergleichbare Protokoll implementieren . Hier ist, was wir sollten, richtig. Mit dieser Typeinschränkung können wir nur Paarinstanzen erstellen, die das vergleichbare Protokoll übernehmen. Generika sind super für verwendet, und Swift macht es uns einfach, generische Typen und Funktionen zu implementieren und zu verwenden. In den folgenden Lektionen wurden die eingebauten schnellen Sammlungstypen 27. Abschnitt 6: Schnelles Sammeln: Willkommen in einem anderen Abschnitt der schnellen Algorithmen und Datenstrukturen Bewertungen in diesem Abschnitt. Wir werden einen genaueren Blick auf die fünften Sammlungstypen des Gebäudes werfen. Sweet bietet drei primäre Sammlungen. Wir sprechen über das Array, das auf Reihenfolge Reihenfolge der Elemente ist. Das Set, das sich auf einer neuen Bestellsequenz von eindeutigen Werten befindet, und das Wörterbuch, das unseren Speicher und überschüssige Schlüsselwertpaare in Swift ermöglicht. Das Array, die Menge und das Wörterbuch sind als generische Typen implementiert, wie wir im Abschnitt über Generika gesehen haben. Dies bietet eine große Flexibilität, da wir jeden Typ mit den generischen Sammlungen verwenden können. Sie können Instanzen von Gläsern, Strukturen und Feuerungen, oder jeden Gebäudetyp wie int float, double und so weiter speichern Strukturen und Feuerungen, oder jeden Gebäudetyp wie int float, . In Ordnung, fangen wir mit der Theorie an. 28. Das Array: Lob speichern Werte aus dem gleichen Typ in einer bestimmten Reihenfolge. Die Werte dürfen nicht eindeutig sein. Jeder Wert kann mehrfach angezeigt werden. Mit anderen Worten, wir könnten das Array als eine Reihenfolge definieren, Pailletten aus nicht eindeutigen Elementen. Wir erstellen auf dem Strahl mit der folgenden Syntax. Da es sich um einen generischen Typ handelt, müssen wir den Typ bereitstellen, der ein Rechen im Speicher ist. Dies ist ein Array aus in Typen. Was das bedeutet, ist, dass wir unser A nur innerhalb verwenden können. Es gibt eine kürzere Möglichkeit, Array zu definieren, indem die Zeit zwischen eckigen Klammern platziert wird. Dies ist die Kurzform, und es ist der bevorzugte Weg, um Honore zu definieren. Eigentlich gibt es nicht einmal sicher, ihre Art, ein Array von Ins für bestimmte Typen zu erstellen. Wir können uns auch auf steife Art Inferenz verlassen, Zehe erarbeiten den Typ des Arrays. Lassen Sie uns nun ein wenig über Typ-Inferenz schnelle Glückwunsch sprechen, der Typ basiert auf dem Brunnen, den wir zur Verfügung stellen, was uns vor einer Menge von Tippen retten kann. Typ-Inferenz hat jedoch seine Einschränkungen. Zum Beispiel, wenn wir unsere Weg so definieren, wird die Typ-Inferenz-Engine davon ausgehen, dass es sich um ein Array von doppelt so großen Raffinerie Off-Floats , wir müssen explizit den Flow-Typ bereitstellen. Jedem Element in Honore ist ein Index zugeordnet. Die Indizes beginnen bei Null, und ihr Wert wird für jedes nachfolgende Element implementiert. Für unser ursprüngliches Beispiel sehen die Indizes so aus. Wir können, entweder es durch Theorie und drucken Sie die Indizes mit Theorie Index off Instanzmethode Alles Ordnung Weniger als dies in X-Code. Hier ist ein Konsolenprotokoll. Wissen Sie, dass index off den ersten Index zurückgibt, wo der angegebene Wert in der Theorie erscheint, deshalb erhalten wir den gleichen Index für eins und zwei. Eine andere Möglichkeit besteht darin, die Arrays für jede Methode zu verwenden. Diese Methode führte Offenlegung für jedes Element in der gleichen Reihenfolge wie eine for-in-Schleife, und das Ergebnis ist das gleiche wie mit dem Fremdbeispiel. 29. Zugriff auf das Array: können wir auf die Elemente aus dem Rabei Index zugreifen. Das Array muss überschüssige Wunden für das erste und das letzte Element erleichtern. Nein, die erste und letzte Rückkehr. Optionale Werte. Wenn die Arrays leer sind, wird ihr Wert Neil sein. Wir haben dieses Sicherheitsnetz nicht, wenn der Zugriff auf das Array nach Index um Zeit Absturz auftritt. Wenn wir versuchen, einen Wert mit auf ungültigen Index abzurufen, können wir Abstürze verhindern, indem wir überprüfen, ob der Index innerhalb der Grenzen ist. Wenn ein Index größer ist als die Größe des Strahls, geht er über das letzte Element hinaus. Außerdem darf der Index keine negative Zahl sein. Wir können uns eine kürzere Form einfallen lassen. Der Strahl hat eine Eigenschaft namens Indizes, die hält, gut die tatsächlichen Indizes für den gegebenen Ray. Wenn es den angegebenen Index enthält, ist es gültig, ihn noch weiter zu schieben. Lassen Sie uns einen benutzerdefinierten sicheren Indexoperator erstellen. Wir implementieren den Betreiber in Honore. Erweiterungen und benutzerdefinierte Operatoren sind wirklich leistungsfähig. Sie lassen uns an Operatoren zu bestehenden Typen, ohne ihren Code zu ändern 30. Array verändern: bisher haben wir gesehen, wie man auf die Elemente von Honore in diesem Video zugreifen wird, wie man das Array zu ändern , um den Inhalt von Honore nach seiner Erstellung zu ändern. Wir müssen es einer Variablen und nicht der Konstante zuweisen. Dies ist, wie wir ein veränderbares Array erstellen können. Instanz. Die Theorie stellt unterschiedliche Instanz offen. Methoden zum Hinzufügen neuer Werte Wir können. Er war auf der Zehe. Fügen Sie ein neues Element am Ende von Honore auf Element einfügen, die Position verwendet die Einfügung gegeben werden . Bei der Instanz. Methode. Das neue Element wird vor dem Element am aktuellen Index eingefügt. Alle Elemente nach dem angegebenen Index werden verschoben. Eine Position nach rechts. Wenn Sie den letzten Index übergeben, wird das neue Element abgebrochen. Zehe das Array. Wenn Sie verwenden, fügen Sie at ein, stellen Sie sicher, dass der Index gültig ist. Andernfalls werden Sie im Laufzeitfehler enden. Nun, um ein Element aus einem Array zu entfernen, können wir die entfernt verwenden. In der Instanz Methode. Nachdem das Element entfernt wurde, wird die Lücke geschlossen. Ich weiß, dass der Index, den wir die entfernen diese Methode übergeben haben, gültig sein muss oder weil um die Zeit , Fehler Gott entfernen alle. Wenn Sie alle Elemente im Array loswerden möchten. Die Methode hat einen Keep-Capacity Parameter, der durch die vierte Kraft festgelegt ist. Vielleicht möchten Sie die Kapazität behalten, wenn Sie planen, das Rennen bald wieder war, das Array nicht mehr Speicher neu zuweisen müssen, was jetzt eine schöne Leistungsoptimierung sein kann, obwohl die Kapazität beibehalten wird, können wir die alte nicht wiederverwenden. Indus greift auf das Gebiet zu, in dem es veraltet ist. Indizes verursacht beim sofortigen Absturz als Faustregel. Überprüfen Sie immer, ob der Index außerhalb der Grenzen liegt, bevor Sie darauf zugreifen. Es gibt weitere Methoden. Entfernen Sie zuerst, entfernt und gibt das erste Element zurück, während Liste entfernen, entfernt und zurückgibt. Das letzte Element. Gehen Sie nicht zuerst entfernen oder entfernen Sie letzte auf einem leeren oder ein, wie es verursachen würde, wie Sie vielleicht bereits wissen. Laufzeitfehler. Wir sprachen über einige der am häufigsten war Array-Methoden. Ich schlage vor, dass Sie mit den Beispielprojekten runter und anfangen, an den Strahlen zu basteln. Paraden, Werte aus dem gleichen Typ in der Reihenfolge speichern. Die Theorie der Juden. Wenn die Reihenfolge der Elemente wichtig ist und wenn die gleichen Werte mehrmals erscheinen sollen , wenn die Reihenfolge nicht wichtig ist oder die Werte eindeutig sein müssen. Sie sollten lieber ein Set verwenden. Wir werden in den kommenden Lektionen über Sets sprechen. 31. Das Set: wir haben gesehen, dass die Rechen und speichern Elemente in einer bestimmten Reihenfolge, können wir sogar Schwierigkeiten in honoree haben. Was ist, wenn Sie eine Kollektion benötigen, die die Einzigartigkeit ihrer Elemente garantiert? Das Set ist die Antwort. Legen Sie eindeutige Werte ohne Reihenfolge fest und ein gegebener Wert kann nur einmal angezeigt werden. Neben der Menge für mathematische Mengenoperationen wie Vereinigung und subtrahieren verwendet, können wir eine Menge mit der folgenden Syntax deklarieren. Ich weiß, dass Sie die Kurzform nicht verwenden können, wie wir es für eine Gehaltserhöhung getan haben. Wenn wir es verteidigen, wie diese Swifts Art Inferenz-Engine es nicht herausfinden kann. Ob wir möchten, um Sie zu setzen oder vielmehr Honore, wir müssen angeben, dass wir einen Satz benötigen. jedoch Typinferenz warjedochnoch für die in der Menge verwendeten Werte arbeiten. Wenn wir die Menge mit einem Array aus in kleine Fehler initialisieren, wird die Typ-Inferenz-Engine den Typ int ableiten. Und wenn er buchstäblich Gleitkommazahl war, wird der In-for-Typ für die Werte doppelt sein. Lassen Sie uns nun die Hauptunterschiede zwischen den Sätzen auf der Erhöhung klären. Mein Blick auf diese Unterschiede wird in der Lage sein, den richtigen zu wählen, die ersten grundlegenden Unterschiede, dass das Set keine Duplikate zulässt. Werfen wir einen Blick auf ein Beispiel, wenn wir Honore erklären, wie dies vier Enden mit dem Wert eins enthalten wird. Wo ist die Menge mit den gleichen Liberalen deklariert wird nur einen Wert haben. Die redundanten Werte werden abgeskimmt. Der andere große Unterschied besteht darin, dass der Satz nicht die definierte Reihenfolge für seine Elemente bereitstellt . Zum Beispiel wird der folgende Gray seinen Inhalt in der angegebenen Reihenfolge drucken. Allerdings, für die mit den gleichen Werten definiert, ist die Reihenfolge nicht definiert. Wir können über die Werte in einem Satz mit einer for-in-Schleife generieren. Denken Sie daran, der Satz die spezifische Reihenfolge seiner Elemente nicht definiert. daher Nehmen Siedaherbei Bedarf nichts über die Reihenfolge an, in der die Elemente zurückgegeben werden. Iterieren einer bestimmten Reihenfolge namens Sordid-Methode, so hat die Elemente aus der Menge als Array zurückgegeben, sortiert mit dem weniger als-Operator. Dies ist die Ausgabe. Wir können auch die vier H-Sammlungsmethode mit Sets verwenden. Diese Methode führt seine Schließung für jedes Element in der Menge 32. Zugriff und Änderung des Satzes: Jetzt, da wir wissen, wie man ein Set erstellt, lassen Sie uns über den Zugriff und die Änderung seines Inhalts sprechen. Im Gegensatz zur Theorie das besagte keine Indizes, wir können die Invents-Instanzmethode verwenden, um zu überprüfen, ob ein Wert in der ersten Menge vorhanden ist gibt einen Fettdruck zurück, so dass wir es in bedingter Logik verwenden können, genau wie in in diesem Beispiel, wenn das Element nicht gefunden werden kann oder wenn die Menge leer ist. Enthält Rückgabefunktion. Apropos leere Sätze, wir können überprüfen, ob ein Satz Elemente durch diese leere Eigenschaft hat. Alternativ können wir die sets count Eigenschaft verwenden. Wie Sie vielleicht erraten haben, dass sich das Land dreht. Die Anzahl der Elemente in der Menge weiß, dass die Sets count und Capacity Eigenschaften unterschiedliche Werte zurückgeben können . Land dreht die Anzahl der vorhandenen Elemente im Set, während die Kapazität anzeigt, wie viele Elemente es speichern kann, ohne neuen Speicher zuzuweisen. Will darüber in einem Moment sprechen. Verwendet die Einfügungen, at instance, Methode, um neue Elemente zu der Menge hinzuzufügen. Um Elemente aus einem Satz zu entfernen, können wir die remote-Methode aufrufen. Das Auto tut nichts, wenn das Element nicht im geringsten ist, die remote-Methode gibt das Element zurück, das aus der Menge entfernt wurde. Wir können diese Funktion verwenden, um zu überprüfen, ob der Wert tatsächlich erweckt wurde, um alle Elemente in einem Satz Auto zu entfernen, entfernen Sie alle Sätze, entfernen Sie unsere Methode hat einen Keep Capacity Parameter, die durch die vierte Kraft gesetzt wird. Es hat den gleichen Effekt wie für eine Erhöhung, indem der Wert der Beibehaltung der Kapazität auf true gesetzt ohne dass der Compiler den SATs-Speicher nach dem Entfernen seiner Elemente beibehalten, sie müssen Speicher bei seiner nächsten Verwendung nicht neu zuweisen. 33. Festlegen von Operationen: das Set stellt nützliche Methoden, die uns grundlegende Operationen Union durchführen lassen erstellt einen neuen Satz mit allen Elementen in den beiden Sätzen. Wenn die beiden Sätze Elemente in gemeinsamem Onley haben, wird eine Instanz in der resultierenden Menge angezeigt. Nein, dass 35 und sieben in beiden Sätzen gefunden werden können. Die resultierende Menge enthält jedoch keine Duplikate. Das Ergebnis des Aufrufs der Schnittpunktsetinstanz. Methode ist eine Menge, die die Elemente, die in beiden Sätzen angezeigt wurden. Wir können auch einen Satz von einem anderen subtrahieren. Das Ergebnis enthält die Werte, die sich nur in der Quellmenge und nicht in der subtrahierten Menge befinden. Die symmetrische Differenzmethode Rückgaben werden mit dem Element festgelegt, das nur in beiden Mengen , aber nicht in beiden gesetzt ist. Das Set enthüllt viele andere nützliche Methoden, wie diejenigen, die uns auf Gleichheit und Mitgliedschaft testen lassen. Ich schlage vor, Sie mit den Beispielprojekten zu beginnen und mit Sets zu experimentieren 34. Das Hashable Protokoll: Hallo, da. Wir werden über das mashable Protokoll sprechen. Zuerst werde ich eine sehr einfache Struktur erstellen. Diese Struktur hat nur eine korrekt off-Typzeichenfolge. Nennen wir es Identitätsfeuer, ohne Ort zu belehren. Wir könntenzum Beispiel Honore erschaffen zum Beispiel . Ich werde die Kurzform verwenden, um die Theorie zu deklarieren. Einfach schlug USOC's. Und lassen Sie uns eine einfache geschlagen mit der identifizieren ihre I D. Dieses Gold umfassen gut. Wir haben keine Probleme. Lassen Sie uns versuchen, dasselbe zu tun. Aber dieses Mal werde ich ein Set deklarieren. Leider gibt es keine Möglichkeit, es war eine verkürzte Form für einen Satz, weil der Compiler keine Möglichkeit hat, es von Honore zu unterscheiden. Grundsätzlich muss ich dem Compiler sagen, dass es sich um einen bestimmten Typ handelt. Los geht's. Jetzt. Wenn ich versuche, meinen Code zu kompilieren, erhalte ich einen Fehler. Der Compiler sagt, dass unser Typ nicht mit dem möglichen Protokoll übereinstimmt. Alles klar, was bedeutet das? Das Set ist ein besonderer, freundlicher Swift Sammlungstyp. Im Gegensatz zu Raise kann ein Satz keine Duplikate haben. Um nach Duplikaten zu suchen, muss der Satz über Typ sein. Das hat eine Möglichkeit zu sagen, ob eine Instanz eindeutig ist. Swift verwendet einen Hash-Wert für diesen Zweck. Der Hash-Wert ist ein eindeutiger Wert vom Typ IND, der gleich sein muss, wenn zwei Werte gleich und schnell sind . Unsere grundlegenden Gebäudetypen sind hackbar, so können wir eine Schnur ein Stier am Ende oder ein Doppel im Set verwenden. Los geht's. Also, wenn ich mein Set genau wie dieses Set doppelt deklariere, wird sich der Compiler nicht mehr beschweren, da double einen Hash-Wert bereitstellt. Damit unsere einfache Struktur mit Set funktioniert,müssen wir das Hassiba-Protokoll bestätigen. Damit unsere einfache Struktur mit Set funktioniert, Zum Glück ist das keine große Sache. Ich hatte gerade einen modischen Konformer. Und wenn Sie das mögliche Protokoll überprüfen, hat es eine einzige Eigenschaft. Es ist eine schreibgeschützte gettable-Eigenschaft namens Hash-Wert. Dieser Hashwert muss also eindeutig sein, da unsere einfache Struktur nur eine Eigenschaft vom Typ string hat und string ein Bautyp ist , der bereits das Hashiba-Protokoll implementiert. Die Implementierung der Hash-Wert-Eigenschaft ist ziemlich unkompliziert. Alles klar, lasst uns versuchen zu kompilieren. Sind kalt jetzt haben wir immer noch ein Problem. Lassen Sie uns überprüfen, war hier los. Alles klar, sind einfache Struck Typ muss auch die Equitable Protocol entsprechen. Warum ist das so? Da Hashiba vom degradierbaren Protokoll erbt und wenn ein Protokoll von einem anderen erbt , müssen alle konformen Typen auch die Anforderungen implementieren, die in diesem Protokoll definiert sind. So wie gehen Sie zurück entspricht dem Gewicht des Protokolls ist auch keine große Sache. Wir müssen den gleichen tow-Operator implementieren, eine statische Methode ist, die tut, ob zwei Instanzen aus dem angegebenen Typ gleich sind oder nicht. Wir betrachten einfache geschlagene Instanzen als gleich, wenn sie IRS gleich sind, jetzt sollte unser Code ohne Fehler kompilieren. Tat derTatist das Thema gegangen, um zusammenzufassen. Es wird Fälle geben, in denen wir das Hashiba-Protokoll verabschieden müssen. Wenn Sie sicherstellen müssen, dass ein gegebener Wert eindeutig schwarz ist, zum Beispiel, wenn Sie einen Satz aus unseren Typen erstellen oder sie als Schlüssel für ein Wörterbuch verwenden, dann müssen wir das Hash-Hable-Protokoll übernehmen, um zu bestätigen, dass das bewohnbare Protokoll sind Typ muss einen schreibgeschützten, richtig genannten Hash-Wert implementieren. auch Da modisch das Equitable Protocol bestätigt, müssen wirauchden gleichen Abschlepp-Betreiber implementieren 35. Das Wörterbuch: das Wörterbuch, auch bekannt als Hash Map Stores. Schlüsselwertpaare verwenden diesen Sammlungstyp, wenn Sie sehr nachschlagen müssen, wurde auf ihrer Identifizierung IRS basiert. Jeder Wert muss mit einem eindeutigen Schlüssel verknüpft sein. Die Reihenfolge der Schlüssel und Werte ist nicht definiert. Genau wie die anderen schnellen Sammlungstypen wird das Wörterbuch auch als generischer Typ implementiert, ein zu großes Wörterbuch. Wir müssen den Schlüssel und den Werttyp angeben. Auf diese Weise können wir ein leeres Wörterbuch erstellen. Eine andere Möglichkeit besteht darin, die anfängliche Isar-Syntax zu verwenden. Wir können ein Wörterbuch mit einem Wörterbuch initialisieren. Literal Swift kann den Typ von den Schlüsseln und den Werten basierend auf der Führungslinie ableiten. Beim Erstellen eines Wörterbuchs soll der Typ der Schlüssel und Werte konsistent sein. Zum Beispiel sind Archies ein Jahrgang Ihres Typs und alle Werte außerhalb des Typs. String-Typ Inferenz funktioniert nicht, wenn der Typ aus den Wörterbuch-Führungslinien gemischt ist. Der Compiler bittet uns explizit bei Typanmerkungen, wenn wir wirklich ein hetero-Genius-Wörterbuch deklarieren wollen , und in bestimmten Fällen möchten Sie das tun. Zum Beispiel wird beim Konvertieren von Jason-Nutzlasten oder ordnungsgemäß Listen Typwörterbuch nicht funktionieren. Das Ganze Geschichte Genius Wörterbuch. Die Schlüssel müssen dem Hash über Protokoll entsprechen. Wie wir in der vorherigen Vorlesung gesehen haben, definiert das Hashiba-Protokoll die Eigenschaftsanforderung namens Hash-Wert. Die Hash-Wert-Eigenschaft muss einen eindeutigen Wert für eine bestimmte Instanz zurückgeben. Keine zwei verschiedenen Instanzen dürfen den gleichen Hash-Wert haben. Die Swift Standard Library hat einen Typ namens Any Hash a ball einen Hash ein Buch und halten Sie den Wert von jedem Typ, der dem Hash über Protokoll entspricht. Dieser Typ kann als Superzeit für Schlüssel in hetero Genius Wörterbüchern verwendet werden, so dass wir einen Header erstellen können . Virginias Sammlung wie diese jede erbliche ist eine Struktur, die uns den Typ angehoben Hashem-Wert erstellen kann, der die angegebene Instanz umschließt. Das passiert hinter den Kulissen. Eigentlich würde diese Version gut kompilieren, wenn wir sie in X kalt tippen. Aber die Kurzschriften-Syntax ist offensichtlich kürzer und lesbarer. Jeder Hash, der eine busbasierte Eigenschaft von RAB-Wert darstellt, kann es zurück in den ursprünglichen Typ umgewandelt werden, wobei die als bedingte als oder erzwingen als Darsteller Operatoren 36. Zugriff auf und Ändern des Textes: können wir auf den Wert zugreifen, der mit einem gegebenen er mit der tiefgestellten Syntax verbunden ist. Wir können auch über die Schlüsselwertpaare aus einem Wörterbuch mit einer for-in-Schleife iterieren. Da es sich um ein Wörterbuch handelt, werden Elemente als Schlüsselwert-Topper zurückgegeben. Wir können die Wörterbücher Schlüssel Eigenschaft akzeptieren, um seine Schlüssel abzurufen. Die Eigenschaft „Wörterbuch-Werte“. Wir geben seine Werte zurück, um ein neues Element toe hinzuzufügen, die Pictionary verwenden einen neuen Schlüssel als tiefgestellten Index und das Zeichen es einen neuen Wert. Um auf vorhandene Element zu aktualisieren, können wir die tiefgestellte Syntax mit einem vorhandenen Schlüssel verwenden. Alternativ können wir den Aktualisierungswert für Schlüsselmethode aufrufen. Diese Methode aktualisiert den Brunnen, den Sie in traditionell verzeihten Schlüssel. Wenn der Schlüssel nicht vorhanden ist, wird er als neues Schlüsselwertpaar zum Wörterbuch verwendet. Sie können einen Wert aus einem Wörterbuch entfernen, indem Sie „near“ für seinen Schlüssel zuweisen. Wir können das gleiche Ergebnis erzielen, aber mit mehr Tippen. Warum ist der Wert für die Schlüsselmethode entfernen, um das Wörterbuch zu löschen, Auto entfernt, alle entfernen. All hat einen Parameter „keep capacity“ , der vom vierten auf „false“ gesetzt wird. Wenn Sie die Operation am besten durchlaufen, bewahren Sie die Kapazität vor dem zugrunde liegenden Wert auf. Dies ist eine Leistungsoptimierung. Wenn Sie planen, das Wörterbuch wiederzuverwenden, 37. Abschnitt 7: Grundlegende Sortierung: in diesem Abschnitt werden wir über grundlegende Sortieralgorithmen sprechen. Diese Algorithmen sind ein wesentlicher Ausgangspunkt, um Probleme auf elegante und effiziente Weise zu lösen . Verständnis der Funktionsweise von Thean und das Wissen, wie man die grundlegenden Sortieralgorithmen implementiert gibt Ihnen eine starke Grundlage für den Aufbau anderer, komplexerer Algorithmen für jeden Algorithmus. Ich werde erklären, wie es funktioniert, und ich zeige Ihnen, wie Sie sie von Grund auf neu implementieren können. Mit der neuesten Version 50 werden wir eine ausgezeichnete Website sortieren 0.80 verwenden, um zu visualisieren, wie welcher Algorithmus funktioniert . Alles klar, was ist das Sortieren? Zuallererst ist das Sortieren eine Technik zum Anordnen von Daten in einer logischen Sequenz. Nach einigen gut definierten Regeln ist die Arbeit mit sortierten Daten sehr effizienter als der Zugriff auf Elemente in einer Nicht-Reihenfolge . Sortierung hat ein Kilo in kommerzieller Datenverarbeitung und wissenschaftlichem Rechnen. Wir werden unsere Reise in den Bereich der Sortieralgorithmen beginnen, indem wir drei elementare Sortiermethoden studieren . Auswahlsortierung funktioniert, indem Sie das kleinste Element auswählen und es durch das vorherige ersetzen . Dieser Algorithmus hat eine quadratische Zeitkomplexität, und es ist einer der einfachen Sortieralgorithmen Einfügesortierung, da sein Name States funktioniert, indem Elemente an ihre richtige Stelle eingefügt werden, um Platz für das aktuelle Element zu schaffen, größere Elemente müssen Bewegen. Eine Position nach rechts. Einfügesortierung hat auch eine quadratische schlechtere Zeitkomplexität. jedoch Die Leistung der Einfügequelle wirdjedochweitgehend durch die anfängliche Reihenfolge der Elemente in der Sequenz beeinflusst . Barbara Sortieren. Dieser Algorithmus arbeitet, indem er wiederholt benachbarte Elemente auswertet und ihre Position schwitzt, wenn sie sich in der falschen Reihenfolge befinden. Die Bubble Sortierung ist einfach zu implementieren, aber sie ist auch ziemlich ineffizient. Die durchschnittliche und schlimmste Komplexität sind beide quadratisch. 38. Auswahl Sortieren: Selektionssortierung ist einer der einfachsten Sortieralgorithmen. Es beginnt mit der Suche nach dem kleinsten Gegenstand und tauscht es mit dem 1. 1 Dann findet es den nächstkleinsten Gegenstand und tauscht ihn mit dem zweiten Gegenstand aus. Der Prozess geht weiter, bis die gesamte Sequenz sortiert ist. In der folgenden Demo werden wir den Auswahl-Sortieralgorithmus mit Swift drei implementieren. Wir analysieren die zeitliche Komplexität dieser Methode, und wir werden visualisieren, wie sie funktioniert. Es ist Zeit, etwas zu codieren, also lasst uns welches Toe X Gold? Die Selektion Sortierfunktion nimmt ein Array von inter nur als Eingabe und gibt die sordid Kopie aus dem Import-Array. Sortierung ist nur dann sinnvoll, wenn die IRA mindestens zwei Elemente hat. Ansonsten haben wir gerade eine Kopie des ursprünglichen Re zurückgegeben. Als nächstes erstellen wir eine Kopie des Arrays. Wir werden den Inhalt von dieser Kopie sortieren und sie von unserer Funktion zurückgeben. Die Funktion hat zwei Schleifen die äußeren Loop-Eateries durch jedes Element, und es behält den Index , der den sordiden Teil aus dem Array verweigert. Die innere Schleife findet die niedrigste Zahl im Rest des Arrays Für jedes Element. Die Funktion tauscht Positionen mit dem niedrigsten Wert aus dem Rest der Theorie, angesichts der unsortierten oder a 1 bis 430 Die äußere Schleife wählt das erste Element, das eins ist. Dann findet die innere Schleife die niedrigste Zahl im Rest des Arrays. Da Null kleiner als eins ist, wird die Position außerhalb der beiden Elemente ausgetauscht. Jetzt haben wir das erste Element im sortierten Teil aus dem Array, das jetzt 0 bis 431 wird. Die äußere Schleife ist das nächste Element zur inneren Schleife findet die niedrigste Zahl ab der nächsten Position. Einer ist kleiner als zwei, so dass ihre Position vertauscht wird. Unsere Frühe hat keine allzu schlimmen Elemente. Vier ist groß durch die äußere Schleife. Als nächstes findet die innere Schleife die niedrigste Zahl, die zu ist, da zwei kleiner als vier ist. Sie sind abgewischt, und wir bekommen 01234 Die äußere Schleife wählt das nächste Element, das frei ist. Der Rest der Rate geht weg. Nur ein Element vier ist nicht kleiner als drei, so dass ihre Position nicht vertauscht wird. Endlich bekommen wir unser sordiges Array. 01234 Lassen Sie uns nun die Zeitkomplexität aus dem Selektionssortieralgorithmus analysieren, die Algorithmusquellentheorie von links nach rechts, die Laufzeit wird durch die Anzahl der Off-Swaps beeinflusst und vergleicht die Anzahl der Austausche hängt von der Originalreihenfolge der Elemente. Der schlimmste Fall ist, wenn das Array Belohnungen sortiert ist. Die Anzahl der Swaps ist gleich der Anzahl der Off-Elemente. Theoretisch wird jedoch jedoch die zeitliche Komplexität aus der Selektionsart durch die Anzahl der vergleicht vier Unter Tag mit einem Element dominiert die äußere Schleife, Analphabeten und Köpfe einmal die innere Schleife wiederholt und minus zwei Mal zuerst als und meins dreimal und so weiter. Wenn die äußere Schleife den vorletzten Index erreicht, will die in einer Schleife auf Analphabeten. Dies bedeutet, dass wir ein minus eins plus und minus zu plus und minus drei und so weiter, plus eine Iterationen insgesamt haben. Wenn wir die Nummer aus dem Worst Case hätten. Weps, wird die Zeitkomplexität und plus und minus eins plus und minus zu plus und minus drei und so eins plus eins, die n Times n plus ein oder zwei ergibt, die n quadriert ist, plus ein über zu, wenn Sie wird sich fragen, wie haben wir diese Formel bekommen, schlage ich vor, dass Sie den Vortrag über konstante Zeitkomplexität zu sehen. Wenn die Eingabe bereits sortiert ist, die Anzahl der Swaps Null. So wird die Komplexität zu einer Zeit und minus eins oder zwei oder in kürzerer Form und quadriert minus und über bis jetzt. Lassen Sie uns ein paar Leistungstests durchführen. Wir erstellen Reraise mit 10 101.000 Elementen . Die im Rat angezeigten Ergebnisse bestätigten die quadratische Zeitkomplexität des Selektionssortieralgorithmus. Als nächstes untersuchen wir die Leistung der Auswahlsortierung mit Auftragsunordnungseingabe. Winnetou in hat eine Theorieerweiterung mit der statischen Methode zum Erstellen inkrementeller Erhöhung. Wie wir angenommen haben, ist die Leistung mit sortierter Eingabe etwas besser. Wie wär's mit dem schlimmsten Fall? Zuerst brauchen wir ein Rennen, das in umgekehrter Reihenfolge gestartet wurde. Wir werden eine weitere Methode zu unserer Erweiterung hinzufügen, die Fluss sortiert oder Rennen erzeugt. In Ordnung, lassen Sie uns unsere Leistungstests wie erwartet durchführen. Die Laufzeiten von der Auswahl Art der schlechtesten, wenn Belohnungen sortiert erhöhen. Ein großer Nachteil der Auswahlsortierung ist, dass sie unempfindlich auf Eingabe ist. Es dauert fast so lange, bis die Auswahlsortierung auf einer Rate ausgeführt wird, die bereits in Ordnung ist, wie für ein zufällig geordnetes Array 39. Auswahl Sortieren - Zusammenfassung: Die Auswahlsortierung ist definitiv einfach zu erfassen und zu implementieren, da sie auf verschachtelten Schleifen beruht. Die Komplexität der Zeit ist quadratisch. Die Laufzeit der Selektionssortierung wird hauptsächlich durch die vom Algorithmus durchgeführten Zahlenabgleichungen beeinflusst . Die Leistung aus der Auswahlsortierung ist unempfindlich auf Eingabe. Die Laufzeit wird nicht sehr viel, ob Sie eine bereits sortierte Sequenz. Was für ein total erlittenes. Als Schlussfolgerung. Die Auswahlsortierung zu verstehen und zu wissen, wie sie implementiert werden soll, ist jedoch wichtig , versuchen Sie es im echten Code zu vermeiden. Im nächsten Schlaf zeige ich Ihnen einen anderen einfachen Algorithmus, viel schneller ist, wenn die Eingabe bereits teilweise sortiert ist. 40. Sortieren: in dieser Vorlesung werden wir über die Einfügung sortieren sprechen. konzessionale Sortierung ist ein grundlegender Sortieralgorithmus , der jedes Element analysiert und an seine richtige Stelle eingefügt wird. Größere Elemente bewegen sich auf Position nach rechts in sozialer Sortierung hat quadratische Zeitkomplexität . jedoch Die Leistung der Einfügesortierung wirdjedochweitgehend durch die anfängliche Reihenfolge der Elemente in der Sequenz beeinflusst . In der folgenden Demo werden wir den Einfüge-Sortieralgorithmus in Swift implementieren. Wir werden visualisieren, wie die Einfüge-Sortierung funktioniert. Dann werden wir die Zeitkomplexität dieser Algorithmen analysieren, die wir arbeiten, in dem ein interessantes Experiment die Effizienz der Einfügesortierung mit dem Selektionssortieralgorithmus verglichen wurde, der in der vorherigen Episode dargestellt wurde. Jetzt wechseln wir zu X-Code. Die Einfüge-Sortierfunktion nimmt einen Tag frei in genau als Eingabe und gibt eine sortierte Kopie aus dem Importary zurück. Wir haben das Import-Array geklont. Diese Kopie wird das sordige Ergebnis enthalten. Die unsoziale Sortierfunktion verwendet zwei Schleifen. Die äußere Schleife schreitet fort, wenn wir das Array verarbeiten, das wir Index eins gestartet haben, weil die innere Schleife den Index beeinträchtigen muss, da sie die Saberi rückwärts umkehrt, nicht dass wir die Eingabegröße nicht wie in der Implementierung validieren müssen . Aus der Auswahl Schwertfunktion. Der äußere Schleifenzähler beginnt bei eins und endet bei Importgröße. Daher leere oder einzelne Elementarrays sowieso nicht verarbeitet. Für ein sortiertes Array muss die Zahl am aktuellen Index größer sein als unsere vorherigen. Die innere Schleife schreitet rückwärts durch die Sortierung ist saberi und Tupfer die Werte, wenn sie eine vorherige Zahl findet , die größer als die am aktuellen Index ist, angesichts der Antwort Händler a 1 bis 430 Der Ausblick schwimmt das Element, das ein Index, die für die äußere Schleife ist, startete Index 1, weil die innere Schleife den Bereich rückwärts durchlaufen muss. Der äußere Index markiert auch den sordiden Teil des Arrays , der an dieser Stelle nur aus einem Element besteht. Die innere Schleife vergleicht die Zahl am aktuellen Index mit den Elementen in dem sordigen Teil aus dem Array, mit dem diese verglichen werden, mit einem da zwei größer als eins sind. Die Nummern werden nicht ausgetauscht. Das Schwert ist Teil umfasst die Zahlen eins bis, und die unsortierten hat die Zahlen 430 Die äußere Schleife wählt das Element, das Index, zu dem vier ist. Die innere Schleife vergleicht für mit den Elementen in der sordiden Teil vier ist nicht kleiner als zwei. Daher wird kein Swap ein Kurs der äußere Index belastet. Das nächste Element ist die Zahlenstraße. Die innere Schleife führt die Vergleiche mit dem sordiden Teil drei kleiner als vier, so dass sie ausgetauscht werden. Drei ist nicht kleiner als zwei, also sind sie keine weiteren Swaps. Wir haben keine 1234 im sordigen Teil, den anderen Index. Da das letzte Mal und vom unsortierten Teil aus dem Array Null gesehen wird, ist es mehr als alle Zahlen in dem sordigen Teil, den es wiederholt wird. Dieser Spaziergang mit jedem Gegenstand aus dem Schwert ist Saberi. Der unsortierte Teil ist leer, also haben wir jetzt alle Elemente in Ordnung. Die Einfügesortierung verwendet zwei verschachtelte Schleifen. Daher ist es die schlimmste Zeit. Komplexität ist quadratisch. Jedoch. Es ist viel mehr Leistung als die Auswahl sortieren. Wenn die Imperatori bereits sortierte Sequenzen enthält, werden wir dies im Moment sehen. Im Gegensatz zur Selektionssortierung, die unempfindlich auf Eingabe ist, können die Laufzeiten aus dem Einfüge-Sortieralgorithmus sehr erheblich von der Reihenfolge des Imperatori abhängen , die besten Fälle, in denen die Arrays bereits sortiert während jeder Generation. Das nächste Element aus dem unsortierten Teil wird nur mit dem rechten meisten Element des Sorties-Unterabschnitts aus dem Bereich verglichen . werden keine Swaps vorgenommen, da die Elemente bereits für das bereits geordnete Array vorhanden sind, das über Elemente verfügt, die der Algorithmus ausführen wird, und minus eins vergleicht und Null Austauschvorgänge . Mit anderen Worten, die beste Laufzeit außerhalb der Einfüge-Sortierung ist Senior. Die schlimmsten Fälle, wenn die Eingabe in umgekehrter Reihenfolge in diesem Fall ist, jede Dauer außerhalb der inneren Schleife. Angst verglichen das aktuelle Element mit allen Elementen im Schwert ist Teil. Die Anzahl der Swaps entspricht der Anzahl der Gegenstände im sordigen Unterabschnitt, der schlimmsten Komplexität der Einfügung, Einsätze und quadrierten Köpfe. Und mit der größeren Notation entdeckten wir einen niedrigeren Begriff, was eine quadratische Laufzeit für den durchschnittlichen Fall ergibt. Wenn jedes Element halb in Ordnung ist. Die Anzahl der Swaps und Vergleiche ist halb im Vergleich zum schlimmsten Fall. Dies gibt uns und quadriert minus und über die auch eine quadratische Zeitkomplexität ist, um die Einfügung Sortierung in linearer Zeit für bereits oder fast sortierte Arrays zusammenzufassen wenn die Eingabe erlitten wird oder in umgekehrter Reihenfolge, die Einfügung sortieren wir runnin quadratische Zeit. Als nächstes werden wir die Leistung der Einfüge-Sorte und Jack messen. Wie es basierend auf der Eingabegröße variiert, erzeugt drei oder erhöht eins, das 10 Elemente hat, eines mit 100 Elementen und eines mit 1000 Elementen . Geschäftslaufzeiten Wir können sagen, dass der Einfüge-Sortieralgorithmus steigende quadratische Zeit . Lassen Sie uns nun unsere Tests mit ungeordneten Arrays wiederholen. Die Laufzeiten ändern sich nicht so abrupt mit der Eingabegröße wie bei erlittenen Eingaben. Die Einfügesortierung wird wie erwartet in linearer Zeit ausgeführt . Schließlich vergleichen wir die Leistung der Selektionssortierung und die Einfüge-Sortieralgorithmen. Zuerst werde ich scharf für die Strahlen verwenden. Wenn die Eingabegröße die Einfüge-Sortierung erhöht, führen Sie langsamer aus. Die beiden Algorithmen sollen in quadratischer Zeit ausgeführt werden, aber die Auswahlsortierung läuft für 100 Zufallszahlen schneller und etwa 20 mal schneller für 1000 Elemente. Die Einfügesortierung führt in der Regel weniger Vergleiche als die Auswahlquelle. Die Auswahlsortierung erfordert jedoch weniger Swaps. Wie wir in der Vorlesung über die Auswahlsortierung gesehen haben, ist die maximale Anzahl aus Swaps gleich toe der Eingabegröße. Mit anderen Worten, es wächst linear mit der Eingabe. Im schlimmsten Fall führt die Einfüge-Sortierung normalerweise Wasser aus und quadratische Swaps aus. Da das Schreiben von Zehenspeicher in der Regel deutlich langsamer ist als das Lesen, kann die Auswahlsortierung für eine größere Eingabe besser als die Einfüge-Sortierung. Die Situation ändert sich drastisch, wenn wir unsere Tests mit sortierter Eingabe ausgeführt haben. Der beste Fall lineare Charakter der Einfüge-Sortierung zeigt ihre Vorteile gegenüber dem Selektionssortieralgorithmus , unempfindlich gegenüber der Eingabe ist, da die Arrays oder die Einfüge-Sortierung verzerrt ist am besten Fall ist. Es wird keine Riemen geben, und die Anzahl der Vergleiche ist ein Minus eins. Der Einfüge-Sortieralgorithmus läuft in linearer Zeit, während der Auswahlsortieralgorithmus quadratische Zeit ansteigt. In unserem Beispiel bedeutet dies eine fast zehnmal geringere Leistung im Vergleich zur Einfügesortierung, um die Laufzeiten für die Einfügesortierung zusammenzufassen . beste Fall ist linear für fast sortierte Eingabe. Durchschnittliche Fälle quadratisch für erlittene Eingabe, und der schlimmste Fall ist auch quadratisch für umgekehrte sortierte Eingabe 41. Sortieren - Zusammenfassung: In der vorherigen Vorlesung haben wir uns den Einfüge-Sortieralgorithmus genauer angesehen. Es ist leicht zu verstehen und zu implementieren, und seine schlimmste Zeitkomplexität ist quadratisch. jedoch ab, Laufzeit nimmtjedoch ab,wenn die Eingabe bereits sortierte Elemente enthält. Im besten Fall, wenn die Eingabe bereits geordnet ist, führt die Einfüge-Sortierung am Ende aus, minus eins vergleicht, wo n als put-Größe gilt. Im Gegensatz zu den Auswahlsortierungen Laufzeit, die, wie wir gesehen haben, unempfindlich auf Eingabe ist, funktioniert die Einfügesortierung besser, wenn der Impuls teilweise oder vollständig als Schlussfolgerung angeordnet ist. Trotz seiner Einfachheit kann die Einfüge-Sortierung überraschenderweisemit teilweise sortierten Sequenzen auftreten überraschenderweise . In der Tat verlässt sich sogar Apple in ihrer Sortierimplementierung auf Einfüge-Sortierung. Wenn der zu sortierende Bereich weniger als 20 Elemente enthält. Fünfziger Open Source, so dass Sie die Implementierung der wunden Funktion im Swift get help Repository 42. Bubble Sortieren: Unser nächstes Thema ist Barbara Sort. Dieser Algorithmus funktioniert, indem er wiederholt benachbarte Elemente erhöht und ihre Position vertauscht . Wenn sie in der folgenden Demo in der falschen Reihenfolge sind, werden wir den Bubble-Sortieralgorithmus implementieren. Wie bei den anderen Algorithmen werden wir die Zeitkomplexität aus der Bubble-Sortierung analysieren und visualisieren, wie es funktioniert . Dann werden wir die Blase Gedanken, die Einfüge-Sortierung und die Auswahl Art von Rhythmus in Bezug auf Effizienz vergleichen . In Ordnung, wechseln wir zu unserem ausschließlichen Spielplatzprojekt. Die Bubble-Sortierfunktion übernimmt den Strahl von Ganzzahlen als Eingabe und gibt eine sortierte Kopie aus dem Import-Array zurück. Die Funktion iterierte wiederholt durch das Array und vergleicht jedes benachbarte Paar. Wenn die Zahlen nicht in der richtigen Reihenfolge sind, wird ihre Position vertauscht. Der Prozess wird fortgesetzt, bis die gesamten Sequenzen sortiert sind. Die niedrigeren Werte blasen bis zum Anfang der Theorie. Die Variable SWAT wird verwendet, um zu verfolgen, ob Swaps während eines Durchgangs durchgeführt wurden. Wenn kein Stopp während der Vergangenheit aufgetreten ist, bedeutet dies, dass die Werte in Ordnung sind und wir tatsächlich die äußere Dubai-Schleife. Lassen Sie uns die Blasen-Sortierung in Aktion sehen. Wir beginnen mit der Antwort, generieren 14 bis 30 im ersten Durchgang. Die ersten 2 Elemente werden überprüft, da eins kleiner als vier ist. Ihr Befehl wird eingehalten. Der nächste Bär ist fremd, weil vier größer ist als ihre Positionen ausgetauscht werden. Dann vergleichen wir vier und drei. Sie sind jetzt in Ordnung, also werden sie ausgetauscht. Das weniger Paar in diesem Durchgang ist vier und Null C Null. Es sind mehr als vier. Ihre Position wird ausgetauscht. Wir fahren mit dem zweiten Durchgang fort. Die ersten 3 Elemente sind bereits in Ordnung. Daher tupft der Algorithmus sie nicht ab. Das erste Paar, das Swapping erfordert, ist es in den zwei und drei gefunden. Das letzte Paar ist bereits in Ordnung, also halten wir sie an der aktuellen Position. Die dritte Vergangenheit bläst den Wert Null, bis sie fast den Anfang erreicht. Aus der Liste jedoch ist es jedochnoch nicht sortiert. Also brauchen wir noch einen Pass. Die Truppe hat an den Börsen weitergegeben. Das allererste Zahlenpaar Null ist schließlich am Anfang der Sequenz, der Rest der frühen oder ungeordneten. Aber der Algorithmus ist sich dessen nicht bewusst, so dass der Algorithmus einen anderen Durchlauf ausführt. Die fünfte und letzte Vergangenheit findet keine Paare, die ausgetauscht werden müssen. Jetzt, da wir die inneren Abläufe aus dem Blasen-Sortieralgorithmus verstehen, lassen Sie uns seine Zeitkomplexität analysieren. Wenn die Eingabe bereits sortiert ist, benötigt die Bubble-Sortierung nur eine Vergangenheit, die ausgeführt wird, und minus eins vergleicht, was die Elemente an Ort und Stelle bleiben, so dass die Anzahl der Swaps Null ist. Das bedeutet, dass die Laufzeit von der Blasensortierung nur von der Eingabegröße abhängt. Wenn die Sequenzen, was für ein ungeordnetes. Mit anderen Worten, die beste Zeitkomplexität aus der Blasen-Sortierung ist linear. Die schlimmsten Fälle, wenn das Array umgekehrt ist entweder ein Element in der Sequenz der Algorithmus, Iran und geht in Ordnung. Bei jedem Besten führt unsere Funktion aus und minus einen Vergleiche. Dies bedeutet n mal n minus eins vergleicht für die umgekehrte Reihenfolge Sequenz. Die Anzahl der Swaps wird ein minus eins im ersten Durchgang sein, en minus zwei im zweiten Durchgang, und so weiter, bis der letzte Austausch im vorletzten Besten erfolgt. Die Gesamtzahl der Swaps ist ein Minus einmal und über die Worst-Case-Laufzeit unserer Blasen-Sortierung. Implementierung ist die Summe von zwei Swaps und Vergleichen. Dies ist eindeutig eine Ordnung aus und quadratische Zeit Komplexität. Die durchschnittliche Zeitkomplexität aus der Blase Thought ist auch quadratisch zusammenzufassen, die Blasensortierung hat eine lineare Laufzeit für Orderunordnung, das Rennen und Läufe. In der Reihenfolge einer quadrierten durchschnittlichen und schlechtesten Zeitkomplexität können diese Laufzeiten ähnlich der zeitlichen Komplexität des Einfüge-Sortieralgorithmus aussehen . jedoch Die Blasensorte benötigtjedochdeutlich mehr Swaps als das Einsteckschwert. Die höhere Anzahl von Swaps führen wir zu einer langsameren Leistung. Daher ist die Einfügesortierung aufgrund ihrer schlechten Leistung deutlich besser als die Blasensortierung . Die Bubble Sortierung wird jedoch fast nie in echter Software verwendet , weil sie einfach zu erfassen und zu implementieren ist. Der Bubble-Sortieralgorithmus wird häufig in einführenden Informatik-Materialien verwendet. Lassen Sie uns nun einige Leistungsmessungen ausführen. Wir vergleichen die Blasensortierung mit der Einfügesortierung und dem Selektionssortieralgorithmus für 10 Elemente. Es gibt keinen spürbaren Unterschied zwischen den drei Algorithmen. Der Bubble-Denkalgorithmus beginnt seine Schwäche beim Sortieren von 100 Zufallszahlen zu zeigen. Seine Leistung wird schlimmer, als die Eingabe-Dimensionierung verrückt 43. Bubble Sortieren - Zusammenfassung: Baba gesucht ist der dritte Sortieralgorithmus, über den wir gesprochen haben. Obwohl es einfach zu implementieren ist, hat es die schlechteste Leistung unter den grundlegenden Sortieralgorithmen. Die hohe Anzahl von Swaps ist für die geringe Leistung der Bubble Sorte verantwortlich. Obwohl wir unsere bestehende Bubble-Sortierimplementierung leicht optimieren könnten, wird die Einfügesortierung sogar die optimierte Version für größere Eingaben übertreffen. Als Schlussfolgerung sollten Sie vermeiden, Barbara Sortierung der Produktion namens Use Insertion sort genannt. Wenn Sie eine einfache, aber akzeptable Lösung benötigen. In diesem Abschnitt analysieren wir einige der grundlegenden Sortieralgorithmen. Sie zu studieren ist definitiv die Mühe wert, unser Wissen in Algorithmen zu vertiefen , wurden jedoch bald gelähmt, Sortieralgorithmen, die viel schneller laufen können als alle von den elementaren Algorithmen, die wir bisher begonnen haben im kommenden Teil. Wir werden die fortschrittlicheren, mehr sortieren und schnelle Sortieralgorithmen untersuchen . Wir sehen uns im nächsten Abschnitt 44. Abschnitt 8: Erweitertes Sortieren: in diesem Abschnitt werden wir zu weit verbreitete Sortieralgorithmen studieren, meine Art und schnelle Sortierung. Diese Algorithmen sind Leistung und können tatsächlich in der Produktion verwendet werden, genannt viel Gedanken und schnelle Sortierung auf, einschließlich in verschiedenen Bibliotheken und Frameworks. Meine Sortierung funktioniert, indem die zu sortierende Sequenz in zwei Hälften aufgeteilt wird. Dann sägt es die Haves und kombiniert schließlich die Ergebnisse. Zusätzliche Sortierung wird durch Zusammenführen der Sabri durchgeführt. Der schnelle Sortieralgorithmus verwendet einen Dividen- und Eroberungsansatz wie die Marschquelle. Der Unterschied ist, dass die resultierende Sabri unsere Bestellung, die Bestellung und wie für die mehr Sortierung, weitere Sortierung ist nicht erforderlich, indem die Teile zusammengeführt werden. Alles klar, fangen wir mit der meisten Sorte an. 45. Sortieren nach: Okay, also reden wir über die mehr Sorte, wie Sie in einer Sekunde sehen werden. Dies ist ein Algorithmus, der durch Aufteilen des Arrays im Schlepptau funktioniert. Hälften. Es geht weiter und teilt die Hälfte auf, bis wir zu den einzelnen Element-Subllisten gelangen. Diese Ein-Element-Arrays werden dann sortiert und zusammengeführt. Als Ergebnis werden wir zwei Elemente haben. Themen, die bestellt werden. Die Sortierung, auftauchende Unterliste wird fortgesetzt. Schließlich gibt es nur eine Liste. Ratet mal, was diese Liste sein wird. Das unheimliche Ergebnis. Wie wäre es mit der Implementierung der meisten würde ihnen von Grund auf zustimmen In der folgenden Demo werde ich Ihnen eine Top-Down-Implementierung zeigen . Aber zuerst, lassen Sie uns visualisieren, wie es funktioniert. Ich werde Sie durch ein Beispiel für die Bestellung Honore mit mehr Sortierung führen. Zuerst teilen wir das Array in zwei Teile auf. Der frühe hat acht Elemente, so dass der Spieß vier indiziert. Wir haben zu Unterlisten, jede mit vier Elementen. In Ordnung, lassen Sie uns mit der Spaltung fortfahren. Nachdem wir die linke Hälfte geteilt haben, gelangen wir zu Unterlisten, jeweils mit zwei Elementen. Als nächstes teilen wir diese beiden. Wir können die linke Seite nicht weiter sprechen. Seitdem haben wir nur ein Element Arrays. So kommt jetzt das Sortieren und Verschmelzen Gesicht. Nach zwei Schritten die Elemente der linken Hälfte angeordnet. Ich folge den gleichen Schritten für die rechte Hälfte einer Straße als zwei weitere Splits auf den beiden Elemente-Unterlisten, und wir bekommen die eine Elementare. Als nächstes werden die einzelnen Element-Unterblets sortiert und kombiniert, bis die rechte Hälfte ebenfalls sortiert ist. Was kommt als Nächstes? Es ist nur noch ein Schritt übrig. In diesem letzten Schritt dachten die beiden, dass es halb gepanzert und verdorben war. Und da gehst du. Das Ergebnis ist die Reihenfolge Ray. Jetzt, da Sie wissen, wie es funktioniert, lassen Sie uns diesen erstaunlichen Algorithmus implementieren. Also hat er die mehr Sortierfunktion. Es hat eine unkomplizierte Unterschrift. Das Eingabeargument ist das Array von Inter nur sortiert werden. Die Funktion kehrt zurück und strahl aus, in gerade gut vor mindestens Tagen bestellt. Es macht keinen Sinn, Honore zu sortieren, das ein Element hat. Die Götter Zustand eins hat die Größe vom Import alle geändert, wenn es weniger als zwei Elemente hat, die Funktion gibt einfach die Eingabe zurück. Als nächstes finden wir den geteilten Index, den wir brauchen, um die rechte in der Mitte zu teilen. Daher wird der Index als die Eingabeanzahl über zwei berechnet Wie Sie wahrscheinlich bemerkt haben, gehen wir die Mursal-Funktion von sich aus. Dieser Rekord Asian wird verwendet, um die Hälfte zu beschleunigen, bis ein oder beide Haus nur ein Element haben. Dann spielt der Algorithmus die Art von viel Phase. Die erste Hilfsfunktion vergleicht die Elemente aus der linken und rechten Unterliste. Der kleinere Wert wird an die sordide ary angehängt. Wenn der ursprüngliche Ray eine ungerade Anzahl von Elementen hat, können wir ihn nicht in genau zwei Hälften spucken. Deswegen brauchen wir die letzten Schecks. Dieser letzte Schritt stellt sicher, dass das letzte Element aus der linken oder rechten Zusammenfassung der sortierten Liste hinzugefügt wird. Schließlich weniger die frisch implementierende mehr Sortierfunktion. Der Sortieralgorithmus ist ein bisschen schwieriger als die grundlegenden, die wir bisher behandelt haben . Vorsichtsmaßnahmen sind auch nicht einfach . Ich schlage vor, dass Sie sich das Spielplatzprojekt genauer ansehen, ein paar Mal ausführen und versuchen, diese Logik zu verstehen. auch den Teil, Besuchen Sieauch den Teil,in dem ich visualisiere, wie die meisten Sortierung funktioniert. Leider kommt der Spielplatz nicht mit dem Bugger, aber vergessen Sie nicht, dass Sie die Schritte und die Werte dem Rat ausdrucken können. Fühlen Sie sich frei, alle Such- oder Druckanweisungen im Code, wo immer Sie mehr Klarheit benötigen 46. Sortieren zusammenführen - Zusammenfassung: Bisher haben wir über drei grundlegende und eine weitere erweiterte Sortieralgorithmus Auswahl sortieren, Einfügen, sortieren baba sortieren und mehr wund gesprochen Einfügen, . Der Muskel ist der effizienteste unter ihnen. Es hat eine logarithmische schlechteste und durchschnittliche Zeitkomplexität. Die meisten Sorte verwendet eine Teilung und Eroberungstechnik. Es ist bitte die ursprüngliche Ray Recursive Lee in kleinere Unterlisten. Dann, in der Art der Merch-Phase, betrifft es das geordnete Ergebnis mehr sortieren weltweit beste mit größeren Eingaben. Wenn Sie kleine Arrays sortieren müssen, sagen wir weniger als 20 Elemente, aufständische Sortierung kann aufgrund seiner einfachen Stadt besser funktionieren. Also, was kommt als Nächstes? Im nächsten Vortrag werden wir einen genaueren Blick auf den sehr beliebten und auch sehr schnellen Sortieralgorithmus , die schnelle Sortierung. 47. Quicksort: schnelle Sortierung ist wahrscheinlich die am weitesten verbreitete Sortieralgorithmus ist im Volksmund auf seine Leistung bezogen . Außerdem ist es nicht allzu schwierig zu implementieren, und es funktioniert gut mit vielen verschiedenen Eingabetypen. jedoch Der Ansatz istjedochanders. Anders als bei der meisten Sortierung erfolgt die endgültige Sortierung von Elementen vor der Merchphase. Bald zeige ich Ihnen, wie Sie eine schnelle Sortierung Swift implementieren. Aber zuerst, lassen Sie uns visualisieren, wie dieser Algorithmus funktioniert. Also hier ist unsere Antwort. Jittery. Zuerst müssen wir einen Drehpunkt auswählen. Der Algorithmus verwendet Dispute, um ihr Recht in drei Teile einer Liste mit allen Elementen aufzuteilen, die kleiner sind als die Personen, eines mit den Elementen, die den Personen gleich sind. Und wie Sie vielleicht einmal davon erraten haben, enthält das alle Elemente, die größer sind als die Menschen. Spucken des Arrays um die Leute wird gefangen Partitionierung. Die Partitionierung wird fortgesetzt, bis keine Sequenzen mehr sortiert werden müssen. Kommen wir nun zu unserem Beispiel zurück. Wir groß das Element, das für S Pivot Index. Die resultierenden drei Unterbeeren enthalten alle Zahlen, die kleiner alsdrei und größer als drei sind drei und größer als drei . Als nächstes teilen wir die Linke am besten einen Geist. Wir wählen das Element bei Index 1 aus. Die resultierende Unterliste enthielt die Zahl 01 und zwei bis. Da es keine größeren Zahlen gibt, als zu etablieren, die halten sollten, die größeren Zahlen leer. Wieder. Wir wählen ein Volk aus und beschleunigen die nächste Zusammenfassung. Sie kommen zu einer Gehaltserhöhung mit nur einem Element. Jetzt ist der Prozess. Die rechte Unterliste, die die Elemente enthält, die größer sind als die ersten Personen, die wir auswählen. Sechs. Ein Geist, der uns die folgenden Sabri's auf leerem Sudbury für Elemente gibt, die kleiner sind als die Menschen. Ein Element Saberi für Elemente gleich den Menschen und ein Element U-Bahn für Elemente größer als die Menschen. Wir sind mit der Partitionierungsphase fertig. Indem wir die abschließenden Unterlisten zusammenführen, erhalten wir das sordige Ergebnis. In Ordnung. nun Lassen Sie unsnundie schnelle Sortierfunktion implementieren. Diese Variante ist die einfachste mögliche Implementierung. Das Volk ist das Element aus der Mitte des Bereichs für Petitionen. Wir verlassen uns auf die Filterfunktion. Die Schnellstartfunktion verursacht sich rekursiv Lee, bis alle etablierten ein Element oder gleiche Elemente enthalten. Schließlich die Unterverzeichnisse zusammengefasst. In Swift. Sie können einfach den Anzeigenoperator verwenden. Tokcan, Cara, NATO erhöhen Lassen Sie uns einen schnellen Testlauf machen. Das sordide Ergebnis wird in der Konsole angezeigt. Warum dieser Code sehr einfach ist. Es ist definitiv keine produktionsfertige schnelle Sortierimplementierung. Anstatt ein Partitionierungsschema zu implementieren, verlassen wir uns auf die Filterbibliotheksfunktion. Dies erzeugt einen sehr einfachen und kompakten Code. jedoch In Bezug auf die Leistung ist diesjedoch definitiv nicht die beste Wahl. Viele Verbesserungen wurden am ursprünglichen Schnellsortieralgorithmus vorgenommen, der vor fast 60 Jahren erfunden wurde. Die Suche nach den optimalen Personen und besseren Partitionierungsschemata kann die Effizienz dieses cleveren Algorithmus weiter verbessern . Eine einfache Möglichkeit, die Leistung der schnellen Sortierung zu verbessern, besteht darin, zu einer Assertion zu wechseln, nach kleineren Arrays zu sortieren. Sogar Apple verwendet Distrikt in der Implementierung von der schnellen Sortierfunktion. 48. Quicksort - Zusammenfassung: Lassen Sie uns schnell zusammenfassen, was wir in der vorherigen Vorlesung gelernt haben. Die Griechen. Was wahrscheinlich schneller ausgeführt wird als jeder andere Vergleichsschacht-Sortieralgorithmus. In den meisten Fällen verwendet dieser Algorithmus die Dividen- und Eroberungsstrategie, um zu partitionieren. Das Array sah dann die Sabris unabhängig voneinander. Das Quick Sword wurde 1960 erfunden. Es wird im Laufe der Zeit konsequent studiert und verfeinert. Härter. Der Erfinder des Algorithmus Dextre, Lamu, Toe und andere haben daran gearbeitet, die Effizienz der schnellen Sortierung zu verbessern. Noch mehr intelligentere Partitionierungsschemata und das Finden der optimalen Menschen können einen großen Unterschied machen . Damit sind wir mit den Sortieralgorithmen fertig. Mittlerweile wissen Sie wahrscheinlich viel mehr über Algorithmen als zu Beginn der Partituren. Aber warte, da ist noch mehr. Wir sehen uns im nächsten Abschnitt. 49. Abschnitt 9: Endliche Gedanken und nützliche Ressourcen: Sie haben also das Ende dieses Kurses erreicht. Herzlichen Glückwunsch. Sie haben viel über Algorithmen gelernt und verstehen ihre Vorteile. Wenn Sie Zweifel haben, zögern Sie nicht, die Vorlesungen im Fachgericht erneut zu besuchen. Die Macht von Algorithmen Konstanten wie lineare oder quadratische Zeitkomplexität wird Sie nicht mehr Ihre Augenbrauen heben. Das Kapitel über die Bigelow-Notation hat einige der häufigsten zeitlichen Komplexitäten durch einen schnellen Code geklärt . Beispiele ohne ins Detail von drei populären grundlegenden Sortieralgorithmen und fortgeschrittenen, einschließlich der extrem weit verbreiteten Schnellsortierung. Mittlerweile sind Sie wahrscheinlich in der Lage, ein Implementieren des Sortieralgorithmus von Grund auf zu erklären. Nun möchten Sie vielleicht Ihr Wissen weiter vertiefen. Also, was kommt als Nächstes? Ich gebe Ihnen einige nützliche Online-Ressource ist, die Ihnen helfen wird, Ihre entsprechend und Problemlösung Skifahrer Fähigkeit zu schärfen , eine große Ressource für Entwickler und Recruiter. Fähigkeit hat eine Menge von Zitaten Übungen und Herausforderungen. Um Ihr Wissen zu testen, bietet die Website einen Online-Editor und Compiler und unterstützt eine Reihe von verschiedenen Programmiersprachen, einschließlich Swift Three. Sie können benutzerdefinierte Testdaten bereitstellen und mehrere Testläufe ausführen, bevor Sie Ihre Lösung senden . Die Lösung wird auf Korrektheit bewertet. Etch Fallszenarien und Zeitkomplexität als auch. Möglicherweise erzielen Sie nicht die höchste Punktzahl, auch wenn Ihre Lösung die erwarteten Ergebnisse liefert. Wenn es Leistungen langsam oder fair ist, extremer Etch Fall ein algorithmischer Ansatz definitiv erforderlich, um die meisten Übungen auf dieser Seite zu lösen . Heck, Arinc Hecker Rank bietet viele Tutorials und Herausforderungen für Project. Oiler ist eine Sammlung von herausfordernden Meth und Computer-Programmierproblemen. Sie sollten weiter daran arbeiten, Ihre algorithmischen Probleme zu lösen Skifahrer zu verbessern. Sie müssen viel üben, um algorithmisches Denken zur Gewohnheit zu machen. Anstatt zu springen, um eine naive, langsame Lösung zu implementieren . Sie werden schließlich feststellen, dass Sie das Problem analysieren. Und unter Berücksichtigung verschiedener Aspekte wie Worst Case, durchschnittliche Zeit von Black City und Gedächtnisüberlegungen, werden Sie nicht nur die Probleme lösen, sondern auch in der Lage sein, elegante, effiziente und zuverlässige langfristige -Lösungen. Ich würde gerne von Ihnen hören. Fühlen Sie sich frei, mir eine Nachricht zu senden, und wenn Sie diesen Kurs nützlich gefunden haben, hinterlassen Sie bitte eine schönere Betrachterbewertung. Vielen Dank