事先道歉,如果这个问题看起来有点广泛或陌生,我并不是要冒犯任何人,但也许有人可以提出建议。我试图寻找类似的问题,但没有感冒。
哪些更好的资源(书籍,博客等)可以教您如何优化代码?
有很多资源可以使代码更具可读性(“代码完成”可能是第一选择)。但是,如何使其运行更快,内存效率更高呢?
当然,每种特定语言都有大量书籍,但是我想知道是否有一些书籍涵盖了内存/操作速度的问题,并且在某种程度上与语言无关?
最佳答案
阅读Structured Programming with go to Statements。虽然这是“过早的优化是万恶之源”的说法,但有人想把事情做得更快或更小时,无论它们在过程中多么紧迫或多么重要,它的出现实际上都是关于尽可能提高效率。
了解有关time complexity,空间复杂度和analysis of algorithms的信息。
拿出一些示例,在这些示例中,您可能希望牺牲较差的空间复杂度来提高时间复杂度,反之亦然。
了解您的语言和所选框架提供的算法和数据结构在时间和空间上的复杂性,尤其是您最常使用的算法和数据结构。
阅读本网站上有关创建良好哈希码的问题的答案。
研究HTTP采取的具有缓存优势的方法,而没有不适当地使用陈旧数据的缺点。考虑一下应用于内存缓存的难易程度。考虑一下您何时说“拧紧它,我可以忍受过时的速度提升了”。考虑一下您何时说“拧紧它,我可以放慢脚步,以保证它给我带来新鲜感”。
了解如何进行多线程。了解何时可以提高性能。了解为什么它经常不使事情变得更糟。
看很多Joe Duffy's blog,表现是他写作中经常关注的问题。
了解如何将项目作为流或迭代进行处理,而不是每次都构建和重建充满每个项目的数据结构。了解何时实际不这样做会更好。
知道什么东西要花钱。您无法合理地决定“我会工作,所以这应该在CPU缓存中,而不是主内存/主内存中,而不是磁盘/磁盘中,而不是通过网络”,除非您很好地知道实际上是什么导致了每个受到打击以及成本差异是多少。更糟糕的是,如果您不知道某些东西会花多少钱,就不能将其视为过早的优化-不费心去优化某些东西通常是最好的选择,但是如果您甚至不考虑通过优化,就不会“避免过早的选择”优化”,您正在摸索中,希望它能起作用。
了解一些有关您使用的脚本引擎/抖动/编译器/等为您进行了哪些优化的信息。了解如何与他们合作而不是与他们对抗。学会不要重新做它会为您做的工作。在一种或两种情况下,您也可以将相同的一般原理应用于您的工作。
在此站点上搜索一些被视为实现细节的案例-是的,所有这些案例中所讨论的细节在当时都不是最重要的事情,但是所有这些实现细节都是出于某种原因而选择的。了解他们是什么。学习反论点。
编辑(我将继续向其中添加一些内容):
当然,不同的书对效率的重视程度也有所不同,但是我记得Stroustrup的C ++编程语言曾多次出现,他将解释与效率相关的几种不同选择,以及如何不为了效率而做出决定会影响“从外部”类的可用性。
这使我想到了另一点。专注于在不同项目中重用的库代码的效率。您永远不会想“也许我应该在这里手动提高效率”,除非是非常专业的案例,否则您要确信,大量工作已投入使用,以使频繁使用的班级变得高效在很多情况下,并专注于识别热点。
对于特殊情况,某些较模糊的数据结构因其服务的情况而值得了解。例如,DAWG是一种非常紧凑的结构,用于存储带有许多常见前缀和后缀(大多数自然语言中的大多数单词)的字符串,您只想在列表中找到与模式匹配的字符串。如果您需要“有效负载”,那么其中每个字母都有一个每个后续字母的节点列表的列表(DAWG的一般化,但以该“有效负载”结尾而不是终端节点),具有一些但不是全部优点。他们还会在O(n)
时间中找到结果,其中n
是所搜索字符串的长度。
多久会出现一次?不太多。它对我来说是一次(实际上是几次,但它们是同一案例的变体),因此,在那之前学习有关DAWG的所有知识对我来说是不值得的。但是我知道得足够多,这才是我以后需要研究的内容,它为我节省了千兆字节(的确,对于16GB RAM的机器来说,应付的空间太多了,不到1.5GB)。直接进行手动滚动DAWG完全是过早的优化,而不是将字符串放入哈希集中,但是轻拂the NIST datastructure site表示可以。
请考虑:“在DAWG中查找字符串为O(n)”“在哈希集中查找字符串为O(1)”这两个语句都是正确的,但是两者的速度趋于可比。为什么?因为DAWG在字符串的长度上为O(n),而在DAWG的大小上实际上为O(1)。就哈希集的大小而言,哈希集为O(1),但是根据字符串的长度计算出来的哈希通常为O(n),就该长度而言,相等检查也为O(n) 。两种说法都是正确的,但是他们正在考虑使用不同的n
!在讨论时间和空间复杂性时,您始终需要知道n
的含义-大多数情况下,它是结构的大小,但并非总是如此。
不要忘记恒定的影响:对于n足够低的值,O(n²)与O(1)相同!请记住,假设kn和k2足够低,并且k和我们要比较的另一种算法或结构的k足够接近,则O(n²)的等式转换为n²* k + n *k₁+ k 2它们并不重要,我们只关心n²。并非总是如此,有时我们会发现k,k 1或k 2足够高,以至于我们陷入麻烦。当n太小以至于使不同方法的不变成本之差很重要时,也不是正确的。当然,通常情况下,当n小时,我们不会有太大的效率问题,但是如果我们对平均大小为n的结构进行m次操作,而m大时该怎么办。如果我们在O(1)和O(n²)方法之间进行选择,则总体上在O(m)和O(n²m)方法之间进行选择。似乎仍然很喜欢前者,但是n较低时,它实际上成为两种不同的O(m)方法之间的选择,并且常数因子更为重要。
了解无锁多线程。也许没有。就我个人而言,我有两个自己的专业代码,使用了除最简单的无锁技术以外的所有代码。一个基于众所周知的方法,我现在就不用理会(它是为.NET2.0最初编写的.NET代码,而.NET4.0库提供了执行相同功能的类)。我最初写的是另一个很有趣的东西,只是在那个有趣的时期之后才使用,这给了我一些可靠的东西(在很多情况下,它仍然被4.0库中的东西击败了,但对于我关心的其他一些情况却没有关于)。我讨厌必须像截止日期那样写一些这样的东西,并且要考虑到客户。
综上所述,如果您出于兴趣而编写代码,那么所涉及的挑战将很有趣,并且当您可以自由放弃在执行过程中没有得到的失败计划时,与之共事是一件令人愉快的事情。对于付费客户来说,这无疑是一件好事,您肯定会学到很多有关效率问题的知识。 (如果要查看我对此所做的一些事情,请查看https://github.com/hackcraft/Ariadne)。
案例研究
实际上,其中包含上述某些原则的相对较好的示例。看看当前在https://github.com/hackcraft/Ariadne/blob/master/Collections/ThreadSafeDictionary.cs的第511行的方法(我在此处开玩笑说它是引诱Dijkstra的人们的火焰诱饵。让我们将其用作案例研究:
此方法最初是使用递归编写的,因为它是自然递归的问题-在当前表上执行操作后,如果存在“下一个”表,我们要对该表执行完全相同的操作,依此类推,直到没有进一步的处理为止。表。
对于几种不同的方法,递归几乎总是比迭代慢。我们是否应该对所有递归调用进行迭代?不,通常不值得,而递归是一种编写清楚其工作方式的代码的绝妙方法。在这里,尽管我运用了上述原则,但由于这是一个在性能至关重要的地方可以被称为的库,因此应该为此付出更多的努力。
我决定提高速度,接下来要做的就是进行测量。我不依赖于“我知道迭代比递归要快,因此在进行更改以避免递归时必须更快”。事实并非如此-写得不好的迭代版本可能不如写得好的递归版本好。
下一个问题是,如何重写它。我有一个经过测试的方法,我知道它可以工作,并且我将其替换为其他版本。我不想用一个不起作用的版本替换它,很明显,那么如何在利用现有资源的最大优势的同时进行重写?
好吧,我知道消除尾音;通常由编译器完成的优化,该优化会更改堆栈的管理方式,从而使递归函数最终具有更接近于迭代属性的属性(从源代码的角度来看,它仍然是递归的,但是就实际编译代码的方式而言,它是迭代的使用堆栈)。
这给了我两点思考的问题:1.也许编译器已经在执行此操作,在这种情况下,我的额外工作将无济于事。 2.如果编译器尚未执行此操作,则可以手动采用相同的基本方法。
做出这个决定后,我替换了方法调用本身的所有要点,但更改了一个参数,该参数对于下一次调用将有所不同,然后返回到开头。即而不是:
CurrentMethod(param0.next, param1, param2, /*...*/);
我们有:
param0 = param0.next;
goto startOfMethod;
完成后,我再次进行测量。现在,通过该类的整个单元测试,运行速度始终比以前快13%。如果距离更近,我会尝试进行更详细的测量,但是对于包含甚至没有调用此方法的代码的运行,如果一致地进行13%的测试,我会非常满意。 (它还告诉我,编译器没有进行同样的优化,否则我将一无所获)。
然后,我整理方法以进行更多对新代码有意义的更改。他们中的大多数让我拿出
goto
,因为goto
确实很讨厌(还有其他地方进行了相同的优化,因为goto
完全重构了,所以优化并不那么明显)。在某些情况下,我将其保留下来,因为13%的价值值得我打破违规原则!因此,以上给出了一个示例:
确定在何处集中优化工作(基于可能会遇到的频率以及我无法预测库的所有使用情况)
使用一般成本知识(大多数情况下,递归成本大于迭代成本)。
测量而不是依赖于上述假设总是适用。
向编译器学习。
理解到这一点,我可能一无所获-也许编译器已经为我做了。
避免导致代码无法读取的优化(将大多数
goto
分解为首次引入的代码)。其中一些是见解和风格问题(决定离开某些
goto
不会引起争议),当然也可以不同意我的决定,但是了解到目前为止所提出的观点将使它成为现实。知情的分歧,而不是下意识的分歧。