编程思想与技术总结

作者:Rui 发布时间:August 5, 2015 分类:JAVA 浏览:497

我不是天才,但我相信,通过有效的方法和训练,以及持之以恒地积累,完全是可以成为一名出色的开发者的。那么,到目前为止,掌握了多少思想、方法和技术可以用于开发程序、处理软件开发过程中所遇到的问题呢?不妨作下总结,以备后用。

1. 抽象:
萃取出主要特征,而摒弃次要不相关的特征;无需了解物质的内部实现细节而基于其提供的抽象来构造应用;声明与实现相分离。计算机科学中的抽象俯拾即是,比 如汇编语言是对机器硬件的抽象,编译器是对高级程序语言的抽象,进程是对程序一次执行的抽象,线程是对任务执行流的抽象等。

2. 封装:
由抽象直接引出的重要概念就是封装。函数是算法的良好封装,对象是状态与逻辑的良好封装, 封装是实现软件模块化、提高软件可维护性的重要技术。封装是实现许多软件工程思想的溯源。比如,隔离变化, 将变化的影响局部化等

3. 复用:
不要重复发明轮子。复用是软件工程领域的重要技术。从标准库函数,STL,JDK这样的代码级复用,到 Struts, hibernate 这样的应用框架复用, 以及 设计模式的复用, 解决方案的复用, 复用无处不在。 复用是站在巨人的肩膀上, 能够直接利用专家级的知识和经验,何乐而不为?

4. 分层:
将系统分解为多个层次,精确定义每层所提供的服务及层次之间提供的服务接口;处于某个层次的层依赖于下一层提供的服务,并为上一层提供服务;各层之间无需知道彼此的细节。典型例子是网络协议栈及操作系统虚拟机的概念。

5. 模式:
在《水平思考的力量》一书中谈到,大脑的运作机制主要是模式机制,即通过模式存储、识别、连接和提取来实现思考。生活中无时不刻使用着模式,模式提高了人们的适应能力和反应能力。设计模式是模式思想在软件设计中的运用。

6. 缓存:
将一部分已求解值存储起来以备后用;或者将一次性存储一部分数据(包括但不仅含有当前所需数据),以便之后紧随着访问。动态规划法是使用缓存思想的典型例子。
存储器高速缓存是缓存思想的又一典型例子,与程序局部性原理密切相关。要想达到更好的程序性能,则必须采用一定手段,使得访问数据的顺序与数据在存储器中的存储顺序保持一致,这样才能提高命中率,防止大量的缺页中断带来的低效。

7. 中断:
保存现场, 。。。, 恢复现场。 中断是实现许多计算机制的重要基础。子程序,进程切换, I/0读写…… 思想是简单的, 影响是深远的。

8. 科学原理和性质
深刻理解科学原理和性质,往往能够催生非常简洁高效的算法和技术,这可能就是计算机科学家与开发者之间的一大区别吧。比如向量的旋转问题,将ab转 换为ba, 也是基于对逆置性质的深刻理解上。R(R(a)R(b)) = ba ; 问题: 将 abc 转换为 cba 呢?
向量的旋转问题: http://blog.csdn.net/shuqin1984/article/details/6331772

9. 二分搜索技术:
用于在有序数组(连续物理存储块)中查找给定关键字,时间复杂度为O(logn)。
例子: 在有序数组里找出给定关键字出现的次数;在不重复的若干整数中找出不存在的整数; 程序调试技巧。

10. 分区技术:
给定一个列表,从中选定一个主轴元素,将它置于某个位置,并将列表中的元素分为两个部分:使前半部分的所有元素都不大于该元素,后半部分的元素都不 小于该元素。例子:快速排序,找出第k大的元素(顺序统计量),请参阅《算法导论》第7章(快速排序)和第9章(顺序统计量)。

11. 分治技术:
将一个任务分解为多个子任务,然后分别求出这些子任务的解,最后综合这些子任务的解,得到总任务的解。时间复杂度是T(n) = aT(n/b) + G(n),主要因素取决于a, b , G(n)。 例子: 最近对问题,归并排序。

12. 递归技术:
一个规模为N的问题的解可以由规模为S(S<=N)的同样性质的问题的解来构造。T(N) = T(S) + G(N). 递归技术是一种非常有效的程序设计技术。
例子: 汉诺塔,二叉树操作
递归技术在二叉树操作的实现: http://blog.csdn.net/shuqin1984/article/details/6260499
二叉树的 Java 实现: http://blog.csdn.net/shuqin1984/article/details/6256415

13. 时空权衡技术:
通过额外操作以时间换空间,或者额外空间存储以空间换时间。在PC机上,通常是以空间换时间,例如,哈希表就是一个典型例子。
以时间换空间的例子,比如说在内存不足的情形下进行海量数据处理,可以采用k 趟遍历,每趟遍历解决一部分数据,得到一些子结果,最后将子结果合并。这样在I/O读写上可能耗费较大量的时间。当k比较小时,采取k趟排序是一个较好的选择。

14. 数组结构: 高效随机访问的下标集到值集的映射。
a) 下标集是存储连续的,即最简单的数组形式;
b) 下标集是非连续的, 例如存储稀疏矩阵的元组集合

15. 链表:
a) 单链表: 在列表中高效地插入、删除;
b) 多重栈、多重队列实现;

16. 栈: 先进后出型数据结构,仅允许在一端进行插入和删除。
a) 深度优先搜索的辅助数据结构,比如回溯技术
b) 典型用例: 表达式计算,走迷宫

17. 队列: 先进先出型数据结构,仅允许在一端进行插入,在另一端进行删除。
a) FIFO服务的最佳选择,比如操作系统中各种就绪、阻塞队列
b) 广度优先搜索的辅助数据结构,比如二叉树的层序遍历

18. 二叉查找树:
在平均情形下,查找、插入、删除、最大元素、最小元素、前驱元素、后继元素的操作均为O(logn),最差情形是O(n)。中序遍历可用于排序。
二叉查找树的 Java 实现: http://blog.csdn.net/shuqin1984/article/details/6246615

19. 散列表:
通常主要支持查找、插入和删除操作,散列表是实现高效检索的重要数据结构;在平均情形下,这些操作可以在O(1)内完成;在最差情形下,在O(n)内完成。
散列表的C语言实现: http://blog.csdn.net/shuqin1984/article/details/6587503

20. 位图技术:
将给定元素标识成一个位,从而在后续处理中标识该元素的存在。可用于稠密集合的排序,节省空间资源。
位图排序: http://blog.csdn.net/shuqin1984/article/details/6204224

21. 堆结构:
在大量数据中用来查找前K大的元素,实现优先级队列以及排序。请查阅算法导论第八章(堆排序)

22. 表结构:
表结构是计算机领域的常用结构,比如编译器符号表, 中断处理程序表, 数据库表等。 表结构也可以看作是 “空间换时间” 的例子, 通过表项事先存储一定信息,然后通过下标就可以迅速找到相应的程序入口地址或者数据项。表结构通常与索引技术结合使用。

23. 算法分析: Ο(n), Ω(n), Θ(n)
通过统计基本操作的次数,并取主项,可以得到算法运行的时间复杂度。
a) Ο(n): 算法的上界,即至多要运行的时间近似;
b) Ω(n): 算法的下界,即至少要运行的时间近似;
c) Θ(n): 算法的精确界,不大于O(n),不小于Ω(n)
NOTE: 这里通俗地说明三种界,精确定义请参考相关的算法书籍。
通过取阶、无穷小可以快速判断算法复杂度。比如
3n^2 + 2nlogn = O(n^2) 这是因为:
(3n^2 +2nlogn)/(n^2) 对 n 取极限(当n趋于无穷大时)为零,而
(3n^2 +2nlogn)/(nlogn) 取极限为无穷大,因此,
3n^2 + 2nlogn = O(n^2), 3n^2 + 2nlogn =Ω(nlogn)
通过对程序中的嵌套循环层数可以快速判断算法的时间复杂度;但有些情况是例外,比如外层循环的下标根据内层循环的下标进行跳跃性前进。
常见算法技术总结: http://blog.csdn.net/shuqin1984/article/details/5859534

24. 算法的三种情况分析:
a) 最优情况分析: 即找出一组输入,使该算法在最短的时间内完成。比如插入排序的最优情况是输入基本有序,时间复杂度为O(n)
b) 最差情况分析: 即找出一组输入,使该算法在最长的时间内完成。比如快速排序的最差情况是输入基本有序,时间复杂度为O(n^2)
c) 平均性能分析: 通过比较精确的数学分析方法,求出该算法在一般输入下的算法运行时间。比如快速排序的平均性能在O(nlogn), 插入排序的平均性能在O(n^2)

25. 索引:
通过标识并避免移动大容量记录从而提升时间效率的方法;也可用于共享内存空间,比如Linux中的文件共享就是用索引技术来实现的。

26. 记法与解释器:
通过记法来表达问题空间,然后,编写解释器来解析记法,得出结果。
例子: 图案打印。先创建一套记法或指令,描述图案的画法,然后编写解析器来解析这些记法或指令,从而打印出图案。
图案打印实现: http://blog.csdn.net/shuqin1984/article/details/6602369

27. 正则表达式
正则表达式是用来描述字符串的模式结构的,比如 \d{4} 可以描述4个数字组成的字符串。正则表达式是文本处理的强有力工具。
正则表达式基础: http://blog.csdn.net/shuqin1984/article/details/6422258

28. 异或妙用:
0^0 = 0,0^1 = 1, 1^0=1, 1^1 = 0. 异或满足交换律和结合律,即a^b^c = a^c^b = b^a^c = b^c^a = c^a^b = c^b^a ;对于整数a,b来说,若a = b,则 a^b =0 ; 若 a^b = 0, 则 a = b ; a^0 = a, a^a = 0, 因此 b^a^b = a 异或可以消去偶数次重复出现的数。
① 不用临时存储空间交换两个整数。a = a^b, b = b^a, a =a^b, 实际上就是 a = a^b, b = b^(a^b) = b^b^a = a , a =(a^b)^a = b
② 有2k+1 个数,其中 k 个数出现了2次,一个数出现了1次,请找出这个只出现了一次的数。

29. “哨兵元素”:
在连续存储块(比如数组)的边界设置一个哨兵元素,从而减少比较次数,或者防止越界。

30. 断言与不变式:
使用断言来检测函数参数的有效性,验证前置条件是否成立;在程序的适当位置插入断言,验证程序执行状态是否正常;在程序的结尾插入断言,验证程序的后置条件是否成立。
不变式可以用来证明程序的正确性。通过设置合理的不变式,并证明在顺序、选择和循环中不变式总成立,从而证明程序的正确性。

标签: none

添加新评论 »