Ich frage mich, was ist die große O-Notation für die Iteration durch NSSet. Die Antwort für ein NSArray ist offensichtlich O (n) - aber was ist die Antwort für NSSet? Auch - ich nehme an, die gleiche Antwort würde für NSDictionary gelten?Was ist die Groß-O-Notation für die Iteration durch NSSet und NSDictionary
Sie können sich ein Bild von der Rechenkomplexität von Apples Datenstrukturen machen, indem Sie sich die Kommentare in den Kopfzeilen ihrer überbrückten Core Foundation-Äquivalente ansehen (da sie im Grunde denselben Code unter der Haube verwenden).
Interessanterweise ist die Zeitkomplexität von CFArray ist nicht tatsächlich garantiert O (n) sein:
Komplexitäts
Die Zugriffszeit für einen Wert in der Anordnung garantiert bei sein schlechteste O (LG N) für jede Implementierung, aktuelle und zukünftige, aber wird oft O (1) (konstante Zeit) sein. Lineare Suchoperationen ähnlich haben eine Worst-Case-Komplexität von O (N * lgN), obwohl die Grenzen typischerweise enger sind, und so weiter. Einfüge- oder Löschoperationen werden typischerweise linear in der Anzahl von Werten in dem Array sein, aber kann im schlimmsten Fall in einigen Implementierungen eindeutig O (N * lgN) sein. Es gibt keine bevorzugten Positionen innerhalb des Arrays für die Leistung; das heißt, es ist nicht unbedingt schneller auf Werte mit niedrigen Indizes zuzugreifen, oder Werte mit hohen Indizes einzufügen oder zu löschen, oder was auch immer.
Diese Zeit Komplexität lassen vermuten, dass CFArray (und damit NSArray) könnte in der Tat als ein Baum implementiert werden (Tests zeigen, dass es könnte sogar zwischen mehreren zugrunde liegenden Datenstrukturen werden schaltend).
Ebenso für CFDictionary, die gegebenen Grenzen haben schon ein breites Spektrum:
Komplexitäts
Die Zugriffszeit für einen Wert im Wörterbuch ist garantiert bei schlimmsten OS (N) für seine jede Implementierung, aktuelle und zukünftige, aber wird oft O (1) (konstante Zeit) sein. Einfüge- oder Löschvorgänge sind typischerweise ebenfalls konstante Zeiten, sind aber in einigen Implementierungen O (N * N) in dem schlechtesten Fall . Der Zugriff auf Werte über einen Schlüssel ist schneller als der direkte Zugriff auf Werte (wenn es solche Operationen gibt). Wörterbücher verwenden tendenziell wesentlich mehr Speicher als ein Array mit der gleichen Anzahl von Werten.
Ich war nicht in der Lage einen ähnlichen Kommentar in dem Core Foundation-Header für CFSet zu finden, aber Inspektion des Quellcodes zeigt, dass es auf CFBasicHash basiert, die eine Hash-Tabelle ist, so würde die Zeitkomplexität als typisch für eine Hash-Tabelle - typischerweise O (1) Einfügen, Entfernen und Testen und im schlimmsten Fall O (n).
Wenn Sie wirklich wissen möchten, wie diese Datenstrukturen genau funktionieren, ist Core Foundation Open Source, so dass Sie den Quellcode unter Apple's website lesen können.
Wenn Sie Wert auf Leistung legen, stellen Sie sicher, dass Sie "schnelle Enumeration" oder Blöcke verwenden. Verwenden Sie keine regelmäßige C 'for' oder' while' Schleife. https://developer.apple.com/library/ios/documentation/Cocoa/Conceptual/Collections/Articles/Enumerators.html –
Diese Frage ist eher ein Kuriositätsthema als eine tatsächliche Frage – YogevSitton
ich sehe. Nun, dann hängt die Antwort davon ab, was im Set ist. NSSet ist keine einfache Klasse, ich wäre nicht überrascht, wenn die Implementierung Zehntausende von Zeilen Code ist. Für Anfänger gibt es nicht einmal eine echte Klasse namens "NSSet". Das ist nur ein Name, der verwendet wird, um alle realen Klassen zu verbinden, die in Sets eingehen. Welche Klasse tatsächlich verwendet wird, ändert sich abhängig vom Inhalt des Sets und den Mustern, die Ihr Code verwendet, um auf das Set zuzugreifen. Im Allgemeinen hat ein Set mit 5 Items sehr unterschiedliche Leistungsmerkmale wie ein Set mit 5 Milliarden Items. Und ja, es kann so viele Daten verarbeiten. –