• 关于

    常用的变量运算

    的搜索结果

回答

问题原因 执行的命令中包含!字符,该字符在 shell 里面是特殊字符,指的是执行历史命令。 处理办法 如果要让!等特殊字符不转义的话,需要在前面加个\ 比如: curl "http://xxxx.com/bao/uploaded/i3/2245429602/TB24JupcFXXXXaAXXXXXXXXXXXX_\!\!2245429602.jpg"   #这个样就不会转义了。   另外,Linux 的 shell 下常用的元字符说明: 字符 说明 IFS 由或或三者之一组成(我们常用 space )。 CR 由产生。 = 设定变量。 $ 作变量或运算替换(请不要与 shell prompt 搞混了)。 > 重导向 stdout。 < 重导向 stdin。 | 命令管线。 & 重导向 file descriptor ,或将命令置于背境执行。 ( ) 将其内的命令置于 nested subshell 执行,或用于运算或命令替换。 { } 将其内的命令置于 non-named function 中执行,或用在变量替换的界定范围。 ; 在前一个命令结束时,而忽略其返回值,继续执行下一个命令。 && 在前一个命令结束时,若返回值为 true,继续执行下一个命令。 || 在前一个命令结束时,若返回值为 false,继续执行下一个命令。 ! 执行 history 列表中的命令。*
KB小秘书 2019-12-02 02:05:43 0 浏览量 回答数 0

回答

问题原因 执行的命令中包含!字符,该字符在 shell 里面是特殊字符,指的是执行历史命令。 处理办法 如果要让!等特殊字符不转义的话,需要在前面加个\ 比如: curl "http://xxxx.com/bao/uploaded/i3/2245429602/TB24JupcFXXXXaAXXXXXXXXXXXX_\!\!2245429602.jpg"   #这个样就不会转义了。   另外,Linux 的 shell 下常用的元字符说明: 字符 说明 IFS 由或或三者之一组成(我们常用 space )。 CR 由产生。 = 设定变量。 $ 作变量或运算替换(请不要与 shell prompt 搞混了)。 > 重导向 stdout。 < 重导向 stdin。 | 命令管线。 & 重导向 file descriptor ,或将命令置于背境执行。 ( ) 将其内的命令置于 nested subshell 执行,或用于运算或命令替换。 { } 将其内的命令置于 non-named function 中执行,或用在变量替换的界定范围。 ; 在前一个命令结束时,而忽略其返回值,继续执行下一个命令。 && 在前一个命令结束时,若返回值为 true,继续执行下一个命令。 || 在前一个命令结束时,若返回值为 false,继续执行下一个命令。 ! 执行 history 列表中的命令。*
KB小秘书 2019-12-02 02:06:01 0 浏览量 回答数 0

回答

用来判断引用类型的变量所指向的对象是否是一个类(或者接口,抽象类,父类)的实例 常用的方法是:result=object instanceof classname.如果Object是class的一个实例,那么instanceof运算符返回为true,不是(或者Object为null),那么结果返回false 输出结果为 true true false
景凌凯 2020-04-03 22:02:15 0 浏览量 回答数 0

万券齐发助力企业上云,爆款产品低至2.2折起!

限量神券最高减1000,抢完即止!云服务器ECS新用户首购低至0.95折!

问题

js页面优化技巧总结

相信大多数做过后台开发的同仁们,特别是遇到与前台大量交互的时候,JS的结构以及可读性是最重要的,不然看起来就是一坨shi。回首看看自己以前写的真是一坨shi。 当然这里不是教你如何写出优雅的代...
小柒2012 2019-12-01 21:44:12 8286 浏览量 回答数 5

问题

为什么云服务器 ECS Linux 执行命令会导致实际执行的是历史命令

问题描述 具体现象是。比如,执行如下指令: curl "http://xxxx.com/bao/uploaded/i3/2245429602/TB24JupcFXXXXaAXXXXXXXXXXX...
boxti 2019-12-01 22:05:32 1180 浏览量 回答数 0

问题

【百问百答】《〈Java开发手册(泰山版)〉灵魂13问》

什么是三目运算符什么是自动装箱和自动拆箱三目运算符为什么会出现 NullPointerExceptionHashMap 容量初始化流程是什么HashMap 为什么推荐设置初始化容量HashMap 初始化容量设置多少合适HashMap 扩容机...
一人吃饱,全家不饿 2021-01-05 14:20:12 1 浏览量 回答数 0

回答

迭代法  迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。   迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。   利用迭代算法解决问题,需要做好以下三个方面的工作:   一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。   二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。   三、对迭代过程进行控制。在什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。   例 1 : 一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。   分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有   u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,……   根据这个规律,可以归纳出下面的递推公式:   u n = u n - 1 × 2 (n ≥ 2)   对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系:   y=x*2   x=y   让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下:   cls   x=1   for i=2 to 12   y=x*2   x=y   next i   print y   end   例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 220,220个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。   分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴2^ 20 个”,即阿米巴分裂 15 次以后得到的个数是 2^20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2^20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。   设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有   x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1)   因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式:   x=x/2 ( x 的初值为第 15 次分裂之后的个数 2^20 )   让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下:   cls   x=2^20   for i=1 to 15   x=x/2   next i   print x   end   ps:java中幂的算法是Math.pow(2, 20);返回double,稍微注意一下   例 3 : 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。   要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。   分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是:   if n 为偶数 then   n=n/2   else   n=n*3+1   end if   这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下:   cls   input "Please input n=";n   do until n=1   if n mod 2=0 then   rem 如果 n 为偶数,则调用迭代公式 n=n/2   n=n/2   print "—";n;   else   n=n*3+1   print "—";n;   end if   loop   end   迭代法   迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行:   (1) 选一个方程的近似根,赋给变量x0;   (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0;   (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。   若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为:   【算法】迭代法求方程的根   { x0=初始近似根;   do {   x1=x0;   x0=g(x1); /*按特定的方程计算新的近似根*/   } while ( fabs(x0-x1)>Epsilon);   printf(“方程的近似根是%f\n”,x0);   }   迭代算法也常用于求方程组的根,令   X=(x0,x1,…,xn-1)   设方程组为:   xi=gi(X) (I=0,1,…,n-1)   则求方程组根的迭代算法可描述如下:   【算法】迭代法求方程组的根   { for (i=0;i   x=初始近似根;   do {   for (i=0;i   y=x;   for (i=0;i   x=gi(X);   for (delta=0.0,i=0;i   if (fabs(y-x)>delta) delta=fabs(y-x);   } while (delta>Epsilon);   for (i=0;i   printf(“变量x[%d]的近似根是 %f”,I,x);   printf(“\n”);   }   具体使用迭代法求根时应注意以下两种可能发生的情况:   (1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制;   (2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。   递归   递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。   能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。   【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。   斐波那契数列为:0、1、1、2、3、……,即:   fib(0)=0;   fib(1)=1;   fib(n)=fib(n-1)+fib(n-2) (当n>1时)。   写成递归函数有:   int fib(int n)   { if (n==0) return 0;   if (n==1) return 1;   if (n>1) return fib(n-1)+fib(n-2);   }   递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。   在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。   在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。   由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。   【问题】 组合问题   问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1   (4)5、3、2 (5)5、3、1 (6)5、2、1   (7)4、3、2 (8)4、3、1 (9)4、2、1   (10)3、2、1   分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。   【程序】   # include   # define MAXN 100   int a[MAXN];   void comb(int m,int k)   { int i,j;   for (i=m;i>=k;i--)   { a[k]=i;   if (k>1)   comb(i-1,k-1);   else   { for (j=a[0];j>0;j--)   printf(“%4d”,a[j]);   printf(“\n”);   }   }   }   void main()   { a[0]=3;   comb(5,3);   }   【问题】 背包问题   问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。   设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。   对于第i件物品的选择考虑有两种可能:   (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。   (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。   按以上思想写出递归算法如下:   try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv)   { /*考虑物品i包含在当前方案中的可能性*/   if(包含物品i是可以接受的)   { 将物品i包含在当前方案中;   if (i   try(i+1,tw+物品i的重量,tv);   else   /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   恢复物品i不包含状态;   }   /*考虑物品i不包含在当前方案中的可能性*/   if (不包含物品i仅是可男考虑的)   if (i   try(i+1,tw,tv-物品i的价值);   else   /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   }
沉默术士 2019-12-02 01:25:10 0 浏览量 回答数 0

问题

【精品问答】关于Java,那些入门级的面试题

Java,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台的总称,最初推出的时候提出 “Write Once, Run Anywhere” 的理想愿景。现如今&#x...
问问小秘 2020-03-27 18:39:09 1073 浏览量 回答数 3

回答

敢用自己的名字做软件名字的,都有非常强大的自信。比如,垠语言什么的。 awk的命名得自于它的三个创始人姓别的首字母,都是80来岁的老爷爷了。当然也有四个人的组合:流行的GoF设计模式。但对于我这游戏爱好者来说,想到的竟然是三位一体,果然是不争气啊。 它长的很像C,为什么这么有名,除了它强大的功能,我们姑且认为a这个字母比较靠前吧。awk比sed简单,它更像一门编程语言。 打印某一列 下面,这几行代码的效果基本是相同的:打印文件中的第一列。 这可能是awk最常用的功能了:打印文件中的某一列。它智能的去切分你的数据,不管是空格,还是TAB,大概率是你想要的。 对于csv这种文件来说,分隔的字符是,。AWK使用-F参数去指定。以下代码打印csv文件中的第1和第2列。 awk -F "," '{print $1,$2}' file 由此,我们可以看出一个基本的awk命令的组成部分。 一般的开发语言,数组下标是以0开始的,但awk的列$是以1开始的,而0指的是原始字符串。 网络状态统计 本小节,采用awk统计netstat命令的一些网络状态,来看一下awk语言的基本要素。netstat的输出类似于: 其中,第6列,标明了网络连接所处于的网络状态。我们先给出awk命令,看一下统计结果。 netstat -ant | awk ' \ BEGIN{print "State","Count" } \ /^tcp/ \ { rt[$6]++ } \ END{ for(i in rt){print i,rt[i]} }' 输出结果为: State Count LAST_ACK 1 LISTEN 64 CLOSE_WAIT 43 ESTABLISHED 719 SYN_SENT 5 TIME_WAIT 146 下面这张图会配合以上命令详细说明,希望你能了解awk的精髓。 乍一看,好吓人的命令,但是很简单。awk和我们通常的程序不太一样,它分为四个部分。 1、BEGIN 开头部分,可选的。用来设置一些参数,输出一些表头,定义一些变量等。上面的命令仅打印了一行信息而已。 2、END 结尾部分,可选的。用来计算一些汇总逻辑,或者输出这些内容。上面的命令,使用简单的for循环,输出了数组rt中的内容。 3、Pattern 匹配部分,依然可选。用来匹配一些需要处理的行。上面的命令,只匹配tcp开头的行,其他的不进入处理。 4、Action 模块。主要逻辑体,按行处理,统计打印,都可以。 注意点 1、awk的主程序部分使用单引号‘包围,而不能是双引号 2、awk的列开始的index是0,而不是1 例子 我们从几个简单的例子,来看下awk的作用。 1、输出Recv-Q不为0的记录 netstat -ant | awk '$2 > 0 {print}' 2、外网连接数,根据ip分组 netstat -ant | awk '/^tcp/{print $4}' | awk -F: '!/^:/{print $1}' | sort | uniq -c 3、打印RSS物理内存占用 top -b -n 1 | awk 'NR>7{rss+=$6}END{print rss} 4、过滤(去掉)空白行 awk 'NF' file 5、打印奇数行 awk 'a=!a' file 6、输出行数 awk 'END{print NR}' file 这些命令,是需要了解awk的一些内部变量的,接下来我们来介绍。 内置变量 FS 下面的两个命令是等价的 。 awk -F ':' '{print $3}' file awk 'BEGIN{FS=":"}{print $3}' file BEGIN块中的FS,就是内部变量,可以直接指定或者输出。如果你的文件既有用,分隔的,也有用:分割的,FS甚至可以指定多个分隔符同时起作用。 FS="[,:|]" 其他 OFS 指定输出内容的分割符,列数非常多的时候,简化操作。相似命令: awk -F ':' '{print $1,"-",$2,"-",$4}' file awk 'BEGIN{FS=":";OFS="-"}{print $1,$2,$4}' file NF 列数。非常有用,比如,过滤一些列数不满足条件的内容。 awk -F, '{if(NF==3){print}}' file NR 行号,例如,下面两个命令是等价的。 cat -n file awk '{print NR,$0}' file RS 记录分隔标志 ORS 指定记录输出的分隔标志 FILENAME 当前处理的文件名称,在一次性处理多个文件时非常有用 编程语言特性 数学运算 从上面的代码可以看出,awk可以做一些简单的运算。它的语言简洁,不需要显示的定义变量的类型。 比如上面的rt[$6]++,就已经默认定义了一个叫做rt的hash(array?),里面的key是网络状态,而value是可以进行运算的(+-*/%)。 包含一些内置的数学运算(有限) int log sqrt exp sin cos atan2 rand srand 字符串操作 类似其他语言,awk也内置了很多字符串操作函数。它本来就是处理字符串的,所以必须强大。 length(str) #获取字符串长度 split(input-string,output-array,separator) substr(input-string, location, length) 语言特性 awk是个小型的编程语言,看它的基本语法,如果你需要复杂一点的逻辑,请自行深入了解,包括一些时间处理函数: # logic if(x=a){} if(x=a){}else{} while(x=a){break;continue;} do{}while(x=a) for(;;){} # array arr[key] = value for(key in arr){arr[key]} delete arr[key] asort(arr) #简单排序 据说,awk可以胜任所有的文本操作。因为它本身就是一门语言啊。 End 曾经使用awk编写过复杂的日志处理和统计程序。虽然比写sed舒畅了很多,但还是备受煎熬。更加上现在有各种nawk,gawk版本之间的区别,所以业务复杂度一增长,就习惯性的转向更加简洁、工具更全的python。 awk处理一些简单的文本还是极其方便的,最常用的还是打印某一列之类的,包括一些格式化输出。对于awk,要简单的滚瓜烂熟,复杂的耳熟能详,毕竟有些大牛,就喜欢写这种脚本呢。 注明:转载于小姐妹养的狗
剑曼红尘 2020-04-01 11:18:23 0 浏览量 回答数 0

回答

  迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。   利用迭代算法解决问题,需要做好以下三个方面的工作:   一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。   二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。   三、对迭代过程进行控制。在什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。   例 1 : 一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。   分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有   u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,……   根据这个规律,可以归纳出下面的递推公式:   u n = u n - 1 × 2 (n ≥ 2)   对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系:   y=x*2   x=y   让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下:   cls   x=1   for i=2 to 12   y=x*2   x=y   next i   print y   end   例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 2 20 个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。   分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴 2 20 个”,即阿米巴分裂 15 次以后得到的个数是 2 20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2 20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。   设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有   x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1)   因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式:   x=x/2 ( x 的初值为第 15 次分裂之后的个数 2 20 )   让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下:   cls   x=2^20   for i=1 to 15   x=x/2   next i   print x   end   例 3 : 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。   要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。   分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是:   if n 为偶数 then   n=n/2   else   n=n*3+1   end if   这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下:   cls   input "Please input n=";n   do until n=1   if n mod 2=0 then   rem 如果 n 为偶数,则调用迭代公式 n=n/2   n=n/2   print "—";n;   else   n=n*3+1   print "—";n;   end if   loop   end   迭代法   迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行:   (1) 选一个方程的近似根,赋给变量x0;   (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0;   (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。   若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为:   【算法】迭代法求方程的根   { x0=初始近似根;   do {   x1=x0;   x0=g(x1); /*按特定的方程计算新的近似根*/   } while ( fabs(x0-x1)>Epsilon);   printf(“方程的近似根是%f\n”,x0);   }   迭代算法也常用于求方程组的根,令   X=(x0,x1,…,xn-1)   设方程组为:   xi=gi(X) (I=0,1,…,n-1)   则求方程组根的迭代算法可描述如下:   【算法】迭代法求方程组的根   { for (i=0;i   x=初始近似根;   do {   for (i=0;i   y=x;   for (i=0;i   x=gi(X);   for (delta=0.0,i=0;i   if (fabs(y-x)>delta) delta=fabs(y-x);   } while (delta>Epsilon);   for (i=0;i   printf(“变量x[%d]的近似根是 %f”,I,x);   printf(“\n”);   }   具体使用迭代法求根时应注意以下两种可能发生的情况:   (1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制;   (2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。   递归   递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。   能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。   【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。   斐波那契数列为:0、1、1、2、3、……,即:   fib(0)=0;   fib(1)=1;   fib(n)=fib(n-1)+fib(n-2) (当n>1时)。   写成递归函数有:   int fib(int n)   { if (n==0) return 0;   if (n==1) return 1;   if (n>1) return fib(n-1)+fib(n-2);   }   递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。   在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。   在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。   由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。   【问题】 组合问题   问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1   (4)5、3、2 (5)5、3、1 (6)5、2、1   (7)4、3、2 (8)4、3、1 (9)4、2、1   (10)3、2、1   分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。   【程序】   # include   # define MAXN 100   int a[MAXN];   void comb(int m,int k)   { int i,j;   for (i=m;i>=k;i--)   { a[k]=i;   if (k>1)   comb(i-1,k-1);   else   { for (j=a[0];j>0;j--)   printf(“%4d”,a[j]);   printf(“\n”);   }   }   }   void main()   { a[0]=3;   comb(5,3);   }   【问题】 背包问题   问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。   设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。   对于第i件物品的选择考虑有两种可能:   (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。   (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。   按以上思想写出递归算法如下:   try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv)   { /*考虑物品i包含在当前方案中的可能性*/   if(包含物品i是可以接受的)   { 将物品i包含在当前方案中;   if (i   try(i+1,tw+物品i的重量,tv);   else   /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   恢复物品i不包含状态;   }   /*考虑物品i不包含在当前方案中的可能性*/   if (不包含物品i仅是可男考虑的)   if (i   try(i+1,tw,tv-物品i的价值);   else   /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/   以当前方案作为临时最佳方案保存;   }   为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表:   物品 0 1 2 3   重量 5 3 2 1   价值 4 4 3 1   并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。   按上述算法编写函数和程序如下:   【程序】   # include   # define N 100   double limitW,totV,maxV;   int option[N],cop[N];   struct { double weight;   double value;   }a[N];   int n;   void find(int i,double tw,double tv)   { int k;   /*考虑物品i包含在当前方案中的可能性*/   if (tw+a.weight<=limitW)   { cop=1;   if (i   else   { for (k=0;k   option[k]=cop[k];   maxv=tv;   }   cop=0;   }   /*考虑物品i不包含在当前方案中的可能性*/   if (tv-a.value>maxV)   if (i   else   { for (k=0;k   option[k]=cop[k];   maxv=tv-a.value;   }   }   void main()   { int k;   double w,v;   printf(“输入物品种数\n”);   scanf((“%d”,&n);   printf(“输入各物品的重量和价值\n”);   for (totv=0.0,k=0;k   { scanf(“%1f%1f”,&w,&v);   a[k].weight=w;   a[k].value=v;   totV+=V;   }   printf(“输入限制重量\n”);   scanf(“%1f”,&limitV);   maxv=0.0;   for (k=0;k find(0,0.0,totV);   for (k=0;k   if (option[k]) printf(“%4d”,k+1);   printf(“\n总价值为%.2f\n”,maxv);   }   作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。   【程序】   # include   # define N 100   double limitW;   int cop[N];   struct ele { double weight;   double value;   } a[N];   int k,n;   struct { int ;   double tw;   double tv;   }twv[N];   void next(int i,double tw,double tv)   { twv.=1;   twv.tw=tw;   twv.tv=tv;   }   double find(struct ele *a,int n)   { int i,k,f;   double maxv,tw,tv,totv;   maxv=0;   for (totv=0.0,k=0;k   totv+=a[k].value;   next(0,0.0,totv);   i=0;   While (i>=0)   { f=twv.;   tw=twv.tw;   tv=twv.tv;   switch(f)   { case 1: twv.++;   if (tw+a.weight<=limitW)   if (i   { next(i+1,tw+a.weight,tv);   i++;   }   else   { maxv=tv;   for (k=0;k   cop[k]=twv[k].!=0;   }   break;   case 0: i--;   break;   default: twv.=0;   if (tv-a.value>maxv)   if (i   { next(i+1,tw,tv-a.value);   i++;   }   else   { maxv=tv-a.value;   for (k=0;k   cop[k]=twv[k].!=0;   }   break;   }   }   return maxv;   }   void main()   { double maxv;   printf(“输入物品种数\n”);   scanf((“%d”,&n);   printf(“输入限制重量\n”);   scanf(“%1f”,&limitW);   printf(“输入各物品的重量和价值\n”);   for (k=0;k   scanf(“%1f%1f”,&a[k].weight,&a[k].value);   maxv=find(a,n);   printf(“\n选中的物品为\n”);   for (k=0;k   if (option[k]) printf(“%4d”,k+1);   printf(“\n总价值为%.2f\n”,maxv);   }   递归的基本概念和特点   程序调用自身的编程技巧称为递归( recursion)。   一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。   一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。   注意:   (1) 递归就是在过程或函数里调用自身;   (2) 在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。
小哇 2019-12-02 01:25:19 0 浏览量 回答数 0

回答

迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。 利用迭代算法解决问题,需要做好以下三个方面的工作: 一、确定迭代变量。在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。 二、建立迭代关系式。所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。 三、对迭代过程进行控制。在什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。 例 1 : 一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。 分析: 这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有 u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,…… 根据这个规律,可以归纳出下面的递推公式: u n = u n - 1 × 2 (n ≥ 2) 对应 u n 和 u n - 1 ,定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系: y=x*2 x=y 让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下: cls x=1 for i=2 to 12 y=x*2 x=y next i print y end 例 2 : 阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 2 20 个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。 分析: 根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴 2 20 个”,即阿米巴分裂 15 次以后得到的个数是 2 20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2 20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。 设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有 x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1) 因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式: x=x/2 ( x 的初值为第 15 次分裂之后的个数 2 20 ) 让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下: cls x=2^20 for i=1 to 15 x=x/2 next i print x end 例 3 : 验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1 。如此经过有限次运算后,总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。 要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。 分析: 定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1 。用 QBASIC 语言把它描述出来就是: if n 为偶数 then n=n/2 else n=n*3+1 end if 这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为: n=1 。参考程序如下: cls input "Please input n=";n do until n=1 if n mod 2=0 then rem 如果 n 为偶数,则调用迭代公式 n=n/2 n=n/2 print "—";n; else n=n*3+1 print "—";n; end if loop end 迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: (1) 选一个方程的近似根,赋给变量x0; (2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; (3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。 若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为: 【算法】迭代法求方程的根 { x0=初始近似根; do { x1=x0; x0=g(x1); /*按特定的方程计算新的近似根*/ } while ( fabs(x0-x1)>Epsilon); printf(“方程的近似根是%f\n”,x0); } 迭代算法也常用于求方程组的根,令 X=(x0,x1,…,xn-1) 设方程组为: xi=gi(X) (I=0,1,…,n-1) 则求方程组根的迭代算法可描述如下: 【算法】迭代法求方程组的根 { for (i=0;i x=初始近似根; do { for (i=0;i y=x; for (i=0;i x=gi(X); for (delta=0.0,i=0;i if (fabs(y-x)>delta) delta=fabs(y-x); } while (delta>Epsilon); for (i=0;i printf(“变量x[%d]的近似根是 %f”,I,x); printf(“\n”); } 具体使用迭代法求根时应注意以下两种可能发生的情况: (1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制; (2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。 递归 递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。 斐波那契数列为:0、1、1、2、3、……,即: fib(0)=0; fib(1)=1; fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 写成递归函数有: int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2); } 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。 在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 【问题】 组合问题 问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1 (4)5、3、2 (5)5、3、1 (6)5、2、1 (7)4、3、2 (8)4、3、1 (9)4、2、1 (10)3、2、1 分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。 【程序】 # include # define MAXN 100 int a[MAXN]; void comb(int m,int k) { int i,j; for (i=m;i>=k;i--) { a[k]=i; if (k>1) comb(i-1,k-1); else { for (j=a[0];j>0;j--) printf(“%4d”,a[j]); printf(“\n”); } } } void main() { a[0]=3; comb(5,3); } 【问题】 背包问题 问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。 设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。 对于第i件物品的选择考虑有两种可能: (1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 (2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 按以上思想写出递归算法如下: try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv) { /*考虑物品i包含在当前方案中的可能性*/ if(包含物品i是可以接受的) { 将物品i包含在当前方案中; if (i try(i+1,tw+物品i的重量,tv); else /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; 恢复物品i不包含状态; } /*考虑物品i不包含在当前方案中的可能性*/ if (不包含物品i仅是可男考虑的) if (i try(i+1,tw,tv-物品i的价值); else /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; } 为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: 物品 0 1 2 3 重量 5 3 2 1 价值 4 4 3 1 并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 按上述算法编写函数和程序如下: 【程序】 # include # define N 100 double limitW,totV,maxV; int option[N],cop[N]; struct { double weight; double value; }a[N]; int n; void find(int i,double tw,double tv) { int k; /*考虑物品i包含在当前方案中的可能性*/ if (tw+a.weight<=limitW) { cop=1; if (i else { for (k=0;k option[k]=cop[k]; maxv=tv; } cop=0; } /*考虑物品i不包含在当前方案中的可能性*/ if (tv-a.value>maxV) if (i else { for (k=0;k option[k]=cop[k]; maxv=tv-a.value; } } void main() { int k; double w,v; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入各物品的重量和价值\n”); for (totv=0.0,k=0;k { scanf(“%1f%1f”,&w,&v); a[k].weight=w; a[k].value=v; totV+=V; } printf(“输入限制重量\n”); scanf(“%1f”,&limitV); maxv=0.0; for (k=0;k find(0,0.0,totV); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); } 作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。 【程序】 # include # define N 100 double limitW; int cop[N]; struct ele { double weight; double value; } a[N]; int k,n; struct { int ; double tw; double tv; }twv[N]; void next(int i,double tw,double tv) { twv.=1; twv.tw=tw; twv.tv=tv; } double find(struct ele *a,int n) { int i,k,f; double maxv,tw,tv,totv; maxv=0; for (totv=0.0,k=0;k totv+=a[k].value; next(0,0.0,totv); i=0; While (i>=0) { f=twv.; tw=twv.tw; tv=twv.tv; switch(f) { case 1: twv.++; if (tw+a.weight<=limitW) if (i { next(i+1,tw+a.weight,tv); i++; } else { maxv=tv; for (k=0;k cop[k]=twv[k].!=0; } break; case 0: i--; break; default: twv.=0; if (tv-a.value>maxv) if (i { next(i+1,tw,tv-a.value); i++; } else { maxv=tv-a.value; for (k=0;k cop[k]=twv[k].!=0; } break; } } return maxv; } void main() { double maxv; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入限制重量\n”); scanf(“%1f”,&limitW); printf(“输入各物品的重量和价值\n”); for (k=0;k scanf(“%1f%1f”,&a[k].weight,&a[k].value); maxv=find(a,n); printf(“\n选中的物品为\n”); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); } 递归的基本概念和特点 程序调用自身的编程技巧称为递归( recursion)。 一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。 一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。 注意: (1) 递归就是在过程或函数里调用自身; (2) 在使用递增归策略时,必须有一个明确的递归结束条件,称为递归出口。
马铭芳 2019-12-02 01:24:44 0 浏览量 回答数 0

回答

迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法,即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点,让计算机对一组指令(或一定步骤)进行重复执行,在每次执行这组指令(或这些步骤)时,都从变量的原值推出它的一个新值。 迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题(一般是解方程或者方程组)的过程,为实现这一过程所使用的方法统称为迭代法(Iterative Method)。 一般可以做如下定义:对于给定的线性方程组x=Bx+f(这里的x、B、f同为矩阵,任意线性方程组都可以变换成此形式),用公式x(k+1)=Bx(k)+f(括号中为上标,代表迭代k次得到的x,初始时k=0)逐步带入求近似解的方法称为迭代法(或称一阶定常迭代法)。如果k趋向无穷大时limx(k)存在,记为x*,称此迭代法收敛。显然x*就是此方程组的解,否则称为迭代法发散。 跟迭代法相对应的是直接法(或者称为一次解法),即一次性的快速解决问题,例如通过开方解决方程x +3= 4。一般如果可能,直接解法总是优先考虑的。但当遇到复杂问题时,特别是在未知量很多,方程为非线性时,我们无法找到直接解法(例如五次以及更高次的代数方程没有解析解,参见阿贝耳定理),这时候或许可以通过迭代法寻求方程(组)的近似解。 最常见的迭代法是牛顿法。其他还包括最速下降法、共轭迭代法、变尺度迭代法、最小二乘法、线性规划、非线性规划、单纯型法、惩罚函数法、斜率投影法、遗传算法、模拟退火等等。 利用迭代算法解决问题,需要做好以下三个方面的工作: 确定迭代变量 在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。 建立迭代关系式 所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以顺推或倒推的方法来完成。 对迭代过程进行控制 在 什么时候结束迭代过程。这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数 是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需 要进一步分析出用来结束迭代过程的条件。 举例 例 1 :一个饲养场引进一只刚出生的新品种兔子,这种兔子从出生的下一个月开始,每月新生一只兔子,新生的兔子也如此繁殖。如果所有的兔子都不死去,问到第 12 个月时,该饲养场共有兔子多少只。 分析:这是一个典型的递推问题。我们不妨假设第 1 个月时兔子的只数为 u 1 ,第 2 个月时兔子的只数为 u 2 ,第 3 个月时兔子的只数为 u 3 ,……根据题意,“这种兔子从出生的下一个月开始,每月新生一只兔子”,则有 u 1 = 1 , u 2 = u 1 + u 1 × 1 = 2 , u 3 = u 2 + u 2 × 1 = 4 ,…… 根据这个规律,可以归纳出下面的递推公式: u n = u(n - 1)× 2 (n ≥ 2) 对应 u n 和 u(n - 1),定义两个迭代变量 y 和 x ,可将上面的递推公式转换成如下迭代关系: y=x*2 x=y 让计算机对这个迭代关系重复执行 11 次,就可以算出第 12 个月时的兔子数。参考程序如下: cls x=1 for i=2 to 12 y=x*2 x=y next i print y end 例 2 :阿米巴用简单分裂的方式繁殖,它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内, 45 分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴 220,220个。试问,开始的时候往容器内放了多少个阿米巴。请编程序算出。 分析:根据题意,阿米巴每 3 分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到 45 分钟后充满容器,需要分裂 45/3=15 次。而“容器最多可以装阿米巴2^ 20 个”,即阿米巴分裂 15 次以后得到的个数是 2^20。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第 15 次分裂之后的 2^20 个,倒推出第 15 次分裂之前(即第 14 次分裂之后)的个数,再进一步倒推出第 13 次分裂之后、第 12 次分裂之后、……第 1 次分裂之前的个数。 设第 1 次分裂之前的个数为 x 0 、第 1 次分裂之后的个数为 x 1 、第 2 次分裂之后的个数为 x 2 、……第 15 次分裂之后的个数为 x 15 ,则有 x 14 =x 15 /2 、 x 13 =x 14 /2 、…… x n-1 =x n /2 (n ≥ 1) 因为第 15 次分裂之后的个数 x 15 是已知的,如果定义迭代变量为 x ,则可以将上面的倒推公式转换成如下的迭代公式: x=x/2 (x 的初值为第 15 次分裂之后的个数 2^20) 让这个迭代公式重复执行 15 次,就可以倒推出第 1 次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。参考程序如下: cls x=2^20 for i=1 to 15 x=x/2 next i print x end ps:java中幂的算法是Math.pow(2,20);返回double,稍微注意一下 例 3 :验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象:对于任意一个自然数 n ,若 n 为偶数,则将其除以 2 ;若 n 为奇数,则将其乘以 3 ,然后再加 1。如此经过有限次运算后,总可以得到自然数 1。人们把谷角静夫的这一发现叫做“谷角猜想”。 要求:编写一个程序,由键盘输入一个自然数 n ,把 n 经过有限次运算后,最终变成自然数 1 的全过程打印出来。 分析:定义迭代变量为 n ,按照谷角猜想的内容,可以得到两种情况下的迭代关系式:当 n 为偶数时, n=n/2 ;当 n 为奇数时, n=n*3+1。用 QBASIC 语言把它描述出来就是: if n 为偶数 then n=n/2 else n=n*3+1 end if 这就是需要计算机重复执行的迭代过程。这个迭代过程需要重复执行多少次,才能使迭代变量 n 最终变成自然数 1 ,这是我们无法计算出来的。因此,还需进一步确定用来结束迭代过程的条件。仔细分析题目要求,不难看出,对任意给定的一个自然数 n ,只要经过有限次运算后,能够得到自然数 1 ,就已经完成了验证工作。因此,用来结束迭代过程的条件可以定义为:n=1。参考程序如下: cls input "Please input n=";n do until n=1 if n mod 2=0 then rem 如果 n 为偶数,则调用迭代公式 n=n/2 n=n/2 print "—";n; else n=n*3+1 print "—";n; end if loop end 迭代法开平方: #include<stdio.h> #include<math.h> void main() { double a,x0,x1; printf("Input a:\n"); scanf("%lf",&a);//为什么在VC6.0中不能写成“scanf("%f",&a);”。 if(a<0) printf("Error!\n"); else { x0=a/2; x1=(x0+a/x0)/2; do { x0=x1; x1=(x0+a/x0)/2; }while(fabs(x0-x1)>=1e-6); } printf("Result:\n"); printf("sqrt(%g)=%g\n",a,x1); } 求平方根的迭代公式:x1=1/2*(x0+a/x0)。 算法:1.先自定一个初值x0,作为a的平方根值,在我们的程序中取a/2作为a的初值;利用迭代公式求出一个x1。此值与真正的a的平方根值相比,误差很大。 ⒉把新求得的x1代入x0中,准备用此新的x0再去求出一个新的x1. ⒊利用迭代公式再求出一个新的x1的值,也就是用新的x0又求出一个新的平方根值x1,此值将更趋近于真正的平方根值。 ⒋比较前后两次求得的平方根值x0和x1,如果它们的差值小于我们指定的值,即达到我们要求的精度,则认为x1就是a的平方根值,去执行步骤5;否则执行步骤2,即循环进行迭代。 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行: ⑴ 选一个方程的近似根,赋给变量x0; ⑵ 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0; ⑶ 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤⑵的计算。 若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为: 【算法】迭代法求方程的根 { x0=初始近似根; do { x1=x0; x0=g(x1); /*按特定的方程计算新的近似根*/ } while (fabs(x0-x1)>Epsilon); printf(“方程的近似根是%f\n”,x0); } 迭代算法也常用于求方程组的根,令 X=(x0,x1,…,xn-1) 设方程组为: xi=gi(X) (I=0,1,…,n-1) 则求方程组根的迭代算法可描述如下: 【算法】迭代法求方程组的根 { for (i=0;i x=初始近似根; do { for (i=0;i y=x; for (i=0;i x=gi(X); for (delta=0.0,i=0;i if (fabs(y-x)>delta) delta=fabs(y-x); } while (delta>Epsilon); for (i=0;i printf(“变量x[%d]的近似根是 %f”,I,x); printf(“\n”); } 具体使用迭代法求根时应注意以下两种可能发生的情况: ⑴ 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制; ⑵ 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。 递归 递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。 能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。 【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。 斐波那契数列为:0、1、1、2、3、……,即: fib(0)=0; fib⑴=1; fib(n)=fib(n-1)+fib(n-2) (当n>1时)。 写成递归函数有: int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2); } 递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问 题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算 fib(n-1)和fib(n- 2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib⑴和fib(0),分别能 立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。 在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib⑴和fib(0)后,返回得到fib⑵的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。 在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。 由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。 【问题】 组合问题 问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为:⑴5、4、3 ⑵5、4、2 ⑶5、4、1 ⑷5、3、2 ⑸5、3、1 ⑹5、2、1 ⑺4、3、2 ⑻4、3、1 ⑼4、2、1 ⑽3、2、1 分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m 个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递 归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。 【程序】 # include # define MAXN 100 int a[MAXN]; void comb(int m,int k) { int i,j; for (i=m;i>=k;i--) { a[k]=i; if (k>1) comb(i-1,k-1); else { for (j=a[0];j>0;j--) printf(“%4d”,a[j]); printf(“\n”); } } } void main() { a[0]=3; comb(5,3); } 【问题】 背包问题 问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。 设n 件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并 保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达 到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止 当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。 对于第i件物品的选择考虑有两种可能: ⑴ 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。 ⑵ 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。 按以上思想写出递归算法如下: try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv) { /*考虑物品i包含在当前方案中的可能性*/ if(包含物品i是可以接受的) { 将物品i包含在当前方案中; if (i try(i+1,tw+物品i的重量,tv); else /*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; 恢复物品i不包含状态; } /*考虑物品i不包含在当前方案中的可能性*/ if (不包含物品i仅是可男考虑的) if (i try(i+1,tw,tv-物品i的价值); else /*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/ 以当前方案作为临时最佳方案保存; } 为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表: 物品 0 1 2 3 重量 5 3 2 1 价值 4 4 3 1 并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。 按上述算法编写函数和程序如下: 【程序】 # include # define N 100 double limitW,totV,maxV; int option[N],cop[N]; struct { double weight; double value; }a[N]; int n; void find(int i,double tw,double tv) { int k; /*考虑物品i包含在当前方案中的可能性*/ if (tw+a.weight<=limitW) { cop=1; if (i else { for (k=0;k option[k]=cop[k]; maxv=tv; } cop=0; } /*考虑物品i不包含在当前方案中的可能性*/ if (tv-a.value>maxV) if (i else { for (k=0;k option[k]=cop[k]; maxv=tv-a.value; } } void main() { int k; double w,v; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入各物品的重量和价值\n”); for (totv=0.0,k=0;k { scanf(“%1f%1f”,&w,&v); a[k].weight=w; a[k].value=v; totV+=V; } printf(“输入限制重量\n”); scanf(“%1f”,&limitV); maxv=0.0; for (k=0;k find(0,0.0,totV); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); } 作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是 从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选 解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在 候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。 对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。 【程序】 # include # define N 100 double limitW; int cop[N]; struct ele { double weight; double value; } a[N]; int k,n; struct { int ; double tw; double tv; }twv[N]; void next(int i,double tw,double tv) { twv.=1; twv tw=tw; twv tv=tv; } double find(struct ele *a,int n) { int i,k,f; double maxv,tw,tv,totv; maxv=0; for (totv=0.0,k=0;k totv+=a[k].value; next(0,0.0,totv); i=0; While (i>=0) { f=twv.; tw=twv tw; tv=twv tv; switch(f) { case 1: twv.++; if (tw+a.weight<=limitW) if (i { next(i+1,tw+a.weight,tv); i++; } else { maxv=tv; for (k=0;k cop[k]=twv[k].!=0; } break; case 0: i--; break; default: twv.=0; if (tv-a.value>maxv) if (i { next(i+1,tw,tv-a.value); i++; } else { maxv=tv-a.value; for (k=0;k cop[k]=twv[k].!=0; } break; } } return maxv; } void main() { double maxv; printf(“输入物品种数\n”); scanf((“%d”,&n); printf(“输入限制重量\n”); scanf(“%1f”,&limitW); printf(“输入各物品的重量和价值\n”); for (k=0;k scanf(“%1f%1f”,&a[k].weight,&a[k].value); maxv=find(a,n); printf(“\n选中的物品为\n”); for (k=0;k if (option[k]) printf(“%4d”,k+1); printf(“\n总价值为%.2f\n”,maxv); }
云篆 2019-12-02 01:25:10 0 浏览量 回答数 0

回答

字符串,是Java中最常用的一个数据类型了。 本文,也是对于Java中字符串相关知识的一个补充,主要来介绍一下字符串拼接相关的知识。本文基于jdk1.8.0_181。 字符串拼接 字符串拼接是我们在Java代码中比较经常要做的事情,就是把多个字符串拼接到一起。 我们都知道,String是Java中一个不可变的类,所以他一旦被实例化就无法被修改。 不可变类的实例一旦创建,其成员变量的值就不能被修改。这样设计有很多好处,比如可以缓存hashcode、使用更加便利以及更加安全等。 但是,既然字符串是不可变的,那么字符串拼接又是怎么回事呢? 字符串不变性与字符串拼接 其实,所有的所谓字符串拼接,都是重新生成了一个新的字符串。下面一段字符串拼接代码: String s = "abcd"; s = s.concat("ef"); 其实最后我们得到的s已经是一个新的字符串了。如下图  s中保存的是一个重新创建出来的String对象的引用。 那么,在Java中,到底如何进行字符串拼接呢?字符串拼接有很多种方式,这里简单介绍几种比较常用的。 使用+拼接字符串 在Java中,拼接字符串最简单的方式就是直接使用符号+来拼接。如: String wechat = "Hollis"; String introduce = "每日更新Java相关技术文章"; String hollis = wechat + "," + introduce; 这里要特别说明一点,有人把Java中使用+拼接字符串的功能理解为运算符重载。其实并不是,Java是不支持运算符重载的。这其实只是Java提供的一个语法糖。后面再详细介绍。 运算符重载:在计算机程序设计中,运算符重载(英语:operator overloading)是多态的一种。运算符重载,就是对已有的运算符重新进行定义,赋予其另一种功能,以适应不同的数据类型。 语法糖:语法糖(Syntactic sugar),也译为糖衣语法,是由英国计算机科学家彼得·兰丁发明的一个术语,指计算机语言中添加的某种语法,这种语法对语言的功能没有影响,但是更方便程序员使用。语法糖让程序更加简洁,有更高的可读性。 concat 除了使用+拼接字符串之外,还可以使用String类中的方法concat方法来拼接字符串。如: String wechat = "Hollis"; String introduce = "每日更新Java相关技术文章"; String hollis = wechat.concat(",").concat(introduce); StringBuffer 关于字符串,Java中除了定义了一个可以用来定义字符串常量的String类以外,还提供了可以用来定义字符串变量的StringBuffer类,它的对象是可以扩充和修改的。 使用StringBuffer可以方便的对字符串进行拼接。如: StringBuffer wechat = new StringBuffer("Hollis"); String introduce = "每日更新Java相关技术文章"; StringBuffer hollis = wechat.append(",").append(introduce); StringBuilder 除了StringBuffer以外,还有一个类StringBuilder也可以使用,其用法和StringBuffer类似。如: StringBuilder wechat = new StringBuilder("Hollis"); String introduce = "每日更新Java相关技术文章"; StringBuilder hollis = wechat.append(",").append(introduce); StringUtils.join 除了JDK中内置的字符串拼接方法,还可以使用一些开源类库中提供的字符串拼接方法名,如apache.commons中提供的StringUtils类,其中的join方法可以拼接字符串。 String wechat = "Hollis"; String introduce = "每日更新Java相关技术文章"; System.out.println(StringUtils.join(wechat, ",", introduce)); 这里简单说一下,StringUtils中提供的join方法,最主要的功能是:将数组或集合以某拼接符拼接到一起形成新的字符串,如: String []list ={"Hollis","每日更新Java相关技术文章"}; String result= StringUtils.join(list,","); System.out.println(result); //结果:Hollis,每日更新Java相关技术文章 并且,Java8中的String类中也提供了一个静态的join方法,用法和StringUtils.join类似。 以上就是比较常用的五种在Java种拼接字符串的方式,那么到底哪种更好用呢?为什么阿里巴巴Java开发手册中不建议在循环体中使用+进行字符串拼接呢?  (阿里巴巴Java开发手册中关于字符串拼接的规约) 使用+拼接字符串的实现原理 前面提到过,使用+拼接字符串,其实只是Java提供的一个语法糖, 那么,我们就来解一解这个语法糖,看看他的内部原理到底是如何实现的。 还是这样一段代码。我们把他生成的字节码进行反编译,看看结果。 String wechat = "Hollis"; String introduce = "每日更新Java相关技术文章"; String hollis = wechat + "," + introduce; 反编译后的内容如下,反编译工具为jad。 String wechat = "Hollis"; String introduce = "\u6BCF\u65E5\u66F4\u65B0Java\u76F8\u5173\u6280\u672F\u6587\u7AE0";//每日更新Java相关技术文章 String hollis = (new StringBuilder()).append(wechat).append(",").append(introduce).toString(); 通过查看反编译以后的代码,我们可以发现,原来字符串常量在拼接过程中,是将String转成了StringBuilder后,使用其append方法进行处理的。 那么也就是说,Java中的+对字符串的拼接,其实现原理是使用StringBuilder.append。 concat是如何实现的 我们再来看一下concat方法的源代码,看一下这个方法又是如何实现的。 public String concat(String str) { int otherLen = str.length(); if (otherLen == 0) { return this; } int len = value.length; char buf[] = Arrays.copyOf(value, len + otherLen); str.getChars(buf, len); return new String(buf, true); } 这段代码首先创建了一个字符数组,长度是已有字符串和待拼接字符串的长度之和,再把两个字符串的值复制到新的字符数组中,并使用这个字符数组创建一个新的String对象并返回。 通过源码我们也可以看到,经过concat方法,其实是new了一个新的String,这也就呼应到前面我们说的字符串的不变性问题上了。 StringBuffer和StringBuilder 接下来我们看看StringBuffer和StringBuilder的实现原理。 和String类类似,StringBuilder类也封装了一个字符数组,定义如下: char[] value; 与String不同的是,它并不是final的,所以他是可以修改的。另外,与String不同,字符数组中不一定所有位置都已经被使用,它有一个实例变量,表示数组中已经使用的字符个数,定义如下: int count; 其append源码如下: public StringBuilder append(String str) { super.append(str); return this; } 该类继承了AbstractStringBuilder类,看下其append方法: public AbstractStringBuilder append(String str) { if (str == null) return appendNull(); int len = str.length(); ensureCapacityInternal(count + len); str.getChars(0, len, value, count); count += len; return this; } append会直接拷贝字符到内部的字符数组中,如果字符数组长度不够,会进行扩展。 StringBuffer和StringBuilder类似,最大的区别就是StringBuffer是线程安全的,看一下StringBuffer的append方法。 public synchronized StringBuffer append(String str) { toStringCache = null; super.append(str); return this; } 该方法使用synchronized进行声明,说明是一个线程安全的方法。而StringBuilder则不是线程安全的。 StringUtils.join是如何实现的 通过查看StringUtils.join的源代码,我们可以发现,其实他也是通过StringBuilder来实现的。 public static String join(final Object[] array, String separator, final int startIndex, final int endIndex) { if (array == null) { return null; } if (separator == null) { separator = EMPTY; } // endIndex - startIndex > 0: Len = NofStrings *(len(firstString) + len(separator)) // (Assuming that all Strings are roughly equally long) final int noOfItems = endIndex - startIndex; if (noOfItems <= 0) { return EMPTY; } final StringBuilder buf = new StringBuilder(noOfItems * 16); for (int i = startIndex; i < endIndex; i++) { if (i > startIndex) { buf.append(separator); } if (array[i] != null) { buf.append(array[i]); } } return buf.toString(); } 效率比较 既然有这么多种字符串拼接的方法,那么到底哪一种效率最高呢?我们来简单对比一下。 long t1 = System.currentTimeMillis(); //这里是初始字符串定义 for (int i = 0; i < 50000; i++) { //这里是字符串拼接代码 } long t2 = System.currentTimeMillis(); System.out.println("cost:" + (t2 - t1)); 我们使用形如以上形式的代码,分别测试下五种字符串拼接代码的运行时间。得到结果如下: + cost:5119 StringBuilder cost:3 StringBuffer cost:4 concat cost:3623 StringUtils.join cost:25726 从结果可以看出,用时从短到长的对比是: StringBuilder<StringBuffer<concat<+<StringUtils.join StringBuffer在StringBuilder的基础上,做了同步处理,所以在耗时上会相对多一些。 StringUtils.join也是使用了StringBuilder,并且其中还是有很多其他操作,所以耗时较长,这个也容易理解。其实StringUtils.join更擅长处理字符串数组或者列表的拼接。 那么问题来了,前面我们分析过,其实使用+拼接字符串的实现原理也是使用的StringBuilder,那为什么结果相差这么多,高达1000多倍呢? 我们再把以下代码反编译下: long t1 = System.currentTimeMillis(); String str = "hollis"; for (int i = 0; i < 50000; i++) { String s = String.valueOf(i); str += s; } long t2 = System.currentTimeMillis(); System.out.println("+ cost:" + (t2 - t1)); 反编译后代码如下: long t1 = System.currentTimeMillis(); String str = "hollis"; for(int i = 0; i < 50000; i++) { String s = String.valueOf(i); str = (new StringBuilder()).append(str).append(s).toString(); } long t2 = System.currentTimeMillis(); System.out.println((new StringBuilder()).append("+ cost:").append(t2 - t1).toString()); 我们可以看到,反编译后的代码,在for循环中,每次都是new了一个StringBuilder,然后再把String转成StringBuilder,再进行append。 而频繁的新建对象当然要耗费很多时间了,不仅仅会耗费时间,频繁的创建对象,还会造成内存资源的浪费。 所以,阿里巴巴Java开发手册建议:循环体内,字符串的连接方式,使用 StringBuilder 的 append 方法进行扩展。而不要使用+。 总结 本文介绍了什么是字符串拼接,虽然字符串是不可变的,但是还是可以通过新建字符串的方式来进行字符串的拼接。 常用的字符串拼接方式有五种,分别是使用+、使用concat、使用StringBuilder、使用StringBuffer以及使用StringUtils.join。 由于字符串拼接过程中会创建新的对象,所以如果要在一个循环体中进行字符串拼接,就要考虑内存问题和效率问题。 因此,经过对比,我们发现,直接使用StringBuilder的方式是效率最高的。因为StringBuilder天生就是设计来定义可变字符串和字符串的变化操作的。 但是,还要强调的是: 1、如果不是在循环体中进行字符串拼接的话,直接使用+就好了。 2、如果在并发场景中进行字符串拼接的话,要使用StringBuffer来代替StringBuilder。
montos 2020-06-01 21:30:32 0 浏览量 回答数 0

回答

索引,索引!!!为经常查询的字段建索引!! 但也不能过多地建索引。insert和delete等改变表记录的操作会导致索引重排,增加数据库负担。优化目标1.减少 IO 次数 IO永远是数据库最容易瓶颈的地方,这是由数据库的职责所决定的,大部分数据库操作中超过90%的时间都是 IO 操作所占用的,减少 IO 次数是 SQL 优化中需要第一优先考虑,当然,也是收效最明显的优化手段。2.降低 CPU 计算 除了 IO 瓶颈之外,SQL优化中需要考虑的就是 CPU 运算量的优化了。order by, group by,distinct … 都是消耗 CPU 的大户(这些操作基本上都是 CPU 处理内存中的数据比较运算)。当我们的 IO 优化做到一定阶段之后,降低 CPU 计算也就成为了我们 SQL 优化的重要目标优化方法改变 SQL 执行计划 明确了优化目标之后,我们需要确定达到我们目标的方法。对于 SQL 语句来说,达到上述2个目标的方法其实只有一个,那就是改变 SQL 的执行计划,让他尽量“少走弯路”,尽量通过各种“捷径”来找到我们需要的数据,以达到 “减少 IO 次数” 和 “降低 CPU 计算” 的目标分析复杂的SQL语句explain 例如: mysql> explain select from (select from ( select * from t3 where id=3952602) a) b; id select_type table type possible_keys key key_len ref rows Extra 1 PRIMARY system NULL NULL NULL NULL 1 2 DERIVED system NULL NULL NULL NULL 1 3 DERIVED t3 const PRIMARY,idx_t3_id PRIMARY 4 1 很显然这条SQL是从里向外的执行,就是从id=3 向上执行.show show tables或show tables from database_name; // 显示当前数据库中所有表的名称 show databases; // 显示mysql中所有数据库的名称 show columns from table_name from database_name; 或MySQL show columns from database_name.table_name; // 显示表中列名称 show grants for user_name@localhost; // 显示一个用户的权限,显示结果类似于grant 命令 show index from table_name; // 显示表的索引 show status; // 显示一些系统特定资源的信息,例如,正在运行的线程数量 show variables; // 显示系统变量的名称和值show processlist; // 显示系统中正在运行的所有进程,也就是当前正在执行的查询。 show table status; // 显示当前使用或者指定的database中的每个表的信息。信息包括表类型和表的最新更新时间 show privileges; // 显示服务器所支持的不同权限 show create database database_name; // 显示create database 语句是否能够创建指定的数据库 show create table table_name; // 显示create database 语句是否能够创建指定的数据库 show engies; // 显示安装以后可用的存储引擎和默认引擎。 show innodb status; // 显示innoDB存储引擎的状态 show logs; // 显示BDB存储引擎的日志 show warnings; // 显示最后一个执行的语句所产生的错误、警告和通知 show errors; // 只显示最后一个执行语句所产生的错误关于enum 存在争议。 对于取值有限且固定的字段,推荐使用enum而非varchar。但是!!其他数据库可能不支持,导致了难于迁移的问题。开启缓存查询 对于完全相同的sql,使用已经存在的执行计划,从而跳过解析和生成执行计划的过程。 应用场景:有一个不经常变更的表,且服务器收到该表的大量相同查询。对于频繁更新的表,查询缓存是不适合的 Mysql 判断是否命中缓存的办法很简单,首先会将要缓存的结果放在引用表中,然后使用查询语句,数据库名称,客户端协议的版本等因素算出一个hash值,这个hash值与引用表中的结果相关联。如果在执行查询时,根据一些相关的条件算出的hash值能与引用表中的数据相关联,则表示查询命中 查询必须是完全相同的(逐字节相同)才能够被认为是相同的。另外,同样的查询字符串由于其它原因可能认为是不同的。使用不同的数据库、不同的协议版本或者不同 默认字符集的查询被认为是不同的查询并且分别进行缓存。 下面sql查询缓存认为是不同的: SELECT * FROM tbl_name Select * from tbl_name 缓存机制失效的场景 如果查询语句中包含一些不确定因素时(例如包含 函数Current()),该查询不会被缓存,不确定因素主要包含以下情况 · 引用了一些返回值不确定的函数 · 引用自定义函数(UDFs)。 · 引用自定义变量。 · 引用mysql系统数据库中的表。 · 下面方式中的任何一种: SELECT ...IN SHARE MODE SELECT ...FOR UPDATE SELECT ...INTO OUTFILE ... SELECT ...INTO DUMPFILE ... SELECT * FROM ...WHERE autoincrement_col IS NULL · 使用TEMPORARY表。 · 不使用任何表。 · 用户有某个表的列级别权限。额外的消耗 如果使用查询缓存,在进行读写操作时会带来额外的资源消耗,消耗主要体现在以下几个方面 · 查询的时候会检查是否命中缓存,这个消耗相对较小 · 如果没有命中查询缓存,MYSQL会判断该查询是否可以被缓存,而且系统中还没有对应的缓存,则会将其结果写入查询缓存 · 如果一个表被更改了,那么使用那个表的所有缓冲查询将不再有效,并且从缓冲区中移出。这包括那些映射到改变了的表的使用MERGE表的查询。一个表可以被许多类型的语句更改,例如INSERT、UPDATE、DELETE、TRUNCATE、ALTER TABLE、DROP TABLE或DROP DATABASE。 对于InnoDB而言,事物的一些特性还会限制查询缓存的使用。当在事物A中修改了B表时,因为在事物提交之前,对B表的修改对其他的事物而言是不可见的。为了保证缓存结果的正确性,InnoDB采取的措施让所有涉及到该B表的查询在事物A提交之前是不可缓存的。如果A事物长时间运行,会严重影响查询缓存的命中率 查询缓存的空间不要设置的太大。 因为查询缓存是靠一个全局锁操作保护的,如果查询缓存配置的内存比较大且里面存放了大量的查询结果,当查询缓存失效的时候,会长时间的持有这个全局锁。因为查询缓存的命中检测操作以及缓存失效检测也都依赖这个全局锁,所以可能会导致系统僵死的情况静态表速度更快定长类型和变长类型 CHAR(M)定义的列的长度为固定的,M取值可以为0~255之间,当保存CHAR值时,在它们的右边填充空格以达到指定的长度。当检索到CHAR值时,尾部的空格被删除掉。在存储或检索过程中不进行大小写转换。CHAR存储定长数据很方便,CHAR字段上的索引效率级高,比如定义char(10),那么不论你存储的数据是否达到了10个字节,都要占去10个字节的空间,不足的自动用空格填充。 VARCHAR(M)定义的列的长度为可变长字符串,M取值可以为0~65535之间,(VARCHAR的最大有效长度由最大行大小和使用的字符集确定。整体最大长度是65,532字节)。VARCHAR值保存时只保存需要的字符数,另加一个字节来记录长度(如果列声明的长度超过255,则使用两个字节)。VARCHAR值保存时不进行填充。当值保存和检索时尾部的空格仍保留,符合标准SQL。varchar存储变长数据,但存储效率没有CHAR高。 如果一个字段可能的值是不固定长度的,我们只知道它不可能超过10个字符,把它定义为 VARCHAR(10)是最合算的。VARCHAR类型的实际长度是它的值的实际长度+1。空间上考虑,用varchar合适;从效率上考虑,用char合适,关键是根据实际情况找到权衡点。VARCHAR和TEXT、BlOB类型 VARCHAR,BLOB和TEXT类型是变长类型,对于其存储需求取决于列值的实际长度(在前面的表格中用L表示),而不是取决于类型的最大可能尺寸。 BLOB和TEXT类型需要1,2,3或4个字节来记录列值的长度,这取决于类型的最大可能长度。VARCHAR需要定义大小,有65535字节的最大限制;TEXT则不需要。如果你把一个超过列类型最大长度的值赋给一个BLOB或TEXT列,值被截断以适合它。 一个BLOB是一个能保存可变数量的数据的二进制的大对象。4个BLOB类型TINYBLOB、BLOB、MEDIUMBLOB和LONGBLOB仅仅在他们能保存值的最大长度方面有所不同。 BLOB 可以储存图片,TEXT不行,TEXT只能储存纯文本文件。 在BLOB和TEXT类型之间的唯一差别是对BLOB值的排序和比较以大小写敏感方式执行,而对TEXT值是大小写不敏感的。换句话说,一个TEXT是一个大小写不敏感的BLOB。 效率来说基本是char>varchar>text,但是如果使用的是Innodb引擎的话,推荐使用varchar代替char char和varchar可以有默认值,text不能指定默认值静态表和动态表 静态表字段长度固定,自动填充,读写速度很快,便于缓存和修复,但比较占硬盘,动态表是字段长度不固定,节省硬盘,但更复杂,容易产生碎片,速度慢,出问题后不容易重建。当只需要一条数据的时候,使用limit 1 表记录中的一行尽量不要超过一个IO单元 区分in和exist select * from 表A where id in (select id from 表B)这句相当于select from 表A where exists(select from 表B where 表B.id=表A.id)对于表A的每一条数据,都执行select * from 表B where 表B.id=表A.id的存在性判断,如果表B中存在表A当前行相同的id,则exists为真,该行显示,否则不显示 区分in和exists主要是造成了驱动顺序的改变(这是性能变化的关键),如果是exists,那么以外层表为驱动表,先被访问,如果是IN,那么先执行子查询。 所以IN适合于外表大而内表小的情况;EXISTS适合于外表小而内表大的情况复杂多表尽量少用join MySQL 的优势在于简单,但这在某些方面其实也是其劣势。MySQL 优化器效率高,但是由于其统计信息的量有限,优化器工作过程出现偏差的可能性也就更多。对于复杂的多表 Join,一方面由于其优化器受限,再者在 Join 这方面所下的功夫还不够,所以性能表现离 Oracle 等关系型数据库前辈还是有一定距离。但如果是简单的单表查询,这一差距就会极小甚至在有些场景下要优于这些数据库前辈。尽量用join代替子查询 虽然 Join 性能并不佳,但是和 MySQL 的子查询比起来还是有非常大的性能优势。 MySQL需要为内层查询语句的查询结果建立一个临时表。然后外层查询语句在临时表中查询记录。查询完毕后,MySQL需要插销这些临时表。所以在MySQL中可以使用连接查询来代替子查询。连接查询不需要建立临时表,其速度比子查询要快。尽量少排序 排序操作会消耗较多的 CPU 资源,所以减少排序可以在缓存命中率高等 IO 能力足够的场景下会较大影响 SQL 的响应时间。 对于MySQL来说,减少排序有多种办法,比如: 上面误区中提到的通过利用索引来排序的方式进行优化 减少参与排序的记录条数 非必要不对数据进行排序尽量避免select * 大多数关系型数据库都是按照行(row)的方式存储,而数据存取操作都是以一个固定大小的IO单元(被称作 block 或者 page)为单位,一般为4KB,8KB… 大多数时候,每个IO单元中存储了多行,每行都是存储了该行的所有字段(lob等特殊类型字段除外)。 所以,我们是取一个字段还是多个字段,实际上数据库在表中需要访问的数据量其实是一样的。 也有例外情况,那就是我们的这个查询在索引中就可以完成,也就是说当只取 a,b两个字段的时候,不需要回表,而c这个字段不在使用的索引中,需要回表取得其数据。在这样的情况下,二者的IO量会有较大差异。尽量少or 当 where 子句中存在多个条件以“或”并存的时候,MySQL 的优化器并没有很好的解决其执行计划优化问题,再加上 MySQL 特有的 SQL 与 Storage 分层架构方式,造成了其性能比较低下,很多时候使用 union all 或者是union(必要的时候)的方式来代替“or”会得到更好的效果。尽量用 union all 代替 union union 和 union all 的差异主要是前者需要将两个(或者多个)结果集合并后再进行唯一性过滤操作,这就会涉及到排序,增加大量的 CPU 运算,加大资源消耗及延迟。所以当我们可以确认不可能出现重复结果集或者不在乎重复结果集的时候,尽量使用 union all 而不是 union。尽量早过滤 在 SQL 编写中同样可以使用这一原则来优化一些 Join 的 SQL。比如我们在多个表进行分页数据查询的时候,我们最好是能够在一个表上先过滤好数据分好页,然后再用分好页的结果集与另外的表 Join,这样可以尽可能多的减少不必要的 IO 操作,大大节省 IO 操作所消耗的时间。避免类型转换 这里所说的“类型转换”是指 where 子句中出现 column 字段的类型和传入的参数类型不一致的时候发生的类型转换: 人为在column_name 上通过转换函数进行转换直接导致 MySQL(实际上其他数据库也会有同样的问题)无法使用索引,如果非要转换,应该在传入的参数上进行转换,由数据库自己进行转换, 如果我们传入的数据类型和字段类型不一致,同时我们又没有做任何类型转换处理,MySQL 可能会自己对我们的数据进行类型转换操作,也可能不进行处理而交由存储引擎去处理,这样一来,就会出现索引无法使用的情况而造成执行计划问题。优先优化高并发的 SQL,而不是执行频率低某些“大”SQL 对于破坏性来说,高并发的 SQL 总是会比低频率的来得大,因为高并发的 SQL 一旦出现问题,甚至不会给我们任何喘息的机会就会将系统压跨。而对于一些虽然需要消耗大量 IO 而且响应很慢的 SQL,由于频率低,即使遇到,最多就是让整个系统响应慢一点,但至少可能撑一会儿,让我们有缓冲的机会。从全局出发优化,而不是片面调整 尤其是在通过调整索引优化 SQL 的执行计划的时候,千万不能顾此失彼,因小失大。尽可能对每一条运行在数据库中的SQL进行 explain 知道 SQL 的执行计划才能判断是否有优化余地,才能判断是否存在执行计划问题。在对数据库中运行的 SQL 进行了一段时间的优化之后,很明显的问题 SQL 可能已经很少了,大多都需要去发掘,这时候就需要进行大量的 explain 操作收集执行计划,并判断是否需要进行优化。尽量避免where子句中对字段进行null值的判断 会导致引擎放弃索引,进而进行全表扫描。 尽量不要给数据库留null值,尽可能地使用not null填充数据库。可以为每个null型的字段设置一个和null对应的实际内容表述。避免在where中使用!=, >, <操作符 否则引擎放弃使用索引,进行全表扫描。常用查询字段建索引避免在where中使用or imagein和not in关键词慎用,容易导致全表扫面 对连续的数值尽量用between通配符查询也容易导致全表扫描避免在where子句中使用局部变量 sql只有在运行时才解析局部变量。而优化程序必须在编译时访问执行计划,这时并不知道变量值,所以无法作为索引的输入项。 image避免在where子句中对字段进行表达式操作 会导致引擎放弃使用索引 image避免在where子句中对字段进行函数操作 image不要where子句的‘=’左边进行函数、算术运算或其他表达式运算 系统可能无法正确使用索引避免update全部字段 只update需要的字段。频繁调用会引起明显的性能消耗,同时带来大量日志。索引不是越多越好 一个表的索引数最好不要超过6个尽量使用数字型字段而非字符型 因为处理查询和连接时会逐个比较字符串的每个字符,而对于数字型而言只需要比较一次就够了。尽可能用varchar/nvarchar代替char/nchar 变长字段存储空间小,对于查询来说,在一个相对较小的字段内搜索效率更高。。。?避免频繁创建和删除临时表,减少系统表资源消耗select into和create table 新建临时表时,如果一次性插入数据量很大,使用select into代替create table,避免造成大量log,以提高速度。 如果数据量不大,为了缓和系统表的资源,先create table,再insert。 拆分大的DELETE和INSERT语句 因为这两个操作是会锁表的,对于高访问量的站点来说,锁表时间内积累的访问数、数据库连接、打开的文件数等等,可能不仅仅让WEB服务崩溃,还会让整台服务器马上挂了。 所以,一定要拆分,使用LIMIT条件休眠一段时间,批量处理。
wangccsy 2019-12-02 01:50:30 0 浏览量 回答数 0

回答

      递归公式 Pc,t = 0.88 * Pc-1,t + 0.12 * Pc-1,t-1       其中c是自变量,范围(1,201),步长为1,Pc,t为函数值(c,t为P的下标)。且P1,1=0.12, Pc,0=0; 当c<t时,Pc,t=0。       程序如下: function [p] = diguihashu(c,t)  if nargin==0,  c=1;t=0;  end  ct=[c,t];  action_ct=num2str(ct);  switch(action_ct)  case '1 1'  p=0.12;  case action_ct  temp=str2num(action_ct);  cc=temp(1);tt=temp(2);  if tt==0||cc<tt  p=0;  else  p=0.88*diguihashu(c-1,t)+0.12*diguihashu(c-1,t-1);  end  otherwise,  error('Unkonwn acction string!');  end  %测试结果:  >> pct=diguihashu(12,5)  pct =  0.0034 %下面是画图程序: clear p=zeros(15,15); for c=1:15     for t=1:15         p(c,t)=diguihashu(c,t);     end end [cc,tt]=meshgrid(1:15,1:15); surf(cc,tt,p) xlabel('c') ylabel('t')        MATLAB是美国MathWorks公司出品的商业数学软件,用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境,主要包括MATLAB和Simulink两大部分。       MATLAB是matrix&laboratory两个词的组合,意为矩阵工厂(矩阵实验室)。是由美国mathworks公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中,为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案,并在很大程度上摆脱了传统非交互式程序设计语言(如C、Fortran)的编辑模式,代表了当今国际科学计算软件的先进水平。       MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。MATLAB可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语言的程序等,主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。       MATLAB的基本数据单位是矩阵,它的指令表达式与数学、工程中常用的形式十分相似,故用MATLAB来解算问题要比用C,FORTRAN等语言完成相同的事情简捷得多,并且MATLAB也吸收了像Maple等软件的优点,使MATLAB成为一个强大的数学软件。在新的版本中也加入了对C,FORTRAN,C++,JAVA的支持。
小旋风柴进 2019-12-02 01:24:32 0 浏览量 回答数 0

问题

【面试必备】2020最新Java集合容器面试题

【面试必备】2020最新Java集合容器面试题 集合容器概述 什么是集合 集合框架:用于存储数据的容器。 集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。 任何集合框架都包含三大块内容:对外的...
剑曼红尘 2020-03-24 14:00:04 7 浏览量 回答数 1

问题

【精品问答】Python二级考试题库

1.关于数据的存储结构,以下选项描述正确的是( D ) A: 数据所占的存储空间量 B: 存储在外存中的数据 C: 数据在计算机中的顺序存储方式 D: 数据的逻辑结构在计算机中的表示 2.关于线性...
珍宝珠 2019-12-01 22:03:38 7177 浏览量 回答数 3

回答

异常是程序中的一些错误,但并不是所有的错误都是异常,并且错误有时候是可以避免的。 比如说,你的代码少了一个分号,那么运行出来结果是提示是错误 java.lang.Error;如果你用System.out.println(11/0),那么你是因为你用0做了除数,会抛出 java.lang.ArithmeticException 的异常。 异常发生的原因有很多,通常包含以下几大类: 用户输入了非法数据。 要打开的文件不存在。 网络通信时连接中断,或者JVM内存溢出。 这些异常有的是因为用户错误引起,有的是程序错误引起的,还有其它一些是因为物理错误引起的。- 要理解Java异常处理是如何工作的,你需要掌握以下三种类型的异常: 检查性异常:最具代表的检查性异常是用户错误或问题引起的异常,这是程序员无法预见的。例如要打开一个不存在文件时,一个异常就发生了,这些异常在编译时不能被简单地忽略。 运行时异常: 运行时异常是可能被程序员避免的异常。与检查性异常相反,运行时异常可以在编译时被忽略。 错误: 错误不是异常,而是脱离程序员控制的问题。错误在代码中通常被忽略。例如,当栈溢出时,一个错误就发生了,它们在编译也检查不到的。 Exception 类的层次 所有的异常类是从 java.lang.Exception 类继承的子类。 Exception 类是 Throwable 类的子类。除了Exception类外,Throwable还有一个子类Error 。 Java 程序通常不捕获错误。错误一般发生在严重故障时,它们在Java程序处理的范畴之外。 Error 用来指示运行时环境发生的错误。 例如,JVM 内存溢出。一般地,程序不会从错误中恢复。 异常类有两个主要的子类:IOException 类和 RuntimeException 类。 在 Java 内置类中(接下来会说明),有大部分常用检查性和非检查性异常。 Java 内置异常类 Java 语言定义了一些异常类在 java.lang 标准包中。 标准运行时异常类的子类是最常见的异常类。由于 java.lang 包是默认加载到所有的 Java 程序的,所以大部分从运行时异常类继承而来的异常都可以直接使用。 Java 根据各个类库也定义了一些其他的异常,下面的表中列出了 Java 的非检查性异常。 异常 描述 ArithmeticException 当出现异常的运算条件时,抛出此异常。例如,一个整数"除以零"时,抛出此类的一个实例。 ArrayIndexOutOfBoundsException 用非法索引访问数组时抛出的异常。如果索引为负或大于等于数组大小,则该索引为非法索引。 ArrayStoreException 试图将错误类型的对象存储到一个对象数组时抛出的异常。 ClassCastException 当试图将对象强制转换为不是实例的子类时,抛出该异常。 IllegalArgumentException 抛出的异常表明向方法传递了一个不合法或不正确的参数。 IllegalMonitorStateException 抛出的异常表明某一线程已经试图等待对象的监视器,或者试图通知其他正在等待对象的监视器而本身没有指定监视器的线程。 IllegalStateException 在非法或不适当的时间调用方法时产生的信号。换句话说,即 Java 环境或 Java 应用程序没有处于请求操作所要求的适当状态下。 IllegalThreadStateException 线程没有处于请求操作所要求的适当状态时抛出的异常。 IndexOutOfBoundsException 指示某排序索引(例如对数组、字符串或向量的排序)超出范围时抛出。 NegativeArraySizeException 如果应用程序试图创建大小为负的数组,则抛出该异常。 NullPointerException 当应用程序试图在需要对象的地方使用 null 时,抛出该异常 NumberFormatException 当应用程序试图将字符串转换成一种数值类型,但该字符串不能转换为适当格式时,抛出该异常。 SecurityException 由安全管理器抛出的异常,指示存在安全侵犯。 StringIndexOutOfBoundsException 此异常由 String 方法抛出,指示索引或者为负,或者超出字符串的大小。 UnsupportedOperationException 当不支持请求的操作时,抛出该异常。 下面的表中列出了 Java 定义在 java.lang 包中的检查性异常类。 异常 描述 ClassNotFoundException 应用程序试图加载类时,找不到相应的类,抛出该异常。 CloneNotSupportedException 当调用 Object 类中的 clone 方法克隆对象,但该对象的类无法实现 Cloneable 接口时,抛出该异常。 IllegalAccessException 拒绝访问一个类的时候,抛出该异常。 InstantiationException 当试图使用 Class 类中的 newInstance 方法创建一个类的实例,而指定的类对象因为是一个接口或是一个抽象类而无法实例化时,抛出该异常。 InterruptedException 一个线程被另一个线程中断,抛出该异常。 NoSuchFieldException 请求的变量不存在 NoSuchMethodException 请求的方法不存在 异常方法 下面的列表是 Throwable 类的主要方法: 序号 方法及说明 1 public String getMessage() 返回关于发生的异常的详细信息。这个消息在Throwable 类的构造函数中初始化了。 2 public Throwable getCause() 返回一个Throwable 对象代表异常原因。 3 public String toString() 使用getMessage()的结果返回类的串级名字。 4 public void printStackTrace() 打印toString()结果和栈层次到System.err,即错误输出流。 5 public StackTraceElement [] getStackTrace() 返回一个包含堆栈层次的数组。下标为0的元素代表栈顶,最后一个元素代表方法调用堆栈的栈底。 6 public Throwable fillInStackTrace() 用当前的调用栈层次填充Throwable 对象栈层次,添加到栈层次任何先前信息中。 捕获异常 使用 try 和 catch 关键字可以捕获异常。try/catch 代码块放在异常可能发生的地方。 try/catch代码块中的代码称为保护代码,使用 try/catch 的语法如下: try { // 程序代码 }catch(ExceptionName e1) { //Catch 块 } Catch 语句包含要捕获异常类型的声明。当保护代码块中发生一个异常时,try 后面的 catch 块就会被检查。 如果发生的异常包含在 catch 块中,异常会被传递到该 catch 块,这和传递一个参数到方法是一样。 实例 下面的例子中声明有两个元素的一个数组,当代码试图访问数组的第三个元素的时候就会抛出一个异常。 ExcepTest.java 文件代码: // 文件名 : ExcepTest.java import java.io.*; public class ExcepTest{ public static void main(String args[]){ try{ int a[] = new int[2]; System.out.println("Access element three :" + a[3]); }catch(ArrayIndexOutOfBoundsException e){ System.out.println("Exception thrown :" + e); } System.out.println("Out of the block"); } } 以上代码编译运行输出结果如下: Exception thrown :java.lang.ArrayIndexOutOfBoundsException: 3 Out of the block 多重捕获块 一个 try 代码块后面跟随多个 catch 代码块的情况就叫多重捕获。 多重捕获块的语法如下所示: try{ // 程序代码 }catch(异常类型1 异常的变量名1){ // 程序代码 }catch(异常类型2 异常的变量名2){ // 程序代码 }catch(异常类型3 异常的变量名3){ // 程序代码 } 上面的代码段包含了 3 个 catch块。 可以在 try 语句后面添加任意数量的 catch 块。 如果保护代码中发生异常,异常被抛给第一个 catch 块。 如果抛出异常的数据类型与 ExceptionType1 匹配,它在这里就会被捕获。 如果不匹配,它会被传递给第二个 catch 块。 如此,直到异常被捕获或者通过所有的 catch 块。 实例 该实例展示了怎么使用多重 try/catch。 try { file = new FileInputStream(fileName); x = (byte) file.read(); } catch(FileNotFoundException f) { // Not valid! f.printStackTrace(); return -1; } catch(IOException i) { i.printStackTrace(); return -1; } throws/throw 关键字: 如果一个方法没有捕获到一个检查性异常,那么该方法必须使用 throws 关键字来声明。throws 关键字放在方法签名的尾部。 也可以使用 throw 关键字抛出一个异常,无论它是新实例化的还是刚捕获到的。 下面方法的声明抛出一个 RemoteException 异常: import java.io.*; public class className { public void deposit(double amount) throws RemoteException { // Method implementation throw new RemoteException(); } //Remainder of class definition } 一个方法可以声明抛出多个异常,多个异常之间用逗号隔开。 例如,下面的方法声明抛出 RemoteException 和 InsufficientFundsException: import java.io.*; public class className { public void withdraw(double amount) throws RemoteException, InsufficientFundsException { // Method implementation } //Remainder of class definition } finally关键字 finally 关键字用来创建在 try 代码块后面执行的代码块。 无论是否发生异常,finally 代码块中的代码总会被执行。 在 finally 代码块中,可以运行清理类型等收尾善后性质的语句。 finally 代码块出现在 catch 代码块最后,语法如下: try{ // 程序代码 }catch(异常类型1 异常的变量名1){ // 程序代码 }catch(异常类型2 异常的变量名2){ // 程序代码 }finally{ // 程序代码 } 实例 ExcepTest.java 文件代码: public class ExcepTest{ public static void main(String args[]){ int a[] = new int[2]; try{ System.out.println("Access element three :" + a[3]); }catch(ArrayIndexOutOfBoundsException e){ System.out.println("Exception thrown :" + e); } finally{ a[0] = 6; System.out.println("First element value: " +a[0]); System.out.println("The finally statement is executed"); } } } 以上实例编译运行结果如下: Exception thrown :java.lang.ArrayIndexOutOfBoundsException: 3 First element value: 6 The finally statement is executed 注意下面事项: catch 不能独立于 try 存在。 在 try/catch 后面添加 finally 块并非强制性要求的。 try 代码后不能既没 catch 块也没 finally 块。 try, catch, finally 块之间不能添加任何代码。 声明自定义异常 在 Java 中你可以自定义异常。编写自己的异常类时需要记住下面的几点。 所有异常都必须是 Throwable 的子类。 如果希望写一个检查性异常类,则需要继承 Exception 类。 如果你想写一个运行时异常类,那么需要继承 RuntimeException 类。 可以像下面这样定义自己的异常类: class MyException extends Exception{ } 只继承Exception 类来创建的异常类是检查性异常类。 下面的 InsufficientFundsException 类是用户定义的异常类,它继承自 Exception。 一个异常类和其它任何类一样,包含有变量和方法。 实例 以下实例是一个银行账户的模拟,通过银行卡的号码完成识别,可以进行存钱和取钱的操作。 InsufficientFundsException.java 文件代码: // 文件名InsufficientFundsException.java import java.io.*; //自定义异常类,继承Exception类 public class InsufficientFundsException extends Exception { //此处的amount用来储存当出现异常(取出钱多于余额时)所缺乏的钱 private double amount; public InsufficientFundsException(double amount) { this.amount = amount; } public double getAmount() { return amount; } } 为了展示如何使用我们自定义的异常类, 在下面的 CheckingAccount 类中包含一个 withdraw() 方法抛出一个 InsufficientFundsException 异常。 CheckingAccount.java 文件代码: // 文件名称 CheckingAccount.java import java.io.*; //此类模拟银行账户 public class CheckingAccount { //balance为余额,number为卡号 private double balance; private int number; public CheckingAccount(int number) { this.number = number; } //方法:存钱 public void deposit(double amount) { balance += amount; } //方法:取钱 public void withdraw(double amount) throws InsufficientFundsException { if(amount <= balance) { balance -= amount; } else { double needs = amount - balance; throw new InsufficientFundsException(needs); } } //方法:返回余额 public double getBalance() { return balance; } //方法:返回卡号 public int getNumber() { return number; } } 下面的 BankDemo 程序示范了如何调用 CheckingAccount 类的 deposit() 和 withdraw() 方法。 BankDemo.java 文件代码: //文件名称 BankDemo.java public class BankDemo { public static void main(String [] args) { CheckingAccount c = new CheckingAccount(101); System.out.println("Depositing $500..."); c.deposit(500.00); try { System.out.println("\nWithdrawing $100..."); c.withdraw(100.00); System.out.println("\nWithdrawing $600..."); c.withdraw(600.00); }catch(InsufficientFundsException e) { System.out.println("Sorry, but you are short $" + e.getAmount()); e.printStackTrace(); } } } 编译上面三个文件,并运行程序 BankDemo,得到结果如下所示: Depositing $500... Withdrawing $100... Withdrawing $600... Sorry, but you are short $200.0 InsufficientFundsException at CheckingAccount.withdraw(CheckingAccount.java:25) at BankDemo.main(BankDemo.java:13) 通用异常 在Java中定义了两种类型的异常和错误。 JVM(Java虚拟机) 异常:由 JVM 抛出的异常或错误。例如:NullPointerException 类,ArrayIndexOutOfBoundsException 类,ClassCastException 类。 程序级异常:由程序或者API程序抛出的异常。例如 IllegalArgumentException 类,IllegalStateException 类。
游客2q7uranxketok 2021-02-07 20:08:10 0 浏览量 回答数 0

问题

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

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

回答

本人学习数据结构时看到的不错的总结,共享一下了 文件有一组记录组成,记录有若干数据项组成,唯一标识记录的数据项称关键字; 排序是将文件按关键字的递增(减)顺序排列; 排序文件中有相同的关键字时,若排序后相对次序保持不变的称稳定排序,否则称不稳定排序; 在排序过程中,文件放在内存中处理不涉及数据的内、外存交换的称内部排序,反之称外部排序; 排序算法的基本操作:1)比较关键字的大小;2)改变指向记录的指针或移动记录本身。 评价排序方法的标准:1)执行时间;2)所需辅助空间,辅助空间为O(1)称就地排序;另要注意算法的复杂程度。 若关键字类型没有比较运算符,可事先定义宏或函数表示比较运算。 8.2插入排序 8.2.1直接插入排序 实现过程: void insertsort(seqlist R) { int i, j; for(i=2;i<=n;i++) if(R[i].key< R[i-1].key{ R[0]=R[i];j=i-1; do{R[j+1]=R[j];j--;} while(R[0].key R[j+1]=R[0]; } } 复制代码 算法中引入监视哨R[0]的作用是:1)保存 R[i] 复制代码 的副本;2)简化边界条件,防止循环下标越界。 关键字比较次数最大为(n+2)(n-1)/2;记录移动次数最大为(n+4)(n-1)/2; 算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序; 8.2.2希尔排序 实现过程:是将直接插入排序的间隔变为d。d的取值要注意:1)最后一次必为1;2)避免d值互为倍数; 关键字比较次数最大为n^1.25;记录移动次数最大为1.6n^1.25; 算法的平均时间是O(n^1.25);是一种就地的不稳定的排序; 8.3交换排序 8.3.1冒泡排序 实现过程:从下到上相邻两个比较,按小在上原则扫描一次,确定最小值,重复n-1次。 关键字比较次数最小为n-1、最大为n(n-1)/2;记录移动次数最小为0,最大为3n(n-1)/2; 算法的最好时间是O(n);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的稳定的排序; 8.3.2快速排序 实现过程:将第一个值作为基准,设置i,j指针交替从两头与基准比较,有交换后,交换j,i。i=j时确定基准,并以其为界限将序列分为两段。重复以上步骤。 关键字比较次数最好为nlog2n+nC(1)、最坏为n(n-1)/2; 算法的最好时间是O(nlog2n);最坏时间是O(n^2);平均时间是O(nlog2n);辅助空间为O(log2n);是一种不稳定排序; 8.4选择排序 8.4.1直接选择排序 实现过程:选择序列中最小的插入第一位,在剩余的序列中重复上一步,共重复n-1次。 关键字比较次数为n(n-1)/2;记录移动次数最小为0,最大为3(n-1); 算法的最好时间是O(n^2);最坏时间是O(n^2);平均时间是O(n^2);是一种就地的不稳定的排序; 8.4.2堆排序 实现过程:把序列按层次填入完全二叉树,调整位置使双亲大于或小于孩子,建立初始大根或小根堆,调整树根与最后一个叶子的位置,排除该叶子重新调整位置。 算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);是一种就地的不稳定排序; 8.5归并排序 实现过程:将初始序列分为2个一组,最后单数轮空,对每一组排序后作为一个单元,对2个单元排序,直到结束。 算法的最好时间是O(nlog2n);最坏时间是O(nlog2n);平均时间是O(nlog2n);辅助空间为O(n);是一种稳定排序; 8.6分配排序 8.6.1箱排序 实现过程:按关键字的取值范围确定箱子的个数,将序列按关键字放入箱中,输出非空箱的关键字。 在桶内分配和收集,及对各桶进行插入排序的时间为O(n),算法的期望时间是O(n),最坏时间是O(n^2)。 8.6.2基数排序 实现过程:按基数设置箱子,对关键字从低位到高位依次进行箱排序。 算法的最好时间是O(d*n+d*rd);最坏时间是O(d*n+d*rd);平均时间是O(d*n+d*rd);辅助空间O(n+rd);是一种稳定排序; 8.7各种内部排序方法的比较和选择 按平均时间复杂度分为: 1) 平方阶排序:直接插入、直接选择、冒泡排序; 2) 线性对数阶:快速排序、堆排序、归并排序; 3) 指数阶:希尔排序; 4) 线性阶:箱排序、基数排序。 选择合适排序方法的因素:1)待排序的记录数;2)记录的大小;3)关键字的结构和初始状态;4)对稳定性的要求;5)语言工具的条件;6)存储结构;7)时间和辅助空间复杂度。 结论: 1) 若规模较小可采用直接插入或直接选择排序; 2) 若文件初始状态基本有序可采用直接插入、冒泡或随机快速排序; 3) 若规模较大可采用快速排序、堆排序或归并排序; 4) 任何借助于比较的排序,至少需要O(nlog2n)的时间,箱排序和基数排序只适用于有明显结构特征的关键字; 5) 有的语言没有提供指针及递归,使归并、快速、基数排序算法复杂; 6) 记录规模较大时为避免大量移动记录可用链表作为存储结构,如插入、归并、基数排序,但快速、堆排序在链表上难以实现,可提取关键字建立索引表,然后对索引表排序。 附二: 第八章排序 ************************************************************************************* 记录中可用某一项来标识一个记录,则称为关键字项,该数据项的值称为关键字。 排序是使文件中的记录按关键字递增(或递减)次序排列起来。·基本操作:比较关键字大小;改变指向记录的指针或移动记录。 ·存储结构:顺序结构、链表结构、索引结构。 经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法是稳定的,否则排序算法是不稳定的。 排序过程中不涉及数据的内、外存交换则称之为"内部排序"(内排序),反之,若存在数据的内外存交换,则称之为外排序。 内部排序方法可分五类:插入排序、选择排序、交换排序、归并排序和分配排序。 评价排序算法好坏的标准主要有两条:执行时间和所需的辅助空间,另外算法的复杂程序也是要考虑的一个因素。 ************************************************************************************* 插入排序:·直接插入排序: ·逐个向前插入到合适位置。 ·哨兵(监视哨)有两个作用: ·作为临变量存放 R[i] 复制代码 ·是在查找循环中用来监视下标变量j是否越界。 ·直接插入排序是就地的稳定排序。时间复杂度为O(n^2),比较次数为(n+2)(n-1)/2;移动次数为(n+4)(n-1)/2; ·希尔排序: ·等间隔的数据比较并按要求顺序排列,最后间隔为1。 ·希尔排序是就地的不稳定排序。时间复杂度为O(n^1.25),比较次数为(n^1.25);移动次数为(1.6n^1.25); 交换排序:·冒泡排序:·自下向上确定最轻的一个。·自上向下确定最重的一个。·自下向上确定最轻的一个,后自上向下确定最重的一个。 ·冒泡排序是就地的稳定排序。时间复杂度为O(n^2),比较次数为n(n-1)/2;移动次数为3n(n-1)/2; ·快速排序:·以第一个元素为参考基准,设定、动两个指针,发生交换后指针交换位置,直到指针重合。重复直到排序完成。 ·快速排序是非就地的不稳定排序。时间复杂度为O(nlog2n),比较次数为n(n-1)/2; 选择排序:·直接选择排序: ·选择最小的放在比较区前。 ·直接选择排序就地的不稳定排序。时间复杂度为O(n^2)。比较次数为n(n-1)/2; ·堆排序 ·建堆:按层次将数据填入完全二叉树,从int(n/2)处向前逐个调整位置。 ·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆,直到全断开。 ·堆排序是就地不稳定的排序,时间复杂度为O(nlog2n),不适宜于记录数较少的文件。。 归并排序: ·先两个一组排序,形成(n+1)/2组,再将两组并一组,直到剩下一组为止。 ·归并排序是非就地稳定排序,时间复杂度是O(nlog2n), 分配排序:·箱排序: ·按关键字的取值范围确定箱子数,按关键字投入箱子,链接所有非空箱。 ·箱排序的平均时间复杂度是线性的O(n). ·基数排序:·从低位到高位依次对关键字进行箱排序。 ·基数排序是非就稳定的排序,时间复杂度是O(d*n+d*rd)。 各种排序方法的比较和选择: ·.待排序的记录数目n;n较大的要用时间复杂度为O(nlog2n)的排序方法; ·记录的大小(规模);记录大最好用链表作为存储结构,而快速排序和堆排序在链表上难于实现; ·关键字的结构及其初始状态; ·对稳定性的要求; ·语言工具的条件; ·存储结构; ·时间和辅助空间复杂度。 排序(sort)或分类 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下: 输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn。 输出:Ril,Ri2,…,Rin,使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。 1.被排序对象--文件 被排序的对象--文件由一组记录组成。 记录则由若干个数据项(或域)组成。其中有一项可用来标识一个记录,称为关键字项。该数据项的值称为关键字(Key)。 注意: 在不易产生混淆时,将关键字项简称为关键字。 2.排序运算的依据--关键字 用来作排序运算依据的关键字,可以是数字类型,也可以是字符类型。 关键字的选取应根据问题的要求而定。 【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录,则必须用"准考证号"作为关键字。若要按照考生的总分数排名次,则需用"总分数"作为关键字。 排序的稳定性 当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。 在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。 注意: 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。 排序方法的分类 1.按是否涉及数据的内、外存交换分 在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为内部排序(简称内排序);反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。 注意: ① 内排序适用于记录个数不很多的小文件 ② 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。 2.按策略划分内部排序方法 可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。 排序算法分析 1.排序算法的基本操作 大多数排序算法都有两个基本的操作: (1) 比较两个关键字的大小; (2) 改变指向记录的指针或移动记录本身。 注意: 第(2)种基本操作的实现依赖于待排序记录的存储方式。 2.待排文件的常用存储方式 (1) 以顺序表(或直接用向量)作为存储结构 排序过程:对记录本身进行物理重排(即通过关键字之间的比较判定,将记录移到合适的位置) (2) 以链表作为存储结构 排序过程:无须移动记录,仅需修改指针。通常将这类排序称为链表(或链式)排序; (3) 用顺序的方式存储待排序的记录,但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表) 排序过程:只需对辅助表的表目进行物理重排(即只移动辅助表的表目,而不移动记录本身)。适用于难于在链表上实现,仍需避免排序过程中移动记录的排序方法。 3.排序算法性能评价 (1) 评价排序算法好坏的标准 评价排序算法好坏的标准主要有两条: ① 执行时间和所需的辅助空间 ② 算法本身的复杂程度 (2) 排序算法的空间复杂度 若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间是O(1),则称之为就地排序(In-PlaceSou)。 非就地排序一般要求的辅助空间为O(n)。 (3) 排序算法的时间开销 大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模,还取决于输入实例中数据的状态。
马铭芳 2019-12-02 01:19:07 0 浏览量 回答数 0

问题

Java技术1000问(3)【精品问答】

为了方便Java开发者快速找到相关技术问题和答案,开发者社区策划了Java技术1000问内容,包含最基础的Java语言概述、数据类型和运算符、面向对象等维度内容。 我们会以每天至少50条的速度,增...
问问小秘 2020-06-02 14:27:10 11463 浏览量 回答数 3

回答

遍历一个 List 有哪些不同的方式?每种方法的实现原理是什么?Java 中 List 遍历的最佳实践是什么? 遍历方式有以下几种: for 循环遍历,基于计数器。在集合外部维护一个计数器,然后依次读取每一个位置的元素,当读取到最后一个元素后停止。 迭代器遍历,Iterator。Iterator 是面向对象的一个设计模式,目的是屏蔽不同数据集合的特点,统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。 foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现,使用时不需要显式声明 Iterator 或计数器。优点是代码简洁,不易出错;缺点是只能做简单的遍历,不能在遍历过程中操作数据集合,例如删除、替换。 最佳实践:Java Collections 框架中提供了一个 RandomAccess 接口,用来标记 List 实现是否支持 Random Access。 如果一个数据集合实现了该接口,就意味着它支持 Random Access,按位置读取元素的平均时间复杂度为 O(1),如ArrayList。如果没有实现该接口,表示不支持 Random Access,如LinkedList。 推荐的做法就是,支持 Random Access 的列表可用 for 循环遍历,否则建议用 Iterator 或 foreach 遍历。 说一下 ArrayList 的优缺点 ArrayList的优点如下: ArrayList 底层以数组实现,是一种随机访问模式。ArrayList 实现了 RandomAccess 接口,因此查找的时候非常快。ArrayList 在顺序添加一个元素的时候非常方便。 ArrayList 的缺点如下: 删除元素的时候,需要做一次元素复制操作。如果要复制的元素很多,那么就会比较耗费性能。插入元素的时候,也需要做一次元素复制操作,缺点同上。 ArrayList 比较适合顺序添加、随机访问的场景。 如何实现数组和 List 之间的转换? 数组转 List:使用 Arrays. asList(array) 进行转换。List 转数组:使用 List 自带的 toArray() 方法。 代码示例: ArrayList 和 LinkedList 的区别是什么? 数据结构实现:ArrayList 是动态数组的数据结构实现,而 LinkedList 是双向链表的数据结构实现。随机访问效率:ArrayList 比 LinkedList 在随机访问的时候效率要高,因为 LinkedList 是线性的数据存储方式,所以需要移动指针从前往后依次查找。增加和删除效率:在非首尾的增加和删除操作,LinkedList 要比 ArrayList 效率要高,因为 ArrayList 增删操作要影响数组内的其他数据的下标。内存空间占用:LinkedList 比 ArrayList 更占内存,因为 LinkedList 的节点除了存储数据,还存储了两个引用,一个指向前一个元素,一个指向后一个元素。线程安全:ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全; 综合来说,在需要频繁读取集合中的元素时,更推荐使用 ArrayList,而在插入和删除操作较多时,更推荐使用 LinkedList。 补充:数据结构基础之双向链表 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。 ArrayList 和 Vector 的区别是什么? 这两个类都实现了 List 接口(List 接口继承了 Collection 接口),他们都是有序集合 线程安全:Vector 使用了 Synchronized 来实现线程同步,是线程安全的,而 ArrayList 是非线程安全的。性能:ArrayList 在性能方面要优于 Vector。扩容:ArrayList 和 Vector 都会根据实际的需要动态的调整容量,只不过在 Vector 扩容每次会增加 1 倍,而 ArrayList 只会增加 50%。 Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。 Arraylist不是同步的,所以在不需要保证线程安全时时建议使用Arraylist。 插入数据时,ArrayList、LinkedList、Vector谁速度较快?阐述 ArrayList、Vector、LinkedList 的存储性能和特性? ArrayList、LinkedList、Vector 底层的实现都是使用数组方式存储数据。数组元素数大于实际存储的数据以便增加和插入元素,它们都允许直接按序号索引元素,但是插入元素要涉及数组元素移动等内存操作,所以索引数据快而插入数据慢。 Vector 中的方法由于加了 synchronized 修饰,因此 Vector 是线程安全容器,但性能上较ArrayList差。 LinkedList 使用双向链表实现存储,按序号索引数据需要进行前向或后向遍历,但插入数据时只需要记录当前项的前后项即可,所以 LinkedList 插入速度较快。 多线程场景下如何使用 ArrayList? ArrayList 不是线程安全的,如果遇到多线程场景,可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样: 为什么 ArrayList 的 elementData 加上 transient 修饰? ArrayList 中的数组定义如下: private transient Object[] elementData; 再看一下 ArrayList 的定义: public class ArrayList extends AbstractList implements List<E>, RandomAccess, Cloneable, java.io.Serializable 可以看到 ArrayList 实现了 Serializable 接口,这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化,重写了 writeObject 实现: 每次序列化时,先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素,然后遍历 elementData,只序列化已存入的元素,这样既加快了序列化的速度,又减小了序列化之后的文件大小。 List 和 Set 的区别 List , Set 都是继承自Collection 接口 List 特点:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。 Set 特点:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。 另外 List 支持for循环,也就是通过下标来遍历,也可以用迭代器,但是set只能用迭代,因为他无序,无法用下标来取得想要的值。 Set和List对比 Set:检索元素效率低下,删除和插入效率高,插入和删除不会引起元素位置改变。 List:和数组类似,List可以动态增长,查找元素效率高,插入删除元素效率低,因为会引起其他元素位置改变 Set接口 说一下 HashSet 的实现原理? HashSet 是基于 HashMap 实现的,HashSet的值存放于HashMap的key上,HashMap的value统一为PRESENT,因此 HashSet 的实现比较简单,相关 HashSet 的操作,基本上都是直接调用底层 HashMap 的相关方法来完成,HashSet 不允许重复的值。 HashSet如何检查重复?HashSet是如何保证数据不可重复的? 向HashSet 中add ()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合equles 方法比较。 HashSet 中的add ()方法会使用HashMap 的put()方法。 HashMap 的 key 是唯一的,由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V。所以不会重复( HashMap 比较key是否相等是先比较hashcode 再比较equals )。 以下是HashSet 部分源码: hashCode()与equals()的相关规定: 如果两个对象相等,则hashcode一定也是相同的 两个对象相等,对两个equals方法返回true 两个对象有相同的hashcode值,它们也不一定是相等的 综上,equals方法被覆盖过,则hashCode方法也必须被覆盖 hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个对象无论如何都不会相等(即使这两个对象指向相同的数据)。 ** ==与equals的区别** ==是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存空间的值是不是相同 ==是指对内存地址进行比较 equals()是对字符串的内容进行比较3.==指引用是否相同 equals()指的是值是否相同 HashSet与HashMap的区别 Queue BlockingQueue是什么? Java.util.concurrent.BlockingQueue是一个队列,在进行检索或移除一个元素的时候,它会等待队列变为非空;当在添加一个元素时,它会等待队列中的可用空间。BlockingQueue接口是Java集合框架的一部分,主要用于实现生产者-消费者模式。我们不需要担心等待生产者有可用的空间,或消费者有可用的对象,因为它都在BlockingQueue的实现类中被处理了。Java提供了集中BlockingQueue的实现,比如ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue,、SynchronousQueue等。 在 Queue 中 poll()和 remove()有什么区别? 相同点:都是返回第一个元素,并在队列中删除返回的对象。 不同点:如果没有元素 poll()会返回 null,而 remove()会直接抛出 NoSuchElementException 异常。 代码示例: Queue queue = new LinkedList (); queue. offer("string"); // add System. out. println(queue. poll()); System. out. println(queue. remove()); System. out. println(queue. size()); Map接口 说一下 HashMap 的实现原理? HashMap概述: HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。 HashMap的数据结构: 在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。 HashMap 基于 Hash 算法实现的 当我们往Hashmap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标存储时,如果出现hash值相同的key,此时有两种情况。(1)如果key相同,则覆盖原始值;(2)如果key不同(出现冲突),则将当前的key-value放入链表中获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值。理解了以上过程就不难明白HashMap是如何解决hash冲突的问题,核心就是使用了数组的存储方式,然后将冲突的key的对象放入链表中,一旦发现冲突就在链表中做进一步的对比。 需要注意Jdk 1.8中对HashMap的实现做了优化,当链表中的节点数据超过八个之后,该链表会转为红黑树来提高查询效率,从原来的O(n)到O(logn) HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做拉链法的方式可以解决哈希冲突。 JDK1.8之前 JDK1.8之前采用的是拉链法。拉链法:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。 JDK1.8之后 相比于之前的版本,jdk1.8在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。 JDK1.7 VS JDK1.8 比较 JDK1.8主要解决或优化了一下问题: resize 扩容优化引入了红黑树,目的是避免单条链表过长而影响查询效率,红黑树算法请参考解决了多线程死循环问题,但仍是非线程安全的,多线程时可能会造成数据丢失问题。 HashMap的put方法的具体流程? 当我们put的时候,首先计算 key的hash值,这里调用了 hash方法,hash方法实际是让key.hashCode()与key.hashCode()>>>16进行异或操作,高16bit补0,一个数和0异或不变,所以 hash 函数大概的作用就是:高16bit不变,低16bit和高16bit做了一个异或,目的是减少碰撞。按照函数注释,因为bucket数组大小是2的幂,计算下标index = (table.length - 1) & hash,如果不做 hash 处理,相当于散列生效的只有几个低 bit 位,为了减少散列的碰撞,设计者综合考虑了速度、作用、质量之后,使用高16bit和低16bit异或来简单处理减少碰撞,而且JDK8中用了复杂度 O(logn)的树结构来提升碰撞下的性能。 putVal方法执行流程图 ①.判断键值对数组table[i]是否为空或为null,否则执行resize()进行扩容; ②.根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③; ③.判断table[i]的首个元素是否和key一样,如果相同直接覆盖value,否则转向④,这里的相同指的是hashCode以及equals; ④.判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对,否则转向⑤; ⑤.遍历table[i],判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插入操作;遍历过程中若发现key已经存在直接覆盖value即可; ⑥.插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold,如果超过,进行扩容。 HashMap的扩容操作是怎么实现的? ①.在jdk1.8中,resize方法是在hashmap中的键值对大于阀值时或者初始化时,就调用resize方法进行扩容; ②.每次扩展的时候,都是扩展2倍; ③.扩展后Node对象的位置要么在原位置,要么移动到原偏移量两倍的位置。 在putVal()中,我们看到在这个函数里面使用到了2次resize()方法,resize()方法表示的在进行第一次初始化时会对其进行扩容,或者当该数组的实际大小大于其临界值值(第一次为12),这个时候在扩容的同时也会伴随的桶上面的元素进行重新分发,这也是JDK1.8版本的一个优化的地方,在1.7中,扩容之后需要重新去计算其Hash值,根据Hash值对其进行分发,但在1.8版本中,则是根据在同一个桶的位置中进行判断(e.hash & oldCap)是否为0,重新进行hash分配后,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上 HashMap是怎么解决哈希冲突的? 答:在解决这个问题之前,我们首先需要知道什么是哈希冲突,而在了解哈希冲突之前我们还要知道什么是哈希才行; 什么是哈希? Hash,一般翻译为“散列”,也有直接音译为“哈希”的,这就是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值(哈希值);这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。 所有散列函数都有如下一个基本特性**:根据同一散列函数计算出的散列值如果不同,那么输入值肯定也不同。但是,根据同一散列函数计算出的散列值如果相同,输入值不一定相同**。 什么是哈希冲突? 当两个不同的输入值,根据同一散列函数计算出相同的散列值的现象,我们就把它叫做碰撞(哈希碰撞)。 HashMap的数据结构 在Java中,保存数据有两种比较简单的数据结构:数组和链表。数组的特点是:寻址容易,插入和删除困难;链表的特点是:寻址困难,但插入和删除容易;所以我们将数组和链表结合在一起,发挥两者各自的优势,使用一种叫做链地址法的方式可以解决哈希冲突: 这样我们就可以将拥有相同哈希值的对象组织成一个链表放在hash值所对应的bucket下,但相比于hashCode返回的int类型,我们HashMap初始的容量大小DEFAULT_INITIAL_CAPACITY = 1 << 4(即2的四次方16)要远小于int类型的范围,所以我们如果只是单纯的用hashCode取余来获取对应的bucket这将会大大增加哈希碰撞的概率,并且最坏情况下还会将HashMap变成一个单链表,所以我们还需要对hashCode作一定的优化 hash()函数 上面提到的问题,主要是因为如果使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode取值出的高位也参与运算,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动,在JDK 1.8中的hash()函数如下: static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算(高低位异或) } 这比在JDK 1.7中,更为简洁,相比在1.7中的4次位运算,5次异或运算(9次扰动),在1.8中,只进行了1次位运算和1次异或运算(2次扰动); JDK1.8新增红黑树 通过上面的链地址法(使用散列表)和扰动函数我们成功让我们的数据分布更平均,哈希碰撞减少,但是当我们的HashMap中存在大量数据时,加入我们某个bucket下对应的链表有n个元素,那么遍历时间复杂度就为O(n),为了针对这个问题,JDK1.8在HashMap中新增了红黑树的数据结构,进一步使得遍历复杂度降低至O(logn); 总结 简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的: 使用链地址法(使用散列表)来链接拥有相同hash值的数据;使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均;引入红黑树进一步降低遍历的时间复杂度,使得遍历更快; **能否使用任何类作为 Map 的 key? **可以使用任何类作为 Map 的 key,然而在使用之前,需要考虑以下几点: 如果类重写了 equals() 方法,也应该重写 hashCode() 方法。 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。 如果一个类没有使用 equals(),不应该在 hashCode() 中使用它。 用户自定义 Key 类最佳实践是使之为不可变的,这样 hashCode() 值可以被缓存起来,拥有更好的性能。不可变的类也可以确保 hashCode() 和 equals() 在未来不会改变,这样就会解决与可变相关的问题了。 为什么HashMap中String、Integer这样的包装类适合作为K? 答:String、Integer等包装类的特性能够保证Hash值的不可更改性和计算准确性,能够有效的减少Hash碰撞的几率 都是final类型,即不可变性,保证key的不可更改性,不会存在获取hash值不同的情况 内部已重写了equals()、hashCode()等方法,遵守了HashMap内部的规范(不清楚可以去上面看看putValue的过程),不容易出现Hash值计算错误的情况; 如果使用Object作为HashMap的Key,应该怎么办呢? 答:重写hashCode()和equals()方法 重写hashCode()是因为需要计算存储数据的存储位置,需要注意不要试图从散列码计算中排除掉一个对象的关键部分来提高性能,这样虽然能更快但可能会导致更多的Hash碰撞; 重写equals()方法,需要遵守自反性、对称性、传递性、一致性以及对于任何非null的引用值x,x.equals(null)必须返回false的这几个特性,目的是为了保证key在哈希表中的唯一性; HashMap为什么不直接使用hashCode()处理后的哈希值直接作为table的下标 答:hashCode()方法返回的是int整数类型,其范围为-(2 ^ 31)~(2 ^ 31 - 1),约有40亿个映射空间,而HashMap的容量范围是在16(初始化默认值)~2 ^ 30,HashMap通常情况下是取不到最大值的,并且设备上也难以提供这么多的存储空间,从而导致通过hashCode()计算出的哈希值可能不在数组大小范围内,进而无法匹配存储位置; 那怎么解决呢? HashMap自己实现了自己的hash()方法,通过两次扰动使得它自己的哈希值高低位自行进行异或运算,降低哈希碰撞概率也使得数据分布更平均; 在保证数组长度为2的幂次方的时候,使用hash()运算之后的值与运算(&)(数组长度 - 1)来获取数组下标的方式进行存储,这样一来是比取余操作更加有效率,二来也是因为只有当数组长度为2的幂次方时,h&(length-1)才等价于h%length,三来解决了“哈希值与数组大小范围不匹配”的问题; HashMap 的长度为什么是2的幂次方 为了能让 HashMap 存取高效,尽量较少碰撞,也就是要尽量把数据分配均匀,每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。 这个算法应该如何设计呢? 我们首先可能会想到采用%取余的操作来实现。但是,重点来了:“取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作(也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方;)。” 并且 采用二进制位操作 &,相对于%能够提高运算效率,这就解释了 HashMap 的长度为什么是2的幂次方。 那为什么是两次扰动呢? 答:这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性&均匀性,最终减少Hash冲突,两次就够了,已经达到了高位低位同时参与运算的目的; HashMap 与 HashTable 有什么区别? 线程安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过 synchronized 修饰。(如果你要保证线程安全的话就使用 ConcurrentHashMap 吧!); 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高一点。另外,HashTable 基本被淘汰,不要在代码中使用它; 对Null key 和Null value的支持: HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null,直接抛NullPointerException。 **初始容量大小和每次扩充容量大小的不同 **: ①创建时如果不指定容量初始值,Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。②创建时如果给定了容量初始值,那么 Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为2的幂次方大小。也就是说 HashMap 总是使用2的幂作为哈希表的大小,后面会介绍到为什么是2的幂次方。 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。 推荐使用:在 Hashtable 的类注释可以看到,Hashtable 是保留类不建议使用,推荐在单线程环境下使用 HashMap 替代,如果需要多线程使用则用 ConcurrentHashMap 替代。 如何决定使用 HashMap 还是 TreeMap? 对于在Map中插入、删除和定位元素这类操作,HashMap是最好的选择。然而,假如你需要对一个有序的key集合进行遍历,TreeMap是更好的选择。基于你的collection的大小,也许向HashMap中添加元素会更快,将map换为TreeMap进行有序key的遍历。 HashMap 和 ConcurrentHashMap 的区别 ConcurrentHashMap对整个桶数组进行了分割分段(Segment),然后在每一个分段上都用lock锁进行保护,相对于HashTable的synchronized锁的粒度更精细了一些,并发性能更好,而HashMap没有锁机制,不是线程安全的。(JDK1.8之后ConcurrentHashMap启用了一种全新的方式实现,利用CAS算法。) HashMap的键值对允许有null,但是ConCurrentHashMap都不允许。 ConcurrentHashMap 和 Hashtable 的区别? ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。 底层数据结构: JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟HashMap1.8的结构一样,数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的; 实现线程安全的方式(重要): ① 在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。(默认分配16个Segment,比Hashtable效率提高16倍。) 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在JDK1.8中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;② Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。 两者的对比图: HashTable: JDK1.7的ConcurrentHashMap: JDK1.8的ConcurrentHashMap(TreeBin: 红黑二叉树节点 Node: 链表节点): 答:ConcurrentHashMap 结合了 HashMap 和 HashTable 二者的优势。HashMap 没有考虑同步,HashTable 考虑了同步的问题。但是 HashTable 在每次同步执行时都要锁住整个结构。 ConcurrentHashMap 锁的方式是稍微细粒度的。 ConcurrentHashMap 底层具体实现知道吗?实现原理是什么? JDK1.7 首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据时,其他段的数据也能被其他线程访问。 在JDK1.7中,ConcurrentHashMap采用Segment + HashEntry的方式进行实现,结构如下: 一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似,是一种数组和链表结构,一个 Segment 包含一个 HashEntry 数组,每个 HashEntry 是一个链表结构的元素,每个 Segment 守护着一个HashEntry数组里的元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment的锁。 该类包含两个静态内部类 HashEntry 和 Segment ;前者用来封装映射表的键值对,后者用来充当锁的角色;Segment 是一种可重入的锁 ReentrantLock,每个 Segment 守护一个HashEntry 数组里得元素,当对 HashEntry 数组的数据进行修改时,必须首先获得对应的 Segment 锁。 JDK1.8 在JDK1.8中,放弃了Segment臃肿的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash不冲突,就不会产生并发,效率又提升N倍。 结构如下: 如果该节点是TreeBin类型的节点,说明是红黑树结构,则通过putTreeVal方法往红黑树中插入节点;如果binCount不为0,说明put操作对数据产生了影响,如果当前链表的个数达到8个,则通过treeifyBin方法转化为红黑树,如果oldVal不为空,说明是一次更新操作,没有对元素个数产生影响,则直接返回旧值;如果插入的是一个新节点,则执行addCount()方法尝试更新元素个数baseCount; 辅助工具类 Array 和 ArrayList 有何区别? Array 可以存储基本数据类型和对象,ArrayList 只能存储对象。Array 是指定固定大小的,而 ArrayList 大小是自动扩展的。Array 内置方法没有 ArrayList 多,比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。 对于基本类型数据,集合使用自动装箱来减少编码工作量。但是,当处理固定大小的基本数据类型的时候,这种方式相对比较慢。 如何实现 Array 和 List 之间的转换? Array 转 List: Arrays. asList(array) ;List 转 Array:List 的 toArray() 方法。 comparable 和 comparator的区别? comparable接口实际上是出自java.lang包,它有一个 compareTo(Object obj)方法用来排序comparator接口实际上是出自 java.util 包,它有一个compare(Object obj1, Object obj2)方法用来排序 一般我们需要对一个集合使用自定义排序时,我们就要重写compareTo方法或compare方法,当我们需要对某一个集合实现两种排序方式,比如一个song对象中的歌名和歌手名分别采用一种排序方法的话,我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序,第二种代表我们只能使用两个参数版的Collections.sort(). 方法如何比较元素? TreeSet 要求存放的对象所属的类必须实现 Comparable 接口,该接口提供了比较元素的 compareTo()方法,当插入元素时会回调该方法比较元素的大小。TreeMap 要求存放的键值对映射的键必须实现 Comparable 接口从而根据键对元素进 行排 序。 Collections 工具类的 sort 方法有两种重载的形式, 第一种要求传入的待排序容器中存放的对象比较实现 Comparable 接口以实现元素的比较; 第二种不强制性的要求容器中的元素必须可比较,但是要求传入第二个参数,参数是Comparator 接口的子类型(需要重写 compare 方法实现元素的比较),相当于一个临时定义的排序规则,其实就是通过接口注入比较元素大小的算法,也是对回调模式的应用(Java 中对函数式编程的支持)。
剑曼红尘 2020-03-24 14:41:57 0 浏览量 回答数 0

问题

应该返回false的用户输入返回true

到目前为止,我一直在程序中使用运算符比较所有字符串。但是,我遇到了一个错误,将其中一个更改为错误.equals(),并修复了该错误。 true==falseÿ...
养狐狸的猫 2019-12-01 20:00:45 8 浏览量 回答数 0

回答

原来是sql_mode问题 sql_mode 常用值说明 官方手册专门有一节介绍 https://dev.mysql.com/doc/refman/5.7/en/sql-mode.html 。 SQL Mode 定义了两个方面:MySQL应支持的SQL语法,以及应该在数据上执行何种确认检查。 SQL语法支持类 ONLY_FULL_GROUP_BY 对于GROUP BY聚合操作,如果在SELECT中的列、HAVING或者ORDER BY子句的列,没有在GROUP BY中出现,那么这个SQL是不合法的。是可以理解的,因为不在 group by 的列查出来展示会有矛盾。 在5.7中默认启用,所以在实施5.6升级到5.7的过程需要注意: ANSI_QUOTES 启用 ANSI_QUOTES 后,不能用双引号来引用字符串,因为它被解释为识别符,作用与 ` 一样。 设置它以后,update t set f1="" ...,会报 Unknown column ‘’ in ‘field list 这样的语法错误。 PIPES_AS_CONCAT 将 || 视为字符串的连接操作符而非 或 运算符,这和Oracle数据库是一样的,也和字符串的拼接函数 CONCAT() 相类似 NO_TABLE_OPTIONS 使用 SHOW CREATE TABLE 时不会输出MySQL特有的语法部分,如 ENGINE ,这个在使用 mysqldump 跨DB种类迁移的时候需要考虑 NO_AUTO_CREATE_USER 字面意思不自动创建用户。在给MySQL用户授权时,我们习惯使用 GRANT ... ON ... TO dbuser顺道一起创建用户。设置该选项后就与oracle操作类似,授权之前必须先建立用户。5.7.7开始也默认了。 数据检查类 NO_ZERO_DATE 认为日期 ‘0000-00-00’ 非法,与是否设置后面的严格模式有关。 1.如果设置了严格模式,则 NO_ZERO_DATE 自然满足。但如果是 INSERT IGNORE 或 UPDATE IGNORE,’0000-00-00’依然允许且只显示warning 2.如果在非严格模式下,设置了NO_ZERO_DATE,效果与上面一样,’0000-00-00’允许但显示warning;如果没有设置NO_ZERO_DATE,no warning,当做完全合法的值。 3.NO_ZERO_IN_DATE情况与上面类似,不同的是控制日期和天,是否可为 0 ,即 2010-01-00 是否合法。 NO_ENGINE_SUBSTITUTION 使用 ALTER TABLE或CREATE TABLE 指定 ENGINE 时, 需要的存储引擎被禁用或未编译,该如何处理。启用NO_ENGINE_SUBSTITUTION时,那么直接抛出错误;不设置此值时,CREATE用默认的存储引擎替代,ATLER不进行更改,并抛出一个 warning。 STRICT_TRANS_TABLES 设置它,表示启用严格模式。 注意 STRICT_TRANS_TABLES 不是几种策略的组合,单独指 INSERT、UPDATE出现少值或无效值该如何处理: 1.把 ‘’ 传给int,严格模式下非法,若启用非严格模式则变成0,产生一个warning 2.Out Of Range,变成插入最大边界值 3.A value is missing when a new row to be inserted does not contain a value for a non-NULL column that has no explicit DEFAULT clause in its definition 面并没有囊括所有的 SQL Mode,选了几个代表性的。 sql_mode一般来说很少去关注它,没有遇到实际问题之前不会去启停上面的条目。我们常设置的 sql_mode 是 ANSI、STRICT_TRANS_TABLES、TRADITIONAL,ansi和traditional是上面的几种组合。 ANSI:更改语法和行为,使其更符合标准SQL 相当于REAL_AS_FLOAT, PIPES_AS_CONCAT, ANSI_QUOTES, IGNORE_SPACE TRADITIONAL:更像传统SQL数据库系统,该模式的简单描述是当在列中插入不正确的值时“给出错误而不是警告”。 相当于 STRICT_TRANS_TABLES, STRICT_ALL_TABLES, NO_ZERO_IN_DATE, NO_ZERO_DATE, ERROR_FOR_DIVISION_BY_ZERO, NO_AUTO_CREATE_USER, NO_ENGINE_SUBSTITUTION ORACLE:相当于 PIPES_AS_CONCAT, ANSI_QUOTES, IGNORE_SPACE, NO_KEY_OPTIONS, NO_TABLE_OPTIONS, NO_FIELD_OPTIONS, NO_AUTO_CREATE_USE 无论何种mode,产生error之后就意味着单条sql执行失败,对于支持事务的表,则导致当前事务回滚;但如果没有放在事务中执行,或者不支持事务的存储引擎表,则可能导致数据不一致。MySQL认为,相比直接报错终止,数据不一致问题更严重。于是 STRICT_TRANS_TABLES 对非事务表依然尽可能的让写入继续,比如给个”最合理”的默认值或截断。而对于 STRICT_ALL_TABLES,如果是单条更新,则不影响,但如果更新的是多条,第一条成功,后面失败则会出现部分更新。 5.6.6 以后版本默认就是NO_ENGINE_SUBSTITUTION,STRICT_TRANS_TABLES,5.5默认为 ‘’ 。 设置 sql_mode 查看 查看当前连接会话的sql模式: mysql> select @@session.sql_mode; 或者从环境变量里取 mysql> show variables like "sql_mode"; 查看全局sql_mode设置: mysql> select @@global.sql_mode; 只设置global,需要重新连接进来才会生效 设置 mysql> set sql_mode=''; mysql> set global sql_mode='NO_ENGINE_SUBSTITUTION,STRICT_TRANS_TABLES'; 如果是自定义的模式组合,可以像下面这样 Adding only one mode to sql_mode without removing existing ones: mysql> SET sql_mode=(SELECT CONCAT(@@sql_mode,',')); Removing only a specific mode from sql_mode without removing others: mysql> SET sql_mode=(SELECT REPLACE(@@sql_mode,'','')); 配置文件里面设置 sql_mode=NO_AUTO_CREATE_USER,NO_ENGINE_SUBSTITUTION
游客2q7uranxketok 2021-02-21 00:51:18 0 浏览量 回答数 0

回答

Python常见数据结构整理 Python中常见的数据结构可以统称为容器(container)。序列(如列表和元组)、映射(如字典)以及集合(set)是三类主要的容器。 一、序列(列表、元组和字符串) 序列中的每个元素都有自己的编号。Python中有6种内建的序列。其中列表和元组是最常见的类型。其他包括字符串、Unicode字符串、buffer对象和xrange对象。下面重点介绍下列表、元组和字符串。 1、列表 列表是可变的,这是它区别于字符串和元组的最重要的特点,一句话概括即:列表可以修改,而字符串和元组不能。 (1)、创建 通过下面的方式即可创建一个列表: 1 2 3 4 list1=['hello','world'] print list1 list2=[1,2,3] print list2 输出: ['hello', 'world'] [1, 2, 3] 可以看到,这中创建方式非常类似于javascript中的数组。 (2)、list函数 通过list函数(其实list是一种类型而不是函数)对字符串创建列表非常有效: 1 2 list3=list("hello") print list3 输出: ['h', 'e', 'l', 'l', 'o'] 2、元组 元组与列表一样,也是一种序列,唯一不同的是元组不能被修改(字符串其实也有这种特点)。 (1)、创建 1 2 3 4 5 6 t1=1,2,3 t2="jeffreyzhao","cnblogs" t3=(1,2,3,4) t4=() t5=(1,) print t1,t2,t3,t4,t5 输出: (1, 2, 3) ('jeffreyzhao', 'cnblogs') (1, 2, 3, 4) () (1,) 从上面我们可以分析得出: a、逗号分隔一些值,元组自动创建完成; b、元组大部分时候是通过圆括号括起来的; c、空元组可以用没有包含内容的圆括号来表示; d、只含一个值的元组,必须加个逗号(,); (2)、tuple函数 tuple函数和序列的list函数几乎一样:以一个序列(注意是序列)作为参数并把它转换为元组。如果参数就算元组,那么该参数就会原样返回: 1 2 3 4 5 6 7 8 t1=tuple([1,2,3]) t2=tuple("jeff") t3=tuple((1,2,3)) print t1 print t2 print t3 t4=tuple(123) print t45 输出: (1, 2, 3) ('j', 'e', 'f', 'f') (1, 2, 3) Traceback (most recent call last): File "F:\Python\test.py", line 7, in <module> t4=tuple(123) TypeError: 'int' object is not iterable 3、字符串 (1)创建 1 2 3 4 5 str1='Hello world' print str1 print str1[0] for c in str1: print c 输出: Hello world H H e l l o w o r l d (2)格式化 字符串格式化使用字符串格式化操作符即百分号%来实现。 1 2 str1='Hello,%s' % 'world.' print str1 格式化操作符的右操作数可以是任何东西,如果是元组或者映射类型(如字典),那么字符串格式化将会有所不同。 1 2 3 4 5 6 strs=('Hello','world') #元组 str1='%s,%s' % strs print str1 d={'h':'Hello','w':'World'} #字典 str1='%(h)s,%(w)s' % d print str1 输出: Hello,world Hello,World 注意:如果需要转换的元组作为转换表达式的一部分存在,那么必须将它用圆括号括起来: 1 2 str1='%s,%s' % 'Hello','world' print str1 输出: Traceback (most recent call last): File "F:\Python\test.py", line 2, in <module> str1='%s,%s' % 'Hello','world' TypeError: not enough arguments for format string 如果需要输出%这个特殊字符,毫无疑问,我们会想到转义,但是Python中正确的处理方式如下: 1 2 str1='%s%%' % 100 print str1 输出:100% 对数字进行格式化处理,通常需要控制输出的宽度和精度: 1 2 3 4 5 6 7 from math import pi str1='%.2f' % pi #精度2 print str1 str1='%10f' % pi #字段宽10 print str1 str1='%10.2f' % pi #字段宽10,精度2 print str1 输出: 3.14 3.141593 3.14 字符串格式化还包含很多其他丰富的转换类型,可参考官方文档。 Python中在string模块还提供另外一种格式化值的方法:模板字符串。它的工作方式类似于很多UNIX Shell里的变量替换,如下所示: 1 2 3 4 from string import Template str1=Template('$x,$y!') str1=str1.substitute(x='Hello',y='world') print str1 输出: Hello,world! 如果替换字段是单词的一部分,那么参数名称就必须用括号括起来,从而准确指明结尾: 1 2 3 4 from string import Template str1=Template('Hello,w${x}d!') str1=str1.substitute(x='orl') print str1 输出: Hello,world! 如要输出符,可以使用$输出: 1 2 3 4 from string import Template str1=Template('$x$$') str1=str1.substitute(x='100') print str1 输出:100$ 除了关键字参数之外,模板字符串还可以使用字典变量提供键值对进行格式化: 1 2 3 4 5 from string import Template d={'h':'Hello','w':'world'} str1=Template('$h,$w!') str1=str1.substitute(d) print str1 输出: Hello,world! 除了格式化之外,Python字符串还内置了很多实用方法,可参考官方文档,这里不再列举。 4、通用序列操作(方法) 从列表、元组以及字符串可以“抽象”出序列的一些公共通用方法(不是你想像中的CRUD),这些操作包括:索引(indexing)、分片(sliceing)、加(adding)、乘(multiplying)以及检查某个元素是否属于序列的成员。除此之外,还有计算序列长度、最大最小元素等内置函数。 (1)索引 1 2 3 4 5 6 str1='Hello' nums=[1,2,3,4] t1=(123,234,345) print str1[0] print nums[1] print t1[2] 输出 H 2 345 索引从0(从左向右)开始,所有序列可通过这种方式进行索引。神奇的是,索引可以从最后一个位置(从右向左)开始,编号是-1: 1 2 3 4 5 6 str1='Hello' nums=[1,2,3,4] t1=(123,234,345) print str1[-1] print nums[-2] print t1[-3] 输出: o 3 123 (2)分片 分片操作用来访问一定范围内的元素。分片通过冒号相隔的两个索引来实现: 1 2 3 4 5 6 7 8 nums=range(10) print nums print nums[1:5] print nums[6:10] print nums[1:] print nums[-3:-1] print nums[-3:] #包括序列结尾的元素,置空最后一个索引 print nums[:] #复制整个序列 输出: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [1, 2, 3, 4] [6, 7, 8, 9] [1, 2, 3, 4, 5, 6, 7, 8, 9] [7, 8] [7, 8, 9] 不同的步长,有不同的输出: 1 2 3 4 5 6 7 8 nums=range(10) print nums print nums[0:10] #默认步长为1 等价于nums[1:5:1] print nums[0:10:2] #步长为2 print nums[0:10:3] #步长为3 ##print nums[0:10:0] #步长为0 print nums[0:10:-2] #步长为-2 输出: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] [0, 2, 4, 6, 8] [0, 3, 6, 9] [] (3)序列相加 1 2 3 4 5 6 7 str1='Hello' str2=' world' print str1+str2 num1=[1,2,3] num2=[2,3,4] print num1+num2 print str1+num1 输出: Hello world [1, 2, 3, 2, 3, 4] Traceback (most recent call last): File "F:\Python\test.py", line 7, in <module> print str1+num1 TypeError: cannot concatenate 'str' and 'list' objects (4)乘法 1 2 3 4 5 6 print [None]*10 str1='Hello' print str1*2 num1=[1,2] print num1*2 print str1*num1 输出: [None, None, None, None, None, None, None, None, None, None] HelloHello [1, 2, 1, 2] Traceback (most recent call last): File "F:\Python\test.py", line 5, in <module> print str1*num1 TypeError: can't multiply sequence by non-int of type 'list' (5)成员资格 in运算符会用来检查一个对象是否为某个序列(或者其他类型)的成员(即元素): 1 2 3 4 5 str1='Hello' print 'h' in str1 print 'H' in str1 num1=[1,2] print 1 in num1 输出: False True True (6)长度、最大最小值 通过内建函数len、max和min可以返回序列中所包含元素的数量、最大和最小元素。 1 2 3 4 5 6 7 8 str1='Hello' print len(str1) print max(str1) print min(str1) num1=[1,2,1,4,123] print len(num1) print max(num1) print min(num1) 输出: 5 o H 5 123 1 二、映射(字典) 映射中的每个元素都有一个名字,如你所知,这个名字专业的名称叫键。字典(也叫散列表)是Python中唯一内建的映射类型。 1、键类型 字典的键可以是数字、字符串或者是元组,键必须唯一。在Python中,数字、字符串和元组都被设计成不可变类型,而常见的列表以及集合(set)都是可变的,所以列表和集合不能作为字典的键。键可以为任何不可变类型,这正是Python中的字典最强大的地方。 1 2 3 4 5 6 7 8 list1=["hello,world"] set1=set([123]) d={} d[1]=1 print d d[list1]="Hello world." d[set1]=123 print d 输出: {1: 1} Traceback (most recent call last): File "F:\Python\test.py", line 6, in <module> d[list1]="Hello world." TypeError: unhashable type: 'list' 2、自动添加 即使键在字典中并不存在,也可以为它分配一个值,这样字典就会建立新的项。 3、成员资格 表达式item in d(d为字典)查找的是键(containskey),而不是值(containsvalue)。 Python字典强大之处还包括内置了很多常用操作方法,可参考官方文档,这里不再列举。 思考:根据我们使用强类型语言的经验,比如C#和Java,我们肯定会问Python中的字典是线程安全的吗。 三、集合 集合(Set)在Python 2.3引入,通常使用较新版Python可直接创建,如下所示: strs=set(['jeff','wong','cnblogs']) nums=set(range(10)) 看上去,集合就是由序列(或者其他可迭代的对象)构建的。集合的几个重要特点和方法如下: 1、副本是被忽略的 集合主要用于检查成员资格,因此副本是被忽略的,如下示例所示,输出的集合内容是一样的。 1 2 3 4 5 set1=set([0,1,2,3,0,1,2,3,4,5]) print set1 set2=set([0,1,2,3,4,5]) print set2 输出如下: set([0, 1, 2, 3, 4, 5]) set([0, 1, 2, 3, 4, 5]) 2、集合元素的顺序是随意的 这一点和字典非常像,可以简单理解集合为没有value的字典。 1 2 strs=set(['jeff','wong','cnblogs']) print strs 输出如下: set(['wong', 'cnblogs', 'jeff'])
琴瑟 2019-12-02 01:22:27 0 浏览量 回答数 0

问题

不搞清这8大算法思想,刷再多题效果也不好的 7月23日 【今日算法】

算法和数据结构一直以来都是程序员的基本内功,可以说没有数据结构的基础建设和算法加持,也就没有这将近八十年的信息革命时代。数据结构可以看作是算法实现的容器,通过一系列特殊结构的数据集合,...
游客ih62co2qqq5ww 2020-07-29 11:10:09 3 浏览量 回答数 1

问题

详解递归 6月18日【今日算法】

前言 递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对时间空间复杂度的理解和分析。 本文只讲一题,也是几乎所有算法书讲递归...
游客ih62co2qqq5ww 2020-06-20 12:04:38 2 浏览量 回答数 0

问题

【Java学习全家桶】1460道Java热门问题,阿里百位技术专家答疑解惑

阿里极客公益活动: 或许你挑灯夜战只为一道难题 或许你百思不解只求一个答案 或许你绞尽脑汁只因一种未知 那么他们来了,阿里系技术专家来云栖问答为你解答技术难题了 他们用户自己手中的技术来帮助用户成长 本次活动特邀百位阿里技术专家对Java常...
管理贝贝 2019-12-01 20:07:15 27612 浏览量 回答数 19

回答

简介 ES是一个基于RESTful web接口并且构建在Apache Lucene之上的开源分布式搜索引擎。 同时ES还是一个分布式文档数据库,其中每个字段均可被索引,而且每个字段的数据均可被搜索,能够横向扩展至数以百计的服务器存储以及处理PB级的数据。 可以在极短的时间内存储、搜索和分析大量的数据。通常作为具有复杂搜索场景情况下的核心发动机。 ES就是为高可用和可扩展而生的。一方面可以通过升级硬件来完成系统扩展,称为垂直或向上扩展(Vertical Scale/Scaling Up)。 另一方面,增加更多的服务器来完成系统扩展,称为水平扩展或者向外扩展(Horizontal Scale/Scaling Out)。尽管ES能够利用更强劲的硬件,但是垂直扩展毕竟还是有它的极限。真正的可扩展性来自于水平扩展,通过向集群中添加更多的节点来分担负载,增加可靠性。ES天生就是分布式的,它知道如何管理多个节点来完成扩展和实现高可用性。意味应用不需要做任何的改动。 Gateway,代表ES索引的持久化存储方式。在Gateway中,ES默认先把索引存储在内存中,然后当内存满的时候,再持久化到Gateway里。当ES集群关闭或重启的时候,它就会从Gateway里去读取索引数据。比如LocalFileSystem和HDFS、AS3等。 DistributedLucene Directory,它是Lucene里的一些列索引文件组成的目录。它负责管理这些索引文件。包括数据的读取、写入,以及索引的添加和合并等。 River,代表是数据源。是以插件的形式存在于ES中。  Mapping,映射的意思,非常类似于静态语言中的数据类型。比如我们声明一个int类型的变量,那以后这个变量只能存储int类型的数据。比如我们声明一个double类型的mapping字段,则只能存储double类型的数据。 Mapping不仅是告诉ES,哪个字段是哪种类型。还能告诉ES如何来索引数据,以及数据是否被索引到等。 Search Moudle,搜索模块,支持搜索的一些常用操作 Index Moudle,索引模块,支持索引的一些常用操作 Disvcovery,主要是负责集群的master节点发现。比如某个节点突然离开或进来的情况,进行一个分片重新分片等。这里有个发现机制。 发现机制默认的实现方式是单播和多播的形式,即Zen,同时也支持点对点的实现。另外一种是以插件的形式,即EC2。 Scripting,即脚本语言。包括很多,这里不多赘述。如mvel、js、python等。    Transport,代表ES内部节点,代表跟集群的客户端交互。包括 Thrift、Memcached、Http等协议 RESTful Style API,通过RESTful方式来实现API编程。 3rd plugins,代表第三方插件。 Java(Netty),是开发框架。 JMX,是监控。 使用案例 1、将ES作为网站的主要后端系统 比如现在搭建一个博客系统,对于博客帖子的数据可以直接在ES上存储,并且使用ES来进行检索,统计。ES提供了持久化的存储、统计和很多其他数据存储的特性。 注意:但是像其他的NOSQL数据存储一样,ES是不支持事务的,如果要事务机制,还是考虑使用其他的数据库做真实库。 2、将ES添加到现有系统 有些时候不需要ES提供所有数据的存储功能,只是想在一个数据存储的基础之上使用ES。比如已经有一个复杂的系统在运行,但是现在想加一个搜索的功能,就可以使用该方案。 3、将ES作为现有解决方案的后端部分 因为ES是开源的系统,提供了直接的HTTP接口,并且现在有一个大型的生态系统在支持他。比如现在我们想部署大规模的日志框架、用于存储、搜索和分析海量的事件,考虑到现有的工具可以写入和读取ES,可以不需要进行任何开发,配置这些工具就可以去运作。 设计结构 1、逻辑设计 文档 文档是可以被索引的信息的基本单位,它包含几个重要的属性: 是自我包含的。一篇文档同时包含字段和他们的取值。 是层次型的。文档中还可以包含新的文档,一个字段的取值可以是简单的,例如location字段的取值可以是字符串,还可以包含其他字段和取值,比如可以同时包含城市和街道地址。 拥有灵活的结构。文档不依赖于预先定义的模式。也就是说并非所有的文档都需要拥有相同的字段,并不受限于同一个模式 {   "name":"meeting",   "location":"office",   "organizer":"yanping" } {   "name":"meeting",   "location":{     "name":"sheshouzuo",        "date":"2019-6-28"   },   "memebers":["leio","shiyi"] } 类型 类型是文档的逻辑容器,类似于表格是行的容器。在不同的类型中,最好放入不同的结构的文档。 字段 ES中,每个文档,其实是以json形式存储的。而一个文档可以被视为多个字段的集合。 映射 每个类型中字段的定义称为映射。例如,name字段映射为String。 索引 索引是映射类型的容器一个ES的索引非常像关系型世界中的数据库,是独立的大量文档集合。   关系型数据库与ES的结构上的对比 2、物理设计 节点 一个节点是一个ES的实例,在服务器上启动ES之后,就拥有了一个节点,如果在另一个服务器上启动ES,这就是另一个节点。甚至可以在一台服务器上启动多个ES进程,在一台服务器上拥有多个节点。多个节点可以加入同一个集群。 当ElasticSearch的节点启动后,它会利用多播(multicast)(或者单播,如果用户更改了配置)寻找集群中的其它节点,并与之建立连接。这个过程如下图所示: 节点主要有3种类型,第一种类型是client_node,主要是起到请求分发的作用,类似路由。第二种类型是master_node,是主的节点,所有的新增,删除,数据分片都是由主节点操作(elasticsearch底层是没有更新数据操作的,上层对外提供的更新实际上是删除了再新增),当然也能承担搜索操作。第三种类型是date_node,该类型的节点只能做搜索操作,具体会分配到哪个date_node,就是由client_node决定,而data_node的数据都是从master_node同步过来的 分片 一个索引可以存储超出单个结点硬件限制的大量数据。比如,一个具有10亿文档的索引占据1TB的磁盘空间,而任一节点都没有这样大的磁盘空间;或者单个节点处理搜索请求,响应太慢。   为了解决这个问题,ES提供了将索引划分成多份的能力,这些份就叫做分片。当你创建一个索引的时候,你可以指定你想要的分片的数量。每个分片本身也是一个功能完善并且独立的“索引”,这个“索引”可以被放置到集群中的任何节点上。 分片之所以重要,主要有两方面的原因:   1、允许你水平分割/扩展你的内容容量 允许你在分片(潜在地,位于多个节点上)之上进行分布式的、并行的操作,进而提高性能/吞吐量 至于一个分片怎样分布,它的文档怎样聚合回搜索请求,是完全由ES管理的,对于作为用户的你来说,这些都是透明的。   2、在一个网络/云的环境里,失败随时都可能发生,在某个分片/节点不知怎么的就处于离线状态,或者由于任何原因消失了。这种情况下,有一个故障转移机制是非常有用并且是强烈推荐的。为此目的,ES允许你创建分片的一份或多份拷贝,这些拷贝叫做复制分片,或者直接叫复制。 复制之所以重要,主要有两方面的原因: (1)在分片/节点失败的情况下,提供了高可用性。因为这个原因,注意到复制分片从不与原/主要(original/primary)分片置于同一节点上是非常重要的。 (2)扩展你的搜索量/吞吐量,因为搜索可以在所有的复制上并行运行 总之,每个索引可以被分成多个分片。一个索引也可以被复制0次(意思是没有复制)或多次。一旦复制了,每个索引就有了主分片(作为复制源的原来的分片)和复制分片(主分片的拷贝)之别。分片和复制的数量可以在索引创建的时候指定。在索引创建之后,你可以在任何时候动态地改变复制数量,但是不能改变分片的数量。   默认情况下,ES中的每个索引被分片5个主分片和1个复制,这意味着,如果你的集群中至少有两个节点,你的索引将会有5个主分片和另外5个复制分片(1个完全拷贝),这样的话每个索引总共就有10个分片。一个索引的多个分片可以存放在集群中的一台主机上,也可以存放在多台主机上,这取决于你的集群机器数量。主分片和复制分片的具体位置是由ES内在的策略所决定的。 3、插件HEAD elasticsearch-head是一个界面化的集群操作和管理工具 ● node:即一个 Elasticsearch 的运行实例,使用多播或单播方式发现 cluster 并加入。 ● cluster:包含一个或多个拥有相同集群名称的 node,其中包含一个master node。 ● index:类比关系型数据库里的DB,是一个逻辑命名空间。 ● alias:可以给 index 添加零个或多个alias,通过 alias 使用index 和根据index name 访问index一样,但是,alias给我们提供了一种切换index的能力,比如重建了index,取名● customer_online_v2,这时,有了alias,我要访问新 index,只需要把 alias 添加到新 index 即可,并把alias从旧的 index 删除。不用修改代码。 ● type:类比关系数据库里的Table。其中,一个index可以定义多个type,但一般使用习惯仅配一个type。 ● mapping:类比关系型数据库中的 schema 概念,mapping 定义了 index 中的 type。mapping 可以显示的定义,也可以在 document 被索引时自动生成,如果有新的 field,Elasticsearch 会自动推测出 field 的type并加到mapping中。 ● document:类比关系数据库里的一行记录(record),document 是 Elasticsearch 里的一个 JSON 对象,包括零个或多个field。 ● field:类比关系数据库里的field,每个field 都有自己的字段类型。 ● shard:是一个Lucene 实例。Elasticsearch 基于 Lucene,shard 是一个 Lucene 实例,被 Elasticsearch 自动管理。之前提到,index 是一个逻辑命名空间,shard 是具体的物理概念,建索引、查询等都是具体的shard在工作。shard 包括primary shard 和 replica shard,写数据时,先写到primary shard,然后,同步到replica shard,查询时,primary 和 replica 充当相同的作用。replica shard 可以有多份,也可以没有,replica shard的存在有两个作用,一是容灾,如果primary shard 挂了,数据也不会丢失,集群仍然能正常工作;二是提高性能,因为replica 和 primary shard 都能处理查询。另外,如上图右侧红框所示,shard数和replica数都可以设置,但是,shard 数只能在建立index 时设置,后期不能更改,但是,replica 数可以随时更改。但是,由于 Elasticsearch 很友好的封装了这部分,在使用Elasticsearch 的过程中,我们一般仅需要关注 index 即可,不需关注shard。   shard、node、cluster 在物理上构成了 Elasticsearch 集群,field、type、index 在逻辑上构成一个index的基本概念,在使用 Elasticsearch 过程中,我们一般关注到逻辑概念就好,就像我们在使用MySQL 时,我们一般就关注DB Name、Table和schema即可,而不会关注DBA维护了几个MySQL实例、master 和 slave 等怎么部署的一样。 ES中的索引原理 (1)传统的关系型数据库 二叉树查找效率是logN,同时插入新的节点不必移动全部节点,所以用树型结构存储索引,能同时兼顾插入和查询的性能。因此在这个基础上,再结合磁盘的读取特性(顺序读/随机读),传统关系型数据库采用了B-Tree/B+Tree这样的数据结构做索引 (2)ES 采用倒排索引 那么,倒排索引是个什么样子呢? 首先,来搞清楚几个概念,为此,举个例子: 假设有个user索引,它有四个字段:分别是name,gender,age,address。画出来的话,大概是下面这个样子,跟关系型数据库一样 Term(单词):一段文本经过分析器分析以后就会输出一串单词,这一个一个的就叫做Term Term Dictionary(单词字典):顾名思义,它里面维护的是Term,可以理解为Term的集合 Term Index(单词索引):为了更快的找到某个单词,我们为单词建立索引 Posting List(倒排列表):倒排列表记录了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息,每条记录称为一个倒排项(Posting)。根据倒排列表,即可获知哪些文档包含某个单词。(PS:实际的倒排列表中并不只是存了文档ID这么简单,还有一些其它的信息,比如:词频(Term出现的次数)、偏移量(offset)等,可以想象成是Python中的元组,或者Java中的对象) (PS:如果类比现代汉语词典的话,那么Term就相当于词语,Term Dictionary相当于汉语词典本身,Term Index相当于词典的目录索引) 我们知道,每个文档都有一个ID,如果插入的时候没有指定的话,Elasticsearch会自动生成一个,因此ID字段就不多说了 上面的例子,Elasticsearch建立的索引大致如下: name字段: age字段: gender字段: address字段: Elasticsearch分别为每个字段都建立了一个倒排索引。比如,在上面“张三”、“北京市”、22 这些都是Term,而[1,3]就是Posting List。Posting list就是一个数组,存储了所有符合某个Term的文档ID。 只要知道文档ID,就能快速找到文档。可是,要怎样通过我们给定的关键词快速找到这个Term呢? 当然是建索引了,为Terms建立索引,最好的就是B-Tree索引(MySQL就是B树索引最好的例子)。 我们查找Term的过程跟在MyISAM中记录ID的过程大致是一样的 MyISAM中,索引和数据是分开,通过索引可以找到记录的地址,进而可以找到这条记录 在倒排索引中,通过Term索引可以找到Term在Term Dictionary中的位置,进而找到Posting List,有了倒排列表就可以根据ID找到文档了 (PS:可以这样理解,类比MyISAM的话,Term Index相当于索引文件,Term Dictionary相当于数据文件) (PS:其实,前面我们分了三步,我们可以把Term Index和Term Dictionary看成一步,就是找Term。因此,可以这样理解倒排索引:通过单词找到对应的倒排列表,根据倒排列表中的倒排项进而可以找到文档记录) 为了更进一步理解,用两张图来具现化这一过程: (至于里面涉及的更加高深的数据压缩技巧,以及多个field联合查询利用跳表的数据结构快速做运算来查询,这些大家有兴趣可以自己去了解)
问问小秘 2020-04-29 15:40:48 0 浏览量 回答数 0

问题

SSH面试题

1.什么是struts2?struts的工作原理? struts2:1)经典的  mvc (Model  View  Controller) 框架                          ...
琴瑟 2019-12-01 21:46:22 3489 浏览量 回答数 0

云产品推荐

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