在编程过程中,通常会遇到的一个问题就是,性能瓶颈。很多时候考虑的都是怎么去做横向扩展,但偏偏忽略掉了最基本的问题就是系统是否真的已经达到了瓶颈?
性能瓶颈通常的表象是资源消耗过多外部处理系统的性能不足;或者资源消耗不多但程序的响应速度却仍达不到要求。
而调优的方式就是 寻找过度消耗资源的代码 和 寻找未充分使用资源但程序执行慢的原因和代码。
就拿汽车来比较,通常不懂变速箱、发动机的原理但也是能开车,同样一个不懂数据结构和算法的人也能编程。很多人觉得基本的数据结构及操作已经在高级语言中封装,都可以直接调用库函数,那么到底有没有必要好好学习数据结构?
通常在程序中,遇到一个实际问题,充分利用数据结构,将数据及其之间的关系有效地存储在计算机中,然后选择合适的算法策略,并用程序高效实现,这才是提高程序性能的主要方式。
如果没有具备这块相应的知识,怎么完成上述的实现?如果脱离了原有的调用,怎么完成程序的高效实现?而所有的应用实现都依赖于基础,基础就是数据结构和算法。了解这块,才能做到无惧任何技术的演变。所有说基础决定高度!
数据结构表示数据在计算机中的存储和组织形式,主要描述数据元素之间和位置关系等。选择适当的数据结构可以提高计算机程序的运行效率(时间复杂度)和存储效率(空间复杂度)。
顺序结构:顺序结构就是使用一组连续的存储单元依次存储逻辑上相邻的各个元素
优点:只需要申请存放数据本身的内存空间即可,支持下标访问,也可以实现随机访问。
缺点:必须静态分配连续空间,内存空间的利用率比较低。插入或删除可能需要移动大量元素,效率比较低
链式结构:链式存储结构不使用连续的存储空间存放结构的元素,而是为每一个元素构造一个节点。节点中除了存放数据本身以外,还需要存放指向下一个节点的指针。
优点:不采用连续的存储空间导致内存空间利用率比较高,克服顺序存储结构中预知元素个数的缺点 插入或删除元素时,不需要移动大量的元素。
缺点:需要额外的空间来表达数据之间的逻辑关系, 不支持下标访问和随机访问。
索引结构:除建立存储节点信息外,还建立附加的索引表来标节点的地址。索引表由若干索引项组成。
优点:是用节点的索引号来确定结点存储地址,检索速度块
缺点:增加了附加的索引表,会占用较多的存储空间。
散列结构:由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外,还可以用于存储。
优点:散列是数组存储方式的一种发展,采用存储数组中内容的部分元素作为映射函数的输入,映射函数的输出就是存储数据的位置, 相比数组,散列的数据访问速度要高于数组
缺点:不支持排序,一般比用线性表存储需要更多的空间,并且记录的关键字不能重复。
数组
栈(后进先出)
队列(先进先出)
链表
二叉树(由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成)
堆(也被称为优先队列(队列+排序规则),图一最大堆,图二最小堆)
红黑树(每节点五元素,颜色(如果一个节点是红的,则它的两个儿子都是黑的)、键值、左子节点、右字节的、父节点)
在Java中,数组是用来存放同一种数据类型的集合,注意只能存放同一种数据类型。
//只声明了类型和长度 数据类型 [] 数组名称 = new 数据类型[数组长度]; //声明了类型,初始化赋值,大小由元素个数决定 数据类型 [] 数组名称 = {数组元素1,数组元素2,......}
未完待续......