Вычислительная сложность модулей и FizzBuzz - PullRequest
Новая
       62

Вычислительная сложность модулей и FizzBuzz

3 голосов
/ 08 мая 2020

Так что я не хочу go выяснять, является ли это наиболее совершенным кодом для задачи FizzBuzz.

Для тех, кто не знаком с FizzBuzz, есть четыре правила для печати диапазона от 1 до 100:

  1. Распечатайте все числа;
  2. Если число делится на 3, вместо этого выведите «Fizz»;
  3. Если число делится на 5, вместо этого выведите «Buzz»;
  4. Если число делится на 3 и 5, выведите «FizzBuzz».)

Я запустил две реализации, чтобы сравнить их скорость: 

# Code A
%%timeit
for i in range(1,10001):
    if i % 15 == 0:
        print('FizzBuzz')
    elif i % 3 == 0:
        print('Fizz')
    elif i % 5 == 0:
        print('Buzz')
    else:
        print(i)

# Code B
%%timeit
for i in range(1,10001):
    if i % 5 == 0 and i % 3 == 0:
        print('FizzBuzz')
    elif i % 3 == 0:
        print('Fizz')
    elif i % 5 == 0:
        print('Buzz')
    else:
        print(i)

Несмотря на дополнительную оценку if кода B, он всегда работал быстрее, чем код A. Приводит ли большее число к более медленному по модулю? Какова основная причина этого?

1 Ответ

3 голосов
/ 08 мая 2020

Основная причина, о которой я мог подумать, это, возможно, оптимизация.

Версия B использует ту же операцию несколько раз, а именно:

  • i mod 5
  • i mod 3

Достаточно интеллектуальный компилятор / интерпретатор мог бы обнаружить это и вычислить эти промежуточные результаты. Поступая таким образом, он сможет немедленно вычислить весь if-блок всего с двумя модификациями.

Короче говоря, я думаю, что код, который завершается выполнением, может выглядеть примерно так: 

for i in range(1,10001):
    a = i % 5
    b = i % 3
    if a == 0 and b == 0:
        print('FizzBuzz')
    elif b == 0:
        print('Fizz')
    elif a == 0:
        print('Buzz')
    else:
        print(i)

Однако код в блоке A, возможно, слишком сложен. Под этим я подразумеваю, что компилятор всегда будет вынужден выполнять 3 операции с модами. Если только он каким-то образом не сможет определить, что 15 = 3 * 5, и использовать это logi c для переделки оператора if.

...