我目前的研究方向是系统软件，以及编译器优化技术，对算法一向是不怎么感冒的，因为导师一直对google招人的笔试方式很不以为然，慢慢的随着自己在实验室做研究经验的积累，慢慢的已经开始有点认同他的看法了。算法虽然优美，但是也不能走极端，为了优美而优美，忽视了底层系统软件和体系结构的支持是不可取的。不过我对编程之美中的各种有意思的算法题目还是很感兴趣的，至少在闲暇之余拿来把玩一下，对于锻炼自己的思维能力还是很有好处的。
比较同意前面zellux的一种看法：衡量一个算法实际效果不单要看复杂度，还要结合其他情况具体分析。尤其是当我看到求二进制中1的个数解法四，查表法复杂度O(1)的时候简直要吐血。这难道是算法追求的终极之美？不敢苟同。其实CMU还有一门经典的课程简称ICS，Introduction to Computer System--in programmer's perspective,（zellux提供的一个位算法可以从ICS的Lab作业中找到影子）如果把这本书作为一顿美餐的原材料，那么Introduction to Algorithms就是将这些原材料做成美味大餐的配方，如果再加上《编程之美》中题目作为调味剂，一个六星级程序大厨就这么诞生了，管他MS还是Intel,IBM,Google都可以游刃有余的。
其实我一直都想找这么一本以实例为基础的算法书作为自己的调味剂，而偶遇编程之美恰恰给了我这个机会，不过对待书中的一些为了追求唯美算法而没有考虑系统的地方还是颇有微词的。比方说求10进制1的数目这个题目，一扎眼就发现google曾将它作为的一道面试题（孰先孰后这里不再论证）原题目如下：
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?
以下是一个目前发现的最高效的算法，虽然比很多算法看起来要长许多，但是它不止是得到199981,它把4000000000内的所有都遍历出来了。而且速度还只是几十毫秒，或者更快。书中的第一问的算法2，里面用到了switch，这个在系统编程里面是很忌讳的，因为他要查跳转表，这个东西是要访存两次的。访存的开销是很大的。目前针对JVM中的interpreter的很多优化就是想办法把解释器中的庞大的一个switch想办法替换成更为有效的方式，所以很多人提出了改变class文件的bytecode的编码方式，由基于栈的转成基于寄存器的。
本题目中用到的case数目不是很多所以感觉上差距不会很大，但是这里我只想说明，算法再怎么高级也要考虑到系统和体系结构方面的东西，否则就有可能是空中楼阁，海市蜃楼。
建议就是希望书再版的话，多加入一些系统方面的探讨。胡言乱语了一番，希望不要被bs....
1. #include "stdafx.h"
2.
3. #include <windows.h>
4. #include <stdlib.h>
5.
6. int f(int n);
7. int count1(int n);
8. int cal(unsigned int number,int nwei,int count1,unsigned int ncount);
9.
10. int gTable[10];
11. const unsigned int gMAX = 4000000000L;
12.
13. int main(int argc, char* argv[])
14. {
15. int i;
16. unsigned int n=1;
17. unsigned int ncount = 0;
18. int nwei = 0;
19. int ncount1;
20.
21. /*if(argc>1)
22. {
23. n = atoi(argv[1]);
24. ncount = f(n);
25. printf("f(%d) = %d\n",n,ncount);
26. }*/
27.
28. int beginTime=GetTickCount();
29. //init gTable
30. for(i=0;i<10;++i)
31. {
32. n *= 10;
33. gTable[i] = f(n-1);
34. }
35.
36. n=0;
37. nwei = 0;
38. ncount1 = 0;
39. while(n<gMAX)
40. {
41. unsigned int temp;
42.
43. temp = 1;
44.
45. ncount =cal(n,nwei,ncount1,ncount);
46. for(i=0;i<nwei;++i)
47. temp *= 10;
48. n += temp;
49. if( (n/temp)/10 == 1)
50. ++nwei;
51. ncount1 = count1(n);
52. }
53.
54. int endTime=GetTickCount();
55. endTime-=beginTime;
56.
57. printf("time: %d ms\n",endTime);
58. return 0;
59. }
60.
61. int f(int n)
62. {
63. int ret = 0;
64. int ntemp=n;
65. int ntemp2=1;
66. int i=1;
67. while(ntemp)
68. {
69. ret += (((ntemp-1)/10)+1) * i;
70. if( (ntemp%10) == 1 )
71. {
72. ret -= i;
73. ret += ntemp2;
74. }
75. ntemp = ntemp/10;
76. i*=10;
77. ntemp2 = n%i+1;
78. }
79. return ret;
80. }
81.
82. int count1(int n)
83. {
84. int count = 0;
85. while(n)
86. {
87. if( (n%10) == 1)
88. ++count;
89. n /= 10;
90. }
91. return count;
92. }
93.
94. int cal(unsigned int number,int nwei,int count1,unsigned int ncount)
95. {
96. int i,n=1;
97. unsigned int maxcount;
98. if(nwei==0)
99. {
100. ncount += count1;
101. if(number == ncount)
102. {
103. printf("f(%d) = %d \n",number,number);
104. }
105. return ncount;
106. }
107. for(i=0;i<nwei;++i)
108. n *= 10;
109. maxcount = ncount + gTable[nwei-1];
110. maxcount += count1*n;
111. if(ncount > (number + (n-1)) )
112. {
113. return maxcount;
114. }
115. if(maxcount < number)
116. {
117. return maxcount;
118. }
119. n /= 10;
120. for(i=0;i<10;++i)
121. {
122. if(i==1)
123. ncount = cal(number+i*n,nwei-1,count1+1,ncount);
124. else
125. ncount = cal(number+i*n,nwei-1,count1,ncount);
126. }
127. return ncount;
128. }
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机技术与应用 → 『 编程心得 』 → (第四期获奖名单公布，最新4节的电子版pdf已开放下载) 预览电子版，写书评，赢取《编程之美—微软技术面试心得》(微软亚洲研究院邹欣等主编)，每周送出3本，机会多多！，欢迎参加由博文视点和本站联合举办的有奖征集书评活动
(订阅本版)
2008/4/29 8:52:00
新浪微博
