算法的更改

如果你不更改数据，另一个主要选项是更改代码。

最大的改进很可能来自算法变化。这与使用快速排序将气泡排序替换为从O(n ^ 2)排序到O(n log n)或使用映射查找替换通过过去是小O(n)的数组的线性扫描等效(O (1))。

最大的改进可能来自算法变化。这相当于用quicksort（O(nlogn)）替换O(n^2)的冒泡排序或者通过哈希查找（O(1)）替换数组（O(n)）的线性扫描。

这就是软件如何变慢。最初设计用于一种用途的结构被重新用于未设计的东西。这是逐渐发生的。

直观地掌握不同的大O级别是很重要的。为你的问题选择正确的数据结构。你不必一直刮刮胡须，但是这样做可以防止很久以后才会发现的愚蠢的性能问题。

基本的复杂类别是:

  • O（1）：字段访问，数组或地图查找
    建议：不要担心

  • O（log n）：二进制搜索
    建议：如果处于循环状态，则只是一个问题

  • O（n）：简单循环
    建议：你一直在这样做

  • O（n log n）：分而治之，排序
    建议：还是相当快的

  • O（n * m）：嵌套循环/二次方
    建议：小心并限制你的大小

  • 二次和次指数之间的任何其他内容
    建议：不要在一百万行上运行

  • O（b ^ n），O（n！）：指数上升
    建议：如果你有十几个或两个数据点，祝您好运

链接:http://bigocheatsheet.com

假设你需要搜索未分类的数据集。“我应该用二分搜索”，你知道一个二分搜索O(log n)比O(n)线性扫描快。但是，二分查找需要对数据进行排序，这意味着你需要先对它进行排序，这将花费O(n log n)时间。如果你正在进行大量搜索，那么分类的前期成本将会得到回报。另一方面，如果你主要做查询，也许有一个数组是错误的选择，你最好支付O(1)查找地图的代价。

选择最简单的合理数据结构并继续。这是用于编写“非慢速软件”的CS 101。这应该是您的默认开发模式。如果您知道需要随机访问，请不要选择链接列表。如果您知道需要按顺序遍历，请不要使用地图。需求变化，你不能总是猜测未来。对工作量做出合理的猜测。

http://daslab.seas.harvard.edu/rum-conjecture/

类似问题的数据结构在做一件工作时会有所不同。随着插入的发生，二叉树每次排序一次。未排序的数组插入速度更快但未排序:最后，“敲定”你需要一次完成排序。

当编写一个供其他人使用的包时，避免每个用例都要优先考虑的诱惑。这将导致代码不可读。按设计的数据结构实际上是单一用途的。你既不能读懂头脑，也不能预测未来。如果用户说“你的软件包对于这个用例太慢”，一个合理的答案可能是“然后在这里使用这个软件包”。一揽子计划应该“做得很好”。

有时混合数据结构将提供你需要的性能改进。例如，通过分段数据，你可以将搜索范围限制在一个存储桶中。这仍然支付O(n)的理论成本，但常数会更小。当我们进行编程调整时，我们将重新审视这些调整。

在讨论大O符号时，人们忘记了两件事

其一，涉及到一个不变的因素。具有相同算法复杂度的两种算法可以具有不同的常数因子。想象一下，循环遍历一个列表100次，而仅循环一次。即使两者都是O（n），也有一个恒定的因子是100倍。

这些常数因素是为什么即使合并排序，快速排序和排列所有O(n log n)，每个人都使用快速排序，因为它是最快的。它具有最小的常数因子。

第二件事是大O只说“随着n增长到无穷大”。它谈到了增长趋势，“随着数字变大，这是主导运行时间的增长因素。” 它没有提到实际的表现，也没有说明它如何表现小n。

经常有一个分界点，在这个分界点以下，木材算法更快。Go标准库sort包的一个很好的例子。大多数时候它使用快速排序，但是当分区大小降到12个元素以下时，它会进行shell排序传递，然后进行插入排序。

对于某些算法，常数因子可能非常大，以致此截点可能比所有合理的输入都大。也就是说，O（n ^ 2）算法对于所有可能处理的输入都比O（n）算法快。

这也是另一种方式：例如，即使小输入的基准变慢，选择使用更复杂的数据结构来给出O（n）缩放而不是O（n ^ 2）。这也适用于大多数无锁数据结构。它们通常在单线程情况下较慢，但在多线程使用它时更具可扩展性。

现代计算机中的存储器层次结构将问题混淆了一点，因为高速缓存更喜欢将片段扫描到追踪指针的有效随机访问的可预测访问。不过，最好从一个好的算法开始。我们将在硬件特定部分讨论这个问题。

“这场斗争可能并不总是最强，也不是最快的比赛，但这是打赌的方式。” - 吉卜林。

有时，针对特定问题的最佳算法不是单一的算法，而是专门针对稍微不同的输入类的算法集合。这个“polyalgorithm”可以快速检测出需要处理的输入类型，然后发送到相应的代码路径。这就是上面提到的排序包所做的：确定问题的大小并选择不同的算法。除了结合quicksort，shell排序和插入排序之外，它还会跟踪快速排序的递归深度并在必要时调用堆排序。在string与bytes包做类似的事情，检测和专门处理不同的情况。与数据压缩一样，您对输入内容的了解越多，定制解决方案就越好。即使优化并不总是适用，通过确定使用和执行不同的逻辑是安全的，使代码复杂化可能是值得的。

这也适用于你的算法需要解决的子问题。例如，能够使用基数排序可以对性能产生重大影响，如果只需要部分排序，则可以使用快速选择。

有时候，而不是专门针对您的特定任务，最好的方法是将其抽象为研究人员已经充分研究的更一般的问题空间。然后，您可以将更一般的解决方案应用于您的特定问题。将你的问题映射到已经有很好研究实现的领域可能是一个重大的胜利。