Objective-c: Szybka rozmyta wyszukiwarka

Question

Czy ktoś wie o szybkiej implementacji dopasowania fuzzy search dla Objective-c? (algorytm odległościowy od odległości).

Znalazłem: https://github.com/thetron/StringScore/blob/master/NSString%2BScore.m - ale niestety jest dość powolne. Muszę to porównać do około 200 ciągów i jest ciągłe - według nowego naciśnięcia klawisza.

Wszelkie pomysły?

Answer 1

Jeśli NSString + Wynik robi to, co chcesz, ale jest zbyt powolny, można zacząć od przyspieszając go. Linie od 23 do 28 w -scoreAgainst:fuzziness:options: to kod instalacyjny, który należy wykonać tylko raz, a nie na każdym z 200 porównywanych. Więc wyciągnij ten kod do metody konfiguracji i zmierz ponownie.

Edit:

Jako ćwiczenie, ja forked StringScore, ekstrahuje kod instalacyjny i zrobił minimalne zmiany, aby uzyskać pewną poprawę wydajności, a następnie mierzy się go. Użyłem 1000 losowych słów, pogrupowałem je po trzy (np. "Zakłócone picie kropek"). Dla każdej z tych grup wykonałem instalację (jak powiedziano w tej oryginalnej odpowiedzi), a następnie porównałem ciąg do wszystkich 1000 grup. Zajmuje to około 11 sekund na moim Core 2 Duo.

Porównywanie jednego słowa do 1000 trwa około 11 ms. Teraz potrzebujesz tylko od 1 do 200, więc prawdopodobnie będzie to znacznie poniżej 10 ms. To powinno działać dla ciebie?

(Nawiasem mówiąc, prawie połowę czasu spędził jeszcze w rangeOfString: znalezienie pojedynczego znaku, to prawdopodobnie można zrobić o wiele szybciej, ale nie chcę, aby w szczegółach algorytmu.)

Answer 2

nie wiem o algorytmie masz na myśli realizowanego w Objective-C

Czy istnieje powód, dla którego nie używasz wbudowanej funkcjonalności NSPredicate z CoreData. Znalazłem to bardzo szybko, szukając więcej niż 200 ciągów.

Na przykład, biorąc pod uwagę NSString * searchText i fetchedResultsController

NSPredicate * predicate = [NSPredicate predicateWithFormat:@"name CONTAINS[cd] %@", searchText]; 

self.filteredListContents = [[[self fetchedResultsController] fetchedObjects] filteredArrayUsingPredicate:predicate]; 

Można również użyć NSPredicate na NSArray, który Zakładam, że masz wypróbowany i okazał się zbyt powolne.

Z dokumentacji jabłoni

NSMutableArray *array = 
[NSMutableArray arrayWithObjects:@"Nick", @"Ben", @"Adam", @"Melissa", nil]; 

NSPredicate *bPredicate = [NSPredicate predicateWithFormat:@"SELF beginswith[c] 'a'"]; 

NSArray *beginWithB = [array filteredArrayUsingPredicate:bPredicate]; 
// beginWithB contains { @"Adam" }. 

NSPredicate *sPredicate = [NSPredicate predicateWithFormat:@"SELF contains[c] 'e'"]; 

[array filterUsingPredicate:sPredicate]; 
// array now contains { @"Nick", @"Ben", @"Melissa" } 

https://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/Predicates/Articles/pSyntax.html