arongnet 阅读(752) 评论(11)

前一阵子,我申请部门内部调动,被其他部门的人面试了一次,面试官让我写一段代码来对一个整形数组排序,我写了下面一段代码
#define SWAP(a,b) do {\
    a = a +b;\
    b = a - b;\
    a = a - b;\
}while(0)
void sort(int number, int vData[])
{
       int ii, jj;
      for(ii=0; ii < number ; ii++)
     {
             for(jj=ii+1; jj < number ; jj ++)
             {
                 if(vData[ii] > vData[jj])
                 {
                   SWAP(vData[ii], vData[jj]);
                 }
             }
     }
}

面试官让我优化一下代码,我又写出下面代码:
#define SWAP(a,b) do {\
    a = a +b;\
    b = a - b;\
    a = a - b;\
}while(0)
void sort(int number, int vData[])
{
       int ii, jj;
       int min;
      for(ii=0; ii < number ; ii++)
     {
           min = ii;
             for(jj=ii+1; jj < number ; jj ++)
             {
                 if(vData[min] > vData[jj])
                 {
                   min = jj;
                 }
             }
            
             if(min != ii)
             {
              SWAP(vData[min],vData[ii]);
             }
     }
}

面试官说能不能再优化一下.其实那时候我已经一脑糨糊,啥快速排序算法啊都不会,只好对面试官说不行了.
面试官指着我那段宏说:你如果用一个中间变量进行交换,会减少很多计算,对于大的排序可以优化很多.

感言:看起来神奇而水平高的算法不一定实用,要考虑算法的实用性.


评论列表
周星星
re: 我的面试经历 - 给一些初学者
为什么会用这种代码?
周星星
re: 我的面试经历 - 给一些初学者
我明白你的意思,但不完全同意你的观点
guest
re: 我的面试经历 - 给一些初学者
do while(0)用的有什么意义?显然是增加了代码量
HYJ
re: 我的面试经历 - 给一些初学者
为什么用小鸡鸡,俺一般都是在i/j/m/k/都用了的情况下才用jj,

:))

在内存白菜价的现在和将来,优化已经从原来的小内存往效率上倾斜了。

在四维空间中,时间和空间是一体的。
ebug
re: 我的面试经历 - 给一些初学者
这个我听说~
用一个中间变量进行交换...

这个真没见过~
#define SWAP(a,b) do {\
    a = a +b;\
    b = a - b;\
    a = a - b;\
}while(0)


找份工作不容易
小马
re: 我的面试经历 - 给一些初学者
请问要怎么在这里申请blog,我怎么申请不了呢?谢谢
小刀人
re: 我的面试经历 - 给一些初学者
to 小马:到http://www.vckbase.com/bbs站务论坛向vckbase申请,申请前请看一下服务协议 http://blog.vckbase.com/Blogruler.aspx
乾坤一笑
re: 我的面试经历 - 给一些初学者
俺有一次极其看不惯某同事写的刷屏函数——如此调用频繁的的地方,变量和操作用的如此冗余,效率低下,代码写的也不美观——我忍无可忍,遂花了40多分钟优化了一下,后来发现:用armcc编译成asm代码,两段代码竟然完全一样。_-_!! 后来俺再也不干这种傻事了——什么该编译负责,什么该程序员负责,一定要分清楚,千万不能越俎代庖。
pAnic
re: 乾坤一笑
我也发现类似的问题,用于MCU的编译器,在某些极端优化方面比PC编译器强太多了,似乎是因为不需要考虑指令兼容性而带来的优势。。。
Linkman的学习记录
re: 我的面试经历 - 给一些初学者
关于这个交换的宏,我在大学计算机语言(FORTRAN)第一堂课,老师便将它将作为技巧教给我们。

后来我当老师时,第一堂课便将它作为反面典型教给学生。
嗜血
re: 我的面试经历 - 给一些初学者
对考官想法, 他没有说明他的意思. 是面向速度优化, 还是面向内存使用量进行优化.
另外可以和他算一笔帐. 可能少两步减法计算. 其实很可能没有减少多少效率.
因为为分配寄存器, 花在弹栈压栈上面时间 很可能和 两次减法运算 相当或者更多.

发表评论
切换编辑模式