分类目录归档:算法

用一层循环遍历二维数组

相比起我们一般用二层循环遍历二维数组,用一层循环不见得有效率上的优势。

但是在某些场合却能方便人们理解和使用。

今天我要使用这个的时候,却发现我有点忘了,然后想明白之后记录于此。

实质其实还是先行后列的遍历方式, 利用的是求余和整除两种运算。

 

假定我们要遍历的是20*20的整数型数组,一层循环的循环变量为n。

 

首先是在c语言这类以0作为数组一维的第一个下标的系统:

我们可以用一个从0到399的循环,那么在循环中要访问的一个数组元素的行标可为n/20,列标可为n%20

这里主要需要考虑的是行列标的变动范围和边界值,n为0-19时,行标一直为0(整除!),列标分别为0-19(%20后的值范围就是0-19);

当n=20(第21次循环,轮到第二行第一列的元素了),n/20=1;n%20=0

 

如果你硬是要让循环从1开始到400,那么你就将上面提到的n变成(n-1)好了。

 

我们再来看以1作为数组一维的第一个下标的系统(例如:易语言):

这次我们先讨论循环从1到400,那么在循环中要访问的一个数组元素的行列标就不是上面那么简单了。

 

先来看行标,同样的,我们利用除法 也是n/20么?不是的,对了,1是起始下标,那么我们给他加个1,即n/20+1对么?

也不对,考虑n=20的时候(第20次循环,轮到第一行第二十个元素),n/20+1=2了,跳到第二行去了。

我们这样处理,应该为n/21+1,我们考虑跳行的边界值n=20、40、60……如果是除以20,那么这将提前跳行了,不是想要的结果。

因为刚刚好除出来整数了,而换成21之后就避开了这种情况。x*20/21=x-1 (整数运算)

 

再来看看列标,+1是必需的,但是答案不是n%20+1,而是(n-1)%20+1

还是考虑跳行的边界值n=20、40、60……如果是前者,还是因为刚刚好除出来整数了,余数为零了,那么这将提前跳列了,不是想要的结果。

如果你硬是要让循环从0开始到399,那么你就将上面提到的n变成(n+1)好了。

 

这个问题不是很难的,怎么费了这么多唇舌还好像说的不是很清楚?

 

几种取数据摘要算法的用时对比

今天写程序过程中需要对数据比较校验两次数据是否一致,于是要采用数据摘要的算法。

于是我测试了一下几种常用算法对同一数据的摘要的计算用时,测试结果如下:

MD4算法 15ms,31ms,219ms,1139
MD5算法 31ms,31ms,280ms,1513ms
SHA1算法 47ms,47ms,453ms,2387ms
Haval算法 31ms,31ms,437ms,2325ms
Tiger算法 78ms,78ms,717ms,3806ms
CRC32算法 16ms,0ms,63ms,328ms
SHA256算法 62ms,78ms,717ms,3837ms
SHA384算法 188ms,172ms,2231ms,11825ms
SHA512算法 187ms,172ms,2215ms,11825ms
RipeMD128算法 47ms,47ms,468ms,2543ms
RipeMD160算法 78ms,78ms,780ms,4118ms

(数据仅供参考)

 

4个测试数据前两个为我的屏幕截图位图,大小3mb左右,第三个测试数据为37.2mb的exe电子书;

最后一个数据是cs1.6的exe安装程序,大小为198mb。

 

测试结果发现CRC32算法有很大的优势,CRC32的结果是4字节整数,理论上的重复概率是 1/0xFFFFFFFF,

大概就是2亿分之一。CRC既然被广泛使用,说明其在特定范围内重复的概率是比较低的。