| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 960 人关注过本帖
标题:一段很“厉害”的程序,有感而发......
只看楼主 加入收藏
辛或
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2023-4-17
结帖率:0
收藏
已结贴  问题点数:10 回复次数:6 
一段很“厉害”的程序,有感而发......
下面这段古怪程序被称为“德芙设施”,我第一次看这程序的时候,觉得真是很“厉害”。

算法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的效率都比德夫算法高。要写出德夫设施那样的程序是很不容易的,但结果却是事半功倍。为什么会写出这么古怪的东西呢?在我看来,如果不是直接要和硬件打交道,就不应该在程序里出现很多循环,还有什么用指针去拨弄数组的操作,这些都是程序质量低下的表现。应该尽可能地去利用标准库。如果德夫去使用标准库的话,就绝不会耗费大量努力去写那个“德夫设施”,而且结果也好得多。有些同学会自己手工写一些很精妙的算法,并以此洋洋自得,以为效率很高。不要抱这种心态,在绝大多数场合,尽量利用标准库才是唯一正确,效率最高的方法。“德夫设施”,其实是一个悲剧。
搜索更多相关主题的帖子: count 算法 元素 int from 
2023-04-17 18:50
外部三电铃
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:那一年
等 级:贵宾
威 望:57
帖 子:2012
专家分:7306
注 册:2007-12-17
收藏
得分:10 
程序代码:
    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 开始)复制。
    }


这段啥意思?每个case下面的语句都是一样的

那一年,苍井空还是处女
2023-04-17 18:58
辛或
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2023-4-17
收藏
得分:0 
以下是引用外部三电铃在2023-4-17 18:58:06的发言:

    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 开始)复制。
    }

这段啥意思?每个case下面的语句都是一样的

就是把一个8次循环展开成8条语句。*to++=*from++,等价于 to[i]=from[i],i++;
2023-04-17 19:03
外部三电铃
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:那一年
等 级:贵宾
威 望:57
帖 子:2012
专家分:7306
注 册:2007-12-17
收藏
得分:0 
*to++=*from++; // 里面并没有i啊

那一年,苍井空还是处女
2023-04-17 19:05
cy326521
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2023-5-23
收藏
得分:0 
2023-06-16 15:35
cheetah
Rank: 3Rank: 3
等 级:论坛游侠
威 望:3
帖 子:119
专家分:118
注 册:2013-6-29
收藏
得分:0 
以下是引用外部三电铃在2023-4-17 19:05:20的发言:

*to++=*from++; // 里面并没有i啊

没错,是没有!我做证!!!

天道酬勤
2023-06-17 20:57
cheetah
Rank: 3Rank: 3
等 级:论坛游侠
威 望:3
帖 子:119
专家分:118
注 册:2013-6-29
收藏
得分:0 
感谢分享!

天道酬勤
2023-06-17 21:15
快速回复:一段很“厉害”的程序,有感而发......
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019684 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved