Tagged: 常数优化 Toggle Comment Threads | 键盘快捷键

  • jinzihao pm7:02 on 2015年10月16日 链接地址 | 回复
    Tags: , 常数优化   

    在OJ上做输入输出量很大的题时,在main()函数开头加两句:(在C中改用malloc(1 << 20)效果相同)

    	setvbuf(stdin, new char[1 << 20], _IOFBF, 1 << 20);
    	setvbuf(stdout, new char[1 << 20], _IOFBF, 1 << 20);
    

    通过创建一个足够大的输入输出缓冲区,可以减少IO操作的频率,提高IO性能。在实际测试中最多达到了300%的性能提升。
    这样看起来似乎有内存泄漏,但由于缓冲区的使命完成之时便是程序结束之时,程序结束时该段内存自然被释放,所以并不必担心内存泄漏。实际上,如果提前对该块内存进行delete[] 操作,是会造成运行时错误的。

     
  • jinzihao pm5:12 on 2015年10月10日 链接地址 | 回复
    Tags: , 常数优化   

    对于浮点数a、b、c,if (a > b * c) 和 if (a / b > c)两种写法等价,但前者明显快于后者。

     
  • jinzihao pm4:44 on 2015年10月9日 链接地址 | 回复
    Tags: , 常数优化   

    在C++中如果需要移动数组,首选string.h里面的memcpy;如果源数组和目标数组有重叠,则改用string.h里面的memmove;尽量不要手写for循环来移动数组,性能上很难超过内置函数。

     
  • jinzihao pm2:01 on 2015年10月9日 链接地址 | 回复
    Tags: , 常数优化   

    (接前一条状态)另外,考虑功能相同的两种写法:

    s2Bit = ((((((((s2[k - 8] * 10 + s2[k - 7]) * 10 + s2[k - 6]) * 10) + s2[k - 5]) * 10 + s2[k - 4]) * 10 + s2[k - 3]) * 10 + s2[k - 2]) * 10 + s2[k - 1]) * 10 + s2[k]; 
    

    s2Bit = s2[k - 8] * 100000000 + s2[k - 7] * 10000000 + s2[k - 6] * 1000000 + s2[k - 5] * 100000 + s2[k - 4] * 10000 + s2[k - 3] * 1000 + s2[k - 2] * 100 + s2[k - 1] * 10 + s2[k];
    

    在性能上后者更有优势,但差别有限(与程序的其他部分分摊后大约节省了14%的时间)

     
  • jinzihao pm1:55 on 2015年10月9日 链接地址 | 回复
    Tags: , 常数优化   

    顺着前一个状态的思路,又写了一个Ver 5,这次效率提升非常明显 (Ver 1在一组数据下的总时间为3.4s,Ver 4为2.9s,而Ver5只有1.8s):
    (注:在此处没有附上的外层循环代码中,变量k从n开始每次向下减9,而n在题目中可以大到5000,故绝大多数情况下k – 8 > 0,执行if {}部分,只有极少数情况执行else {}部分,即退化为Ver 4)

    //Ver 5
    if (k - 8 > 0) {
    	s2Bit = s2[k - 8] * 100000000 + s2[k - 7] * 10000000 + s2[k - 6] * 1000000 +
    		s2[k - 5] * 100000 + s2[k - 4] * 10000 + s2[k - 3] * 1000 +
    		s2[k - 2] * 100 + s2[k - 1] * 10 + s2[k];
    }
    else {
    	for (l = 0; l < k; ++l) {
    		s2Bit = (s2Bit + s2[l]) * 10;
    	}
    	s2Bit += s2[l];
    }
    
     
  • jinzihao pm12:49 on 2015年10月9日 链接地址 | 回复
    Tags: , 常数优化   

    以下四个版本的代码均摘自一道关于高精度乘法的题,作用均为把9位0~9的数字合并为一个长整数。其中llpow为一个预定义的数组,llpow[i]为10的i次方。
    实际测试发现,Ver 4的性能最优,Ver 2次之,Ver 1较差,Ver3最差…
    思考:
    Ver2相比Ver1,发现for循环的判断部分(第二个参数)一定要精简,判断部分要被执行n次,而初始化部分(第一个参数)只被执行1次,这里只不过循环9次,都有可以检测到的性能差别。
    Ver4相比Ver3,发现修改s2Bit是个很费时的操作,表达式能一步完成尽量不要分两步
    疑问:
    Ver4中(s2Bit + s2[l])的结果难道不要存到临时变量中吗?这个操作效率很高?还是编译器做了优化?还是处理器做了优化?
    Ver2慢于Ver4是否因为数组(llpow10)的寻址浪费了时间呢?还是不然?

    //Ver 1
    for (l = k; l > ((k - 9 > -1) ? k - 9 : -1); --l) {
    	s2Bit += s2[l] * llpow10[k - l];  
    }
    
    //Ver 2
    for (l = ((k - 8 > 0) ? k - 8 : 0); l < k; ++l) {
    	s2Bit += s2[l] * llpow10[k - l];  
    }
    s2Bit += s2[l];
    
    //Ver 3
    for (l = ((k - 8 > 0) ? k - 8 : 0); l < k; ++l) {
    	s2Bit += s2[l];
    	s2Bit *= 10;
    }
    s2Bit += s2[l];
    
    // Ver 4
    for (l = ((k - 8 > 0) ? k - 8 : 0); l < k; ++l) {
    	s2Bit = (s2Bit + s2[l]) * 10;
    }
    s2Bit += s2[l];
    
     
c
写新的
j
下一篇文章/下一个回复
k
前一篇文章/以前的回复
r
回复
e
编辑
o
显示/隐藏 回复
t
回到顶部
l
go to login
h
show/hide help
shift + esc
取消