iphone - 搜索 NSArray 包含 NSDictionary，具有“时间效率”

Question

我知道已经有很多问题被问到了，但是我要再提出一个问题。我有一个数组包含大量（数千条记录）NSDictionary格式的数据，我正在尝试在字典中的键中执行搜索到数组中。

我正在UITextField - (BOOL)textField:(UITextField *)textField shouldChangeCharactersInRange:(NSRange)range replacementString:(NSString *)string;数据源方法中执行搜索，

我的搜索要求在整个字符串中，

示例字符串，

aaa, abeb, abcd, abbec 类似字符串

搜索流程，

如果a返回我所有的字符串，

如果aa只返回 aaa，

如果ab返回abeb, abcd, abbec喜欢，

重要的是，如果cd它只返回 abcd

我用这些方法试过了，

使用NSPredicates

NSLog(@"start search at : %@",[NSDate date]);
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"Name contains[cd] %@", matchString];
searchArray = [[meadArray filteredArrayUsingPredicate:predicate] mutableCopy];
NSLog(@"Search found count = %d",searchArray.count);
[tableCheck reloadData];
NSLog(@"End search at : %@",[NSDate date]);

另一种方式 - 通过迭代，

NSLog(@"start search at : %@",[NSDate date]);
for (NSDictionary *word in arrayNames)
{
    if ([matchString length] == 0)
    {
        [searchArray addObject:word];
        continue;
    }
    NSRange lastRange = [[[word valueForKey:@"Name"] uppercaseString] rangeOfString:upString];

    if ( lastRange.location != NSNotFound)
    {
        if(range.location == 0 || lastRange.location == 0)
        {
            [searchArray addObject:word];
        }
    }
}    
NSLog(@"End search at : %@",[NSDate date]);

这两种方法都运行良好，结果如我所料，但仅在模拟器中！当我在设备中测试相同的内容时，根据搜索的扩展，它大约需要 1 / 2 / 3 秒，首先说如果我输入，a它需要 3 秒，因为aa它需要大约 2 秒，依此类推。IT LOOKS CLUMSY ON DEVICE, ANY PRESSED KEY WILL BE REMAIN HIGHLIGHTED UNTIL SEARCH NOT DONE.

有什么方法可以让我使用我正在使用的相同方法或任何其他替代方法执行更快的搜索！

更新 1

还尝试使用CFArrayBSearchValues它只返回搜索字符串的索引，但我想要返回所有匹配的字符串的东西。

unsigned index = (unsigned)CFArrayBSearchValues((CFArrayRef)meadArray, CFRangeMake(0, CFArrayGetCount((CFArrayRef)meadArray)), (CFStringRef)matchString,(CFComparatorFunction)CFStringCompare, NULL);

更新 2

As per the Alladinian comment, I performed search operation in background thread, yes now its not lock UI, but still searching is too slow, What I'm doing is, performing a selector for some delay say 0.25 seconds, also cancelling any previous selector calls, and then performing searching in background, also reloading table in main thread. Its working like, If I type character with some delay, its works good, but if I type whole word at once, it will loading / updating table as per the characters pressed, at last it will show me the actual output, takes 3-4 seconds for showing the actual content.

Any suggestion or help highly appreciated!

score 2 · Accepted Answer

Your search is slower than it needs to be. searchString.length shouldn't be checked in the loop, that should be done outside. valueForKey: is a very general method that allows you to access any kinds of different key paths - objectForKey is a lot lot faster! Next, your check for a case sensitive match always translates the whole word to uppercase. That's not only incorrect once your users enter some more interesting search strings, but it's also slow and memory intensive (if there are thousands of strings, you are creating thousands of auto-released objects). Use rangeOfString:options: instead.

Finally, you can try the NSArray methods enumerateObjectsUsingBlock: or enumerateObjectsWithOptions:usingBlock: which allows the enumeration to happen on multiple threads.

indexesOfObjectsPassingTest: or indexesOfObjectsWithOptions:passingTest: gets the indexes of the elements you are looking for, which will be faster. This is especially useful if you do another search for a longer string, for example searching for abc after searching for ab, because there are NSArray methods restricting a search to an index set.

score 1 · Accepted Answer

I have used sqlite's Full Text Search modules in several projects and they work extremely well. It will require providing your own compiled version of sqlite, which can be a bit tricky - but the whole process is explained here.

Depending on what you need to do, you may want to pre-fill this database, or insert data as you receive it - or some combination of both. Trying to program a solution yourself would be an interesting exercise, but you would be reinventing algorithms that already exist in sqlite FTS.

If you are doing a search-as-you-type, you have to make sure you are queuing your operations properly in the background and that they are cancellable - there are many ways to pull this off; a very popular one uses NSOperation.

Hope this helps.

score 1 · Accepted Answer

This answer is following anktastic answer, I am also adding my answer because someone will directly get a solution for which we made lots of effort :)

- (BOOL)textField:(UITextField *)textField shouldChangeCharactersInRange:(NSRange)range replacementString:(NSString *)string 
{
    //Cancel any previous selector calls
    [NSRunLoop cancelPreviousPerformRequestsWithTarget:self];

        if(string.length > 0)
        {
            NSString *str = [txt1.text substringToIndex:[txt1.text length] - 1];
            //delay is useful in smooth search - if you're performing web service calls for searching on cloud, then you should give delay as per your test
            [self performSelector:@selector(startSearch:) withObject:str afterDelay:0.05f];
        }
    }
}

- (void) startSearch:(NSString *)matchString
{
    //Cancel any previous operation added in queue
    [queue cancelAllOperations];
    //Create new operation
    NSInvocationOperation* operation = [[NSInvocationOperation alloc]initWithTarget:self selector:@selector(search:) object:matchString];
    [queue addOperation:operation];
}

- (void) search:(NSString *)matchString
{
    //Performing search operation
    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"Name contains[cd] %@", matchString];
    searchArray = [[meadArray filteredArrayUsingPredicate:predicate] mutableCopy];
    //only call again after any previous reload done
    [self performSelectorOnMainThread:@selector(reloadInMainThread) withObject:nil waitUntilDone:YES];
}

- (void) reloadInMainThread 
{
    //Reloading table in main thread for instance search effect
    [tableCheck reloadData];
}

score 0 · Accepted Answer

Does the strings in array/dictionary change? If not, I suggest that you extract all keys in dictionary to a single array. Do this before you search, and you only need to do this once.

If I didn't misunderstood your question, my suggestion is like this:

NSArray *arrayOfDicts = /*the array with dictionarys you have*/

NSMutableArray *allKeys = [NSMutableArray array]

for (NSDictionary *d in arrayOfDicts) {
     for (NSString *key in d) {
          [allKeys addObject:key];
     }
}

then search the allKeys array.

score 0 · Accepted Answer

Case insensitive string comparison is slower than case sensitive comparison. You could store uppercaseName as an additional key in your dictionaries (or as additional column in the sqlite table) and change the predicate to

[NSPredicate predicateWithFormat:@"uppercaseName CONTAINS %@", [matchString uppercaseString]]

iphone - 搜索 NSArray 包含 NSDictionary，具有“时间效率”

5 回答 5

Related

Reference