Как уменьшить время выполнения для нахождения последней ненулевой цифры факториала числа?

У меня есть вопрос, в котором я должен найти последнюю ненулевую цифру факториала числа. Я использовал один и тот же код для java и C, но в обоих случаях это занимает разное время.

int lastDigitDiffZero(long n) {

     int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
     int i=(int) n;

     if (n < 10)
       return dig[i]; 

     if (((n/10)%10)%2 == 0)
       return (6*lastDigitDiffZero(n/5)*dig[(int)n%10]) % 10;
     else
       return (4*lastDigitDiffZero(n/5)*dig[(int)n%10]) % 10;
}

Я хочу знать, почему это занимает разное время и что мне делать, чтобы сократить время работы?


c java time-complexity factorial
person Abhay Mohan Gupta    schedule 24.01.2018    source источник
comment
java-код займет больше времени на выполнение. потому что байт-код компилируется jvm в инструкции машинного уровня. Код C будет быстрее, чем java. Пожалуйста, прочитайте о виртуальной машине Java и о том, почему Java не зависит от платформы, и у вас будет ответ.   -  person akshaya pandey    schedule 24.01.2018
comment
java имеет JVM ниже. это увеличивает время компиляции/интерпретации/выполнения   -  person samthegolden    schedule 24.01.2018
comment
JVM, хотя и увеличивает время, может выполнять автоматическую оптимизацию, обычно после каждых 10 000 циклов процессора, таким образом, дайте ему время прогрева, прежде чем проверять время выполнения, также вы можете отключить сборщик мусора, если ваш код прост и не создает/удаляет много объектов, это повысит производительность   -  person shahaf    schedule 24.01.2018
comment
@akshayapandey дал ответ на ваш первый вопрос. Для второго вы можете опубликовать сообщение на [CodeReview](codereview.stackexchange.com); обратите внимание, что рабочий код обязателен   -  person meowgoesthedog    schedule 25.01.2018
comment
Ваша функция названа неверно (вы даже приняли ответ на другой вопрос). Используйте leastSignificantDigitInFactorial(), а еще лучше задокументируйте его с помощью doxygen (или лучше ).   -  person greybeard    schedule 08.03.2018

Ответы (2)


arrow_upward
0
arrow_downward

Ты не можешь просто:

private static int lastDigitDiffZero(long n)
{
   int temp = (int) n;
   int mod = temp%10;

  return (mod == 0 ? lastDigitDiffZero(temp/10) : mod);
}
person IDK    schedule 24.01.2018
comment
2! равно 6, но это дает 2: как это альтернатива to find the last non-zero digit of factorial of a number? - person greybeard; 08.03.2018

arrow_upward
1
arrow_downward

Пожалуйста, найдите оптимизированную версию:

private static final int DIG[] = { 1, 1, 2, 6, 4, 2, 2, 4, 2, 8 };

static int lastDigitDiffZero(long n) {
        if (n < 10)
            return DIG[(int) n];
        int t1 = (int) (n % 10);
        int t2 = lastDigitDiffZero(n / 5) * DIG[t1];
        if (((n / 10) % 10) % 2 == 0) {
            return (6 * t2) % 10;
        } else
            return (4 * t2) % 10;
}
person BluEOS    schedule 24.01.2018