Golang 有多快？—— 对比 Go 和 Python 实现的 Eratosthenes 筛选法

时间宝贵，所以为什么浪费时间等待程序运行？除非过去几年与世隔绝，否则不会错过 Go 的兴起。由谷歌工程师 Robert Griesemer，Rob Pike 和 Ken Thompson 创造的 新颖的编程语言，Go 被誉为近乎完美，在易用性上可以与 Python 相媲美，而在执行速度上又可以与 C 语言相媲美。真的如传闻所说吗？今天，我们会分别使用 Go 和 Python 实现埃拉托色尼筛选法，并以耗时为结果。最终，得到的问题的结果，也就是“Golang 到底有多快？”

Eratosthenes 筛选法

Eratosthenes 是古希腊博学家。对很多领域均有涉猎（数学，地理，诗歌，天文学，音乐 —— 还不仅仅只是这些）他是一位著名的学者，据称他是第一个测量地球周长及其轴线倾斜度的人。要知道当时是公元前 3 世纪，就会足够让人惊奇。

尽管如此，我们将从他的一项尝试中使用一种技术进入数论世界：Eratosthenes 筛选法。简单来说，这是一个从整数集合中生成（或者说“筛选”）质数列表的相对有效的方法。生成最大为 n 的质数的方法如下：

• 构造一个整数集合，a，例如 a = {2, 3, ..., n}。
• 遍历 a 的元素，每轮遍历移除该原色的倍数（但是不移除这个原始的元素）。
• a 现在是一个包含着最大为 n 的质数集合。

理解该方法的一个奇妙方式是看下面的这个动图：

Python 代码

先从 Python 代码开始，因为它可能是最简单易懂的。下面是实际运行代码的精简版本（如果想看带错误捕获的实际运行版本，从我的 GitHub 仓库检出）。

def sieve(primes, factor):
    for p in primes:
        if p != 0 and p != factor:
            if p % factor == 0:
                primes[primes.index(p)] = 0
    return primes


def main(n):
    primes = [i for i in range(2, n + 1)]
    for p in primes:
        if p != 0:
            primes = sieve(primes, p)
    print('\n'.join([str(p) for p in primes if p != 0]))

这段代码是如何工作的？

• 主函数接受一个参数，n，这个整型参数限定了我们要生成的质数的大小。
• 之后，创建一个包含 2 到 n 的数字的列表。
• 对于这些数字中的每一个数字，通过向列表中的每一个元素调用 sieve 函数来移除其所有的倍数。(实际上是将倍数设置为 0，因为遍历过程中移除他们会导致错误)
• 最后我们输出一个剩下的所有质数的列表（即，原列表中所有不是 0 的元素）确保另起一行分隔他们。
• 注意第 4 行的 p % factor。这是一个获取（在这个例子中）p 除以 factor 的余数的“取模函数”。如果余数是 0，那我们便得到了一个倍数（比如，10 ÷ 5=2，余数是 0）。

Go 代码

为了保证对比公平，在 Go 的筛选代码中使用完全一样的算法。出来这里是（从 GitHub上面的完整代码中剥离出来的）精简代码外，我不会重复深入解释这段代码。来将这段代码与上面的 Python 代码进行对比。

func main() {
    var primes []int

    for i := 2; i <= n; i++ {
        primes = append(primes, i)
    }

    for i := 0; i < len(primes); i++ {
        if primes[i] != 0 {
            sieve(primes, primes[i])
        }
    }

    for i := 0; i < len(primes); i++ {
        if primes[i] != 0 {
            fmt.Println(primes[i])
        }
    }
}

func sieve(primes []int, factor int) {
    for index, value := range(primes) {
        if value != 0 && value != factor {
            if value % factor == 0 {
                primes[index] = 0
            }
        }
    }
}

• 第 2 行到第 6 行的代码创建我们的数字列表。
• 第 8 行到第 12 行代码遍历该列表，使用 sieve 函数（工作流程与 Python 代码中的完全一样）移除（每个元素的）倍数。
• 最后输出列表，每个指数另起一行来进行分隔。

结果出来了！

我在 bash shell 中使用 time 函数（见下面的例子）来测试这些代码[^1]，使用不同的 n （范围从 1 到 100,000）同时使用 Jupyter Notebook 生成下面的结果。图表由 Plotly 生成

$ time bin/sieve 10
2
3
5
7
real    0m0.004s
user    0m0.000s
sys     0m0.005s

结果十分明显，Go 要比 Python 要快，尤其是在大规模数字计算领域上。当在在较小规模时（n < 1000）他们并没有明显差异（Go 相较于 Python 轻微缓慢的节奏来说，几乎是瞬时的），当达到了 10,000 的规模，Python 落后了很多。

总结

Go 是一种开源编程语言，可轻松构建简单，可靠和高效的软件。—— golang.org

总结如下，Go 明显比 Python 快得多。正如该语言的网站所说，它简单，可靠且非常高效。因此，是的，如果您发现 Python 更容易或更简单或者只是更快地编程，请使用 Python。但是对于时间紧迫，计算能力强的软件，Go 可能是正确的选择。

更新：如果您需要坚持使用 Python 但又想尽可能地提高它的速度，为什么不看看我的其他文章：5 种可以立即提高 Python 速度的方法。

[^1]: 确实，我应该每个 n 次测试一次。但是通过一遍就说明了这种趋势，所以我节省了一些时间，只停留了一轮。