在淘宝做网站可以改域名吗,运行时间 wordpress,网站开发有什么软件,桂林网站建设服务电话文章目录1. 时间、空间复杂度 ! 性能2. 抛开数据规模谈数据结构和算法都是“耍流氓”3. 结合数据特征和访问方式来选择数据结构4. 区别对待IO密集、内存密集和计算密集5. 善用语言提供的类#xff0c;避免重复造轮子6. 千万不要漫无目的地过度优化熟知每种数据结构和算法的功能…
文章目录1. 时间、空间复杂度 ! 性能2. 抛开数据规模谈数据结构和算法都是“耍流氓”3. 结合数据特征和访问方式来选择数据结构4. 区别对待IO密集、内存密集和计算密集5. 善用语言提供的类避免重复造轮子6. 千万不要漫无目的地过度优化熟知每种数据结构和算法的功能、特点、时间空间复杂度还是不够的。工程上的问题往往都比较开放往往需要综合各种因素比如编码难度、维护成本、数据特征、数据规模等最终选择一个工程的最合适解而非理论上的最优解。 1. 时间、空间复杂度 ! 性能
复杂度不是执行时间和内存消耗的精确值 大O表示法表示复杂度的时候复杂度给出的只能是一个非精确量值的趋势。代码的执行时间有时不跟时间复杂度成正比 时间复杂度是Onlogn的算法比时间复杂度是On2的算法执行效率要高。前提是算法处理的是大规模数据的情况。对于处理不同问题的不同算法其复杂度大小没有可比性
2. 抛开数据规模谈数据结构和算法都是“耍流氓”
在数据规模很小的情况下普通算法和高级算法之间的性能差距会非常小。 大部分情况下我们直接用最简单的存储结构和最暴力的算法就可以了。
比如对于长度在100以内的字符串匹配我们直接使用朴素的字符串匹配算法就够了。如果用KMP、BM这些更加高效的字符串匹配算法实际上就大材小用了。因为这对于处理时间是毫秒量级敏感的系统来说性能的提升并不大。相反这些高级算法会徒增编码的难度还容易产生bug。
3. 结合数据特征和访问方式来选择数据结构
如何将一个背景复杂、开放的问题通过细致的观察、调研、假设理清楚要处理数据的特征与访问方式这才是解决问题的重点。
比如前面讲过Trie树这种数据结构是一种非常高效的字符串匹配算法。但是如果你要处理的数据并没有太多的前缀重合并且字符集很大显然就不适合利用Trie树了。所以在用Trie树之前我们需要详细地分析数据的特点甚至还要写些分析代码、测试代码明确要处理的数据是否适合使用Trie 树这种数据结构。
再比如图的表示方式有很多种邻接矩阵、邻接表、逆邻接表、二元组等等。你面对的场景应该用哪种方式来表示具体还要看你的数据特征和访问方式。如果每个数据之间联系很少对应到图中就是一个稀疏图就比较适合用邻接表来存储。相反如果是稠密图那就比较适合采用邻接矩阵来存储。
4. 区别对待IO密集、内存密集和计算密集
如果要处理的数据存储在磁盘比如数据库中。那代码的性能瓶颈有可能在磁盘IO而并非算法本身。这个时候你需要合理地选择数据存储格式和存取方式减少磁盘IO的次数。
比如最终推荐人的例子。如果某个用户是经过层层推荐才来注册的获取他的最终推荐人的时候就需要多次访问数据库性能显然不高。 我们知道某个用户的最终推荐人一旦确定就不会变动。所以可以离线计算每个用户的最终推荐人并且保存在表中的某个字段里。当要查看某个用户的最终推荐人的时候访问一次数据库就可以获取到。
如果数据是存储在内存中那还需要考虑代码是内存密集型的还是CPU密集型的。
所谓CPU密集型简单点理解就是代码执行效率的瓶颈主要在CPU执行的效率。我们从内存中读取一次数据到CPU缓存或者寄存器之后会进行多次频繁的CPU计算比如加减乘除CPU计算耗时占大部分。所以在选择数据结构和算法的时候要尽量减少逻辑计算的复杂度。比如用位运算代替加减乘除运算等。
所谓内存密集型简单点理解就是代码执行效率的瓶颈在内存数据的存取。对于内存密集型的代码计算操作都比较简单比如字符串比较操作实际上就是内存密集型的。每次从内存中读取数据之后我们只需要进行一次简单的比较操作。所以内存数据的读取速度是字符串比较操作的瓶颈。因此在选择数据结构和算法的时候需要考虑是否能减少数据的读取量数据是否在内存中连续存储是否能利用CPU缓存预读。
5. 善用语言提供的类避免重复造轮子
大部分常用的数据结构和算法编程语言都提供了现成的类和函数实现。比如Java中的HashMap就是散列表的实现TreeMap就是红黑树的实现等。除非有特殊的要求一般直接使用编程语言中提供的这些类或函数。
这些编程语言提供的类和函数经过无数验证过的不管是正确性、鲁棒性都要超过你自己造的轮子。
重复造轮子并没有那么简单。你需要写大量的测试用例并且考虑各种异常情况还要团队能看懂、能维护。出力不讨好。
这也是很多高级的数据结构和算法比如Trie树、跳表等在工程中并不经常被应用的原因。但这并不代表学习数据结构和算法是没用的。深入理解原理有助于你能更好地应用这些编程语言提供的类和函数。能否深入理解所用工具、类的原理这也是普通程序员跟技术专家的区别。
6. 千万不要漫无目的地过度优化
一段代码执行只需要0.01秒你非得用一个非常复杂的算法或者数据结构将其优化成0.005秒。这种微小优化的意义也并不大。维护成本高。
要学会估算。不仅要对普通情况下的数据规模和性能压力做估算还需要对异常以及将来一段时间内可能达到的数据规模和性能压力做估算。这样我们才能做到未雨绸缪写出来的代码才能经久可用。
还有当你真的要优化代码的时候一定要先做Benchmark 基准测试。这样才能避免你想当然地换了一个更高效的算法但真实情况下性能反倒下降了。
