一段很“厉害”的程序,有感而发......
下面这段古怪程序被称为“德芙设施”,我第一次看这程序的时候,觉得真是很“厉害”。算法1
程序代码:
/** * 将from所指向的数组复制到to所指向的数组。count是需复制的元素个数。 */ void send(int *from, int *to, int count) { /** * int n = (count + 7) / 8 的意思是:将数组元素划分成 n=(count+7)/8 组。 * 其中第一组包括前 count%8 个元素,其它 n-1 组每组包括8个元素。如from所 * 指向的数组是:int a[17],则将数组a划分成3【(17+7)/8 = 3】组,象下面这样: * a[0] | a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8] | a[9]a[10]a[11]a[12]a[13]a[14]a[15]a[16] */ int n = (count + 7) / 8; /** * 第一组共【count%8】个元素,switch语句将直接跳第一组元素个数的编号处开始复制。 */ switch (count % 8) { do { case 0: // 若第一组有8个元素,从这里开始。 *to++ = *from++; case 7: // 若第一组有7个元素,从这里开始。 *to++ = *from++; case 6: // 若第一组有6个元素,从这里开始。 *to++ = *from++; case 5: // 若第一组有5个元素,从这里开始。 *to++ = *from++; case 4: // 若第一组有4个元素,从这里开始。 *to++ = *from++; case 3: // 若第一组有3个元素,从这里开始。 *to++ = *from++; case 2: // 若第一组有2个元素,从这里开始。 *to++ = *from++; case 1: // 若第一组有1个元素,从这里开始。 *to++ = *from++; } while (--n > 0); // 在拷贝完第一组元素后,剩下的以8个一组(循环从 case 0 开始)复制。 } }
我做了详尽的注释,第一次看到的同学应该也不难理解。很明显,这段代码是要优化数组复制的效率,它的高效之处在于:它大大降低了复制循环的次数。(用switch-case语句,直接跳进do-while循环结构里只是一些“新奇”的操作。)看看下面这个复制算法。
算法2
程序代码:
void send(int *from, int *to, int count){ for(int i=0; i<count; ++i){ *to++ = *from++; } }
有经验的同学会知道,对于很长的数组,算法2的循环条件判断 i<count 会占去了全部执行时间的一半左右。而算法1把循环条件判断减少到了1/8,效率会有非常明显的提高。但是再看看下面这个程序:
算法3
void send(int *from, int *to, int count){ memcpy(to, from, sizeof(int)*count); }
对于C++程序来说,正确的做法是使用标准模板库函数:copy 来拷贝数组。
算法4
void send(int *from, int *to, int count){ std::copy(a, a + count, b); }
算法3和算法4的效率都比德夫算法高。要写出德夫设施那样的程序是很不容易的,但结果却是事半功倍。为什么会写出这么古怪的东西呢?在我看来,如果不是直接要和硬件打交道,就不应该在程序里出现很多循环,还有什么用指针去拨弄数组的操作,这些都是程序质量低下的表现。应该尽可能地去利用标准库。如果德夫去使用标准库的话,就绝不会耗费大量努力去写那个“德夫设施”,而且结果也好得多。有些同学会自己手工写一些很精妙的算法,并以此洋洋自得,以为效率很高。不要抱这种心态,在绝大多数场合,尽量利用标准库才是唯一正确,效率最高的方法。“德夫设施”,其实是一个悲剧。