0

私はスクラブルゲームを構築していますが、単語辞書に問題があります。約700,000語、約18MBの大きさが含まれています。

今、私はdict全体を配列にロードしています。これはiPhone4では12秒かかります。 

wordList = [NSMutableArray arrayWithContentsOfFile: [[self applicationDocumentsDirectory] stringByAppendingString:@"/wordlist.plist"]];

2つの質問があります：

  1. ワードリストをより速くロードしたり、メモリを削減したりするためのより良い方法はありますか？

  2. 文字のセットからすべての可能な単語を取得するには、約12秒かかります。それをより速くすることは可能ですか？コードは次のとおりです。

    -(NSMutableArray *)getValidWords:(NSString *)letters{
    NSMutableArray *list = [[NSMutableArray alloc] init];

    for (int i = 0, c = [wordList count]; i < c; i++){
    if ([self isWordValid: [wordList objectAtIndex: i] forLetters:letters]){
        [list addObject:[wordList objectAtIndex: i]];
    }
}

return list;

    }

    - (BOOL)isWordValid:(NSString *)word forLetters:(NSString *)ltrs{
    int i, z;
    NSRange range;
    BOOL found;
    static NSMutableString *letters = nil;

    if ([word length] < 2) return NO;

    if(letters == nil) {
        letters = [[NSMutableString alloc] initWithString:ltrs];
    }
    else {
        [letters setString: ltrs];
    }

    found = NO;
    range.length = 1;
    for(i = 0; i < [word length]; i++){
        for(z = 0; z < [letters length]; z++){
            if([word characterAtIndex:i] == [letters characterAtIndex:z]){
                 range.location = z;
                 [letters deleteCharactersInRange: range];
                 found = YES;
                 break;
            }
       }
       if (found == NO){
            return NO;
       }

       found = NO;
  }

  return YES;
}
4

3 に答える 3

3

高速化するには、いくつか変更する必要があります。

  1. 古い C スタイルのループの代わりに高速な列挙を使用します。

  2. 多くのメソッド呼び出しを避けます。

  3. 可能であれば、NSPredicate や Regex を使用してください。

メソッドが呼び出されるたびに[letters length]、何百万回も見つけるのではなく (これはネストされたループの第 3 レベル内にあります)、変数に格納して使用します。

高速列挙: 代わりにfor(int i=0; i<[someArrays count];i++)使用しますfor(id object in someArrays)。

于 2013-01-15T12:23:16.617 に答える
2

手始めに、NSCharacterSetあなたから を作成しletters、長い関数を呼び出す前にこの関数を呼び出します。これは、可能性を減らすためのより高速なチェックであり、計算時間を改善するはずです。

NSCharacterSet* lettersSet = [NSCharacterSet characterSetWithCharactersInString:letters];

- (BOOL)isWordValid:(NSString*)word forLettersSet:(NSCharacterSet*)lettersSet {
    if ([word length] < 2) return NO;

    NSCharacterSet* wordLetters = [NSCharacterSet characterSetWithCharactersInString:word];

    return [lettersSet isSupersetOfSet:wordLetters];
}

理想的には、単語データベースは各単語の文字数を事前に計算しておく必要がevery = {e=2, r=1, v=1, y=1}あります (たとえば、これらの構造でのみ機能する必要があります。文字の順序は重要ではないことに注意してください。この事実を使用すると、アルゴリズムのパフォーマンスが大幅に向上します。

Core Data データベースを作成することもできます。すべての単語は、すべての文字の数値フィールドを持つ 1 つのレコードになります。次に、使用可能な単語を非常に高速に返すリクエストを作成できます。(もちろん、データベースはおそらくより多くのスペースを必要とします)。

編集:クラスを見つけたNSCountedSetので、それを使用してみましょう:

-(NSCountedSet*)lettersSetFromString:(NSString*)string {
    NSCountedSet* letters = [NSCountedSet set];
    [string enumerateSubstringsInRange:NSMakeRange(0, self.length)  
                               options:NSStringEnumerationByComposedCharacterSequences   
                            usingBlock:^(NSString *substring, NSRange substringRange, NSRange enclosingRange, BOOL *stop) {
        [letters addObject:substring];
    }];
} 

-(NSMutableArray *)validWordsForLetters:(NSString*)letters {
    NSCountedSet* lettersSet = [self lettersSetFromString:letters];

    NSMutableArray* results = [NSMutableArray array];

    for (NSString* word in wordList) {
        if ([word length] < 2) {
            continue;
        }

        NSCountedSet* wordLettersSet = [self lettersSetFromString:word];

        if ([wordLettersSet isSubsetOfSet:lettersSet]) {
            [results addObject:word];
        }
    }

    return results;
}

すべての単語のカウントされたセットを事前に生成すると、パフォーマンスが大幅に向上します。Core Data データベースを使用することは、OS メモリにとってより高速で優れたものになります。

于 2013-01-15T12:27:26.800 に答える
2

これを使って
[NSThread detachNewThreadSelector:@selector(fetchWords:) toTarget:self withObject:data];

メインスレッドでやらない

単語を検索する必要がある場合は、このコードを使用して変更してください

NSMutableArray *subpredicates = [NSMutableArray array];

    for(NSString *term in arryOfWordsToBeSearched) {
        NSPredicate *p = [NSPredicate predicateWithFormat:@"self contains[cd] %@",term];
        [subpredicates addObject:p];
        }

     NSPredicate *filter = [NSCompoundPredicate andPredicateWithSubpredicates:subpredicates];
    result = (NSMutableArray*)[arryOfDummyData filteredArrayUsingPredicate: filter];

// 結果は配列です

于 2013-01-15T12:04:15.017 に答える