使用 numpy 加速 FizzBuzz
Accelerating FizzBuzz with numpy
FizzBuzz 问题：给定一个自然数 N >= 0 打印一个数字序列 0 - N 替换所有可被 3 整除的数字单词 fizz，每个数字都可以被 5 整除，单词 buzz，每个数字都可以被 3 和 5 整除，单词 fizzbuzz.
Numpy 在这方面不是很好（它没有为字符串提供太多加速），但我认为它不应该太可怕，也许，如果使用得当，它可以击败普通的 python .然而，令我惊讶的是，天真的实现情况恰恰相反。 为什么会这样，如何对此进行改进？
这是我用来生成时间的代码。它包括一个纯 python 参考实现、一个简单的 numpy 实现和一个 numba.jit 变体，因为我认为它可以作为性能的合理下限。
import numpy as np
import matplotlib.pyplot as plt
import numba as nb
import timeit
def classic_fizzbuzz(N: int) -> str:
result = list()
for idx in range(N):
if idx % 3 == 0 and idx % 5 == 0:
result.append("fizzbuzz")
elif idx % 5 == 0:
result.append("buzz")
elif idx % 3 == 0:
result.append("fizz")
else:
result.append(str(idx))
return " ".join(result)
def numpy_fizzbuzz(N: int) -> str:
integers = np.arange(N)
result = np.arange(N).astype(str)
result = np.where(integers % 3 == 0, "fizz", result)
result = np.where(integers % 5 == 0, "buzz", result)
result = np.where(integers % 15 == 0, "fizzbuzz", result)
return " ".join(result)
@nb.jit(nopython=True)
def numba_fizzbuzz(N:int) -> str:
result = list()
for idx in range(N):
if idx % 3 == 0 and idx % 5 == 0:
result.append("fizzbuzz")
elif idx % 5 == 0:
result.append("buzz")
elif idx % 3 == 0:
result.append("fizz")
else:
result.append(str(idx))
return " ".join(result)
# do not measure initial compile time
numba_fizzbuzz(20)
def time_fizzbuzz(fn):
repeats = 100
times = list()
N_values = np.linspace(0, int(1e4), 100, dtype=int)
for idx in N_values:
N = int(idx)
times.append(timeit.timeit(lambda: fn(N), number=repeats) / repeats)
return N_values, times
fig, ax = plt.subplots(dpi=150) # web-quality
contendants = {
"classic": classic_fizzbuzz,
"numpy": numpy_fizzbuzz,
"numba": numba_fizzbuzz
}
for fn in contendants.values():
ax.plot(*time_fizzbuzz(fn))
ax.set_ylabel("Average Time (s)")
ax.set_label("Input")
fig.suptitle(
"Comparison of FizzBuzz implementations in Python.",
# fontsize="medium",
)
ax.set_title("Timings for various input N (averaged over 100 runs each)", fontsize="small")
ax.legend(
contendants.keys(),
loc="center left",
bbox_to_anchor=(1, 0.5),
title="Contestants",
)
fig.tight_layout()
fig.savefig("timings.png")
发生这种情况的原因是您使用 numpy 方法将所有元素迭代了三次。您必须为每个 np.where 调用检查 整个 数组。 python 实现只迭代数组一次。正如您所展示的，这更快，尽管迭代的各个步骤可能更慢。话虽这么说，您可以（ab）对这个应用程序使用 np.vectorize，尽管它显然不是为了提高性能。在这方面，this question 非常相关。
在您的特殊情况下，您可以通过利用 15 可被 3 和 5 整除来优化您的 numpy 函数：
def numpy_fizzbuzz(N: int) -> str:
integers = np.arange(N)
result = np.arange(N).astype(str)
# Find indices in 'integers' that are divisible by 3 and 5
mod_3 = np.argwhere(integers % 3 == 0)
mod_5 = np.argwhere(integers % 5 == 0)
# If a number is divisible by 3 and 5, it is also divisible by 15
mod_15 = np.intersect1d(mod_3, mod_5, assume_unique=True)
# Update results at corresponding indices
result[mod_3] = 'fizz'
result[mod_5] = 'buzz'
result[mod_15] = 'fizzbuzz'
return " ".join(result)
然而，这只会导致我平台上的 speed-up 的 18%。
timeit.timeit(lambda: classic_fizzbuzz(int(1e4)), number=1000)
# 5.5598067000009905
timeit.timeit(lambda: numpy_fizzbuzz_old(1e4), number=1000)
# 15.149480800000674
timeit.timeit(lambda: numpy_fizzbuzz(1e4), number=1000)
# 12.509547700001349
此外，在加入之前将结果转换为列表会产生更显着的改进。
# Using:
# return " ".join(result.tolist())
timeit.timeit(lambda: numpy_fizzbuzz_converted(1e4), number=1000)
# 7.723402100000385
您可以使用 np.select 而不是创建并行字符串数组来显着改进 numpy 版本：
def numpy_select(N: int) -> str:
integers = np.arange(N)
return ' '.join(np.select([(integers%3 == 0) & (integers%5 == 0),
(integers%3 == 0), (integers%5 == 0)],
['fizzbuzz','fizz','buzz'], integers).tolist())
您的 Classic Python 版本可以像这样更快一点：
def c2(N: int) -> str:
return ' '.join(['fizzbuzz' if x%15==0 else
'fizz' if x%3==0 else
'buzz' if x%5==0 else str(x) for x in range(N)])
将这些插入您的基准测试：
FizzBuzz 问题：给定一个自然数 N >= 0 打印一个数字序列 0 - N 替换所有可被 3 整除的数字单词 fizz，每个数字都可以被 5 整除，单词 buzz，每个数字都可以被 3 和 5 整除，单词 fizzbuzz.
Numpy 在这方面不是很好（它没有为字符串提供太多加速），但我认为它不应该太可怕，也许，如果使用得当，它可以击败普通的 python .然而，令我惊讶的是，天真的实现情况恰恰相反。 为什么会这样，如何对此进行改进？
这是我用来生成时间的代码。它包括一个纯 python 参考实现、一个简单的 numpy 实现和一个 numba.jit 变体，因为我认为它可以作为性能的合理下限。
import numpy as np
import matplotlib.pyplot as plt
import numba as nb
import timeit
def classic_fizzbuzz(N: int) -> str:
result = list()
for idx in range(N):
if idx % 3 == 0 and idx % 5 == 0:
result.append("fizzbuzz")
elif idx % 5 == 0:
result.append("buzz")
elif idx % 3 == 0:
result.append("fizz")
else:
result.append(str(idx))
return " ".join(result)
def numpy_fizzbuzz(N: int) -> str:
integers = np.arange(N)
result = np.arange(N).astype(str)
result = np.where(integers % 3 == 0, "fizz", result)
result = np.where(integers % 5 == 0, "buzz", result)
result = np.where(integers % 15 == 0, "fizzbuzz", result)
return " ".join(result)
@nb.jit(nopython=True)
def numba_fizzbuzz(N:int) -> str:
result = list()
for idx in range(N):
if idx % 3 == 0 and idx % 5 == 0:
result.append("fizzbuzz")
elif idx % 5 == 0:
result.append("buzz")
elif idx % 3 == 0:
result.append("fizz")
else:
result.append(str(idx))
return " ".join(result)
# do not measure initial compile time
numba_fizzbuzz(20)
def time_fizzbuzz(fn):
repeats = 100
times = list()
N_values = np.linspace(0, int(1e4), 100, dtype=int)
for idx in N_values:
N = int(idx)
times.append(timeit.timeit(lambda: fn(N), number=repeats) / repeats)
return N_values, times
fig, ax = plt.subplots(dpi=150) # web-quality
contendants = {
"classic": classic_fizzbuzz,
"numpy": numpy_fizzbuzz,
"numba": numba_fizzbuzz
}
for fn in contendants.values():
ax.plot(*time_fizzbuzz(fn))
ax.set_ylabel("Average Time (s)")
ax.set_label("Input")
fig.suptitle(
"Comparison of FizzBuzz implementations in Python.",
# fontsize="medium",
)
ax.set_title("Timings for various input N (averaged over 100 runs each)", fontsize="small")
ax.legend(
contendants.keys(),
loc="center left",
bbox_to_anchor=(1, 0.5),
title="Contestants",
)
fig.tight_layout()
fig.savefig("timings.png")
发生这种情况的原因是您使用 numpy 方法将所有元素迭代了三次。您必须为每个 np.where 调用检查 整个 数组。 python 实现只迭代数组一次。正如您所展示的，这更快，尽管迭代的各个步骤可能更慢。话虽这么说，您可以（ab）对这个应用程序使用 np.vectorize，尽管它显然不是为了提高性能。在这方面，this question 非常相关。
在您的特殊情况下，您可以通过利用 15 可被 3 和 5 整除来优化您的 numpy 函数：
def numpy_fizzbuzz(N: int) -> str:
integers = np.arange(N)
result = np.arange(N).astype(str)
# Find indices in 'integers' that are divisible by 3 and 5
mod_3 = np.argwhere(integers % 3 == 0)
mod_5 = np.argwhere(integers % 5 == 0)
# If a number is divisible by 3 and 5, it is also divisible by 15
mod_15 = np.intersect1d(mod_3, mod_5, assume_unique=True)
# Update results at corresponding indices
result[mod_3] = 'fizz'
result[mod_5] = 'buzz'
result[mod_15] = 'fizzbuzz'
return " ".join(result)
然而，这只会导致我平台上的 speed-up 的 18%。
timeit.timeit(lambda: classic_fizzbuzz(int(1e4)), number=1000)
# 5.5598067000009905
timeit.timeit(lambda: numpy_fizzbuzz_old(1e4), number=1000)
# 15.149480800000674
timeit.timeit(lambda: numpy_fizzbuzz(1e4), number=1000)
# 12.509547700001349
此外，在加入之前将结果转换为列表会产生更显着的改进。
# Using:
# return " ".join(result.tolist())
timeit.timeit(lambda: numpy_fizzbuzz_converted(1e4), number=1000)
# 7.723402100000385
您可以使用 np.select 而不是创建并行字符串数组来显着改进 numpy 版本：
def numpy_select(N: int) -> str:
integers = np.arange(N)
return ' '.join(np.select([(integers%3 == 0) & (integers%5 == 0),
(integers%3 == 0), (integers%5 == 0)],
['fizzbuzz','fizz','buzz'], integers).tolist())
您的 Classic Python 版本可以像这样更快一点：
def c2(N: int) -> str:
return ' '.join(['fizzbuzz' if x%15==0 else
'fizz' if x%3==0 else
'buzz' if x%5==0 else str(x) for x in range(N)])
将这些插入您的基准测试：