Technologische Neuigkeiten, Bewertungen und Tipps!

Sets in Swift erklärt

Hinweis: Der folgende Artikel hilft Ihnen weiter: Sets in Swift erklärt

Zurück zum Blog

Sets in Swift sind leistungsstark. Sie ähneln Arrays und Wörterbüchern, sind aber auch sehr unterschiedlich. Der Set-Sammlungstyp ist ein interessanter Aspekt der Swift-Programmierung. Finden wir heraus, wie Sie es nutzen können!

In diesem Beitrag erfahren Sie:

  • So verwenden Sie Set in Swift
  • Warum Set ein so leistungsstarker Sammlungstyp ist
  • Wie sich Zeitkomplexität und Hash-Tabellen auf Set auswirken
  • Wie man Mengen vergleicht, um Unterschiede und Gemeinsamkeiten zu finden
  • Welche Zutaten haben ein Cappuccino und ein Latte gemeinsam?

Lassen Sie uns zunächst besprechen, wie Sie mit Set in Swift arbeiten können. Leere Mengen erstellen, Elemente hinzufügen und entfernen – das ist der Arbeit mit Arrays und Wörterbüchern sehr ähnlich.

Hier ist ein kurzes Beispiel:

Lass Früchte tragen:Set = [“apple”, “banana”, “strawberry”, “jackfruit”]
drucken(Frucht)

Im obigen Code erstellen wir mithilfe der Literalsyntax eine neue Menge namens „fruit“. Der Typ Set wird explizit bereitgestellt. Andernfalls würden wir aufgrund der Typinferenz ein Array erstellen.

Die Art der Frucht ist eigentlich Set oder Set-of-Strings. Genau wie Arrays und Wörterbücher ist Set eine generische Struktur. Ein Satz kann jeden Typ enthalten, der dem Hashable-Protokoll entspricht. (Mehr dazu später.)

Sie können einen Artikel wie folgt zu einem Set hinzufügen:

var Fruit = Set()
Fruit.insert („Ananas“)
drucken(Frucht)

Im obigen Code wird mit Set() ein leerer Satz mithilfe der Initialisierungssyntax erstellt. Sie geben den Typ des Sets an, gefolgt von Klammern (). Anschließend wird ein Artikel „Ananas“ in das Set eingefügt.

Auch das Entfernen eines Artikels aus einem Set ist einfach. So was:

var Fruit:Set = [“apple”, “banana”, “strawberry”, “jackfruit”]
Fruit.remove(“Banane”)
drucken(Frucht)

Die Artikel in einem Set müssen einzigartig sein! Sie können einem Set nicht dieselben zwei Elemente hinzufügen. So was:

var Fruit:Set = [“apple”, “banana”, “orange”]
let result = Fruit.insert(“Orange”)
drucken(Frucht)

drucken(Ergebnis)

Im obigen Code wird die „orangefarbene“ Zeichenfolge nicht in den Satz eingefügt. Der Rückgabewert der Funktion insert(_:), der der Ergebniskonstante zugewiesen ist, sagt uns genau Folgendes:

(eingefügt: false, memberAfterInsert: „orange“)
Und genau wie Arrays und Wörterbücher verfügt ein Set über eine Reihe hilfreicher Funktionen, wie zum Beispiel:

  • isEmpty gibt true zurück, wenn die Menge keine Elemente enthält
  • count gibt die Anzahl der Elemente im Set zurück
  • first gibt das erste Element im Satz zurück
  • randomElement() gibt ein zufälliges Element aus der Menge zurück
  • first(where:) gibt Elemente zurück, die ein bestimmtes Prädikat erfüllen

Machen wir weiter und finden heraus, was Set so besonders macht …

Mengen ähneln Arrays und Wörterbüchern, sind aber auch sehr unterschiedlich.

  • Ein Array verknüpft numerische Indizes, z. B. 0…n, mit Werten. Arrays haben eine feste, fortlaufende Reihenfolge. Ein gutes Beispiel ist eine Liste Ihrer Lieblingsfilme, geordnet von den beliebtesten bis zu den unbeliebtesten.
  • Ein Wörterbuch verknüpft Schlüssel mit Werten, und Schlüssel müssen hashbar sein, z. B. String. Wörterbücher sind nicht geordnet. Ein gutes Beispiel ist ein Highscore: eine Liste der Namen von Personen und ihrer jeweiligen Highscores.

Eine Menge ist eine eindimensionale Liste von Elementen, genau wie ein Array. Es verfügt nicht über numerische Indizes (wie Arrays), sondern über Werte, die Hashable entsprechen müssen (wie Wörterbücher). Es ist fast so, als wären die Werte der Schlüssel. Diese Eigenschaft macht Set so besonders!

Stellen Sie sich vor, wir möchten herausfinden, ob „Matrix“ (aus dem Jahr 1999) einer Ihrer Lieblingsfilme ist. Wir könnten einen Algorithmus entwerfen, um das herauszufinden. So was:

lass Favoriten = [“Rocky”, “The Matrix”, “Lord of the Rings”]

für Film in den Favoriten
{
if movie == „The Matrix“ {
print („Ja, The Matrix ist einer deiner Favoriten!“)
brechen
}
}

Note: Im obigen Code ist favorites ein Array – kein Set.

Der obige Code sucht nach „The Matrix“, indem er diese Zeichenfolge mit jedem der Filme im Favoriten-Array vergleicht. Im schlimmsten Fall muss es alle Elemente in den Favoriten durchlaufen, um eine Übereinstimmung zu finden.

Wir sagen, dass die Zeitkomplexität des obigen Algorithmus O(n) ist, die sogenannte lineare Zeit. Das ist für drei Filme in Ordnung, aber stellen Sie sich vor, wie lange es dauert, wenn die Liste der Filme beliebig groß wird. Möglicherweise müssen Sie Millionen von Filmen einzeln durchsuchen!

Informatiker haben für dieses Problem eine Lösung gefunden, die sogenannte Hash-Tabelle. Wörterbücher verwenden eine Hash-Tabelle für Schlüssel und Sets verwenden sie für Werte.

Bei Mengen wandelt der Hash-Tabellenmechanismus jeden Wert der Menge in eine eindeutige Zeichenfolge um, die als Hash bezeichnet wird. Basierend auf einer Arithmetik entspricht dieser Hash einer bekannten Speicheradresse eines Elements in der Menge.

Dadurch können wir jedes Element mithilfe seines Hashs finden, ohne jedes Element in der Liste durchsuchen zu müssen. Wir kennen den Wert, also kennen wir den Hash, also kennen wir die Speicheradresse. Diese Suchoperation hat eine Zeitkomplexität von O(1), die als konstante Zeit bezeichnet wird. Diese Idee ist revolutionär, denn sie bedeutet, dass wir jeden Artikel in der Sammlung effizient finden können!

Warum nicht ein Array verwenden? Das Nachschlagen eines Elements in einem Array ist ebenfalls eine O(1)-Operation. Sie müssen die Indexnummer eines Arrays kennen, um ein Element nachzuschlagen, was nicht immer praktikabel ist.

Warum nicht ein Wörterbuch verwenden? Das Nachschlagen eines Elements in einem Wörterbuch anhand seines Schlüssels ist eine O(1)-Operation. Ein Set ähnelt in dieser Hinsicht einem Wörterbuch, mit der Ausnahme, dass Sie selbst keine hashbaren Schlüssel bereitstellen müssen. In einem Wörterbuch basiert der Schlüssel eines Paares nicht auf seinem Wert.

Kehren wir zum Beispiel der Lieblingsfilme zurück. Es ist ganz einfach herauszufinden, ob ein beliebiger Film zu Ihren Lieblingsfilmen gehört:

let movies:Set = [“Rocky”, “The Matrix”, “Lord of the Rings”]

if movies.contains(“Rocky”) {
print(„Rocky ist einer deiner Lieblingsfilme!“)
}

Im obigen Code erstellen wir dieselbe Filmsammlung als Satz von Zeichenfolgen. Mit der Funktion enthält(_:) prüfen wir, ob der String „Rocky“ in der Menge vorhanden ist. Wenn das zutrifft, wird ein Teil des Textes als Ausgabe ausgegeben.

Die Funktion enthält(_:) verwendet den Hash-Tabellenmechanismus. Für die Suche wird keine Schleife verwendet! Es berechnet den Hashwert der Zeichenfolge „Rocky“ und verwendet diesen Wert, um direkt auf das Element in der Sammlung zuzugreifen. Wenn es ein Element für diesen Hashwert gibt, gibt „contains(_:)“ „true“ zurück. Wenn nichts gefunden wird, können wir sicher sein, dass es nicht in der Menge vorhanden ist.

Der große Unterschied besteht im Mechanismus, der zum Auffinden von Elementen in der Sammlung verwendet wird. Ein Array muss jedes Element im Array einzeln überprüfen. Eine Menge kann basierend auf ihrem Hash direkt auf den Wert zugreifen, ohne dass die gesamte Sammlung überprüft werden muss.

Die zeitliche Komplexität der Funktion „contains(_:)“ einer Menge beträgt O(1) (Dokumentation). Die zeitliche Komplexität der Funktion „contains(where:)“ eines Arrays beträgt O(n) (Dokumentation).

Aber … was ist, wenn Sie eine Liste Ihrer Lieblingsfilme mit Metadaten führen und herausfinden möchten, ob ein Film in dieser Liste enthalten ist? Filmnamen reichen also nicht aus.

Erstellen wir zunächst eine einfache Movie-Struktur mit einigen Eigenschaften. So was:

Strukturfilm
{
Variablenname:String
var Jahr:Int
Var-Bewertung:Int
}

Dieser Film benötigt Initialisierer, also fügen wir auch diese hinzu:

init(name: String, Jahr: Int, Bewertung: Int) {
self.name = Name
self.year = Jahr
Selbstbewertung = Bewertung
}

init(withName name: String) {
self.name = Name
self.year = 0
Selbstbewertung = 0
}

Die erste init()-Funktion erzeugt ein Objekt vom Typ Movie mit allen drei Eigenschaften: Name, Jahr und Bewertung. Dieser Initialisierer wird normalerweise standardmäßig hinzugefügt, es sei denn, Sie fügen einer Struktur (oder Klasse) Ihre eigenen Initialisierer hinzu.

Der zweite Initialisierer init(withName:) dient lediglich der Bequemlichkeit. Es wird kein „vollständiger“ Film erstellt, sondern nur ein Stub, der nur einen Namen hat. Das Jahr und die Bewertung der Eigenschaften werden auf 0 gesetzt. Wir werden sie später verwenden.

Bevor wir Movie in einem Set verwenden können, muss die Struktur dem Hashable-Protokoll entsprechen. Wir müssen drei Anpassungen vornehmen.

Ändern Sie zunächst die Definition der Struktur, um das Hashable-Protokoll einzuschließen. So was:

Strukturfilm: Hashbar
{

Zweitens müssen wir der Movie-Struktur eine Funktion == hinzufügen. So was:

static func == (lhs: Film, rhs: Film) -> Bool {
return lhs.name == rhs.name
}

Die obige Funktion sieht kompliziert aus, ist es aber nicht! Folgendes passiert:

  • Die Funktion == ist Teil des Hashable-Protokolls. Es wird verwendet, um zwei Objekte von Movie zu vergleichen, um festzustellen, ob sie gleich sind. (Ja, == ist ein gültiger Funktionsname!)
  • Wenn sie gleich sind, gibt die Funktion „true“ zurück. Ist dies nicht der Fall, gibt die Funktion „false“ zurück.
  • Die beiden Movie-Objekte, die wir vergleichen, heißen lhs und rhs, was für left-hand-side und right-hand-side steht. Erinnern Sie sich an Mathe? Jede Gleichung hat diese beiden Seiten.
  • Wir ermitteln die Gleichheit, indem wir die Namenseigenschaften der beiden Movie-Objekte vergleichen. Wir vergleichen buchstäblich die Namen der Filme. Wenn die Namen gleich sind, sind die Objekte gleich.

Der Vergleich von Filmnamen ist ein rudimentärer Ansatz, um festzustellen, ob zwei Filmobjekte gleich sind. Ausgenommen sind beispielsweise Filme mit demselben Namen, aber unterschiedlichen Erscheinungsjahren. Eine Lösung wäre, sowohl den Namen als auch das Jahr in der Funktion == zu vergleichen.

Drittens müssen wir die Funktion hash(into:) implementieren. Diese Funktion ist auch Teil des Hashable-Protokolls. Hier ist wie:

func hash(into hasher: inout Hasher) {
hasher.combine(name)
}

Mit dieser Funktion können wir Daten für die Hash-Funktion bereitstellen. Mit dieser Hash-Funktion wird eine Hash-Tabelle für den Satz berechnet. Der Funktion wird eine Referenz auf ein Hasher-Objekt übergeben.

Wir fügen den Filmnamen mithilfe der Funktion „combine(_:)“ zum Hasher hinzu. Es ist wichtig, dass sowohl die Funktion == als auch die Funktion hash(into:) dieselben Eigenschaften verwenden.

Zu diesem Zeitpunkt verfügt ein Movie-Objekt über eine Eigenschaft namens hashValue. Wir können auch testen, ob zwei Movie-Objekte gleich sind. So was:

let a = Film(Name: „Rocky“, Jahr: 1976, Bewertung: 5)
let b = Movie(withName: „Rocky“)

print(a == b)
// Ausgabe: true

print(a.hashValue)
// Ausgabe: etwa „5474910254413230307“

Okay, lass uns weitermachen! Wir werden jetzt eine Reihe von Filmen erstellen. So was:

let movies:Set = [
Movie(name: “Rocky”, year: 1976, rating: 5),
Movie(name: “The Matrix”, year: 1999, rating: 10),
Movie(name: “Lord Of The Rings”, year: 2001, rating: 8),
Movie(name: “The Secret Life Of Walter Mitty”, year: 2013, rating: 7),
Movie(name: “Deadpool”, year: 2016, rating: 3)
]

Mit diesem Set können wir ein paar coole Dinge machen. Wie wäre es, herauszufinden, ob ein Film Ihr Favorit ist? Hier ist wie:

if movies.contains(Movie(withName: „Rocky“)) {
print („Ja! Rocky ist ein Favorit.“)
}

Im obigen Code erstellen wir ein neues Movie-Objekt mit dem Movie(withName:)-Initialisierer. Aufgrund der Art und Weise, wie wir Hashable implementiert haben, können wir Movie-Objekte verwenden, um die Mitgliedschaft im Set zu testen. Der obige Code prüft, ob Rocky im Filmset vorhanden ist. Dies ist eine O(1)-Operation.

Und wie wäre es, Ihren Lieblingsfilm zu finden? Hier ist wie:

if let movie = movies.sorted(by: { $0.rating > $1.rating }).first {
print(„Mein Lieblingsfilm ist: \(movie.name)“)
}

Der obige Code verwendet die Funktion sorted(by:), um Filme nach ihrer Bewertungseigenschaft (von der höchsten zur niedrigsten) zu sortieren. Das Ergebnis von sorted(by:) ist ein Array, und wir erhalten das erste (dh am höchsten bewertete) Element im Array mit der ersten Eigenschaft. Die gesamte Operation weist eine Zeitkomplexität von O(log n) auf.

Was ist, wenn wir die Bewertung eines bestimmten Films ermitteln möchten? Hier ist wie:

if let index = movies.firstIndex(of: Movie(withName: „Herr der Ringe“)) {
let lotr = movies[index]
print(„Ich habe LOTR mit Ranking = \(lotr.rating)“ bewertet.)
}

Im obigen Code erhalten wir den Index des Films „Der Herr der Ringe“ mit der Funktion „firstIndex(of:)“. Genau wie bei enthält(_:) wird der Film mit seinem Index (einem Hashwert) gefunden. Dies ist eine O(1)-Operation. In der Bedingung verwenden wir die tiefgestellte Syntax, um das Movie-Objekt aus Filmen abzurufen und seine Bewertung auszugeben.

Es ist manchmal kontraintuitiv, ein Set in Verbindung mit firstIndex(of:) zu verwenden. Warum fügen Sie sie nicht einfach in ein Array oder ein Wörterbuch ein? Die meisten Objektsammlungen haben ohnehin eindeutige Indizes, wie etwa objectId in Parse Server und $key für Firebase.

Der Grund, warum wir Set hier verwenden, liegt darin, dass uns die Reihenfolge der Filme egal ist und wir einen Film anhand seines Namens in O(1)-Zeit finden möchten. Das Durchsuchen von Arrays und Wörterbüchern nach einer Eigenschaft dauert O(n) Zeit. Wir hätten den Filmnamen als Wörterbuchschlüssel verwenden können, aber das hat keinerlei Vorteile gegenüber der Verwendung von Set. (Siehe „Warum nicht … verwenden?“ oben.)

Wenn Ihre Sammlung eine feste Reihenfolge erfordert, verwenden Sie Array. Wenn Sie die O(1)-Vorteile der Verwendung von Set nutzen möchten, können Sie einen separaten Index mit einem Set erstellen. Fügen Sie die Eigenschaft, nach der Sie suchen möchten, in dieses Set ein und stellen Sie sicher, dass es das Array mit den tatsächlichen Objekten genau „spiegelt“. Verwenden Sie den Satz, um zu testen, ob ein Element in der Sammlung enthalten ist, und das Array (oder Wörterbuch), um das relevante Objekt abzurufen. Dies ist praktisch ein Suchindex.

Okay, noch eine letzte Sache. So wählen Sie die Filme mit einer Bewertung von 8 oder höher aus:

let top = movies.filter({ $0.rating >= 8 })

für den Film oben {
print(film.name)
}

Der obige Code gilt nicht nur für Set – jede Sammlung oder Sequenz kann mit filter(_:) gefiltert werden. Interessant ist, dass die Art des Oberteils die gleiche ist wie bei Filmen, also Set. Das ist effizient!

Lass uns weitermachen!

Die Superleistung von Set besteht darin, dass es effizient bestimmen kann, ob ein bestimmtes Element Teil einer Menge ist. Wir nennen dieses Attribut „Mitgliedschaft“. Ist ein Element Mitglied einer Menge?

Aus diesem Grund ist Set nützlich, um Sammlungen miteinander zu vergleichen und Ähnlichkeiten und Unterschiede zwischen Sätzen zu finden. Es gibt einige unterschiedliche Vergleiche, die wir zwischen zwei Sätzen anstellen können:

  1. Eine Vereinigung ist eine Kombination von Mengen. Man kann es sich am einfachsten als „A plus B“ merken.
  2. Durch eine Subtraktion werden Elemente aus Menge A entfernt, die in Menge B vorhanden sind. Man kann sich das am einfachsten als „A minus B“ merken.
  3. Eine Schnittmenge ist eine Menge mit Elementen, die in beiden Mengen vorkommen. Man kann es sich am einfachsten als gemeinsame Elemente merken, die zwischen A und B geteilt werden.
  4. Eine symmetrische Differenz ist eine Menge mit Elementen, die entweder in A oder B, aber nicht in beiden existieren. Es handelt sich um Gegenstände, die nicht zwischen A und B geteilt werden.

Schauen Sie sich hier die Zutaten einiger typisch italienischer Kaffeesorten an:

Lass Cappuccino:Set = [“espresso”, “milk”, “milk foam”]
let americano:Set = [“espresso”, “water”]
let machiato:Set = [“espresso”, “milk foam”]
let latte:Set = [“espresso”, “milk”]

Können wir Unterschiede und Gemeinsamkeiten zwischen Kaffeesorten feststellen? Lass es uns herausfinden!

Union

Lassen Sie uns zunächst eine Kombination aus Machiato und Latte herstellen. Hier ist wie:

let result = machiato.union(latte)
drucken(Ergebnis)
// Ausgang: [“espresso”, “milk foam”, “milk”]

Zufälligerweise sind dies genau die Zutaten eines Cappuccinos! Können wir diese Gleichheit testen? Ja! Hier ist wie:

if machiato.union(latte) == cappuccino {
print(„Machiato + Latte hat die gleichen Zutaten wie Cappuccino…“)
}

Aus Liebe zum Kaffee: Die Menge an Espresso, Milch und Schaum variiert zwischen Cappuccino, Latte und Machiato. In diesem Tutorial vergleichen wir nur Zutaten.

Subtraktion

Zweitens subtrahieren wir Americano vom Cappuccino. Was wäre ein Cappuccino ohne Espresso? Das:

let result = cappuccino.subtracting(americano)
drucken(Ergebnis)
// Ausgang: [“milk foam”, “milk”]

Es spielt keine Rolle, dass im Cappuccino kein Wasser enthalten ist, denn was nicht drin ist, kann man sowieso nicht abziehen. Und denken Sie daran, dass a – b nicht dasselbe ist wie b – a. So was:

let result = americano.subtracting(cappuccino)
drucken(Ergebnis)
// Ausgang: [“water”]
Überschneidung

Drittens machen wir eine Mischung aus Latte und Cappuccino. Welche Zutaten haben die beiden Kaffeesorten gemeinsam? Diese:

let result = latte.intersection(cappuccino)
drucken(Ergebnis)
// Ausgang: [“espresso”, “milk”]

Ein Cappuccino und ein Latte enthalten jeweils Espresso und Milch. Können wir auch herausfinden, was alle Kaffeesorten gemeinsam haben?

let result = latte.intersection(cappuccino).intersection(machiato).intersection(americano)
drucken(Ergebnis)
// Ausgang: [“espresso”]

Eindrucksvoll! Seien Sie jedoch vorsichtig bei der Verkettung dieser Vorgänge, da die Reihenfolge wichtig ist. Das Entfernen von „Espresso“ aus Machiato würde beispielsweise die Kette unterbrechen, obwohl „Espresso“ dann in 3 von 4 Kaffees geteilt wird.

Symmetrischer Unterschied

Viertens der Unterschied zwischen den Kaffeesorten. Was ist der Unterschied zwischen einem Americano und Latte? Es ist das:

let result = latte.symmetricDifference(americano)
drucken(Ergebnis)
// Ausgang: [“milk”, “water”]

Man könnte sagen, dass Milch und Wasser zwischen diesen beiden Kaffeesorten nicht geteilt werden. Dies wird als symmetrische Differenz bezeichnet, da Elemente aus beiden Mengen ausgewählt werden. Ein asymmetrischer Unterschied würde nur subtrahieren!

Praktische Anwendungsfälle

Die obigen Beispiele sind nicht praktikabel, es sei denn, Sie erstellen eine App, die auf Unterschiede zwischen italienischen Kaffeesorten hinweist. Was sind einige reale Anwendungsfälle für den Vergleich von Sätzen?

  • Wenn Sie Daten pro Wochentag gesammelt haben, können Sie eine Union verwenden, um die Daten für Dienstag und Mittwoch in einem Satz zu kombinieren.
  • Wenn Ihre Social-Media-App das Entfreunden von Benutzern ermöglicht, können Sie Subtract verwenden, um Follower für einen bestimmten Benutzer zu entfernen.
  • Wenn Sie wissen möchten, welche Follower die Benutzer A und B gemeinsam haben, können Sie eine Schnittmenge verwenden.
  • Wenn Sie sich im Krieg befinden und Spione finden möchten, die keine Doppelagenten sind, können Sie eine symmetrische Differenz verwenden. (Denk darüber nach!)

Genau wie andere Funktionen in Swift verfügt die vergleichende Funktionsfamilie für Set über Varianten, die Vorgänge direkt oder durch Rückgabe eines neuen Werts ausführen. In-Place-Algorithmen beanspruchen keinen zusätzlichen Platz, verändern aber Ihre ursprünglichen Werte. In Swift verwenden die meisten Funktionen, die direkt ausgeführt werden, starke Verben wie formIntersection(), sort() und subtract().

Pfui! Das ist ziemlich viel Kraft für einen Kollektionstyp, der so einfach und harmlos aussieht.

Wir haben untersucht, wie Sie Set verwenden können, um Elemente in einer Sammlung effizient zu finden, und wie dies mit einer Hash-Tabelle zusammenhängt. Und wir haben besprochen, wie Set Ihnen dabei helfen kann, Ähnlichkeiten und Unterschiede zwischen Datenpunkten zu finden. Eindrucksvoll!

Sets sind Teil von Sammlungen in Swift. Wir haben einige Sammlungstypen, wie zum Beispiel: