Ich kann auf zwei Arten in einem NSDictionary auf das Vorhandensein eines Schlüssels testen:Welche Methode zum Überprüfen, ob ein NSDictionary einen bestimmten Schlüssel enthält, ist schneller?
BOOL containsKey = [[dictionary allKeys] containsObject:foo];
BOOL containsKey = ([dictionary objectForKey:foo] != nil);
, welche Methode ist schneller, und warum?
Ein Hash-Lookup sollte im Allgemeinen schneller sein als über alle Wörterbuchschlüssel gehen und ein Array von ihnen erstellen (Speicherzuweisung ist relativ teuer) und dann das Array durchsuchen (was nicht einmal eine binäre Suche sein kann, da das Array nicht sortiert ist).
Um der Wissenschaft willen habe ich zwei ausführbare Dateien erstellt, die jeden Stil 1 Million Mal ausführen und zeitlich festlegen.
Mit AllKeys:
real 0m4.185s
user 0m3.890s
sys 0m0.252s
Mit objectForKey:
real 0m0.396s
user 0m0.189s
sys 0m0.029s
Offensichtlich können verschiedene Faktoren beeinflussen diese - Größe des Wörterbuchs, das Zwischenspeichern der AllKeys Wert zurückgeben, usw. würde ich nicht erwarten Es gibt einen Fall, in dem die Array-Suche schneller ist als die Suche nach einem Wörterbuch.
Ich sehe nicht, wie die Frage nach dem Array allKeys könnte möglicherweise schneller sein, sonst würde NSDictionary zumindest das Äquivalent intern tun.
EDIT: Ich nehme an, dass Sie einen Fall konstruieren könnten, wo die allKeys Methode schneller sein würde - durch eine lange Zeit in Ihrem Schlüssel hash Methode nehmen, aber nicht in Ihrem isEqual: Verfahren, zum Beispiel. Und Sie könnten auch in eine verrückte Implementierung für NSDictionary tauschen, in dem sie auch vertauscht werden.
Vereinbar. Nach allKeys zu fragen, wird dir ein NSArray geben, das iterativeObject muss dann iterativ nach foo suchen suchen.Auf der anderen Seite verwendet objectForKey einen Hash, um die Position von foo im Wörterbuch zu berechnen, so dass die Existenz von foo direkt bestimmt werden kann. –
Wenn Sie über Leistungsfragen wie diese nachdenken, denken Sie daran, dass die Foundation-Datenklassen ihre zugrunde liegenden Datenstrukturen auslagern, je nachdem, wie viele Objekte Sie darin speichern. Zum Beispiel denke ich, dass ein kleines NSArray tatsächlich eine Hash-Tabelle für Speicher verwendet, bis sie eine bestimmte Größe erreicht.
Ist es nicht wahrscheinlicher, dass umgekehrt eine Hash-Tabelle vorteilhafter wird? Das Testen von etwa 10 Objekten auf Gleichheit ist trivial. Haben Sie mehrere tausend Objekte, und eine Hash-Tabelle wird zu einem klaren Gewinn. –
Sie könnten sehr gut Recht haben, ich erinnere mich, dass jemand vor einiger Zeit einen Artikel (zusammen mit Benchmarks) darüber geschrieben hat, aber ich habe seitdem nicht viel darüber nachgedacht. –
http://ridiculousfish.com/blog/posts/array.html wäre der Beitrag, an den Sie denken –
"Bitte zeigen Sie Ihre Arbeit?" Sie haben die gleichen Werkzeuge wie wir. Sie sollten versuchen, den unterschiedlichen Code zu profilieren, wenn Sie die Antwort auf so etwas wissen möchten. – danielpunkass
Daniel ist absolut richtig, das war ein sehr fauler Weg, um die Antwort auf eine einfach zu testende Frage zu bekommen. Aber ich habe eine wirklich gute Antwort und einige echte Leistungsergebnisse, also danke allen, dass ich ein bisschen faul geworden bin. – alfwatt
Ich bekomme, dass Leute durch die "Bitte zeigen Sie Ihre Arbeit" -Linie in der obigen Frage ein wenig ausgelöscht werden, aber ich dachte, dass der Punkt des Stapelüberlaufs ist, Antworten auf alle Arten von grundlegenden Fragen zu haben, nein? Also, um zu klären, habe ich das nicht gefragt, weil ich die Antwort nicht kenne, konnte mich selbst nicht herausfinden, oder ein unhöflicher Idiot zu sein. Eher, weil die Antwort nicht sofort offensichtlich ist, es sei denn, Sie sind vertraut mit den Sammlungen der Stiftung schien es eine gute Frage und Antwort zur Verfügung zu haben. – alfwatt