4

ここ SO で得た多くの支援のおかげで、合計約 50,000 の単語のリストに対して、部分アナグラムの約 15,000 の 8 文字の単語のリストをチェックするアルゴリズムを取得しました (したがって、合計で1 億 800 万回の反復)。このメソッドは、比較ごとに 1 回呼び出します (つまり、7 億 5000 万回)。次のエラーが発生します。常に、1,350 までの 119 回目の反復の途中にあるはずです。

AnagramFINAL(2960,0xac8c7a28) malloc: *** mmap(size=2097152) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug

メモリの問題を、膨大な数の割り当てられた CFString (不変) に絞り込みました。問題を解決するために何ができるか考えていますか? 私は ARC と を使用して@autoreleasepoolいますが、他に何ができるかわかりません。リリースすべきときに何かがリリースされていないようです。

AnagramDetector.h

#import <Foundation/Foundation.h>

@interface AnagramDetector : NSObject {

        NSDictionary *allEightLetterWords;
NSDictionary *allWords;

    NSFileManager *fileManager;
    NSArray *paths;
    NSString *documentsDirectory;
    NSString *filePath;
}

- (BOOL) does: (NSString *) longWord contain: (NSString *) shortWord;
- (NSDictionary *) setupAllWordList;
- (NSDictionary *) setupEightLetterWordList;
- (void) saveDictionary: (NSMutableDictionary *)currentArray;

@end

AnagramDetector.m

@implementation AnagramDetector

- (id) init {
    self = [super init];
    if (self) {
        fileManager = [NSFileManager defaultManager];
        paths = NSSearchPathForDirectoriesInDomains(NSDocumentDirectory, NSUserDomainMask, YES);
        documentsDirectory = [paths objectAtIndex:0];
    }
    return self;
}

- (BOOL) does: (NSString *) longWord contain: (NSString *) shortWord {
    @autoreleasepool {
          NSMutableString *longerWord = [longWord mutableCopy];
          for (int i = 0; i < [shortWord length]; i++) {
              NSString *letter = [shortWord substringWithRange: NSMakeRange(i, 1)];
              NSRange letterRange = [longerWord rangeOfString: letter];
              if (letterRange.location != NSNotFound) {
                  [longerWord deleteCharactersInRange: letterRange];
              } else {
                  return NO;
              }
          }
        return YES;
    }
}

- (NSDictionary *) setupAllWordList {

    @autoreleasepool {
        NSString *fileWithAllWords = [[NSBundle mainBundle] pathForResource:@"AllDefinedWords" ofType:@"plist"];
        allWords = [[NSDictionary alloc] initWithContentsOfFile: fileWithAllWords];
        NSLog(@"Total number of words: %d.", [allWords count]);
    }
    return allWords;
}


- (NSDictionary *) setupEightLetterWordList {

    @autoreleasepool {
        NSString *fileWithEightWords = [[NSBundle mainBundle] pathForResource:@"AllDefinedEights" ofType:@"plist"];
        allEightLetterWords = [[NSDictionary alloc] initWithContentsOfFile: fileWithEightWords];
        NSLog(@"Total number of words: %d.", [allEightLetterWords count]);
    }
    return allEightLetterWords;
}

- (void) saveDictionary: (NSMutableDictionary *)currentArray {

    @autoreleasepool {
        filePath = [documentsDirectory stringByAppendingPathComponent: @"A.plist"];
        [fileManager createFileAtPath:filePath contents: nil attributes: nil];
        [currentArray writeToFile: filePath atomically:YES];
        [currentArray removeAllObjects];
    }
}

@end

起動時に実行されるコード (VC がないため、今のところ AppDelegate 内):

@autoreleasepool {

    AnagramDetector *detector = [[AnagramDetector alloc] init];

    NSDictionary *allWords   = [[NSDictionary alloc] initWithDictionary:[detector setupAllWordList]];
    NSDictionary *eightWords = [[NSDictionary alloc] initWithDictionary:[detector setupEightLetterWordList]];

    int remaining = [eightWords count];

    for (NSString *currentEightWord in eightWords) {
        if (remaining % 10 == 0) NSLog(@"%d ::: REMAINING :::", remaining);
        for (NSString *currentAllWord in allWords) {
            if ([detector does: [eightWords objectForKey: currentEightWord] contain: [allWords objectForKey: currentAllWord]]) {
                // NSLog(@"%@ ::: CONTAINS ::: %@", [eightWords objectForKey: currentEightWord], [allWords objectForKey: currentAllWord]);
            }
        }
        remaining--;
    }
}

楽器

4

1 に答える 1

5

問題は、多くの自動解放されたオブジェクトが、解放されるのを待っているメモリをいっぱいにすることです。したがって、解決策は、独自の自動解放プール スコープを追加して、自動解放されたオブジェクトを収集し、それらをより早く解放することです。

次のようなことをお勧めします。

for (NSString *currentEightLetterWord in [eightLetterWordsDictionary allKeys]) {
    @autoreleasepool { 
        for (NSString *currentWord in [allWordsDictionary allKeys]) {
        }
    }
}

内部のすべての自動解放されたオブジェクト@autoreleasepool { .. }は、外側のループの反復ごとに解放されます。

ご覧のとおり、ARC を使用すると、ほとんどの参照カウントとメモリ管理の問題を考える必要がなくなりますが、自動解放されたオブジェクトを直接的または間接的に作成するメソッドを使用すると、ARC を使用してオブジェクトが自動解放プールに配置される可能性があります。

私があまりお勧めしない別の解決策は、autorelease を使用するメソッドを使用しないようにすることです。次に、does:contain:ぎこちなく次のように書き換えることができます。

- (BOOL) does: (NSString* ) longWord contain: (NSString *) shortWord {
    NSMutableString *haystack = [longWord mutableCopy];
    NSMutableString *needle = [shortWord mutableCopy];
    while([haystack length] > 0 && [needle length] > 0) {
        NSMutableCharacterSet *set = [[NSMutableCharacterSet alloc] init];
        [set addCharactersInRange:NSMakeRange([needle characterAtIndex:0], 1)];
        if ([haystack rangeOfCharacterFromSet:set].location == NSNotFound) return NO;
        haystack = [haystack mutableCopy];
        [haystack deleteCharactersInRange:NSMakeRange(0, [haystack rangeOfCharacterFromSet: set].location)];
        needle = [needle mutableCopy];
        [needle deleteCharactersInRange:NSMakeRange(0, 1)];
    }
    return YES;
}
于 2012-11-15T14:47:38.277 に答える