Keen的博客

记录所思、所想、所遇

欢迎来到我的个人站~


算法与应用数学

最常见的数据结构:数组、链表结构,以及最基本的元数据处理算法

  • 查找算法:枚举查找、哈希查找、二分查找。最常见的应用场景是:内存缓存数据查询
  • 排序算法:选择排序、冒泡排序、快速排序、插入排序、归并排序。最常见的应用场景是:内存缓存数据排序

查找算法

  • 用处最广的算法,一般而言,使用枚举查找,时间复杂度O(n)。对于大多数场景,是在一个小数据量(通常在内存数组或链表等结构)中存储的数据的查找。
  • 如果还想更快,只能引入散列表(也称为哈希表),通过有逻辑的hash函数,来实现O(1)级别的查找。通常使用的字典、hash_map就是这种。这里,哈希函数是实现该任务的最关键因素,也是决定程序是否真的比枚举好的决定性因素(因为通常枚举实现非常简单,程序不会有bug,但是哈希函数,需要考虑内存存储空间的消耗、需要考虑哈希函数映射关系、需要考虑哈希函数本身实现的性能消耗等,所以比较适合采用现有成熟的组件来使用)。使用哈希查找,是最典型的用空间换取时间的方法,如果有100w个数据要查找,可以建立100w个hash桶,通过hash算法直接映射到这100w个桶中,就可以实现瞬间查找。但是实际上,我们通常是无法这么做到,通常会将桶到个数,限制到有限个,例如1w个,而进一步将数据平缓到映射到这1w个当中。其实hash函数本质上,也是做数据均匀分类到一种有效机制。要做到均匀分类,实际上就是要做到用均等概率,来映射每个值,保证hash分类产生均等概率函数。
  • 二分查找,真正使用的场景比较小,因为它受限于数据采用顺序排序的方式存储。不过之所以使用场景比较小,是因为我们很少用到需要非常大量的查询的性能消耗场景,因为大多都是在内存中对小量数据数组进行查找,而这些数据,查找和修改的频率,不会相差太大。真正用途较广的,或许只有一些组件中使用。但是正因为我们使用得非常少,说明我们对性能的追求,并为达到极致,实战中,还应该更多的考虑这些点。

哈希函数实现方式

ToDo

排序算法

  • 最常使用的是选择排序,时间复杂度O(n^2),每次选择最小的值,交换到首位。我们不在乎这一点点性能消耗,也是由于n通常会非常小,通常为千级别,而且它实现最简单,我们也可以利用多线程技术,让这种想对稍微耗时操作放置在独自的线程中异步处理。说白了,还是数据量不够巨大,对性能追求不高。
  • 冒泡排序,时间复杂度虽然也为O(n^2),但是通常不使用它,因为我们操作的数据块,通常是多线程使用,我们希望读更可能多,而写更可能少。冒泡排序相对于选择排序,它几乎每次操作都在写数据,对于数据的比较,它没有比选择排序耗时少,而增加了写操作。简单来说,冒泡排序是减少了一个全局变量的存储空间消耗(选择排序使用一个x_min内存变量,来表征全局最小),每次依靠本数组的数据交换,来实现将最小值不断往前提升。不过另外一方面,它每次交换,都会让小数往左,大数往右,每次比较的同时,整体进行来调整,一般而言,最终操作的步数,应该是要比选择排序少,因为很可能到提前将所有数据都排序完成。不过总体来说,使用频率不如选择排序。
  • 快速排序,利用了递归的机制,每次选择一个基准值,将比它小的靠左,比它大的靠右放,然后利用递归,分别对左侧的数据和右侧的数据,再次进行前面相同的操作。这样,它将本来要用O(n^2)的时间消耗,降低到O(nlog(n)),它的本质,跟冒泡排序有点像,都是每次的操作,都整体操作数据,使得情况变得比上一次好。不过它比冒泡排序优良的点在于,冒泡排序虽然也是整体数据调整,每次都比上一次好,但是算法本身并未对这个好产生感知,最终的效果是,即时中间步骤已经排序完成,最终也还是需要遍历到结尾。而快速排序在这一点上进行了改进,每次情况变得更好,还能通过操作步数的减少,尽可能的展示这种变好的可能情况,而它减少步数的操作的本质是,每一次操作都将整个长度除以2,也就是,拆分log(n)层,就基本上将整个数据拆分成2个。这里边其实还有一个因素在于,拆分这个动作,其实也是耗时了,相比于冒泡排序、选择排序,拆分这个动作是多余出来的,但是由于拆分只是递归中栈指针和几个寄存器的操作,耗时可以忽略不计,正是利用了这种耗时权重的意义的东西,才造就了快速排序优良的性能优势。
  • 插入排序,与选择排序类似,每次都选择最小都值,只不过不是交换,而是放到第三个数据块中,依次放入(当然也可以选择直接使用当前数据块,那就跟冒泡排序有点类似,不同于冒泡排序的是,它每次选择的值,是插入前面数据块的中间,而冒牌排序,每次都是挑选剩余都最小都值出来)。它的存在,对于一堆乱序都数据块而言,其实意义不是很大,因为每次都要遍历完整都数据块,找到最小值。但是,如果把它用于处理两个顺序数据块的排序,就非常合适了,因为只需要遍历一次,我们就能确定整个数据排序完成。
  • 归并排序,跟快速排序类似,同样采用递归的思想,时间复杂度也为O(nlog(n)),但是不同于快速排序的点在于,快速排序是自顶向下,每次都全部遍历找到比基准值小和比基准值大都值,重新组成新数据块。而归并排序,是自底向上,不断二分数据块,直到不能再分,然后自底向上,然后采用插入排序,不断将左右两个顺序都数据块,重新组成一个更大都数据块。相比于快速排序,每次划分都使得情况变得更好,归并排序是直到划分到底层之后,才开始逐步向上排序以及merge排序完的结果。实际场景中,使用快速排序更多,实现更简单直接。

元数据表征方式,比较常见到,是采用数组、链表的形式。而图,也是一种更复杂到元数据表征方式,能表征更大的场景下的概念。可以说,数组、链表等,所表征的每一个数据元素之间,是独立不相关的,彼此完全独立。而图所表示的每一个数据元素之间具有相关性的概念。例如一个纯色图片,可以用二维数组表征,它的每个数据元素,都是一个色号,元素与元素之间,没有任何相关性;而一旦来说一副艺术图,用二维数组表征的话,其实它的元素之间,是具有相关性的,这种相关性,主要表现在相邻元素(上下左右)的相关性,以及相邻数据块(上下左右)的相关性。研究独立的东西,只研究单点,一个个攻破即可,研究关联性的东西,则需要借助相关性的概念,借助关联来分析。

打赏一个呗

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏,你说多少就多少