Jaki jest najszybszy sposób wyszukiwania ciągów w Objective-C?

Wprowadzam rodzaj autouzupełniania dla aplikacji na iOS. Dane używane dla wartości autouzupełniania to plik tekstowy z wartościami rozdzielonymi przecinkami, zawierający około 100 000 ciągów. To, co robię teraz:Jaki jest najszybszy sposób wyszukiwania ciągów w Objective-C?

Przeczytaj plik tekstowy i utworzyć NSArray z 100000 NSString.
Jak typów użytkowników, wykonaj [array containsObject:text]

Na pewno jest lepszy/szybszy sposób to zrobić odnośnika. jakieś pomysły?

Źródło

2012-07-20 user1007895

Możesz spróbować pomiń ciągi, które nie pasują nawet do pierwszej litery, nie ma sensu szukanie od jabłek do jogurtu, jeśli twoje słowo to zebra. Nie jestem pewien najlepszego sposobu na wdrożenie tego, być może wielowymiarową tablicę? Pierwszy wymiar może być pierwszą literą, drugim wymiarem drugiej litery itd., Aż do trzeciej lub czwartej litery, wtedy możesz po prostu zachować pozostałą część słowa. –

Jeśli nie potrzebujesz zamawiania, wydaje mi się, że zestawy są szybsze przy sprawdzaniu, czy zawiera obiekt, czy nie. Nadal nie jest zoptymalizowany pod kątem ciągów.Powinieneś zajrzeć do takich rzeczy, jak drzewa binarne itp., Jeśli potrzebujesz niestandardowego kodu, ogólne podejście byłoby podobne, niezależnie od platformy/języka, z którym pracujesz. –

Zawsze jest * szybszy sposób. Czy widzisz jednak opóźnienie w twoim interfejsie? Zrobiłem dokładnie to samo dla autouzupełniania (z mniejszą tablicą wejściową) i nie miałem widocznego opóźnienia, pomimo naiwnego algorytmu wyszukiwania. – kubi

Absolutnie, jest! Nie jest to jednak "w Objective-C": najprawdopodobniej trzeba by to zakodować samemu.

Chodzi o to, aby przekonwertować listę ciągów znaków na suffix tree, strukturę danych, która umożliwia szybkie wyszukiwanie według prefiksu. Wyszukiwanie możliwych uzupełnień w drzewie sufiksu jest bardzo szybkie, ale sama konstrukcja nie jest łatwa do zbudowania. Szybkie wyszukiwanie w Internecie ujawniło, że nie ma łatwo dostępnej implementacji w Celu C, ale możesz być w stanie uzyskać port an implementation in another language, use a C implementation, a nawet napisać własną, jeśli nie jesteś szczególnie naciskany na czas.

Być może łatwiejszym podejściem byłoby sortowanie ciągów alfabetycznych i uruchamianie wyszukiwania binarnego na prefiksie, który został wprowadzony do tej pory. Choć nie jest to tak wydajne jak drzewo przyrostków, posortowana metoda tablicowa będzie akceptowalna dla ciągów 100K, ponieważ trafisz w odpowiednie miejsce w ramach siedemnastu kontroli.

Źródło

2012-07-20 20:42:34 dasblinkenlight

+1 za wskazanie Celu C jest C i nie powinieneś się obawiać, że spadniesz do C patrząc na zadania wymagające dużej wydajności :) Będę również nazywał drzewo binarne, które jest prawdopodobnie najłatwiejsze do implementacji. – Taum

+1 po prostu kochaj swoją odpowiedź – Omarj

NDTrie (https://github.com/nathanday/ndtrie) i PJTernarySearchTree (https://github.com/peakji/PJTernarySearchTree) są dokładnie tym w Objective-C! –

Najprostszym jest prawdopodobnie wyszukiwanie binarne. Zobacz -[NSArray indexOfObject:inSortedRange:options:usingComparator:].

W szczególności chciałbym spróbować czegoś takiego:

Pre-sort tablica się zapisanie do pliku
Podczas ładowania tablicę, ewentualnie @selector(compare:) (jeśli martwisz się o nią przypadkowo nieposortowane lub kolejność sortowania Unicode dla niektórych przypadków krawędzi). Powinno to być w przybliżeniu O (n) przy założeniu, że tablica jest już w większości sortowana.
Aby znaleźć pierwszy potencjalny mecz, [array indexOfObject:searchString inSortedRange:(NSRange){0,[array count]} options:NSBinarySearchingInsertionIndex|NSBinarySearchingFirstEqual usingComparator:@selector(compare:)]
Przechodzi w dół tablicy, dopóki wpisy nie będą już zawierać searchString jako przedrostka. Prawdopodobnie chcesz zrobić przypadków porównań/diakrytyczną/szerokość niewrażliwe aby ustalić, czy jest to prefiks (NSAnchoredSearch | NSCaseInsensitiveSearch | NSDiacriticInsensitiveSearch | NSWidthInsensitiveSearch)

To może nie „prawidłowo” obsłużyć wszystkie lokalizacje (turecki w szczególności), ale żadna nie zastąpi compare: z localizedCompare: ani nie będzie naiwne składanie ciągów. (Ma tylko 9 linii, ale zajęło mu około jednego dnia pracy, ma około 40 linii kodu i 200 linii testowych, więc prawdopodobnie nie powinienem się nim dzielić.)

Źródło

2012-07-20 20:59:14

Jaki jest najszybszy sposób wyszukiwania ciągów w Objective-C?

Odpowiedz

Powiązane problemy