怎样监测熊掌号绑定成功网站,闵行专业做网站,网站开发树形图,上海做网站的公司哪个好文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
MapReduce本质就是一个分值算法。
什么是分治算法
分治算法的核心是#xff1a;分而治之。也就是将原问题分解为n个规模较小#xff0c;并且结构与原问题相似的子…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
MapReduce本质就是一个分值算法。
什么是分治算法
分治算法的核心是分而治之。也就是将原问题分解为n个规模较小并且结构与原问题相似的子问题递归地解决这些子问题并且合并子问题的结果得到原问题的解。
与递归的区别递归是一种编程技巧分治是一种算法思想。
使用分治法的步骤 1 分解将原问题分解为一系列子问题 2 解决递归地解决各个子问题当问题足够小可以直接求解 3 合并将子问题的结果合并为原问题的解。
分治算法能解决的问题的特征 1 原问题与分解后的子问题具有相同的模式。 2 子问题可以独立求解子问题之间没有相关性这点与动态规划是有区别的。动态规划分解后的子问题可能是重复的需要把结果保存下来避免重复计算。 3 具有分解终止条件。当子问题足够小可以直接求解。 4 子问题的解合并为原问题的解合并操作不能太复杂否则起不到降低复杂度的效果。
计算数组的逆序度
假设我们有n个数据希望从小到大排序。当数组完全有序的时候有序度为n(n−1)2\dfrac{n(n-1)}{2}2n(n−1)逆序度为0。当数组是按照从大到小排序的时候那有序度是0无序度是n(n−1)2\dfrac{n(n-1)}{2}2n(n−1)。除了这两种极端情况我们计算数组逆序对的个数表示逆序度。
如何编程求出一组数组中逆序对的个数呢
直观的想法就是从第0个元素开始算一个后面有几个元素比它小计数为k0。再从第1个元素开始算一个后面有几个元素比它小计数为k1…一直算到最后一个元素。这几个计数(k0,k1…)加和就是逆序对的个数。时间复杂度是O(n^2)。是不是可以改进呢
我们试着用分治思想解决。求数组A的逆序对个数可以分解为前后两个部分数组分别标记为A1A2。递归求解A1A2逆序对个数K1K2再求出A1与A2之间逆序对个数K3。K1K2K3就是原问题的解。
当数组中只有两个元素的时候就可以知道K1K2的值。 如何求K3。我们可以参考归并排序的合并操作。将数组A1A2排序。假设数组A1{1,5,6},A2{2,3,4}。A1长度为3。 合并排序 1来自A1数组不用管 1,2 来自A2数组此时A1数组还有3-1个元素没有排序所以2小于A1数组中的2个元素 1,2,3来自A2数组此时A1数组还有3-1个元素没有排序所以2小于A1数组中的2个元素 1,2,3,4(来自A2数组此时A1数组还有3-1个元素没有排序所以2小于A1数组中的2个元素) 1,2,3,4,5来自A1数组不用管 1,2,3,4,5,6来自A1数组不用管 最终此次合并操作发现逆序对个数是2226。 合并为原问题的解K1K26。 合并操作是一个O(n)的时间复杂度。
public class ArrayReverseCount {private int num 0;public int count(int[] a){int n a.length;return mergeSortCounting(a,0,n-1);}private int mergeSortCounting(int[] a, int start, int end) {if(startend){return 0;}int q (startend)/2;int k1 mergeSortCounting(a,start,q);int k2 mergeSortCounting(a,q1,end);int k3 merge(a,start,q,end);return k1k2k3;}private int merge(int[] a, int start, int q, int end) {int[] temp new int[end-start1];int i start;int j q1;int k 0;int nums 0;while(iq jend){if(a[j]a[i]){temp[k]a[j];nums q-i1;}else{temp[k] a[i];}}while(iq){temp[k] a[i];}while(jend){temp[k] a[j];}for(i0;iend-start;i){a[starti] temp[i];}return nums;}
}经典练习题目
二维平面上有 n 个点如何快速计算出两个距离最近的点对 有两个 nn 的矩阵 AB如何快速求解两个矩阵的乘积 CAB 自己练习
分治思想处理海量数据
前面学到的一些算法和数据结构都是基于内存存储和单机处理的。如果要处理的数据量大没有办法一次加载到内存中。这时候这些算法和数据结构就不能发挥作用了。但我们可以使用分治思想来处理这个问题。
例如我们需要对10G的订单按照金额排序。单机只有3G内存。那么我们可以把这10G订单扫描一遍找到订单金额的最小值和最大值。将这10G订单按照订单金额从小到大分成几个区间。例如1-100放入一个小文件101-200放入另外一个文件。以此类推。这样形成的一个一个小文件可以加载到内存中。对单个文件最排序排序之后再合并排序结果。
如果订单数据是放在GFS这样的分布式文件系统上。被分成的多个小文件可以同时被不同的机器加载处理最后再合并结果集。这样并行处理速度就快多了。这里需要注意一点数据存储的机器与处理的机器需要在同一个网段内或者局域网。否则数据传输速度会是最大的时间开销。反而会慢。
Mapreduce 与 分治算法
这也就是MapReduce的原理。单个机器的性能不足以完成任务就把任务分配到多台服务器 。最后再合并结果。MapReduce是一个任务调度 框架。数据依赖GFS存储依赖Borg管理机器。它从 GFS 中拿数据交给 Borg 中的机器执行并且时刻监控机器执行的进度一旦出现机器宕机、进度卡壳等就重新从 Borg 中调度一台机器执行。
