数据结构与算法(五)查询

很多时候,我们会比较在意查询的时间,因为这是用户最常使用的功能,并且是实时的需求,非常影响用户体验,以下是各种数据结构查询的效率,我们可以看到平衡二叉树等查找效率比较高,其实这是将时间前移了,因为平衡二叉树本身就是有序的,相当于已经对数据进行了一个排序,我们可以看到插入构造这个树的时间LOG(N)。

image

一.无序数据基础查找

像单链表这种无序队列,插入的时候很快的,直接加到末尾就可以,但是其查找确实耗时,使用了直接查找法。

所以为了加速查找的速度,需要将数据预先进行排序,一般就是生成的 时候就进行排序,比如数据库表加索引,构造二叉树,哈希表存储数据,这样在这些有序数据基础上进行数据查找就快多了,虽然在构造的时候会消耗时间,甚至让总时间都增加了,但是,有什么关系呢。

二.有序数据查找

无序数据查找效率比较慢,所以一般查找前都会排序,分担一部分的压力。

折半查找法

适用场景:针对已排序序列,并且只适用于顺序存储结构的序列,这样才能O(1)找到其中间值。但是这样一来,其插入,删除会变得比较低效,鱼熊不可兼得。

B树(二叉查找树)算法

其查找效率与树的深度有关。

HASH查找

算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

算法流程:

1)用给定的哈希函数构造哈希表;

2)根据选择的冲突处理方法解决地址冲突;

常见的解决冲突的方法:拉链法和线性探测法。 详细的介绍可以参见:  哈希表 。

3)在哈希表的基础上执行哈希查找。

这也是用空间换时间的例子之一。所以哈希表是查询效率的极致了。但是要解决好健冲突问题,比如拉链法,相当于将有共同哈希值的数据存储到一个链上,哈希值索引指向这个链,如果链COUNT>1,则再在链上顺序查找,这也有分治法的应用效果,基本上std::map 这种 kv存储结构就是哈希表的应用。这还可以衍生出进行大数据外排查找Top K问题。

数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。综合两者特性,设计一种寻址容易,插入删除也容易的数据结构,如拉链法实现的哈希表。

拉链法实现的哈希表应该也算是一个分块查找,索引查找的实现方式

分块查找(索引查找)

分块查找又称索引顺序查找,它是顺序查找的一种改进方法。

算法思想: 将n个数据元素”按块有序”划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……

这种也适合使用并行进行查找。

算法流程:

step1 先选取各块中的最大关键字构成一个索引表;

step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。

数据结构与算法(四)排序

根据待排序数据量能否被全部装载到内存中进行排序分为:内部排序外部排序。当然我们都希望直接在内存中进行排序,因为IO的延迟非常的大,但对于大数据集来说,内存是远远不够的,这时候就涉及到外排序,外排序通过读/写外存的次数来衡量其效率。基本上上学的时候学的都是内部排序,同时万不得已,都尽量使用内部排序,或者转化为内部排序。其实也就是说,我们要以空间换时间,以稳定性换时间,所以如何选择排序方法要综合场景来进行

一.基本排序

http://ibinguo.net/wp-content/uploads/2016/12/image_thumb8.png

image

冒泡排序->快速排序->归并排序

冒泡排序是最基本的排序算法,遍历所有数据,一次遍历查出最大值。所以如果要查询某个最大值也可以使用下冒泡。但是这个速度不敢恭维,所以有了变种快速排序,当然是以牺牲部分空间及稳定性为条件的。

快速排序快排是基础单线程排序中效率最好的了。以分治的思想进行排序,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

 

插入排序->希尔排序->并归排序

插入排序:遍历剩余所有数据,遍历待排序数据,将数据插入到一个已排序好的队列中,该已排序好的队列慢慢增大。

插入排序是每次将一个数据插入待排序序列,即步长为1希尔排序也可称为分组插入方法,则是步长>1,每个分组内使用插入排序或者二分插入排序。

并归排序:

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时,把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成,将它们依次两两归并得到长度为2的若干有序子表,再对它们两两合并。直到得到长度为n的有序表,排序结束。
归并操作的工作原理如下:

  1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  2、设定两个指针,最初位置分别为两个已经排序序列的起始位置

  3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

  4、重复步骤3直到某一指针达到序列尾

堆排序

堆实际上是一棵完全二叉树,利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。

二.适用场景

综合上述,得到的各种情况下的最优排序分别是:

(1)序列完全有序,或者序列只有尾部部分无序,且无序数据都是比较大的值时, 【直接插入排序】最佳(哪怕数据量巨大,这种情形下也比其他任何算法快)

(2)数据基本有序,只有少量的无序数据零散分布在序列中时,【希尔排序】最佳

(3)数据基本逆序,或者完全逆序时,  【希尔排序】最佳(哪怕是数据量巨大,希尔排序处理逆序数列,始终是最好的,当然三数取中优化的快速排序也工作良好)

(4)数据包含大量重复值,【希尔排序】最佳(来自实验测试,直接插入排序也表现得很好)

(5)数据量比较大或者巨大,单线程排序,且较小几率出现基本有序和基本逆序时,【快速排序】最佳

(6)数据量巨大,单线程排序,且需要保证最坏情形下也工作良好,【堆排序】最佳

(7)数据量巨大,可多线程排序,不在乎空间复杂度时,【归并排序】最佳

 

三.