ios - 尝试在 iOS 中查找反向相同的最长子字符串时出现内存错误

Question

当我试图找到反向相同的最长子串时，我遇到了内存不足错误。应用程序在吃掉所有计算机内存后崩溃。

mach_vm_map(size=1048576) failed (error code=3) *** error: can't allocate region securely

我使用字符串调用 viewDidLoad 中的函数，我的代码也在下面。感谢您的帮助。

- (void)viewDidLoad {
    [super viewDidLoad];

    NSString *text = @"FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";

    [self findTheLongestReverse:text];
}

- (BOOL)findTheLongestReverse:(NSString *)str
{
    NSInteger txtIndex = [str length];
    int k, i;

    for(k = 0; k < (txtIndex +1); k++) {
        for (i = 0; i < (k + 1); i++) {
            NSRange subStrRange = NSMakeRange(i, txtIndex - k);

            NSString *subString = [str substringWithRange:subStrRange];

            NSInteger charIndex = [subString length];
            NSMutableString *reversedString = [NSMutableString string];
            while (charIndex > 0) {
                charIndex--;
                NSRange subStrRange2 = NSMakeRange(charIndex, 1);

                [reversedString appendString:[subString substringWithRange:subStrRange2]];
            }

            if([subString isEqualToString:reversedString]) {
                NSLog(@"reverse word is: %@", subString);
                return YES;
            }

        }

    }

    return NO;
}

Answer 1

就时间和所需内存而言，这是一个非常低效的算法。对于长度为 n 的字符串，您将执行 n 次平方遍历内部 for 循环，每次至少创建 3 个临时字符串。然后你在其中有一个 while 循环，为每次通过该 while 循环创建另一个临时字符串。我必须做更多的分析，但这甚至可能是一个 n 立方算法，这真的很可怕。

临时对象在内存中累积，直到当前自动释放池被耗尽。通常那是您的方法返回的时间。

您可以通过将内部 for 循环的全部内容包含在一个

中来解决内存问题

@autoreleasepool
{
}

阻止。这将导致在每次代码退出大括号时释放在大括号内创建的所有自动释放对象。因此，每次您离开内部 for 循环时，您创建的多个临时字符串对象都会被释放。这不会使您的算法更有效率，但它应该可以防止您因内存压力而崩溃..

编辑:

与其构建大量临时字符串并使用字符串搜索，这个问题可能最适合更简单的代码。

使用 characterAtIndex 方法循环遍历字符串，一次获取一个字符，并将当前字符与也使用 characterAtIndex 的其他字符进行比较。我必须坐下来用铅笔和纸花几分钟来设计一个算法，但编写一个在字符串中找到最大回文的方法而不创建任何临时字符串应该很简单。