Was ist der schnellste Weg, um Strings in Objective-C zu suchen?

Absolut, da ist es! Es ist jedoch nicht "in Objective-C": Wahrscheinlich müssten Sie es selbst programmieren.

Die Idee besteht darin, Ihre String-Liste in eine Suffix-Struktur zu konvertieren Struktur, mit der Sie sehr schnell nach Präfix suchen können. Die Suche nach möglichen Vervollständigungen in einem Suffix-Baum ist sehr schnell, aber die Struktur selbst ist nicht einfach zu erstellen. Eine schnelle Suche im Internet ergab, dass es in Objective C keine leicht verfügbare Implementierung gibt, aber Sie können möglicherweise Eine Implementierung in einer anderen Sprache portieren, Verwenden Sie eine C-Implementierung , oder schreiben Sie Ihre eigene, wenn Sie nicht besonders auf Zeit bedacht sind.

Vielleicht wäre es einfacher, die Strings alphabetisch zu sortieren und eine binäre Suche nach dem Präfix durchzuführen, das bisher eingegeben wurde. Obwohl sie nicht so effizient ist wie ein Suffix-Baum, ist der Sorted-Array-Ansatz für 100K-Strings akzeptabel, weil Sie in weniger als 17 Checks an den richtigen Punkt kommen.

Am einfachsten ist wahrscheinlich die binäre Suche. Siehe -[NSArray indexOfObject:inSortedRange:options:usingComparator:] .

Insbesondere würde ich Folgendes versuchen:

• Sortieren Sie das von Ihnen gespeicherte Array in der Datei
vor
• Wenn Sie das Array laden, möglicherweise @selector(compare:) (wenn Sie befürchten, dass es versehentlich unsortiert wurde oder die Unicode-Sortierreihenfolge für einige Edge-Fälle geändert wird). Dies sollte ungefähr O (n) sein, vorausgesetzt, das Array ist größtenteils bereits sortiert.
• Um die erste mögliche Übereinstimmung zu finden, [array indexOfObject:searchString inSortedRange:(NSRange){0,[array count]} options:NSBinarySearchingInsertionIndex|NSBinarySearchingFirstEqual usingComparator:@selector(compare:)]
• Gehen Sie das Array nach unten, bis die Einträge searchString nicht mehr als Präfix enthalten. Wahrscheinlich möchten Sie case / diacritic / width-insensitive Vergleiche durchführen, um festzustellen, ob es sich um ein Präfix handelt (NSAnchoredSearch | NSCaseInsensitiveSearch | NSDiacriticInsensitiveSearch | NSWidthInsensitiveSearch)

Dies kann nicht "korrekt" mit allen Gebietsschemata umgehen (insbesondere Türkisch), aber auch nicht compare: durch localizedCompare: ersetzen, noch wird naive String-Faltung. (Es ist nur 9 Zeilen lang, aber dauerte etwa einen Tag Arbeitszeit, um richtig zu kommen und hat etwa 40 Zeilen Code und 200 Zeilen Test, also sollte ich es hier wahrscheinlich nicht teilen.)