时间戳

首页 > 解决方案 > 模数和 FizzBu​​zz 的计算复杂度

python - 模数和 FizzBu​​zz 的计算复杂度

问题描述

所以我不想讨论这是否是 FizzBu​​zz 挑战的最完美代码。

对于那些不熟悉 FizzBu​​zz 的人来说，打印出 1-100 的范围有四个规则：

  1. 打印出所有数字；
  2. 如果数字能被 3 整除，则打印“Fizz”；
  3. 如果数字能被 5 整除，则打印“Buzz”；
  4. 如果该数字可以被 3 和 5 整除，则打印“FizzBu​​zz”。）

我运行了两个实现，以比较它们的速度：

# 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 运行得更快。更大的数字会导致模数变慢吗？造成这种情况的根本原因是什么？

标签： pythontime-complexitycomplexity-theory

解决方案

我能想到的主要原因可能是优化。

版本 B 多次使用相同的操作，即：

  • 我国防部 5
  • 我修改了 3

一个相当聪明的编译器/解释器可能会发现这一点，并计算这些中间结果。通过这样做，它可以立即计算整个 if 块，只需 2 次 mod 操作。

简而言之，我认为最终被执行的代码可能看起来像这样：

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 个 mod 操作。除非它能够以某种方式发现 15 = 3 * 5，并使用该逻辑重新处理 if 语句。

推荐阅读