优化狂热！！！
4.00/5 (4投票s)
优化，还是不优化，这是个问题……
什么是过早优化？
你可能以前听过这个词，但它到底是什么意思？毕竟，优化是一件好事，应该融入到软件工程师所做的所有事情中，对吧？纯粹从学术角度来看，这绝对是真的。
然而，在现实情况中，我们需要维护代码。随着代码复杂性的增加，维护成本和风险也会随之增加。我们是在构建一个每秒处理数百万笔金融交易的系统吗？还是在构建一个搜索优惠的演唱会门票的系统？这个问题会对平衡点在哪里产生深远的影响。
即使在这些截然不同的场景下，系统的某些部分也需要比其他部分更多的优化或更少的优化。过滤客户交易记录与银行所有记录的系统可能需要疯狂优化，但我们真的需要为了改变排序方式从日期到金额而做到那种程度吗？
案例研究：素数
素数是只能被 1 和它本身整除的整数。这些数字在计算机科学的许多领域都发挥着重要作用。它们为何如此重要已超出了本文的范畴，但它们是处理复杂算法的有趣案例研究。我们将比较几种找出给定上限内的所有素数的方法。所有示例均以 Kotlin 编写，并且示例时间是通过在单元测试中平均运行 10 次来测量的。
暴力破解
在这个练习中，我们将遍历给定上限内的每一个数字，并确定它是否是素数。我们将通过检查到潜在素数平方根（任何大于平方根的数都不可能成为其因子）为止的所有潜在因子来做到这一点。如果没有找到因子，我们就将其放入一个数组。一旦我们到达上限，我们就停止，我们也就有了所有需要的素数。简而言之，我们遍历每一个数字，并尝试该数字的每一种可能的因子来找到素数。效率不高，对吧？
我们可以给 isPrime 检查增加一点智能，稍后我们会看到它对数字的影响。使用这个（稍微复杂一点的）算法，如果值为 1，我们直接返回 false；否则，如果值为 2 或 3，我们自动返回 true。一旦超过这一点，它就会排除所有能被 2 或 3 整除的数。然后，情况变得更有趣，它从下一个“已知素数” 5 开始，只要测试值的平方不超过 n，我们就测试它是否可整除，将其增加到下一个奇数，然后重复。如果我们发现任何因子，我们就返回 false。如果我们通过了循环，我们就返回 true。
fun isPrime(n: Int): Boolean {
val max = Math.sqrt(n.toDouble()).toInt()
for (factor in 2..max) {
if (n % factor == 0) {
return false
}
}
return true
}
fun isPrimeWithSmartCheck(n: Int): Boolean {
if (n == 1) {
return false
} else if (n <= 3) {
return true
} else if (n % 2 == 0 || n % 3 == 0) {
return false
}
var testValue: Int = 5
while (testValue * testValue <= n) {
if (n % testValue == 0) {
return false
}
testValue += 2
}
return true
}
fun findPrimes(n: Int): List<Int> {
var primes: MutableList<Int> = ArrayList()
for (i in 2..n) {
if (isPrime(i)) {
primes.add(i)
}
}
return primes
}
埃拉托斯特尼筛法
埃拉托斯特尼（Eratosthenes）是一位希腊数学家（兼职）。他是数论的先驱，并引入了埃拉托斯特尼筛法。这是一种相当知名的查找素数的有效方法。
我们首先创建一个长度为 n 的布尔值列表，默认值为 true。我们将大小设置为 n + 1 以包括零。我们立即排除零和一，将它们设置为 false，因为它们不被计为素数。
接下来，我们遍历布尔数组跟踪的可能性列表。对于每个数字，从 2 开始，我们检查该索引的布尔值是否为 true。如果是，我们就将其添加到素数列表中。然后，我们遍历该数字到布尔数组末尾的所有倍数，将任何倍数标记为 false。这意味着我们找到的下一个 true 值是一个素数，所以我们将其添加到素数列表并重复。这种方法的优点是，每次找到一个素数，我们就会减少剩余待检查值的数量。当我们到达布尔列表的末尾时，我们就得到了最终的素数列表。
fun sieveOfEratosthenes(n: Int): List<Int> {
var primes: MutableList<Int> = ArrayList()
var list = MutableList(n + 1, {i -> true})
list[0] = false
list[1] = false
for (i in list.indices) {
if (list[i]) {
primes.add(i)
var j = i
while (j < list.count()) {
list[j] = false
j += i
}
}
}
return primes
}
棘手的数字
那么，埃拉托斯特尼筛法比暴力破解法效率高多少呢？嗯，这取决于。虽然它在处理大型 n 值时表现非常好，但在处理较小的数字时，暴力破解法实际上比筛法更快。通过添加智能检查，我们甚至可以使暴力破解法稍微更具竞争力，但即使如此，它也一直被原始的、野蛮的方法击败，直到 n 超过 1000。
average time in milliseconds
n | sieve | brute force | w/smart check
--------------------------------------------------------
10 | 0.649766 | 0.006483 | 0.496988
100 | 0.639629 | 0.025545 | 0.579207
1000 | 1.038445 | 0.235613 | 0.653132
10000 | 3.082918 | 1.784386 | 1.767561
50000 | 6.192984 | 11.570596 | 5.937535
100000 | 12.807858 | 29.364065 | 14.411587
1000000 | 103.172073 | 622.648549 | 377.154029
2000000 | 329.524157 | 1673.22857 | 888.082857
如上表所示，一旦 n 达到 50,000，埃拉托斯特尼筛法就轻松夺冠。但有趣的是，代码量最少的原始暴力破解方法在 n 低于该阈值时，却远远领先于筛法。此外，通过添加一点点复杂性，将 isPrime 检查切换为使用更智能的方法，该阈值会接近 100,000，但在 n 低于 10,000 时，简单的暴力破解方法仍然优于智能检查。虽然在 200 万这个量级上的收益高达 4 倍，但在较小规模上，简单方法的收益速度快达 100 倍！
故事的寓意
直觉是人类大脑的一个强大表现，它在我们不知情的情况下进行了大量的计算，并将其过滤成一种“直觉”感觉。在识别代码中的瓶颈或低效之处时，开发人员常常会依赖这种机制。不幸