Qual è il modo più veloce per cercare tra le stringhe in Objective-C?

Sto implementando una sorta di completamento automatico per un'app iOS. I dati che sto utilizzando per i valori di completamento automatico sono un file di testo separato da virgole con circa 100.000 stringhe. Questo è quello che sto facendo ora:Qual è il modo più veloce per cercare tra le stringhe in Objective-C?

leggere il file di testo, e creare un NSArray con 100.000 NSString.
Come l'utente, fare [array containsObject:text]

Sicuramente c'è una/più veloce modo migliore per farlo ricerca. qualche idea?

fonte

2012-07-20 user1007895

Puoi provare a saltare le stringhe che non corrispondono nemmeno alla prima lettera, nessun punto nella ricerca dalle mele allo yogurt se la tua parola è zebra. Non sono sicuro del modo migliore per implementare questo, forse un array multidimensionale? La prima dimensione potrebbe essere la prima lettera, la seconda lettera della seconda dimensione, ecc., Fino a quando non è come terza o quarta lettera, quindi potresti semplicemente contenere il resto della parola. –

Se non hai bisogno di ordinare penso che i set siano più veloci quando si controlla se contiene o meno un oggetto. Tuttavia non è ancora ottimizzato per le stringhe.Probabilmente dovresti esaminare elementi come alberi binari, ecc. Se hai bisogno di creare un codice personalizzato, l'approccio generale sarebbe simile, indipendentemente dalla piattaforma/lingua con cui stai lavorando. –

C'è * sempre * un modo più veloce. Stai vedendo un ritardo nella tua interfaccia utente, però? Ho fatto esattamente la stessa cosa per il completamento automatico (con un array di input più piccolo) e non ho avuto lag visibile, nonostante l'algoritmo di ricerca ingenuo. – kubi

Assolutamente, c'è! Tuttavia non è "in Objective-C": molto probabilmente, dovresti codificarlo da solo.

L'idea è di convertire l'elenco di stringhe in una suffix tree, una struttura dati che consente di cercare per prefisso molto rapidamente. La ricerca di possibili completamenti in un albero di suffisso è molto veloce, ma la struttura stessa non è facile da costruire. Una rapida ricerca su Internet ha rivelato che non vi è un'implementazione prontamente disponibile nell'Obiettivo C, ma potresti essere in grado di port an implementation in another language, use a C implementation, o anche di scrivere il tuo se non sei particolarmente sollecitato per il tempo.

Forse un approccio più semplice sarebbe quello di ordinare le stringhe in ordine alfabetico ed eseguire una ricerca binaria sul prefisso che è stato inserito fino a quel momento. Sebbene non sia efficiente come un albero dei suffissi, l'approccio dell'array ordinato sarà accettabile per le stringhe da 100 K, perché si arriva al punto giusto in meno di diciassette controlli.

fonte

2012-07-20 20:42:34 dasblinkenlight

+1 per indicare che Objective-C è C e non dovresti aver paura di passare a C quando si guardano le operazioni ad alte prestazioni :) Seguirò anche l'albero binario che è probabilmente il più facile da implementare. – Taum

+1 adoro la tua risposta – Omarj

NDTrie (https://github.com/nathanday/ndtrie) e PJTernarySearchTree (https://github.com/peakji/PJTernarySearchTree) sono proprio questo in Objective-C! –

La più semplice è probabilmente la ricerca binaria. Vedi -[NSArray indexOfObject:inSortedRange:options:usingComparator:].

In particolare, mi piacerebbe provare qualcosa di simile:

pre-ordinare l'array che si salva al file
quando si carica la matrice, forse @selector(compare:) (se si è preoccupato essere accidentalmente non ordinati o modificare l'ordinamento Unicode per alcuni casi limite). Questo dovrebbe essere di circa O (n) assumendo che la matrice sia in gran parte già ordinata.
Per trovare la prima corrispondenza potenziale, [array indexOfObject:searchString inSortedRange:(NSRange){0,[array count]} options:NSBinarySearchingInsertionIndex|NSBinarySearchingFirstEqual usingComparator:@selector(compare:)]
Cammina lungo la matrice finché le voci non contengono più searchString come prefisso. Probabilmente si vuole fare caso il confronto/diacritic/larghezza-insensitive per determinare se si tratta di un prefisso (NSAnchoredSearch | NSCaseInsensitiveSearch | NSDiacriticInsensitiveSearch | NSWidthInsensitiveSearch)

Questo non può "correttamente" gestire tutte le localizzazioni (Turco in particolare), ma nessuno dei due sostituirà compare: con localizedCompare:, né ingenuo piegatura delle corde. (È lungo solo 9 righe, ma ha impiegato circa un giorno di lavoro per avere ragione e ha circa 40 linee di codice e 200 linee di test, quindi probabilmente non dovrei condividerlo qui.)

fonte

2012-07-20 20:59:14

Qual è il modo più veloce per cercare tra le stringhe in Objective-C?

risposta

Problemi correlati