Эффект рекурсивного алгоритма - Java

Question

Я работаю над проектом кодирования, и у меня проблема со скоростью программы. Программа принимает вход между 1 и 80, этот вход представляет собой ряд совпадений, и выводит, сколько разных чисел можно сделать с таким количеством совпадений.

Ex: Номер 1 может быть выполнен с 2 спичечных палочками, а число 2 требует 5 матча палочку

Вот полное приглашение программы:

Вот мой код к алгоритму, который я придумал для вычисления всего возможного выхода, он функционирует достаточно хорошо для нижнего конца входов, хотя он становится крайне неэффективным для больших входов, таких как 80 часов, чтобы вычислить все возможности. Как я могу сократить это время до минимума?

п представляет вход, и все объектные счетчик делает это следить за каждым возможным количеством созданного

public static void digitCounter(int n, Counter count) { 
    if (n < 2) { 
     //ouput 
    } else { 
     if (count.getCount() == 0) { 

      // If there are enough match sticks to form it 
      // accounts for 0 only once 
      if (n >= 7) { 
       // counts 0 
       count.setCount(10); 
       // counts 1 
       digitCounter(n - 2, count); 
       // counts 2 
       digitCounter(n - 5, count); 
       // counts 3 
       digitCounter(n - 5, count); 
       // count 4 
       digitCounter(n - 4, count); 
       // counts 5 
       digitCounter(n - 5, count); 
       // counts 6 
       digitCounter(n - 6, count); 
       // counts 7 
       digitCounter(n - 3, count); 
       // counts 8 
       digitCounter(n - 7, count); 
       // counts 9 
       digitCounter(n - 5, count); 
      } else if (n == 6) { 
       count.setCount(9); 
       digitCounter(n - 2, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 4, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 6, count); 
       digitCounter(n - 3, count); 
       digitCounter(n - 5, count); 
      } else if (n == 5) { 
       count.setCount(7); 
       digitCounter(n - 2, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 4, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 3, count); 
       digitCounter(n - 5, count); 
      } else if (n == 4) { 
       count.setCount(3); 
       digitCounter(n - 2, count); 
       digitCounter(n - 4, count); 
       digitCounter(n - 3, count); 
      } else if (n == 3) { 
       count.setCount(2); 
       digitCounter(n - 2, count); 
       digitCounter(n - 3, count); 
      } else if (n == 2) { 
       count.setCount(1); 
       digitCounter(n - 2, count); 
      } 
     } 

     // Accounts for every other number after 0 is accounted for so 
     // numbers with leading 0's are not formed 
     // Ex: 001 is illegal 
     else { 
      if (n >= 7) { 
       count.setCount(count.getCount() + 10); 
       digitCounter(n - 6, count); 
       digitCounter(n - 2, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 4, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 6, count); 
       digitCounter(n - 3, count); 
       digitCounter(n - 7, count); 
       digitCounter(n - 5, count); 
      } else if (n == 6) { 
       count.setCount(count.getCount() + 9); 
       digitCounter(n - 6, count); 
       digitCounter(n - 2, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 4, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 6, count); 
       digitCounter(n - 3, count); 
       digitCounter(n - 5, count); 
      } else if (n == 5) { 
       count.setCount(count.getCount() + 7); 
       digitCounter(n - 2, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 4, count); 
       digitCounter(n - 5, count); 
       digitCounter(n - 3, count); 
       digitCounter(n - 5, count); 
      } else if (n == 4) { 
       count.setCount(count.getCount() + 3); 
       digitCounter(n - 2, count); 
       digitCounter(n - 4, count); 
       digitCounter(n - 3, count); 
      } else if (n == 3) { 
       count.setCount(count.getCount() + 2); 
       digitCounter(n - 2, count); 
       digitCounter(n - 3, count); 
      } else if (n == 2) { 
       count.setCount(count.getCount() + 1); 
       digitCounter(n - 2, count); 
      } 
     } 
    } 

Answer 1

Что делать, если вы изменили свой дизайн так, чтобы digitCounter(n)вернулся подсчет чисел, которые могут быть сформированы по n зубочисткам, а затем кешировать это значение в постоянной карте? При входе в digitCounter проверьте свою карту и верните кешированное значение, если вы уже рассчитали его один раз. Тогда у вас все равно будет рекурсивный алгоритм, но не нужно будет делать повторяющиеся вызовы для того же N.

Answer 2

Вы можете умножьте количество решений, получаемых с заданным количеством совпадений. Вы также можете кэшировать количество решений до номера давки.

public static long solutionsFor(int matchCount) { 
    long[] counts = new long[matchCount+1]; 
    for(int i = 0; i <= matchCount; i++) { 
     long count = ... calculate count based on previous values ... 
     counts[i] = count; 
    } 
    return counts[matchCount]; 
} 

Прирост производительности является то, что стоимость O (п), и вы, скорее всего, получите ответ в течение нескольких миллисекунд для самых больших проблем, которые возвращают long.

Answer 3

Ваша проблема заключается в том, что один звонок digitCounter может порождать до 10 звонков до digitCounter, что может вызвать еще больше звонков на него. Таким образом, ваша первая попытка оптимизации - уменьшить количество вызовов.

@pamphlet спросил:

Так что многие из ваших случаев называют digitCounter (п-5, количество) несколько раз. Do вы ожидаете, что результат будет отличаться вторым, третьим или четвертым временем вы называете это?

Это должно быть вашим первым ключом для оптимизации. Фактический счет, который вы добавляете в свой счетчик, должен быть одинаковым при каждом вызове digitCounter(n-5, count). Поэтому я предлагаю вам позволить счетчику цифр возвращать счет напрямую и добавлять его самостоятельно. Чтобы указать, следует ли считать 0 или нет, добавьте флаг, указывающий, является ли он самым верхним вызовом digitCounter или нет.

Звоните digitCounter с n = 10.

для count=0 вы будете в конечном итоге в следующем коде (комментарии удалены)

 if (n >= 7) { 
      count.setCount(10); 
      digitCounter(n - 2, count); 
      digitCounter(n - 5, count); 
      digitCounter(n - 5, count); 
      digitCounter(n - 4, count); 
      digitCounter(n - 5, count); 
      digitCounter(n - 6, count); 
      digitCounter(n - 3, count); 
      digitCounter(n - 7, count); 
      digitCounter(n - 5, count); 
     } else if (n == 6) { 

вы эффективным вызова

digitCounter(n - 2, count); 1x

1x digitCounter(n - 3, count);

1x digitCounter(n - 4, count);

4x digitCounter(n - 5, count);

1x digitCounter(n - 6, count);

1x digitCounter(n - 7, count);

Вызов digitCounter(n - 5, count);, который digitCounter(5, count); при п = 10 приводит additial 10 звонков digitCounter. поэтому, вызывая его один раз вместо 4 раза, вы сохраняете 3 раза (1 + 10) = 33 звонка.

Другая оптимизация - это сохранение последнего звонка, который вы выполняете. Вы знаете, что результат для digitCounter(0) равен 0. Итак, почему вы пытаетесь его вычислить?

 } else if (n == 2) { 
      count.setCount(count.getCount() + 1); 
      digitCounter(n - 2, count); 
     } 

можно переписать в

 } else if (n == 2) { 
      count.setCount(count.getCount() + 1); 
      digitCounter(2 - 2, count); 
     } 

так что вы можете удалить вызов digitCounter(2 - 2, count);, так как он не влияет на результаты. Аналогично, результат для digitCounter(1) равен 0. Поэтому после оптимизации дела n=3 мы удалили еще 2 ненужных вызова. digitCounter(2) всегда 1. Таким образом, для n=4 вы можете удалить ненужные 3 вызовы, просто увеличить счетчик на 4 вместо 3.

вы также можете оптимизировать n=5 таким же образом. digitCounter(3) всегда 2. Таким образом, вы можете устранить 7 дополнительных вызовов и увеличить счетчик на 10 вместо 7. Я позволю себе оптимизировать случай n=6 для себя.

Это должно привести к значительному сокращению рекурсивных вызовов. Это может показаться минимальным, но оно быстро складывается.

Следующая оптимизация будет кэшировать как предложено @JVMATL вы можете получить значительную экономию для большого N. Призыв к digitCounter(n-2) приведет к вызову для digitCounter((n-2) -2) что эквивалентно digitCounter(n-4). Поэтому вам не нужно снова вычислять значение, что приводит к огромной экономии для больших n (например, n=80). Даже при том, что кэширование может не помочь вам для небольших n и даже может увеличить время выполнения (кому все равно миллисекунды), вы получаете большой выигрыш для больших n (достигает легко секунд/минут).