1. Algorithm：每周至少做一个 leetcode 的算法题
  2. Review：阅读并点评至少一篇英文技术文章
  3. Tip：学习至少一个技术技巧
  4. Share：分享一篇有观点和思考的技术文章

ARTS挑战

Algorithm

排序算法汇总：

纯内存排序

  • 基于比较的排序算法
    • 插入排序
      • 直接插入
      • Shell排序
      • 罕见：伸展排序、二叉查找树排序、图书馆排序、耐心排序
    • 交换排序 两两比较然后交换或者不交换
      • 冒泡
      • 快排
      • 罕见：鸡尾酒排序、奇偶排序、梳排序、侏儒排序、臭皮匠排序、Bogo排序
    • 选择排序
      • 直接选择
      • 堆排序
      • 罕见：平滑排序、笛卡尔树排序、锦标赛排序、圈排序
    • 归并排序
      • 归并排序
      • 罕见：梯级归并排序、振荡归并排序、多相归并排序、串列排序
  • 基于非比较的排序算法
    • 基数排序
    • 计数排序
    • 桶排序
    • 罕见：美国旗帜排序、珠排序、爆炸排序、鸽巢排序、相邻图排序、闪电排序、插值排序
  • 混合排序
    • TimSort Java Collocations.sort()的实现，since JDK1.7。
    • 罕见：块排序、内省排序、Spread排序、J排序
  • 并发排序
    • 罕见：双调排序器、Batcher归并网络、两两排序网络
  • 其它排序
    • 罕见：拓扑排序、煎饼排序、意粉排序

直接插入

描述：将整个数列分为两部分，前面为有序列，后面为无序列，初始状态有序列中只有第一个数，便利后续每一个数，将其插入前面的有序列，直到无序列为空，排序完成。

时间复杂度:

  • best： O(n) 待排序为正序
  • Avg: O(n^2)
  • worst: O(n^2)} 空间复杂度:{O(1)}

Shell排序

描述： 缩小增量排序， 该方法实质上是一种分组插入方法。取一个增量D = d1，把相距d1位置的数当做一组，一共分为d1组，对每组进行插入排序，然后缩小增量，在进行分组并插入排序，直到增量D=1，数列即有序。

冒泡排序

描述： 属于交换排序，从头开始，两两比较，确保前大后小，否则交换，接着后移一位，重复比较交换的动作，直到最后，最后一个数为最大值。故叫冒泡，每次冒出一个未排序数列中的最大值。

时间复杂度：

  • best： O(n) 已经有序
  • Avg： O(n^2) 每冒一次为i（n~1），冒n次, n的阶加， 即为O(n^2)
  • worst: O(n^2)

快速排序

描述： 对冒泡的一种改进，也是交换排序。

  1. 在数列中先找到一个数作为pivot，将整个数列分为两部分，即比pivot小的和比pivot大的
  2. 然后在两个数列中重复第一步操作
  3. 递归直到子数列为1，不可再分，即为有序

时间复杂度：

  • best： O(nlogn)
  • Avg： O(nlogn) 递归层数logn，每一层比较次数大概是n
  • worst: O(n^2) 每次取pivot时没有把数列分为两部分，例如每次都取第一个数

直接选择排序

描述：它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

  • best： O(n) 本身已经是正序
  • Avg： O(n^2)
  • worst: O(n^2)

堆排序

描述：

  1. 选择排序，先将整个数列构建为最大堆，然后取堆顶元素，即为最大或最小，接着对余下的数列继续调整为最大堆，取出堆顶元素，即为第二大/小的元素，以此循环直至堆中只剩下一个元素，即为有序列。
  2. 其中构建最大堆的操作为：默认整个数列为一个堆，假设父节点位置为i，那么子节点的位置为2i+1和2i+2,假设一个节点位置为i，那么它的父节点为floor((i-1)/2);找到最后一个节点的父节点（(arr.length-2)/2）调整以该节点为根节点为子堆为最大堆，然后依次往前，使该节点的左兄弟节点，父节点，父节点的左兄弟节点。。。都进行最大堆的调整操作，进而使得整个数列成为最大堆。
  3. 其中调整最大堆的操作是，检查任意一个子节点是否比父节点大/小，如果是则交换，使得这个子堆满足最大/小堆的性质

时间复杂度：

  • best： O(nlogn)
  • Avg： O(nlogn)
  • worst: O(nlogn)

归并排序

归并，即将N个有序列合为一个有序列的方法，也叫作N路归并，算法还是比较简单

  1. 每一路维护一个前进指针
  2. 找出N路前进指针对应值做大的，添加到最终有序列中；
  3. 当前路的前进指针移动一位
  4. 重复步骤2，直至每一路都为空

归并排序：采用分治法

  • 方式1：从上往下，采用递归，将数列一分为二，递归调用将前后两部分排序，这时得到两个有序列，将两个有序列进行2路归并。
  • 方式2： 从下网上，采用步长的方式，初始步长为2，每个子序列排序，得到N/2个有序的序列，然后将步长×2=4，将两个有序的序列归并，得到长度为4的有序列，重复直到步长大于等于n，序列即有序。

基数排序

将所有的数字统一位数，不够前面补0，从低位到高位。例如一组两位的数列，先根据各位，将所有的数分配到0-9的桶里，得到按照各位排序的序列，然后按照十位，再次分配，得到按照十位排好序的数列，此时得到的即为有序列。这种方法利用了数字的特性。假设高位相同，先将低位的前后顺序确定好，然后往高位走，重复这样的步骤，最终所有位数的先后顺序都确定，即有序。

桶排序

将整个数列分为几个区间，分别对每个区间的数进行排序，使用什么排序都可以，例如插入排序；然后依次输出每个区间的值，即为有序列

计数排序

外部排序

描述：外部排序常用的算法就是归并排序，只不过做了改造和优化，目前最常用的就是多路归并算法当然还有大数据框架相关解决方案。

现有100G数据要进行排序。实现方案描述如下：

多路归并排序

  1. 将100G数据拆分为N份，使得每份的大小都能装入内存
  2. 将这N份数据分别在内存中排序后写入文件，内存排序可以选择效率比较高的就可以
  3. 每个文件取前m大小，使得N份m能装入内存，然后进行N路归并，将排序结果输出到文件
  4. 如果某一路的m大小的数据用完就继续从该文件读取m，重复步骤3
  5. 直到N个文件都读取完成，输出结果即为已排序结果。

MapReduce

依赖MapReduce框架，map函数输出（key-value），master按照key进行hash到N个worker，worker内部对拿到的数据按照key排序，得到N个有序列，因为master进行reduce任务分区的时候是通过hash算法，我们可以把数据分为N块，这N块之间的顺序可以很容易确定，没块内部也已经是有序，那么整体就是有序的。

Review

MapReduce-3.实现

  • 执行过程
    1. 分片（16-64M）
    2. Master分配任务，M个map任务，R个reduce任务
    3. 分配了map任务的worker读取任务数据，执行用户定义的map函数，输出中间结果在内存缓冲
    4. 缓存周期持久化，并分为R个区，将文件路径告诉master，master接着分配reduce任务
    5. 分配了reduce任务的worker根据从master中得到的路径去map worker中读取数据，然后对数据进行排序，让相同key的分为一组。如果要排序的数据太大则使用外部排序
    6. reduce worker遍历排序结果，得到{key->List(value)},接着执行用户的reduce方法，得到最终结果
    7. 当所有的map和reduce任务都完成，master唤醒用户程序，这时mapreduce调用返回。
  • master数据结构 master保存分配的任务，并记录状态（空闲、执行中、完成），并关联执行机器
  • 失败容忍
    • worker失败： master会给每一个worker发心跳，发现worker挂掉，就把这个worker的任务分给其它worker
    • master失败：master周期性进行checkpoint，把数据持久化，要是master挂了就启用备机。
    • 失败处理语义：
  • 计算本地化： 为了减少带宽占用，把任务分配到任务数据存储所在的机器或者同一个交换机的其它机器（计算并值，机架感知）
  • 任务粒度：map任务数要比机器大，太大也不好，增加master负担
  • 备份任务执行：有的机器因为各种问题处理速度慢，拖慢整个任务，解决方案是总体任务差不多快完成的时候，把还没完成的子任务分配一个备机执行，只要任意一个执行完成就可以。

Tip

CPU与内存的那些事

这篇文章比较长，算是囫囵吞枣读了一遍，对于理解计算机体系结构有很好的帮助，之前连南桥北桥都搞不清楚的我，终于理解了一些。

内容总结如下：

  • 体系结构
    • 北桥：CPU，内存，PCIE x16这些高速设备
    • 南桥： 网卡，磁盘等这些慢速设备
    • 设备速度：CPU：0.33ns，L1 cache:1ns,L2 Cache:4.7ns,RAM:83ns,disk:10+ms,lan:1~10ms,wan:~80ms
  • CPU操作内存
    • 针脚：地址Pins、数据Pins、请求Pins
    • 前端总线：仲裁，请求，侦听，响应，数据操作
    • 多级缓存
  • 芯片组与内存映射
    • 内存映射IO
    • CPU逻辑地址翻译
    • CPU的运行模式：实模式，32位保护模式，64位保护模式
  • 引导过程
    • BIOS引导
    • 内核引导
    • 从复位向量（reset vector）->BIOS->MBR->引导装载程序->实模式内核->保护模式内核，跳转跳转再跳转，经过所有这些杂七杂八的步骤，最后来到引导处理器（boot processor）中的空闲循环cpu_idle()。
  • 内存地址转换与分段
    • 为了使用比较小的位宽操作更大的地址空间
    • 段寄存器
  • CPU的运行环, 特权级与保护
    • 常用的环为0和3，大约15条指令被CPU限制只能在ring 0执行
    • CPU特权级并不会对操作系统的用户造成什么影响，不管你是根用户，管理员，访客还是一般用户。

未完待续。。。

Share

论选择困难症