• 关于

    区间计算出问题什么情况

    的搜索结果

问题

【今日算法】4月29日-区间交集问题

先看下题目,LeetCode 第 986 题就是这个问题: 给定两个由一些闭区间组成的列表,每个区间列表都是成对不相交的,并且已经排序。 返回这两个区间列表的交集。 ࿰...
游客ih62co2qqq5ww 2020-04-30 13:06:04 2 浏览量 回答数 1

问题

由阿里云服务器宕机看真正云计算

据阿里云官方公告称:由于电力故障导致阿里云部分云服务器于10月30日16:57开始出现无法访问,受影响的包含阿里云科技博客ifanr等网站。 无独有偶,此前在8月6日࿰...
chinasoso 2019-12-01 21:09:28 9672 浏览量 回答数 3

问题

【今日算法】4月20日-二分查找详解

先给大家讲个笑话乐呵一下: 有一天阿东到图书馆借了 N 本书,出图书馆的时候,警报响了,于是保安把阿东拦下,要检查一下哪本书没有登记出借。阿东正准备把每一本书在报警器下...
游客ih62co2qqq5ww 2020-04-20 13:50:19 4 浏览量 回答数 1

问题

经典动态规划:高楼扔鸡蛋 6月2日 【今日算法】

今天要聊一个很经典的算法问题,若干层楼,若干个鸡蛋,让你算出最少的尝试次数,找到鸡蛋恰好摔不碎的那层楼。国内大厂以及谷歌脸书面试都经常考察这道题,只不过他们觉得扔鸡蛋太浪...
游客ih62co2qqq5ww 2020-06-02 16:06:52 3 浏览量 回答数 1

问题

【今日算法】备战大厂必备题目,持续更新

学习算法,每天进步一点点! 想要进入大厂,发现算法题总是困难重重,我们整理了备战大厂那些必不可少的算法题目,周一到周五每天更新一道,答案会在出题第二天倾情奉上哦~ 72...
游客ih62co2qqq5ww 2020-04-08 09:21:40 3542 浏览量 回答数 4

问题

什么是B+树 6月1日【今日算法】

前言 每当我们执行某个 SQL 发现很慢时,都会下意识地反应是否加了索引,那么大家是否有想过加了索引为啥会使数据查找更快呢,索引的底层一般又是用什么结构存储的呢,相信大家看了标题已经...
游客ih62co2qqq5ww 2020-06-01 14:50:52 1 浏览量 回答数 1

问题

LogGroup对银行的应用是怎样的?

以19世纪银行为例。某个城市有若干用户(Producer),到银行去存取钱(User Operation),银行有若干个柜员(Consumer...
轩墨 2019-12-01 21:58:50 1492 浏览量 回答数 0

问题

从一道面试题谈谈一线大厂码农应该具备的基本能力 7月16日 【今日算法】

##关于一线码农的面试,我想说 求职面试在绝大部分人来说都是必不可少的,自己作为求职者也参与了不少面试(无论成功或者失败),作为技术面试官参与面试也有四五年的经验&#x...
游客ih62co2qqq5ww 2020-07-22 13:45:47 118 浏览量 回答数 1

问题

竞赛中的点滴成长

  时隔一个月再去回顾这个比赛,其实更多的是一种反思与过程的分享吧。来自南昌航空大学材料学院的一名大三本科生,参加这个比赛纯粹是因为喜欢,或者说,是抱着一种不怕死不怕被虐不怕丢脸的心态...
仰慕学姐 2019-12-01 21:54:56 9215 浏览量 回答数 5

回答

    using System;     using System.Collections.Generic;     using System.Linq;     using System.Text;    namespace test{    class QuickSort    {        static void Main(string[] args)        {            int[] array = { 49, 38, 65, 97, 76, 13, 27 };            sort(array, 0, array.Length - 1);            Console.ReadLine();        }        /**一次排序单元,完成此方法,key左边都比key小,key右边都比key大。         **@param array排序数组          **@param low排序起始位置          **@param high排序结束位置         **@return单元排序后的数组 */        private static int sortUnit(int[] array, int low, int high)        {            int key = array[low];            while (low < high)            {                /*从后向前搜索比key小的值*/                while (array[high] >= key && high > low)                    --high;                 /*比key小的放左边*/                array[low] = array[high];                   /*从前向后搜索比key大的值,比key大的放右边*/                while (array[low] <= key && high > low)                    ++low;                 /*比key大的放右边*/                array[high] = array[low];            }            /*左边都比key小,右边都比key大。//将key放在游标当前位置。//此时low等于high */            array[low] = key;            foreach (int i in array)            {                Console.Write({0}\t, i);            }            Console.WriteLine();            return high;        }            /**快速排序 *@paramarry *@return */        public static void sort(int[] array, int low, int high)        {            if (low >= high)                return;             /*完成一次单元排序*/            int index = sortUnit(array, low, high);             /*对左边单元进行排序*/            sort(array, low, index - 1);            /*对右边单元进行排序*/            sort(array, index + 1, high);        }    }} 运行结果:27 38 13 49 76 97 6513 27 38 49 76 97 65  13 27 38 49 65 76 97快速排序就是递归调用此过程——在以49为中点分割这个数据序列,分别对前面一部分和后面一部分进行类似的快速排序,从而完成全部数据序列的快速排序,最后把此数据序列变成一个有序的序列,根据这种思想对于上述数组A的快速排序的全过程如图6所示:初始状态 {49 38 65 97 76 13 27} 进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65} 分别对前后两部分进行快速排序{27 38 13} 经第三步和第四步交换后变成 {13 27 38} 完成排序。{76 97 65} 经第三步和第四步交换后变成 {65 76 97} 完成排序。图示 快速排序的最坏情况基于每次划分对主元的选择。基本的快速排序选取第一个元素作为主元。这样在数组已经有序的情况下,每次划分将得到最坏的结果。一种比较常见的优化方法是随机化算法,即随机选取一个元素作为主元。这种情况下虽然最坏情况仍然是O(n^2),但最坏情况不再依赖于输入数据,而是由于随机函数取值不佳。实际上,随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)。所以随机化快速排序可以对于绝大多数输入数据达到O(nlogn)的期望时间复杂度。一位前辈做出了一个精辟的总结:“随机化快速排序可以满足一个人一辈子的人品需求。”随机化快速排序的唯一缺点在于,一旦输入数据中有很多的相同数据,随机化的效果将直接减弱。对于极限情况,即对于n个相同的数排序,随机化快速排序的时间复杂度将毫无疑问的降低到O(n^2)。解决方法是用一种方法进行扫描,使没有交换的情况下主元保留在原位置。 QUICKSORT(A,p,r)1 if p<r2 then q ←PARTITION(A,p,r)3 QUICKSORT(A,p,q-1)4 QUICKSORT(A,q+1,r)为排序一个完整的数组A,最初的调用是QUICKSORT(A,1,length[A])。快速排序算法的关键是PARTITION过程,它对子数组A[p..r]进行就地重排:PARTITION(A,p,r)1 x←A[r]2 i←p-13 for j←p to r-14 do if A[j]≤x5 then i←i+16 exchange A[i]←→A[j]7 exchange A[i+1]←→A[r]8 return i+1 对PARTITION和QUICKSORT所作的改动比较小。在新的划分过程中,我们在真正进行划分之前实现交换:(其中PARTITION过程同快速排序伪代码(非随机))RANDOMIZED-PARTITION(A,p,r)1 i← RANDOM(p,r)2 exchange A[r]←→A[i]3 return PARTITION(A,p,r)新的快速排序过程不再调用PARTITION,而是调用RANDOMIZED-PARTITION。RANDOMIZED-QUICKSORT(A,p,r)1 if p<r2 then q← RANDOMIZED-PARTITION(A,p,r)3 RANDOMIZED-QUICKSORT(A,p,q-1)4 RANDOMIZED-QUICKSORT(A,q+1,r) 这里为方便起见,我们假设算法Quick_Sort的范围阈值为1(即一直将线性表分解到只剩一个元素),这对该算法复杂性的分析没有本质的影响。我们先分析函数partition的性能,该函数对于确定的输入复杂性是确定的。观察该函数,我们发现,对于有n个元素的确定输入L[p..r],该函数运行时间显然为θ(n)。最坏情况无论适用哪一种方法来选择pivot,由于我们不知道各个元素间的相对大小关系(若知道就已经排好序了),所以我们无法确定pivot的选择对划分造成的影响。因此对各种pivot选择法而言,最坏情况和最好情况都是相同的。我们从直觉上可以判断出最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候(设输入的表有n个元素)。下面我们暂时认为该猜测正确,在后文我们再详细证明该猜测。对于有n个元素的表L[p..r],由于函数Partition的计算时间为θ(n),所以快速排序在序坏情况下的复杂性有递归式如下:T(1)=θ(1),T(n)=T(n-1)+T(1)+θ(n) (1)用迭代法可以解出上式的解为T(n)=θ(n2)。这个最坏情况运行时间与插入排序是一样的。下面我们来证明这种每次划分过程产生的两个区间分别包含n-1个元素和1个元素的情况就是最坏情况。设T(n)是过程Quick_Sort作用于规模为n的输入上的最坏情况的时间,则T(n)=max(T(q)+T(n-q))+θ(n),其中1≤q≤n-1 (2)我们假设对于任何k<n,总有T(k)≤ck,其中c为常数;显然当k=1时是成立的。将归纳假设代入(2),得到:T(n)≤max(cq2+c(n-q)2)+θ(n)=c*max(q2+(n-q)2)+θ(n)因为在[1,n-1]上q2+(n-q)2关于q递减,所以当q=1时q2+(n-q)2有最大值n2-2(n-1)。于是有:T(n)≤cn2-2c(n-1)+θ(n)≤cn2只要c足够大,上面的第二个小于等于号就可以成立。于是对于所有的n都有T(n)≤cn。这样,排序算法的最坏情况运行时间为θ(n2),且最坏情况发生在每次划分过程产生的两个区间分别包含n-1个元素和1个元素的时候。时间复杂度为o(n2)。最好情况如果每次划分过程产生的区间大小都为n/2,则快速排序法运行就快得多了。这时有:T(n)=2T(n/2)+θ(n),T(1)=θ(1) (3)解得:T(n)=θ(nlogn)快速排序法最佳情况下执行过程的递归树如下图所示,图中lgn表示以10为底的对数,而本文中用logn表示以2为底的对数.由于快速排序法也是基于比较的排序法,其运行时间为Ω(nlogn),所以如果每次划分过程产生的区间大小都为n/2,则运行时间θ(nlogn)就是最好情况运行时间。但是,是否一定要每次平均划分才能达到最好情况呢。要理解这一点就必须理解对称性是如何在描述运行时间的递归式中反映的。我们假设每次划分过程都产生9:1的划分,乍一看该划分很不对称。我们可以得到递归式:T(n)=T(n/10)+T(9n/10)+θ(n),T(1)=θ(1) (4)请注意树的每一层都有代价n,直到在深度log10n=θ(logn)处达到边界条件,以后各层代价至多为n。递归于深度log10/9n=θ(logn)处结束。这样,快速排序的总时间代价为T(n)=θ(nlogn),从渐进意义上看就和划分是在中间进行的一样。事实上,即使是99:1的划分时间代价也为θ(nlogn)。其原因在于,任何一种按常数比例进行划分所产生的递归树的深度都为θ(nlogn),其中每一层的代价为O(n),因而不管常数比例是什么,总的运行时间都为θ(nlogn),只不过其中隐含的常数因子有所不同。(关于算法复杂性的渐进阶,请参阅算法的复杂性)平均情况快速排序的平均运行时间为θ(nlogn)。我们对平均情况下的性能作直觉上的分析。要想对快速排序的平均情况有个较为清楚的概念,我们就要对遇到的各种输入作个假设。通常都假设输入数据的所有排列都是等可能的。后文中我们要讨论这个假设。当我们对一个随机的输入数组应用快速排序时,要想在每一层上都有同样的划分是不太可能的。我们所能期望的是某些划分较对称,另一些则很不对称。事实上,我们可以证明,如果选择L[p..r]的第一个元素作为支点元素,Partition所产生的划分80%以上都比9:1更对称,而另20%则比9:1差,这里证明从略。平均情况下,Partition产生的划分中既有“好的”,又有“差的”。这时,与Partition执行过程对应的递归树中,好、差划分是随机地分布在树的各层上的。为与我们的直觉相一致,假设好、差划分交替出现在树的各层上,且好的划分是最佳情况划分,而差的划分是最坏情况下的划分。在根节点处,划分的代价为n,划分出来的两个子表的大小为n-1和1,即最坏情况。在根的下一层,大小为n-1的子表按最佳情况划分成大小各为(n-1)/2的两个子表。这儿我们假设含1个元素的子表的边界条件代价为1。在一个差的划分后接一个好的划分后,产生出三个子表,大小各为1,(n-1)/2和(n-1)/2,代价共为2n-1=θ(n)。一层划分就产生出大小为(n-1)/2+1和(n-1)/2的两个子表,代价为n=θ(n)。这种划分差不多是完全对称的,比9:1的划分要好。从直觉上看,差的划分的代价θ(n)可被吸收到好的划分的代价θ(n)中去,结果是一个好的划分。这样,当好、差划分交替分布划分都是好的一样:仍是θ(nlogn),但θ记号中隐含的常数因子要略大一些。关于平均情况的严格分析将在后文给出。在前文从直觉上探讨快速排序的平均性态过程中,我们已假定输入数据的所有排列都是等可能的。如果输入的分布满足这个假设时,快速排序是对足够大的输入的理想选择。但在实际应用中,这个假设就不会总是成立。解决的方法是,利用随机化策略,能够克服分布的等可能性假设所带来的问题。一种随机化策略是:与对输入的分布作“假设”不同的是对输入的分布作“规定”。具体地说,在排序输入的线性表前,对其元素加以随机排列,以强制的方法使每种排列满足等可能性。事实上,我们可以找到一个能在O(n)时间内对含n个元素的数组加以随机排列的算法。这种修改不改变算法的最坏情况运行时间,但它却使得运行时间能够独立于输入数据已排序的情况。另一种随机化策略是:利用前文介绍的选择支点元素pivot的第四种方法,即随机地在L[p..r]中选择一个元素作为支点元素pivot。实际应用中通常采用这种方法。快速排序的随机化版本有一个和其他随机化算法一样的有趣性质:没有一个特别的输入会导致最坏情况性态。这种算法的最坏情况性态是由随机数产生器决定的。你即使有意给出一个坏的输入也没用,因为随机化排列会使得输入数据的次序对算法不产生影响。只有在随机数产生器给出了一个很不巧的排列时,随机化算法的最坏情况性态才会出现。事实上可以证明几乎所有的排列都可使快速排序接近平均情况性态,只有非常少的几个排列才会导致算法的近最坏情况性态。一般来说,当一个算法可按多条路子做下去,但又很难决定哪一条保证是好的选择时,随机化策略是很有用的。如果大部分选择都是好的,则随机地选一个就行了。通常,一个算法在其执行过程中要做很多选择。如果一个好的选择的获益大于坏的选择的代价,那么随机地做一个选择就能得到一个很有效的算法。我们在前文已经了解到,对快速排序来说,一组好坏相杂的划分仍能产生很好的运行时间 。因此我们可以认为该算法的随机化版本也能具有较好的性态。
liujae 2019-12-02 01:18:45 0 浏览量 回答数 0

回答

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 [编辑本段]基本概念 * 若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function),按这个思想建立的表为散列表。 * 对不同的关键字可能得到同一散列地址,即key1≠key2,而f(key1)=f(key2),这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“象” 作为记录在表中的存储位置,这种表便称为散列表,这一映象过程称为散列造表或散列,所得的存储位置称散列地址。 * 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。 [编辑本段]常用的构造散列函数的方法 散列函数能使对一个数据序列的访问过程更加迅速有效,通过散列函数,数据元素将被更快地定位ǐ 1. 直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b,其中a和b为常数(这种散列函数叫做自身函数) 2. 数字分析法 3. 平方取中法 4. 折叠法 5. 随机数法 6. 除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模,也可在折叠、平方取中等运算之后取模。对p的选择很重要,一般取素数或m,若p选的不好,容易产生同义词。 [编辑本段]处理冲突的方法 1. 开放寻址法:Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列,可有下列三种取法: 1. di=1,2,3,…, m-1,称线性探测再散列; 2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列; 3. di=伪随机数序列,称伪随机探测再散列。 == 2. 再散列法:Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数,即在同义词产生地址冲突时计算另一个散列函数地址,直到冲突不再发生,这种方法不易产生“聚集”,但增加了计算时间。 3. 链地址法(拉链法) 4. 建立一个公共溢出区 [编辑本段]查找的性能分析 散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,依然用平均查找长度来衡量。 查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素: 1. 散列函数是否均匀; 2. 处理冲突的方法; 3. 散列表的装填因子。 散列表的装填因子定义为:α= 填入表中的元素个数 / 散列表的长度 α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。 实际上,散列表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。 了解了hash基本定义,就不能不提到一些著名的hash算法,MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法,而它们都是以 MD4 为基础设计的。那么他们都是什么意思呢? 这里简单说一下: (1) MD4 MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的,MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。 (2) MD5 MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组,其输出是4个32位字的级联,与 MD4 相同。MD5比MD4来得复杂,并且速度较之要慢一点,但更安全,在抗分析和抗差分方面表现更好 (3) SHA-1 及其他 SHA1是由NIST NSA设计为同DSA一起使用的,它对长度小于264的输入,产生长度为160bit的散列值,因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。 那么这些Hash算法到底有什么用呢? Hash算法在信息安全方面的应用主要体现在以下的3个方面: (1) 文件校验 我们比较熟悉的校验算法有奇偶校验和CRC校验,这2种校验并没有抗数据篡改的能力,它们一定程度上能检测并纠正数据传输中的信道误码,但却不能防止对数据的恶意破坏。 MD5 Hash算法的"数字指纹"特性,使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法,不少Unix系统有提供计算md5 checksum的命令。 (2) 数字签名 Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢,所以在数字签名协议中,单向散列函数扮演了一个重要的角色。 对 Hash 值,又称"数字摘要"进行数字签名,在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。 (3) 鉴权协议 如下的鉴权协议又被称作挑战--认证模式:在传输信道是可被侦听,但不可被篡改的情况下,这是一种简单而安全的方法。 MD5、SHA1的破解 2004年8月17日,在美国加州圣芭芭拉召开的国际密码大会上,山东大学王小云教授在国际会议上首次宣布了她及她的研究小组近年来的研究成果——对MD5、HAVAL-128、MD4和RIPEMD等四个著名密码算法的破译结果。 次年二月宣布破解SHA-1密码。 [编辑本段]实际应用 以上就是一些关于hash以及其相关的一些基本预备知识。那么在emule里面他具体起到什么作用呢? 大家都知道emule是基于P2P (Peer-to-peer的缩写,指的是点对点的意思的软件), 它采用了"多源文件传输协议”(MFTP,the Multisource FileTransfer Protocol)。在协议中,定义了一系列传输、压缩和打包还有积分的标准,emule 对于每个文件都有md5-hash的算法设置,这使得该文件独一无二,并且在整个网络上都可以追踪得到。 什么是文件的hash值呢? MD5-Hash-文件的数字文摘通过Hash函数计算得到。不管文件长度如何,它的Hash函数计算结果是一个固定长度的数字。与加密算法不同,这一个Hash算法是一个不可逆的单向函数。采用安全性高的Hash算法,如MD5、SHA时,两个不同的文件几乎不可能得到相同的Hash结果。因此,一旦文件被修改,就可检测出来。 当我们的文件放到emule里面进行共享发布的时候,emule会根据hash算法自动生成这个文件的hash值,他就是这个文件唯一的身份标志,它包含了这个文件的基本信息,然后把它提交到所连接的服务器。当有他人想对这个文件提出下载请求的时候, 这个hash值可以让他人知道他正在下载的文件是不是就是他所想要的。尤其是在文件的其他属性被更改之后(如名称等)这个值就更显得重要。而且服务器还提供了,这个文件当前所在的用户的地址,端口等信息,这样emule就知道到哪里去下载了。 一般来讲我们要搜索一个文件,emule在得到了这个信息后,会向被添加的服务器发出请求,要求得到有相同hash值的文件。而服务器则返回持有这个文件的用户信息。这样我们的客户端就可以直接的和拥有那个文件的用户沟通,看看是不是可以从他那里下载所需的文件。 对于emule中文件的hash值是固定的,也是唯一的,它就相当于这个文件的信息摘要,无论这个文件在谁的机器上,他的hash值都是不变的,无论过了多长时间,这个值始终如一,当我们在进行文件的下载上传过程中,emule都是通过这个值来确定文件。 那么什么是userhash呢? 道理同上,当我们在第一次使用emule的时候,emule会自动生成一个值,这个值也是唯一的,它是我们在emule世界里面的标志,只要你不卸载,不删除config,你的userhash值也就永远不变,积分制度就是通过这个值在起作用,emule里面的积分保存,身份识别,都是使用这个值,而和你的id和你的用户名无关,你随便怎么改这些东西,你的userhash值都是不变的,这也充分保证了公平性。其实他也是一个信息摘要,只不过保存的不是文件信息,而是我们每个人的信息。 那么什么是hash文件呢? 我们经常在emule日志里面看到,emule正在hash文件,这里就是利用了hash算法的文件校验性这个功能了,文章前面已经说了一些这些功能,其实这部分是一个非常复杂的过程,目前在ftp,bt等软件里面都是用的这个基本原理,emule里面是采用文件分块传输,这样传输的每一块都要进行对比校验,如果错误则要进行重新下载,这期间这些相关信息写入met文件,直到整个任务完成,这个时候part文件进行重新命名,然后使用move命令,把它传送到incoming文件里面,然后met文件自动删除,所以我们有的时候会遇到hash文件失败,就是指的是met里面的信息出了错误不能够和part文件匹配,另外有的时候开机也要疯狂hash,有两种情况一种是你在第一次使用,这个时候要hash提取所有文件信息,还有一种情况就是上一次你非法关机,那么这个时候就是要进行排错校验了。 关于hash的算法研究,一直是信息科学里面的一个前沿,尤其在网络技术普及的今天,他的重要性越来越突出,其实我们每天在网上进行的信息交流安全验证,我们在使用的操作系统密钥原理,里面都有它的身影,特别对于那些研究信息安全有兴趣的朋友,这更是一个打开信息世界的钥匙,他在hack世界里面也是一个研究的焦点。 一般的线性表、树中,记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系,在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上,查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。因而查找时,只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录,则必定在f(K)的存储位置上,由此不需要进行比较便可直接取得所查记录。在此,称这个对应关系f为哈希函数,按这个思想建立的表为哈希表(又称为杂凑法或散列表)。 哈希表不可避免冲突(collision)现象:对不同的关键字可能得到同一哈希地址 即key1≠key2,而hash(key1)=hash(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。 因此,在建造哈希表时不仅要设定一个好的哈希函数,而且要设定一种处理冲突的方法。可如下描述哈希表:根据设定的哈希函数H(key)和所选中的处理冲突的方法,将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置,这种表被称为哈希表。 对于动态查找表而言,1) 表长不确定;2)在设计查找表时,只知道关键字所属范围,而不知道确切的关键字。因此,一般情况需建立一个函数关系,以f(key)作为关键字为key的录在表中的位置,通常称这个函数f(key)为哈希函数。(注意:这个函数并不一定是数学函数) 哈希函数是一个映象,即:将关键字的集合映射到某个地址集合上,它的设置很灵活,只要这个地址集合的大小不超出允许范围即可。 现实中哈希函数是需要构造的,并且构造的好才能使用的好。 用途:加密,解决冲突问题。。。。 用途很广,比特精灵中就使用了哈希函数,你可 以自己看看。 具体可以学习一下数据结构和算法的书。 [编辑本段]字符串哈希函数 (著名的ELFhash算法) int ELFhash(char *key) return h%MOD; }
晚来风急 2019-12-02 01:22:24 0 浏览量 回答数 0

问题

备战大厂每日挑战算法,坚持打卡更有社区定制周边奖品等你赢!

算法工程师,一个听起来非常高大上的职业~ 不但轻轻松松月入过万,更是进入大厂必考的题目。如何通过大厂算法岗面试?如何轻轻松松拿到高薪?如何成为算法技术大牛? 今天开发者...
被纵养的懒猫 2020-04-07 11:41:45 5309 浏览量 回答数 5

回答

流处理,听起来很高大上啊,其实就是分块读取。有这么一些情况,有一个很大的几个G的文件,没办法一次处理,那么就分批次处理,一次处理1百万行,接着处理下1百万行,慢慢地总是能处理完的。 使用类似迭代器的方式 data=pd.read_csv(file, chunksize=1000000)for sub_df in data: print('do something in sub_df here') 1234索引 Series和DataFrame都是有索引的,索引的好处是快速定位,在涉及到两个Series或DataFrame时可以根据索引自动对齐,比如日期自动对齐,这样可以省去很多事。 缺失值 pd.isnull(obj)obj.isnull()12将字典转成数据框,并赋予列名,索引 DataFrame(data, columns=['col1','col2','col3'...], index = ['i1','i2','i3'...]) 12查看列名 DataFrame.columns 查看索引 DataFrame.index 重建索引 obj.reindex(['a','b','c','d','e'...], fill_value=0] 按给出的索引顺序重新排序,而不是替换索引。如果索引没有值,就用0填充 就地修改索引 data.index=data.index.map(str.upper)12345列顺序重排(也是重建索引) DataFrame.reindex[columns=['col1','col2','col3'...])` 也可以同时重建index和columns DataFrame.reindex[index=['a','b','c'...],columns=['col1','col2','col3'...])12345重建索引的快捷键 DataFrame.ix[['a','b','c'...],['col1','col2','col3'...]]1重命名轴索引 data.rename(index=str.title,columns=str.upper) 修改某个索引和列名,可以通过传入字典 data.rename(index={'old_index':'new_index'}, columns={'old_col':'new_col'}) 12345查看某一列 DataFrame['state'] 或 DataFrame.state1查看某一行 需要用到索引 DataFrame.ix['index_name']1添加或删除一列 DataFrame['new_col_name'] = 'char_or_number' 删除行 DataFrame.drop(['index1','index2'...]) 删除列 DataFrame.drop(['col1','col2'...],axis=1) 或 del DataFrame['col1']1234567DataFrame选择子集 类型 说明obj[val] 选择一列或多列obj.ix[val] 选择一行或多行obj.ix[:,val] 选择一列或多列obj.ix[val1,val2] 同时选择行和列reindx 对行和列重新索引icol,irow 根据整数位置选取单列或单行get_value,set_value 根据行标签和列标签选择单个值针对series obj[['a','b','c'...]]obj['b':'e']=512针对dataframe 选择多列 dataframe[['col1','col2'...]] 选择多行 dataframe[m:n] 条件筛选 dataframe[dataframe['col3'>5]] 选择子集 dataframe.ix[0:3,0:5]1234567891011dataframe和series的运算 会根据 index 和 columns 自动对齐然后进行运算,很方便啊 方法 说明add 加法sub 减法div 除法mul 乘法 没有数据的地方用0填充空值 df1.add(df2,fill_value=0) dataframe 与 series 的运算 dataframe - series 规则是: -------- v 指定轴方向 dataframe.sub(series,axis=0)规则是:-------- --- | | | | ----->| | | | | | | | | | | | -------- ---12345678910111213141516171819202122apply函数 f=lambda x:x.max()-x.min() 默认对每一列应用 dataframe.apply(f) 如果需要对每一行分组应用 dataframe.apply(f,axis=1)1234567排序和排名 默认根据index排序,axis = 1 则根据columns排序 dataframe.sort_index(axis=0, ascending=False) 根据值排序 dataframe.sort_index(by=['col1','col2'...]) 排名,给出的是rank值 series.rank(ascending=False) 如果出现重复值,则取平均秩次 在行或列上面的排名 dataframe.rank(axis=0)12345678910111213描述性统计 方法 说明count 计数describe 给出各列的常用统计量min,max 最大最小值argmin,argmax 最大最小值的索引位置(整数)idxmin,idxmax 最大最小值的索引值quantile 计算样本分位数sum,mean 对列求和,均值mediam 中位数mad 根据平均值计算平均绝对离差var,std 方差,标准差skew 偏度(三阶矩)Kurt 峰度(四阶矩)cumsum 累积和Cummins,cummax 累计组大致和累计最小值cumprod 累计积diff 一阶差分pct_change 计算百分数变化唯一值,值计数,成员资格 obj.unique()obj.value_count()obj.isin(['b','c'])123处理缺失值 过滤缺失值 只要有缺失值就丢弃这一行 dataframe.dropna() 要求全部为缺失才丢弃这一行 dataframe.dropna(how='all') 根据列来判断 dataframe.dropna(how='all',axis=1) 填充缺失值 1.用0填充 df.fillna(0) 2.不同的列用不同的值填充 df.fillna({1:0.5, 3:-1}) 3.用均值填充 df.fillna(df.mean()) 此时axis参数同前面, 123456789101112131415161718192021将列转成行索引 df.set_index(['col1','col2'...])1数据清洗,重塑 合并数据集 取 df1,df2 都有的部分,丢弃没有的 默认是inner的连接方式 pd.merge(df1,df2, how='inner') 如果df1,df2的连接字段名不同,则需要特别指定 pd.merge(df1,df2,left_on='l_key',right_on='r_key') 其他的连接方式有 left,right, outer等。 如果dataframe是多重索引,根据多个键进行合并 pd.merge(left, right, on=['key1','key2'],how = 'outer') 合并后如果有重复的列名,需要添加后缀 pd.merge(left, right, on='key1', suffixes=('_left','_right'))1234567891011121314索引上的合并 针对dataframe中的连接键不是列名,而是索引名的情况。 pd.merge(left, right, left_on = 'col_key', right_index=True) 即左边的key是列名,右边的key是index。 多重索引 pd.merge(left, right, left_on=['key1','key2'], right_index=True)123456dataframe的join方法 实现按索引合并。 其实这个join方法和数据库的join函数是以一样的理解 left.join(right, how='outer') 一次合并多个数据框 left.join([right1,right2],how='outer')123456轴向连接(更常用) 连接:concatenation 绑定:binding 堆叠:stacking列上的连接 np.concatenation([df1,df2],axis=1) #np包pd.concat([df1,df2], axis=1) #pd包 和R语言中的 cbind 是一样的 如果axis=0,则和 rbind 是一样的 索引对齐,没有的就为空 join='inner' 得到交集 pd.concat([df1,df2], axis=1, join='innner') keys 参数,还没看明白 ignore_index=True,如果只是简单的合并拼接而不考虑索引问题。 pd.concat([df1,df2],ignore_index=True)123456789101112131415合并重复数据 针对可能有索引全部或者部分重叠的两个数据集 填充因为合并时索引赵成的缺失值 where函数 where即if-else函数 np.where(isnull(a),b,a)12combine_first方法 如果a中值为空,就用b中的值填补 a[:-2].combine_first(b[2:]) combine_first函数即对数据打补丁,用df2的数据填充df1中的缺失值 df1.combine_first(df2)12345重塑层次化索引 stact:将数据转为长格式,即列旋转为行 unstack:转为宽格式,即将行旋转为列result=data.stack()result.unstack()12长格式转为宽格式 pivoted = data.pivot('date','item','value') 前两个参数分别是行和列的索引名,最后一个参数则是用来填充dataframe的数据列的列名。如果忽略最后一个参数,得到的dataframe会带有层次化的列。 123透视表 table = df.pivot_table(values=["Price","Quantity"], index=["Manager","Rep"], aggfunc=[np.sum,np.mean], margins=True)) values:需要对哪些字段应用函数 index:透视表的行索引(row) columns:透视表的列索引(column) aggfunc:应用什么函数 fill_value:空值填充 margins:添加汇总项 然后可以对透视表进行筛选 table.query('Manager == ["Debra Henley"]')table.query('Status == ["pending","won"]')123456789101112131415移除重复数据 判断是否重复 data.duplicated()` 移除重复数据 data.drop_duplicated() 对指定列判断是否存在重复值,然后删除重复数据 data.drop_duplicated(['key1'])123456789交叉表 是一种用于计算分组频率的特殊透视表. 注意,只对离散型的,分类型的,字符型的有用,连续型数据是不能计算频率这种东西的。 pd.crosstab(df.col1, df.col2, margins=True)1类似vlookup函数 利用函数或映射进行数据转换 1.首先定义一个字典 meat_to_animal={ 'bacon':'pig', 'pulled pork':'pig', 'honey ham':'cow' } 2.对某一列应用一个函数,或者字典,顺便根据这一列的结果创建新列 data['new_col']=data['food'].map(str.lower).map(meat_to_animal)123456789替换值 data.replace(-999,np.na) 多个值的替换 data.replace([-999,-1000],np.na) 对应替换 data.replace([-999,-1000],[np.na,0]) 对应替换也可以传入一个字典 data.replace({-999:np.na,-1000:0})123456789离散化 定义分割点 简单分割(等宽分箱) s=pd.Series(range(100))pd.cut(s, bins=10, labels=range(10)) bins=[20,40,60,80,100] 切割 cats = pd.cut(series,bins) 查看标签 cats.labels 查看水平(因子) cats.levels 区间计数 pd.value_count(cats) 自定义分区的标签 group_names=['youth','youngAdult','MiddleAge','Senior']pd.cut(ages,bins,labels=group_names)1234567891011121314151617181920212223分位数分割 data=np.random.randn(1000)pd.qcut(data,4) #四分位数 自定义分位数,包含端点 pd.qcut(data,[0,0.3,0.5,0.9,1])12345异常值 查看各个统计量 data.describe() 对某一列 col=data[3]col[np.abs(col)>3] 选出全部含有“超过3或-3的值的行 data[(np.abs(data)>3).any(1)] 异常值替换 data[np.abs(data)>3]=np.sign(data)*312345678910111213抽样 随机抽取k行 df.take(np.random.permutation(len(df))[:k]) 随机抽取k行,但是k可能大于df的行数 可以理解为过抽样了 df.take(np.random.randint(0,len(df),size=k))1234567数据摊平处理 相当于将类别属性转成因子类型,比如是否有车,这个字段有3个不同的值,有,没有,过段时间买,那么将会被编码成3个字段,有车,没车,过段时间买车,每个字段用0-1二值填充变成数值型。 对摊平的数据列增加前缀 dummies = pd.get_dummies(df['key'],prefix='key') 将摊平产生的数据列拼接回去 df[['data1']].join(dummies)12345字符串操作 拆分 strings.split(',') 根据正则表达式切分 re.split('s+',strings) 连接 'a'+'b'+'c'...或者'+'.join(series) 判断是否存在 's' in strings`strings.find('s') 计数 strings.count(',') 替换 strings.replace('old','new') 去除空白字符 s.strip()12345678910111213141516171819202122232425正则表达式 正则表达式需要先编译匹配模式,然后才去匹配查找,这样能节省大量的CPU时间。 re.complie:编译 findall:匹配所有 search:只返回第一个匹配项的起始和结束地址 match:值匹配字符串的首部 sub:匹配替换,如果找到就替换 原始字符串 strings = 'sdf@153.com,dste@qq.com,sor@gmail.com' 编译匹配模式,IGNORECASE可以在使用的时候对大小写不敏感 pattern = r'[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}'regex = re.compile(pattern,flags=re.IGNORECASE) 匹配所有 regex.findall(strings) 使用search m = regex.search(strings) #获取匹配的地址strings[m.start():m.end()] 匹配替换 regex.sub('new_string', strings)12345678910111213141516根据模式再切分 将模式切分,也就是将匹配到的进一步切分,通过pattern中的括号实现. pattern = r'([A-Z0-9._%+-]+)@([A-Z0-9.-]+)\.([A-Z]{2,4})'regex = re.compile(pattern)regex.findall(strings) 如果使用match m=regex.match(string)m.groups() 效果是这样的 suzyu123@163.com --> [(suzyu123, 163, com)] 获取 list-tuple 其中的某一列 matches.get(i)12345678910111213分组聚合,计算 group_by技术 根据多个索引分组,然后计算均值 means = df['data1'].groupby([df['index1'],df['index2']).mean() 展开成透视表格式 means.unstack()12345分组后价将片段做成一个字典 pieces = dict(list(df.groupby('index1'))) pieces['b']123groupby默认是对列(axis=0)分组,也可以在行(axis=1)上分组 语法糖,groupby的快捷函数 df.groupby('index1')['col_names']df.groupby('index1')[['col_names']] 是下面代码的语法糖 df['col_names'].groupby(df['index1']) df.groupby(['index1','index2'])['col_names'].mean()1234567通过字典或series进行分组 people = DataFrame(np.random.randn(5, 5), columns=['a', 'b', 'c', 'd', 'e'], index=['Joe', 'Steve', 'Wes', 'Jim','Travis']) 选择部分设为na people.ix[2:3,['b','c']]=np.na mapping = {'a': 'red', 'b': 'red', 'c': 'blue', 'd': 'blue', 'e': 'red', 'f' : 'orange'} people.groupby(mapping,axis=1).sum()1234567891011通过函数进行分组 根据索引的长度进行分组 people.groupby(len).sum()12数据聚合 使用自定义函数 对所有的数据列使用自定义函数 df.groupby('index1').agg(myfunc) 使用系统函数 df.groupby('index1')['data1']describe()12345根据列分组应用多个函数 分组 grouped = df.groupby(['col1','col2']) 选择多列,对每一列应用多个函数 grouped['data1','data2'...].agg(['mean','std','myfunc'])12345对不同列使用不同的函数 grouped = df.groupby(['col1','col2']) 传入一个字典,对不同的列使用不同的函数 不同的列可以应用不同数量的函数 grouped.agg({'data1':['min','max','mean','std'], 'data2':'sum'}) 123456分组计算后重命名列名 grouped = df.groupby(['col1','col2']) grouped.agg({'data1':[('min','max','mean','std'),('d_min','d_max','d_mean','d_std')], 'data2':'sum'}) 1234返回的聚合数据不要索引 df.groupby(['sex','smoker'], as_index=False).mean()1分组计算结果添加前缀 对计算后的列名添加前缀 df.groupby('index1').mean().add_prefix('mean_')12将分组计算后的值替换到原数据框 将函数应用到各分组,再将分组计算的结果代换原数据框的值 也可以使用自定义函数 df.groupby(['index1','index2'...]).transform(np.mean)123更一般化的apply函数 df.groupby(['col1','col2'...]).apply(myfunc) df.groupby(['col1','col2'...]).apply(['min','max','mean','std'])123禁用分组键 分组键会跟原始对象的索引共同构成结果对象中的层次化索引 df.groupby('smoker', group_keys=False).apply(mean)1分组索引转成df的列 某些情况下,groupby的as_index=False参数并没有什么用,得到的还是一个series,这种情况一般是尽管分组了,但是计算需要涉及几列,最后得到的还是series,series的index是层次化索引。这里将series转成dataframe,series的层次化索引转成dataframe的列。 def fmean(df): """需要用两列才能计算最后的结果""" skus=len(df['sku'].unique()) sums=df['salecount'].sum() return sums/skus 尽管禁用分组键,得到的还是series salemean=data.groupby(by=['season','syear','smonth'],as_index=False).apply(fmean) 将series转成dataframe,顺便设置索引 sub_df = pd.DataFrame(salemean.index.tolist(),columns=salemean.index.names,index=salemean.index) 将groupby的结果和sub_df合并 sub_df['salemean']=salemean12345678910111213桶分析与分位数 对数据切分段,然后对每一分段应用函数 frame = DataFrame({'col1':np.random.randn(1000), 'col2':np.random.randn(1000)}) 数据分段,创建分段用的因子 返回每一元素是属于哪一分割区间 factor = pd.cut(frame.col1, 4) 分组计算,然后转成数据框形式 grouped = frame.col2.groupby(factor)grouped.apply(myfunc).unstack()12345678910用分组的均值填充缺失值 自定义函数 fill_mean= lambda x:x.fillna(x.mean()) 分组填充 df.groupby(group_key).apply(fill_mean)12345分组后不同的数据替换不同的值 定义字典 fill_value = {'east':0.5, 'west':-1} 定义函数 fill_func = lambda x:x.fillna(fill_value(x.name)) 分组填充 df.groupby(['index1','index2'...]).apply(fill_func)12345678sql操作 有时候觉得pandas很方便,但是有时候却很麻烦,不如SQL方便。因此pandas中也有一些例子,用pandas实现SQL的功能,简单的就不说了,下面说些复杂点的操作。 之所以说这个复杂的语句,是因为不想将这些数据操作分写在不同的语句中,而是从头到尾连续编码实现一个功能。 SQL复杂操作用到的主要函数是assign,简单说其实和join的功能是一样的,根据df1,df2的索引值来将df2拼接到df1上。 两个函数是query,也听方便的。 有一批销量数据,筛选出那些有2个月以上的销量产品的数据,说白了就是剔除那些新上市产品的数据 方法是先统计每个产品的数据量,然后选出那些数据量>2的产品,再在数据表中选择这些产品 sku smonth a 1 a 2 a 3 a 4 b 5 b 6 b 7 b 8 c 9 c 10 按sku分组,统计smonth的次数,拼接到salecount中,然后查询cnt>2的 salecount.assign(cnt=salecount.groupby(['sku'])['smonth'].count()).query('cnt>2')
xuning715 2019-12-02 01:10:39 0 浏览量 回答数 0

回答

在开始谈我对架构本质的理解之前,先谈谈对今天技术沙龙主题的个人见解,千万级规模的网站感觉数量级是非常大的,对这个数量级我们战略上 要重 视 它 , 战术上又 要 藐 视 它。先举个例子感受一下千万级到底是什么数量级?现在很流行的优步(Uber),从媒体公布的信息看,它每天接单量平均在百万左右, 假如每天有10个小时的服务时间,平均QPS只有30左右。对于一个后台服务器,单机的平均QPS可以到达800-1000,单独看写的业务量很简单 。为什么我们又不能说轻视它?第一,我们看它的数据存储,每天一百万的话,一年数据量的规模是多少?其次,刚才说的订单量,每一个订单要推送给附近的司机、司机要并发抢单,后面业务场景的访问量往往是前者的上百倍,轻松就超过上亿级别了。 今天我想从架构的本质谈起之后,希望大家理解在做一些建构设计的时候,它的出发点以及它解决的问题是什么。 架构,刚开始的解释是我从知乎上看到的。什么是架构?有人讲, 说架构并不是一 个很 悬 乎的 东西 , 实际 上就是一个架子 , 放一些 业务 和算法,跟我们的生活中的晾衣架很像。更抽象一点,说架构其 实 是 对 我 们 重复性业务 的抽象和我 们 未来 业务 拓展的前瞻,强调过去的经验和你对整个行业的预见。 我们要想做一个架构的话需要哪些能力?我觉得最重要的是架构师一个最重要的能力就是你要有 战 略分解能力。这个怎么来看呢: 第一,你必须要有抽象的能力,抽象的能力最基本就是去重,去重在整个架构中体现在方方面面,从定义一个函数,到定义一个类,到提供的一个服务,以及模板,背后都是要去重提高可复用率。 第二, 分类能力。做软件需要做对象的解耦,要定义对象的属性和方法,做分布式系统的时候要做服务的拆分和模块化,要定义服务的接口和规范。 第三, 算法(性能),它的价值体现在提升系统的性能,所有性能的提升,最终都会落到CPU,内存,IO和网络这4大块上。 这一页PPT举了一些例子来更深入的理解常见技术背后的架构理念。 第一个例子,在分布式系统我们会做 MySQL分 库 分表,我们要从不同的库和表中读取数据,这样的抽象最直观就是使用模板,因为绝大多数SQL语义是相同的,除了路由到哪个库哪个表,如果不使用Proxy中间件,模板就是性价比最高的方法。 第二看一下加速网络的CDN,它是做速度方面的性能提升,刚才我们也提到从CPU、内存、IO、网络四个方面来考虑,CDN本质上一个是做网络智能调度优化,另一个是多级缓存优化。 第三个看一下服务化,刚才已经提到了,各个大网站转型过程中一定会做服务化,其实它就是做抽象和做服务的拆分。第四个看一下消息队列,本质上还是做分类,只不过不是两个边际清晰的类,而是把两个边际不清晰的子系统通过队列解构并且异步化。新浪微博整体架构是什么样的 接下我们看一下微博整体架构,到一定量级的系统整个架构都会变成三层,客户端包括WEB、安卓和IOS,这里就不说了。接着还都会有一个接口层, 有三个主要作用: 第一个作用,要做 安全隔离,因为前端节点都是直接和用户交互,需要防范各种恶意攻击; 第二个还充当着一个 流量控制的作用,大家知道,在2014年春节的时候,微信红包,每分钟8亿多次的请求,其实真正到它后台的请求量,只有十万左右的数量级(这里的数据可能不准),剩余的流量在接口层就被挡住了; 第三,我们看对 PC 端和移 动 端的需求不一样的,所以我们可以进行拆分。接口层之后是后台,可以看到微博后台有三大块: 一个是 平台服 务, 第二, 搜索, 第三, 大数据。到了后台的各种服务其实都是处理的数据。 像平台的业务部门,做的就是 数据存储和读 取,对搜索来说做的是 数据的 检 索,对大数据来说是做的数据的 挖掘。微博其实和淘宝是很类似 微博其实和淘宝是很类似的。一般来说,第一代架构,基本上能支撑到用户到 百万 级别,到第二代架构基本能支撑到 千万 级别都没什么问题,当业务规模到 亿级别时,需要第三代的架构。 从 LAMP 的架构到面向服 务 的架构,有几个地方是非常难的,首先不可能在第一代基础上通过简单的修修补补满足用户量快速增长的,同时线上业务又不能停, 这是我们常说的 在 飞 机上 换 引擎的 问题。前两天我有一个朋友问我,说他在内部推行服务化的时候,把一个模块服务化做完了,其他部门就是不接。我建议在做服务化的时候,首先更多是偏向业务的梳理,同时要找准一个很好的切入点,既有架构和服务化上的提升,业务方也要有收益,比如提升性能或者降低维护成本同时升级过程要平滑,建议开始从原子化服务切入,比如基础的用户服务, 基础的短消息服务,基础的推送服务。 第二,就是可 以做无状 态 服 务,后面会详细讲,还有数据量大了后需要做数据Sharding,后面会将。 第三代 架构 要解决的 问题,就是用户量和业务趋于稳步增加(相对爆发期的指数级增长),更多考虑技术框架的稳定性, 提升系统整体的性能,降低成本,还有对整个系统监控的完善和升级。 大型网站的系统架构是如何演变的 我们通过通过数据看一下它的挑战,PV是在10亿级别,QPS在百万,数据量在千亿级别。我们可用性,就是SLA要求4个9,接口响应最多不能超过150毫秒,线上所有的故障必须得在5分钟内解决完。如果说5分钟没处理呢?那会影响你年终的绩效考核。2015年微博DAU已经过亿。我们系统有上百个微服务,每周会有两次的常规上线和不限次数的紧急上线。我们的挑战都一样,就是数据量,bigger and bigger,用户体验是faster and faster,业务是more and more。互联网业务更多是产品体验驱动, 技 术 在 产 品 体验上最有效的贡献 , 就是你的性能 越来越好 。 每次降低加载一个页面的时间,都可以间接的降低这个页面上用户的流失率。微博的技术挑战和正交分解法解析架构 下面看一下 第三代的 架构 图 以及 我 们 怎么用正交分解法 阐 述。 我们可以看到我们从两个维度,横轴和纵轴可以看到。 一个 维 度 是 水平的 分层 拆分,第二从垂直的维度会做拆分。水平的维度从接口层、到服务层到数据存储层。垂直怎么拆分,会用业务架构、技术架构、监控平台、服务治理等等来处理。我相信到第二代的时候很多架构已经有了业务架构和技术架构的拆分。我们看一下, 接口层有feed、用户关系、通讯接口;服务层,SOA里有基层服务、原子服务和组合服务,在微博我们只有原子服务和组合服务。原子服务不依赖于任何其他服务,组合服务由几个原子服务和自己的业务逻辑构建而成 ,资源层负责海量数据的存储(后面例子会详细讲)。技 术框架解决 独立于 业务 的海量高并发场景下的技术难题,由众多的技术组件共同构建而成 。在接口层,微博使用JERSY框架,帮助你做参数的解析,参数的验证,序列化和反序列化;资源层,主要是缓存、DB相关的各类组件,比如Cache组件和对象库组件。监 控平台和服 务 治理 , 完成系统服务的像素级监控,对分布式系统做提前诊断、预警以及治理。包含了SLA规则的制定、服务监控、服务调用链监控、流量监控、错误异常监控、线上灰度发布上线系统、线上扩容缩容调度系统等。 下面我们讲一下常见的设计原则。 第一个,首先是系统架构三个利器: 一个, 我 们 RPC 服 务组 件 (这里不讲了), 第二个,我们 消息中 间 件 。消息中间件起的作用:可以把两个模块之间的交互异步化,其次可以把不均匀请求流量输出为匀速的输出流量,所以说消息中间件 异步化 解耦 和流量削峰的利器。 第三个是配置管理,它是 代码级灰度发布以及 保障系统降级的利器。 第二个 , 无状态 , 接口 层 最重要的就是无状 态。我们在电商网站购物,在这个过程中很多情况下是有状态的,比如我浏览了哪些商品,为什么大家又常说接口层是无状态的,其实我们把状态从接口层剥离到了数据层。像用户在电商网站购物,选了几件商品,到了哪一步,接口无状态后,状态要么放在缓存中,要么放在数据库中, 其 实 它并不是没有状 态 , 只是在 这 个 过 程中我 们 要把一些有状 态 的 东 西抽离出来 到了数据层。 第三个, 数据 层 比服 务层 更需要 设计,这是一条非常重要的经验。对于服务层来说,可以拿PHP写,明天你可以拿JAVA来写,但是如果你的数据结构开始设计不合理,将来数据结构的改变会花费你数倍的代价,老的数据格式向新的数据格式迁移会让你痛不欲生,既有工作量上的,又有数据迁移跨越的时间周期,有一些甚至需要半年以上。 第四,物理结构与逻辑结构的映射,上一张图看到两个维度切成十二个区间,每个区间代表一个技术领域,这个可以看做我们的逻辑结构。另外,不论后台还是应用层的开发团队,一般都会分几个垂直的业务组加上一个基础技术架构组,这就是从物理组织架构到逻辑的技术架构的完美的映射,精细化团队分工,有利于提高沟通协作的效率 。 第五, www .sanhao.com 的访问过程,我们这个架构图里没有涉及到的,举个例子,比如当你在浏览器输入www.sanhao网址的时候,这个请求在接口层之前发生了什么?首先会查看你本机DNS以及DNS服务,查找域名对应的IP地址,然后发送HTTP请求过去。这个请求首先会到前端的VIP地址(公网服务IP地址),VIP之后还要经过负载均衡器(Nginx服务器),之后才到你的应用接口层。在接口层之前发生了这么多事,可能有用户报一个问题的时候,你通过在接口层查日志根本发现不了问题,原因就是问题可能发生在到达接口层之前了。 第六,我们说分布式系统,它最终的瓶颈会落在哪里呢?前端时间有一个网友跟我讨论的时候,说他们的系统遇到了一个瓶颈, 查遍了CPU,内存,网络,存储,都没有问题。我说你再查一遍,因为最终你不论用上千台服务器还是上万台服务器,最终系统出瓶颈的一定会落在某一台机(可能是叶子节点也可能是核心的节点),一定落在CPU、内存、存储和网络上,最后查出来问题出在一台服务器的网卡带宽上。微博多级双机房缓存架构 接下来我们看一下微博的Feed多级缓存。我们做业务的时候,经常很少做业务分析,技术大会上的分享又都偏向技术架构。其实大家更多的日常工作是需要花费更多时间在业务优化上。这张图是统计微博的信息流前几页的访问比例,像前三页占了97%,在做缓存设计的时候,我们最多只存最近的M条数据。 这里强调的就是做系统设计 要基于用 户 的 场 景 , 越细致越好 。举了一个例子,大家都会用电商,电商在双十一会做全国范围内的活动,他们做设计的时候也会考虑场景的,一个就是购物车,我曾经跟相关开发讨论过,购物车是在双十一之前用户的访问量非常大,就是不停地往里加商品。在真正到双十一那天他不会往购物车加东西了,但是他会频繁的浏览购物车。针对这个场景,活动之前重点设计优化购物车的写场景, 活动开始后优化购物车的读场景。 你看到的微博是由哪些部分聚合而成的呢?最右边的是Feed,就是微博所有关注的人,他们的微博所组成的。微博我们会按照时间顺序把所有关注人的顺序做一个排序。随着业务的发展,除了跟时间序相关的微博还有非时间序的微博,就是会有广告的要求,增加一些广告,还有粉丝头条,就是拿钱买的,热门微博,都会插在其中。分发控制,就是说和一些推荐相关的,我推荐一些相关的好友的微博,我推荐一些你可能没有读过的微博,我推荐一些其他类型的微博。 当然对非时序的微博和分发控制微博,实际会起多个并行的程序来读取,最后同步做统一的聚合。这里稍微分享一下, 从SNS社交领域来看,国内现在做的比较好的三个信息流: 微博 是 基于弱关系的媒体信息流 ; 朋友圈是基于 强 关系的信息流 ; 另外一个做的比 较 好的就是今日 头 条 , 它并不是基于关系来构建信息流 , 而是基于 兴趣和相关性的个性化推荐 信息流 。 信息流的聚合,体现在很多很多的产品之中,除了SNS,电商里也有信息流的聚合的影子。比如搜索一个商品后出来的列表页,它的信息流基本由几部分组成:第一,打广告的;第二个,做一些推荐,热门的商品,其次,才是关键字相关的搜索结果。 信息流 开始的时候 很 简单 , 但是到后期会 发现 , 你的 这 个流 如何做控制分发 , 非常复杂, 微博在最近一两年一直在做 这样 的工作。刚才我们是从业务上分析,那么技术上怎么解决高并发,高性能的问题?微博访问量很大的时候,底层存储是用MySQL数据库,当然也会有其他的。对于查询请求量大的时候,大家知道一定有缓存,可以复用可重用的计算结果。可以看到,发一条微博,我有很多粉丝,他们都会来看我发的内容,所以 微博是最适合使用 缓 存 的系统,微博的读写比例基本在几十比一。微博使用了 双 层缓 存,上面是L1,每个L1上都是一组(包含4-6台机器),左边的框相当于一个机房,右边又是一个机房。在这个系统中L1缓存所起的作用是什么? 首先,L1 缓 存增加整个系 统 的 QPS, 其次 以低成本灵活扩容的方式 增加 系统 的 带宽 。想象一个极端场景,只有一篇博文,但是它的访问量无限增长,其实我们不需要影响L2缓存,因为它的内容存储的量小,但它就是访问量大。这种场景下,你就需要使用L1来扩容提升QPS和带宽瓶颈。另外一个场景,就是L2级缓存发生作用,比如我有一千万个用户,去访问的是一百万个用户的微博 ,这个时候,他不只是说你的吞吐量和访问带宽,就是你要缓存的博文的内容也很多了,这个时候你要考虑缓存的容量, 第二 级缓 存更多的是从容量上来 规划,保证请求以较小的比例 穿透到 后端的 数据 库 中 ,根据你的用户模型你可以估出来,到底有百分之多少的请求不能穿透到DB, 评估这个容量之后,才能更好的评估DB需要多少库,需要承担多大的访问的压力。另外,我们看双机房的话,左边一个,右边一个。 两个机房是互 为 主 备 , 或者互 为热备 。如果两个用户在不同地域,他们访问两个不同机房的时候,假设用户从IDC1过来,因为就近原理,他会访问L1,没有的话才会跑到Master,当在IDC1没找到的时候才会跑到IDC2来找。同时有用户从IDC2访问,也会有请求从L1和Master返回或者到IDC1去查找。 IDC1 和 IDC2 ,两个机房都有全量的用户数据,同时在线提供服务,但是缓存查询又遵循最近访问原理。还有哪些多级缓存的例子呢?CDN是典型的多级缓存。CDN在国内各个地区做了很多节点,比如在杭州市部署一个节点时,在机房里肯定不止一台机器,那么对于一个地区来说,只有几台服务器到源站回源,其他节点都到这几台服务器回源即可,这么看CDN至少也有两级。Local Cache+ 分布式 缓 存,这也是常见的一种策略。有一种场景,分布式缓存并不适用, 比如 单 点 资 源 的爆发性峰值流量,这个时候使用Local Cache + 分布式缓存,Local Cache 在 应用 服 务 器 上用很小的 内存资源 挡住少量的 极端峰值流量,长尾的流量仍然访问分布式缓存,这样的Hybrid缓存架构通过复用众多的应用服务器节点,降低了系统的整体成本。 我们来看一下 Feed 的存 储 架构,微博的博文主要存在MySQL中。首先来看内容表,这个比较简单,每条内容一个索引,每天建一张表,其次看索引表,一共建了两级索引。首先想象一下用户场景,大部分用户刷微博的时候,看的是他关注所有人的微博,然后按时间来排序。仔细分析发现在这个场景下, 跟一个用户的自己的相关性很小了。所以在一级索引的时候会先根据关注的用户,取他们的前条微博ID,然后聚合排序。我们在做哈希(分库分表)的时候,同时考虑了按照UID哈希和按照时间维度。很业务和时间相关性很高的,今天的热点新闻,明天就没热度了,数据的冷热非常明显,这种场景就需要按照时间维度做分表,首先冷热数据做了分离(可以对冷热数据采用不同的存储方案来降低成本),其次, 很容止控制我数据库表的爆炸。像微博如果只按照用户维度区分,那么这个用户所有数据都在一张表里,这张表就是无限增长的,时间长了查询会越来越慢。二级索引,是我们里面一个比较特殊的场景,就是我要快速找到这个人所要发布的某一时段的微博时,通过二级索引快速定位。 分布式服务追踪系统 分布式追踪服务系统,当系统到千万级以后的时候,越来越庞杂,所解决的问题更偏向稳定性,性能和监控。刚才说用户只要有一个请求过来,你可以依赖你的服务RPC1、RPC2,你会发现RPC2又依赖RPC3、RPC4。分布式服务的时候一个痛点,就是说一个请求从用户过来之后,在后台不同的机器之间不停的调用并返回。 当你发现一个问题的时候,这些日志落在不同的机器上,你也不知道问题到底出在哪儿,各个服务之间互相隔离,互相之间没有建立关联。所以导致排查问题基本没有任何手段,就是出了问题没法儿解决。 我们要解决的问题,我们刚才说日志互相隔离,我们就要把它建立联系。建立联系我们就有一个请求ID,然后结合RPC框架, 服务治理功能。假设请求从客户端过来,其中包含一个ID 101,到服务A时仍然带有ID 101,然后调用RPC1的时候也会标识这是101 ,所以需要 一个唯一的 请求 ID 标识 递归迭代的传递到每一个 相关 节点。第二个,你做的时候,你不能说每个地方都加,对业务系统来说需要一个框架来完成这个工作, 这 个框架要 对业务 系 统 是最低侵入原 则 , 用 JAVA 的 话 就可以用 AOP,要做到零侵入的原则,就是对所有相关的中间件打点,从接口层组件(HTTP Client、HTTP Server)至到服务层组件(RPC Client、RPC Server),还有数据访问中间件的,这样业务系统只需要少量的配置信息就可以实现全链路监控 。为什么要用日志?服务化以后,每个服务可以用不同的开发语言, 考虑多种开发语言的兼容性 , 内部定 义标 准化的日志 是唯一且有效的办法。最后,如何构建基于GPS导航的路况监控?我们刚才讲分布式服务追踪。分布式服务追踪能解决的问题, 如果 单一用 户发现问题 后 , 可以通 过请 求 ID 快速找到 发 生 问题 的 节 点在什么,但是并没有解决如何发现问题。我们看现实中比较容易理解的道路监控,每辆车有GPS定位,我想看北京哪儿拥堵的时候,怎么做? 第一个 , 你肯定要知道每个 车 在什么位置,它走到哪儿了。其实可以说每个车上只要有一个标识,加上每一次流动的信息,就可以看到每个车流的位置和方向。 其次如何做 监 控和 报 警,我们怎么能了解道路的流量状况和负载,并及时报警。我们要定义这条街道多宽多高,单位时间可以通行多少辆车,这就是道路的容量。有了道路容量,再有道路的实时流量,我们就可以基于实习路况做预警? 对应于 分布式系 统 的话如何构建? 第一 , 你要 定义 每个服 务节 点它的 SLA A 是多少 ?SLA可以从系统的CPU占用率、内存占用率、磁盘占用率、QPS请求数等来定义,相当于定义系统的容量。 第二个 , 统计 线 上 动态 的流量,你要知道服务的平均QPS、最低QPS和最大QPS,有了流量和容量,就可以对系统做全面的监控和报警。 刚才讲的是理论,实际情况肯定比这个复杂。微博在春节的时候做许多活动,必须保障系统稳定,理论上你只要定义容量和流量就可以。但实际远远不行,为什么?有技术的因素,有人为的因素,因为不同的开发定义的流量和容量指标有主观性,很难全局量化标准,所以真正流量来了以后,你预先评估的系统瓶颈往往不正确。实际中我们在春节前主要采取了三个措施:第一,最简单的就是有降 级 的 预 案,流量超过系统容量后,先把哪些功能砍掉,需要有明确的优先级 。第二个, 线上全链路压测,就是把现在的流量放大到我们平常流量的五倍甚至十倍(比如下线一半的服务器,缩容而不是扩容),看看系统瓶颈最先发生在哪里。我们之前有一些例子,推测系统数据库会先出现瓶颈,但是实测发现是前端的程序先遇到瓶颈。第三,搭建在线 Docker 集群 , 所有业务共享备用的 Docker集群资源,这样可以极大的避免每个业务都预留资源,但是实际上流量没有增长造成的浪费。 总结 接下来说的是如何不停的学习和提升,这里以Java语言为例,首先, 一定要 理解 JAVA;第二步,JAVA完了以后,一定要 理 解 JVM;其次,还要 理解 操作系统;再次还是要了解一下 Design Pattern,这将告诉你怎么把过去的经验抽象沉淀供将来借鉴;还要学习 TCP/IP、 分布式系 统、数据结构和算法。
hiekay 2019-12-02 01:39:25 0 浏览量 回答数 0

问题

【算法】五分钟算法小知识:洗牌算法

我知道大家会各种花式排序,但是如果叫你打乱一个数组,你是否能做到胸有成竹?即便你拍脑袋想出一个算法,怎么证明你的算法就是正确的呢?乱序算法不像排序算法,结果...
游客ih62co2qqq5ww 2020-05-06 13:22:45 11 浏览量 回答数 1

回答

请参考个人博客:https://blog.csdn.net/u010870518/article/details/79450295 在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出B树以及为什么MySQL数据库索引选择使用B+树! 学过数据结构的一般对最基础的树都有所认识,因此我们就从与我们主题更为相近的二叉查找树开始。 一、二叉查找树 (1)二叉树简介: 二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质: 1、任意节点左子树不为空,则左子树的值均小于根节点的值; 2、任意节点右子树不为空,则右子树的值均大于于根节点的值; 3、任意节点的左右子树也分别是二叉查找树; 4、没有键值相等的节点; 上图为一个普通的二叉查找树,按照中序遍历的方式可以从小到大的顺序排序输出:2、3、5、6、7、8。 对上述二叉树进行查找,如查键值为5的记录,先找到根,其键值是6,6大于5,因此查找6的左子树,找到3;而5大于3,再找其右子树;一共找了3次。如果按2、3、5、6、7、8的顺序来找同样需求3次。用同样的方法在查找键值为8的这个记录,这次用了3次查找,而顺序查找需要6次。计算平均查找次数得:顺序查找的平均查找次数为(1+2+3+4+5+6)/ 6 = 3.3次,二叉查找树的平均查找次数为(3+3+3+2+2+1)/6=2.3次。二叉查找树的平均查找速度比顺序查找来得更快。 (2)局限性及应用 一个二叉查找树是由n个节点随机构成,所以,对于某些情况,二叉查找树会退化成一个有n个节点的线性链。如下图: 大家看上图,如果我们的根节点选择是最小或者最大的数,那么二叉查找树就完全退化成了线性结构。上图中的平均查找次数为(1+2+3+4+5+5)/6=3.16次,和顺序查找差不多。显然这个二叉树的查询效率就很低,因此若想最大性能的构造一个二叉查找树,需要这个二叉树是平衡的(这里的平衡从一个显著的特点可以看出这一棵树的高度比上一个输的高度要大,在相同节点的情况下也就是不平衡),从而引出了一个新的定义-平衡二叉树AVL。 二、AVL树 (1)简介 AVL树是带有平衡条件的二叉查找树,一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡,左右子树树高不超过1,和红黑树相比,它是严格的平衡二叉树,平衡条件必须满足(所有节点的左右子树高度差不超过1)。不管我们是执行插入还是删除操作,只要不满足上面的条件,就要通过旋转来保持平衡,而旋转是非常耗时的,由此我们可以知道AVL树适合用于插入删除次数比较少,但查找多的情况。 从上面是一个普通的平衡二叉树,这张图我们可以看出,任意节点的左右子树的平衡因子差值都不会大于1。 (2)局限性 由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多,更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树。 (3)应用 1、Windows NT内核中广泛存在; 三、红黑树 (1)简介 一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树(由于是若平衡,可以推出,相同的节点情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数变少,所以对于搜索、插入、删除操作多的情况下,我们就用红黑树。 (2)性质 1、每个节点非红即黑; 2、根节点是黑的; 3、每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的; 4、如果一个节点是红的,那么它的两儿子都是黑的; 5、对于任意节点而言,其到叶子点树NULL指针的每条路径都包含相同数目的黑节点; 6、每条路径都包含相同的黑节点; (3)应用 1、广泛用于C++的STL中,Map和Set都是用红黑树实现的; 2、著名的Linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间; 3、IO多路复用epoll的实现采用红黑树组织管理sockfd,以支持快速的增删改查; 4、Nginx中用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器; 5、Java中TreeMap的实现; 四、B/B+树 说了上述的三种树:二叉查找树、AVL和红黑树,似乎我们还没有摸到MySQL为什么要使用B+树作为索引的实现,不要急,接下来我们就先探讨一下什么是B树。 (1)简介 我们在MySQL中的数据一般是放在磁盘中的,读取数据的时候肯定会有访问磁盘的操作,磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。 为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。 总的来说,B/B+树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉,B树每个内节点有多个分支),与红黑树相比,在相同的的节点的情况下,一颗B/B+树的高度远远小于红黑树的高度(在下面B/B+树的性能分析中会提到)。B/B+树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成,而CPU的速度非常快,所以B树的操作效率取决于访问磁盘的次数,关键字总数相同的情况下B树的高度越小,磁盘I/O所花的时间越少。 注意B-树就是B树,-只是一个符号。 (2)B树的性质 1、定义任意非叶子结点最多只有M个儿子,且M>2; 2、根结点的儿子数为[2, M]; 3、除根结点以外的非叶子结点的儿子数为[M/2, M]; 4、每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字) 5、非叶子结点的关键字个数=指向儿子的指针个数-1; 6、非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1]; 7、非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树; 8、所有叶子结点位于同一层; 这里只是一个简单的B树,在实际中B树节点中关键字很多的,上面的图中比如35节点,35代表一个key(索引),而小黑块代表的是这个key所指向的内容在内存中实际的存储位置,是一个指针。 五、B+树 (1)简介 B+树是应文件系统所需而产生的一种B树的变形树(文件的目录一级一级索引,只有最底层的叶子节点(文件)保存数据)非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中,这不就是文件系统文件的查找吗? 我们就举个文件查找的例子:有3个文件夹a、b、c, a包含b,b包含c,一个文件yang.c,a、b、c就是索引(存储在非叶子节点), a、b、c只是要找到的yang.c的key,而实际的数据yang.c存储在叶子节点上。 所有的非叶子节点都可以看成索引部分! (2)B+树的性质(下面提到的都是和B树不相同的性质) 1、非叶子节点的子树指针与关键字个数相同; 2、非叶子节点的子树指针p[i],指向关键字值属于[k[i],k[i+1]]的子树.(B树是开区间,也就是说B树不允许关键字重复,B+树允许重复); 3、为所有叶子节点增加一个链指针; 4、所有关键字都在叶子节点出现(稠密索引). (且链表中的关键字恰好是有序的); 5、非叶子节点相当于是叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层; 6、更适合于文件系统; 非叶子节点(比如5,28,65)只是一个key(索引),实际的数据存在叶子节点上(5,8,9)才是真正的数据或指向真实数据的指针。 (3)应用 1、B和B+树主要用在文件系统以及数据库做索引,比如MySQL; 六、B/B+树性能分析 n个节点的平衡二叉树的高度为H(即logn),而n个节点的B/B+树的高度为logt((n+1)/2)+1;   若要作为内存中的查找表,B树却不一定比平衡二叉树好,尤其当m较大时更是如此。因为查找操作CPU的时间在B-树上是O(mlogtn)=O(lgn(m/lgt)),而m/lgt>1;所以m较大时O(mlogtn)比平衡二叉树的操作时间大得多。因此在内存中使用B树必须取较小的m。(通常取最小值m=3,此时B-树中每个内部结点可以有2或3个孩子,这种3阶的B-树称为2-3树)。 七、为什么说B+树比B树更适合数据库索引? 1、 B+树的磁盘读写代价更低:B+树的内部节点并没有指向关键字具体信息的指针,因此其内部节点相对B树更小,如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相对IO读写次数就降低了。 2、B+树的查询效率更加稳定:由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。 3、由于B+树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B+树更加适合在区间查询的情况,所以通常B+树用于数据库索引。 PS:我在知乎上看到有人是这样说的,我感觉说的也挺有道理的: 他们认为数据库索引采用B+树的主要原因是:B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作或者说效率太低。 ———————————————— 版权声明:本文为CSDN博主「徐刘根」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/u010870518/java/article/details/79450295
AA大大官 2020-03-31 14:54:01 0 浏览量 回答数 0

问题

【精品问答】110+数据挖掘面试题集合

数据挖掘工程师面试宝典双手呈上,快来收藏吧! 1.异常值是指什么?请列举1种识别连续型变量异常值的方法? 2.什么是聚类分析? 3.聚类算法有哪几种?选择一种详细描述其计算原理和步骤。 4.根据要求写出SQL ...
珍宝珠 2019-12-01 21:56:45 2713 浏览量 回答数 3

问题

【精品问答】python技术1000问(2)

为了方便python开发者快速找到相关技术问题和答案,开发者社区策划了python技术1000问内容,包含最基础的如何学python、实践中遇到的技术问题、python面试等维度内容。 我们会以每天至少50条的...
问问小秘 2019-12-01 22:03:02 3129 浏览量 回答数 1

回答

本文主要介绍Java中的自动拆箱与自动装箱的有关知识。 基本数据类型 基本类型,或者叫做内置类型,是Java中不同于类(Class)的特殊类型。它们是我们编程中使用最频繁的类型。 Java是一种强类型语言,第一次申明变量必须说明数据类型,第一次变量赋值称为变量的初始化。 Java基本类型共有八种,基本类型可以分为三类: 字符类型char 布尔类型boolean 数值类型byte、short、int、long、float、double。 数值类型又可以分为整数类型byte、short、int、long和浮点数类型float、double。 Java中的数值类型不存在无符号的,它们的取值范围是固定的,不会随着机器硬件环境或者操作系统的改变而改变。 实际上,Java中还存在另外一种基本类型void,它也有对应的包装类 java.lang.Void,不过我们无法直接对它们进行操作。 基本数据类型有什么好处 我们都知道在Java语言中,new一个对象是存储在堆里的,我们通过栈中的引用来使用这些对象;所以,对象本身来说是比较消耗资源的。 对于经常用到的类型,如int等,如果我们每次使用这种变量的时候都需要new一个Java对象的话,就会比较笨重。所以,和C++一样,Java提供了基本数据类型,这种数据的变量不需要使用new创建,他们不会在堆上创建,而是直接在栈内存中存储,因此会更加高效。 整型的取值范围 Java中的整型主要包含byte、short、int和long这四种,表示的数字范围也是从小到大的,之所以表示范围不同主要和他们存储数据时所占的字节数有关。 先来个简答的科普,1字节=8位(bit)。java中的整型属于有符号数。 先来看计算中8bit可以表示的数字: 最小值:10000000 (-128)(-2^7) 最大值:01111111(127)(2^7-1) 整型的这几个类型中, byte:byte用1个字节来存储,范围为-128(-2^7)到127(2^7-1),在变量初始化的时候,byte类型的默认值为0。 short:short用2个字节存储,范围为-32,768 (-2^15)到32,767 (2^15-1),在变量初始化的时候,short类型的默认值为0,一般情况下,因为Java本身转型的原因,可以直接写为0。 int:int用4个字节存储,范围为-2,147,483,648 (-2^31)到2,147,483,647 (2^31-1),在变量初始化的时候,int类型的默认值为0。 long:long用8个字节存储,范围为-9,223,372,036,854,775,808 (-2^63)到9,223,372,036, 854,775,807 (2^63-1),在变量初始化的时候,long类型的默认值为0L或0l,也可直接写为0。 超出范围怎么办 上面说过了,整型中,每个类型都有一定的表示范围,但是,在程序中有些计算会导致超出表示范围,即溢出。如以下代码: int i = Integer.MAX_VALUE; int j = Integer.MAX_VALUE; int k = i + j; System.out.println("i (" + i + ") + j (" + j + ") = k (" + k + ")"); 输出结果:i (2147483647) + j (2147483647) = k (-2) **这就是发生了溢出,溢出的时候并不会抛异常,也没有任何提示。**所以,在程序中,使用同类型的数据进行运算的时候,一定要注意数据溢出的问题。 包装类型 Java语言是一个面向对象的语言,但是Java中的基本数据类型却是不面向对象的,这在实际使用时存在很多的不便,为了解决这个不足,在设计类时为每个基本数据类型设计了一个对应的类进行代表,这样八个和基本数据类型对应的类统称为包装类(Wrapper Class)。 包装类均位于java.lang包,包装类和基本数据类型的对应关系如下表所示 基本数据类型包装类byteBytebooleanBooleanshortShortcharCharacterintIntegerlongLongfloatFloatdoubleDouble 在这八个类名中,除了Integer和Character类以后,其它六个类的类名和基本数据类型一致,只是类名的第一个字母大写即可。 为什么需要包装类 很多人会有疑问,既然Java中为了提高效率,提供了八种基本数据类型,为什么还要提供包装类呢? 这个问题,其实前面已经有了答案,因为Java是一种面向对象语言,很多地方都需要使用对象而不是基本数据类型。比如,在集合类中,我们是无法将int 、double等类型放进去的。因为集合的容器要求元素是Object类型。 为了让基本类型也具有对象的特征,就出现了包装类型,它相当于将基本类型“包装起来”,使得它具有了对象的性质,并且为其添加了属性和方法,丰富了基本类型的操作。 拆箱与装箱 那么,有了基本数据类型和包装类,肯定有些时候要在他们之间进行转换。比如把一个基本数据类型的int转换成一个包装类型的Integer对象。 我们认为包装类是对基本类型的包装,所以,把基本数据类型转换成包装类的过程就是打包装,英文对应于boxing,中文翻译为装箱。 反之,把包装类转换成基本数据类型的过程就是拆包装,英文对应于unboxing,中文翻译为拆箱。 在Java SE5之前,要进行装箱,可以通过以下代码: Integer i = new Integer(10); 自动拆箱与自动装箱 在Java SE5中,为了减少开发人员的工作,Java提供了自动拆箱与自动装箱功能。 自动装箱: 就是将基本数据类型自动转换成对应的包装类。 自动拆箱:就是将包装类自动转换成对应的基本数据类型。 Integer i =10; //自动装箱 int b= i; //自动拆箱 Integer i=10 可以替代 Integer i = new Integer(10);,这就是因为Java帮我们提供了自动装箱的功能,不需要开发者手动去new一个Integer对象。 自动装箱与自动拆箱的实现原理 既然Java提供了自动拆装箱的能力,那么,我们就来看一下,到底是什么原理,Java是如何实现的自动拆装箱功能。 我们有以下自动拆装箱的代码: public static void main(String[]args){ Integer integer=1; //装箱 int i=integer; //拆箱 } 对以上代码进行反编译后可以得到以下代码: public static void main(String[]args){ Integer integer=Integer.valueOf(1); int i=integer.intValue(); } 从上面反编译后的代码可以看出,int的自动装箱都是通过Integer.valueOf()方法来实现的,Integer的自动拆箱都是通过integer.intValue来实现的。如果读者感兴趣,可以试着将八种类型都反编译一遍 ,你会发现以下规律: 自动装箱都是通过包装类的valueOf()方法来实现的.自动拆箱都是通过包装类对象的xxxValue()来实现的。 哪些地方会自动拆装箱 我们了解过原理之后,在来看一下,什么情况下,Java会帮我们进行自动拆装箱。前面提到的变量的初始化和赋值的场景就不介绍了,那是最简单的也最容易理解的。 我们主要来看一下,那些可能被忽略的场景。 场景一、将基本数据类型放入集合类 我们知道,Java中的集合类只能接收对象类型,那么以下代码为什么会不报错呢? List<Integer> li = new ArrayList<>(); for (int i = 1; i < 50; i ++){ li.add(i); } 将上面代码进行反编译,可以得到以下代码: List<Integer> li = new ArrayList<>(); for (int i = 1; i < 50; i += 2){ li.add(Integer.valueOf(i)); } 以上,我们可以得出结论,当我们把基本数据类型放入集合类中的时候,会进行自动装箱。 场景二、包装类型和基本类型的大小比较 有没有人想过,当我们对Integer对象与基本类型进行大小比较的时候,实际上比较的是什么内容呢?看以下代码: Integer a=1; System.out.println(a==1?"等于":"不等于"); Boolean bool=false; System.out.println(bool?"真":"假"); 对以上代码进行反编译,得到以下代码: Integer a=1; System.out.println(a.intValue()==1?"等于":"不等于"); Boolean bool=false; System.out.println(bool.booleanValue?"真":"假"); 可以看到,包装类与基本数据类型进行比较运算,是先将包装类进行拆箱成基本数据类型,然后进行比较的。 场景三、包装类型的运算 有没有人想过,当我们对Integer对象进行四则运算的时候,是如何进行的呢?看以下代码: Integer i = 10; Integer j = 20; System.out.println(i+j); 反编译后代码如下: Integer i = Integer.valueOf(10); Integer j = Integer.valueOf(20); System.out.println(i.intValue() + j.intValue()); 我们发现,两个包装类型之间的运算,会被自动拆箱成基本类型进行。 场景四、三目运算符的使用 这是很多人不知道的一个场景,作者也是一次线上的血淋淋的Bug发生后才了解到的一种案例。看一个简单的三目运算符的代码: boolean flag = true; Integer i = 0; int j = 1; int k = flag ? i : j; 很多人不知道,其实在int k = flag ? i : j;这一行,会发生自动拆箱。反编译后代码如下: boolean flag = true; Integer i = Integer.valueOf(0); int j = 1; int k = flag ? i.intValue() : j; System.out.println(k); 这其实是三目运算符的语法规范。当第二,第三位操作数分别为基本类型和对象时,其中的对象就会拆箱为基本类型进行操作。 因为例子中,flag ? i : j;片段中,第二段的i是一个包装类型的对象,而第三段的j是一个基本类型,所以会对包装类进行自动拆箱。如果这个时候i的值为null,那么就会发生NPE。(自动拆箱导致空指针异常) 场景五、函数参数与返回值 这个比较容易理解,直接上代码了: //自动拆箱 public int getNum1(Integer num) { return num; } //自动装箱 public Integer getNum2(int num) { return num; } 自动拆装箱与缓存 Java SE的自动拆装箱还提供了一个和缓存有关的功能,我们先来看以下代码,猜测一下输出结果: public static void main(String... strings) { Integer integer1 = 3; Integer integer2 = 3; if (integer1 == integer2) System.out.println("integer1 == integer2"); else System.out.println("integer1 != integer2"); Integer integer3 = 300; Integer integer4 = 300; if (integer3 == integer4) System.out.println("integer3 == integer4"); else System.out.println("integer3 != integer4"); } 我们普遍认为上面的两个判断的结果都是false。虽然比较的值是相等的,但是由于比较的是对象,而对象的引用不一样,所以会认为两个if判断都是false的。在Java中,==比较的是对象应用,而equals比较的是值。所以,在这个例子中,不同的对象有不同的引用,所以在进行比较的时候都将返回false。奇怪的是,这里两个类似的if条件判断返回不同的布尔值。 上面这段代码真正的输出结果: integer1 == integer2 integer3 != integer4 原因就和Integer中的缓存机制有关。在Java 5中,在Integer的操作上引入了一个新功能来节省内存和提高性能。整型对象通过使用相同的对象引用实现了缓存和重用。 适用于整数值区间-128 至 +127。 只适用于自动装箱。使用构造函数创建对象不适用。 具体的代码实现可以阅读Java中整型的缓存机制一文,这里不再阐述。 我们只需要知道,当需要进行自动装箱时,如果数字在-128至127之间时,会直接使用缓存中的对象,而不是重新创建一个对象。 其中的javadoc详细的说明了缓存支持-128到127之间的自动装箱过程。最大值127可以通过-XX:AutoBoxCacheMax=size修改。 实际上这个功能在Java 5中引入的时候,范围是固定的-128 至 +127。后来在Java 6中,可以通过java.lang.Integer.IntegerCache.high设置最大值。 这使我们可以根据应用程序的实际情况灵活地调整来提高性能。到底是什么原因选择这个-128到127范围呢?因为这个范围的数字是最被广泛使用的。 在程序中,第一次使用Integer的时候也需要一定的额外时间来初始化这个缓存。 在Boxing Conversion部分的Java语言规范(JLS)规定如下: 如果一个变量p的值是: -128至127之间的整数(§3.10.1) true 和 false的布尔值 (§3.10.3) ‘\u0000’至 ‘\u007f’之间的字符(§3.10.4) 范围内的时,将p包装成a和b两个对象时,可以直接使用a==b判断a和b的值是否相等。 自动拆装箱带来的问题 当然,自动拆装箱是一个很好的功能,大大节省了开发人员的精力,不再需要关心到底什么时候需要拆装箱。但是,他也会引入一些问题。 包装对象的数值比较,不能简单的使用==,虽然-128到127之间的数字可以,但是这个范围之外还是需要使用equals比较。 前面提到,有些场景会进行自动拆装箱,同时也说过,由于自动拆箱,如果包装类对象为null,那么自动拆箱时就有可能抛出NPE。 如果一个for循环中有大量拆装箱操作,会浪费很多资源。 参考资料 Java的自动拆装箱
montos 2020-06-01 21:24:01 0 浏览量 回答数 0

云产品推荐

上海奇点人才服务相关的云产品 小程序定制 上海微企信息技术相关的云产品 国内短信套餐包 ECS云服务器安全配置相关的云产品 开发者问答 阿里云建站 自然场景识别相关的云产品 万网 小程序开发制作 视频内容分析 视频集锦 代理记账服务 阿里云AIoT