Ist objectForKey langsam für große NSDictionary?

  1. Angenommen, wir haben sehr große NSDictionary, wenn wir möchten, rufen Sie die objectForKey Methode, wird es machen viele Vorgänge in der core-Wert zu erhalten? Oder wird es Punkt-zu-Wert in den Speicher direkt?
  2. Wie funktioniert es im Kern?
InformationsquelleAutor Almas Adilbek | 2011-11-13
  1. 28

    Den CFDictionary Abschnitt der Sammlungen Programmierung Themen für Core Foundation (die Sie in Aussehen sollte, wenn Sie mehr wissen wollen) Staaten:

    Einem dictionary—Objekt der CFDictionary Art—ist ein hashing-basierte
    Sammlung, deren Tasten für den Zugriff auf Ihre Werte willkürlich sind,
    im Programm definierte Teile der Daten (oder Zeiger auf Daten). Obwohl der key
    ist in der Regel ein string (oder, in Core Foundation, eine CFString-Objekt), es
    kann alles sein, die passen in der Größe einer Zeiger—Ganzzahl,
    Verweis auf ein Core-Foundation-Objekt, ein Zeiger auf eine Daten -
    Struktur (so unwahrscheinlich das sein mag).

    Dies ist, was wikipedia zu sagen hat, über hash-Tabellen:

    Ideal, die hash-Funktion sollte die Zuordnung jeder mögliche Schlüssel zu einem einzigartigen
    slot-index, aber dieses ideal ist in der Praxis selten erreichbar (es sei denn,
    die hash-Schlüssel sind fest fixiert, d.h. neue Einträge werden nie zur Tabelle Hinzugefügt
    nachdem er erstellt wurde). Vielmehr sind die meisten hash-Tabelle designs davon ausgehen, dass
    hash-Kollisionen—verschiedene Schlüssel, die Karte zu der gleichen hash—Wert-wird
    auftreten und müssen untergebracht werden in gewisser Weise. In einem gut dimensionierten hash
    Tabelle sind die durchschnittlichen Kosten (Anzahl der Instruktionen) für jede Suche ist
    unabhängig von der Anzahl der Elemente in der Tabelle gespeichert. Viele hash
    Tisch-designs auch ermöglichen, beliebigen Einfüge-und Löschvorgänge
    Schlüssel-Wert-Paare, bei Konstanten Mittelwert (ja, abgeschrieben) Kosten pro
    Betrieb.

    Die Leistung hängt daher von der Qualität der hash. Wenn es gut ist, dann ist der Zugriff auf Elemente einer O(1) operation (d.h. nicht abhängig von der Anzahl der Elemente).

    EDIT:

    In der Tat nach dem Lesen weiter die Sammlungen Programmierung Themen für Core Foundation, apple gibt eine Antwort auf Ihre Frage:

    Die Zugriffszeit für einen Wert in einem CFDictionary Objekt ist garantiert
    werden im schlimmsten Fall O(log N) für jede Umsetzung, aber oft ist O(1)
    (Konstante Zeit). Einfügen oder löschen von Operationen sind in der Regel in
    Konstante Zeit, aber O(N*log N) im schlimmsten Fall. Es ist
    schneller Zugriff auf die Werte über einen Schlüssel als den Zugriff auf Sie direkt.
    Wörterbücher neigen dazu, wesentlich mehr Speicher als ein array mit
    die gleiche Anzahl von Werten.

    • Klar! Danke! 😉
    • Die Tatsache, dass es zeigt, entweder in O(log N) oder O(1) macht mich Frage mich, ob Sie eine rot-schwarz-Baum implementation hat, oder wenn die log-N-Konten für die doppelte Verkettung.
    • Der Schlimmste Fall ist für hash-Kollisionen
    • Für die Zukunft Verweise, Core Foundation ist open source. CFDictionary umgesetzt wird intern durch ein CFBasicHash.
    • gut zu wissen. Ich war nur darüber nachzudenken, wie CFArray hat mehrere Implementierungen für verschiedene Zwecke. und fragte mich, ob das auch mit dem Wörterbuch.
    InformationsquelleAutor jbat100
  2. 4

    NSDictionary ist im wesentlichen eine Hash-Tabelle Struktur, also Big-O für den lookup ist O(1). Um zu vermeiden, dass Umschichtungen (und zu erreichen, die O(1)) Komplexität, die Sie verwenden sollten dictionaryWithCapacity: erstellen Sie ein neues Wörterbuch mit der entsprechenden Größe in Bezug auf die Größe Ihres Datenbestandes.

    • Mit dictionaryWithCapacity wird im Normalfall bieten nur minimale oder gar keine Leistung zu erhöhen. In der Tat die Apple docs sagen, dass es ist nur ein Hinweis. Ich habe ein Benchmark mit NSArray Größen zwischen 10 und 10.000.000 und fand keinen sinnvollen Vorteil. Der größte Nachteil ist die Zeit und denken verbringen, auf der Berechnung, dass ist besser spendt
    • Sie können nicht garantieren, wird es keine Kollisionen in der Tabelle unabhängig von der Tabellengröße.
    InformationsquelleAutor mja
Schreibe einen Kommentar