Ошибка памяти при попытке найти самую длинную подстроку, которая в обратном порядке в 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 кубика, который действительно ужасен.

Временные объекты накапливаются в памяти до тех пор, пока текущий пул авторекламы не будет слит. Обычно это когда ваш метод возвращается.

Вы можете решить эту проблему памяти, прилагая все содержимое вашей внутренней цикл в

@autoreleasepool 
{ 
} 

блока. Это приведет к тому, что все объекты автоматического выпуска, созданные внутри фигурных скобок, будут выпущены каждый раз, когда ваш код выйдет из фигурных скобок. Поэтому каждый раз, когда вы покидаете свой внутренний цикл, будут освобождены многочисленные временные строковые объекты. Это не сделает ваш алгоритм любой более эффективной, но это должно предотвратить крах из-за нехватки памяти ..

Edit:

Вместо того, чтобы строить тонны временных строк и с помощью строки поиска, эта проблема, вероятно, лучше всего подходят для более простого кода.

Прокрутите строку, забирающую один символ за раз с использованием метода characterAtIndex, и сравните текущий символ с другими символами, также используя characterAtIndex. Мне пришлось бы с карандашом и бумагой сработать несколько минут, чтобы разработать алгоритм, но написать метод, который найдет самый большой палиндром в строке, не составит труда, не создавая никаких временных строк.

Answer 2

Работает ли ваша программа правильно (если неэффективно) для более коротких строк?

Правильно ли он работает, если есть нет подстроки на всех одинаковых в обратном направлении?

Правильно ли он работает для простой, действительно очевидной подстроки, такой как «ee»?

Работает ли он для строк с нулевой длиной - "" - однобуквенные строки - "x" - а также строки с четным и четным числом букв?

Duncan C правильный, вы выделяете слишком много памяти из-за неэффективности своего алгоритма. Однако, прежде чем выбирать более эффективный алгоритм, определите, является ли алгоритм - неэффективный, который у вас уже есть, по крайней мере, правильный, если голодны.

Это поможет вам лучше понять вашу проблему и ваше решение.

В этот момент попытайтесь найти лучший алгоритм.

Если вы действительно не знаете, как найти лучший алгоритм, я предлагаю вам прочитать «Алгоритмы» Роберта Седжуика. Я предпочитаю его второе издание, с алгоритмами, приведенными в pascal. Его можно использовать для восьми баксов.

Однако имейте в виду, что в большинстве текстов алгоритмов рассматривается только время выполнения, но не память. В общем, но не всегда быстрый алгоритм не будет использовать больше памяти, чем вход, и «немного лишний». Но есть некоторые алгоритмы, такие как таблицы поиска или предварительно вычисленные таблицы, где можно получить большую скорость, но за счет использования большого количества памяти.

Распределение требует времени по многим причинам - вам нужно вызвать распределитель, он должен найти свободный блок, который достаточно велик, вы будете разбивать кеш данных, может быть больше кода, чем алгоритм, который не работает Вы не будете выделять так много, вы будете пейджинговыми, если ваш код работает на настольной или серверной ОС (но не на мобильных устройствах, обычно они не используют хранилище резервных копий).