posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯系 :: 聚合  :: 管理

          《編程之美》上的一道題目的討論

          Posted on 2008-04-15 00:23 ZelluX 閱讀(4270) 評論(8)  編輯  收藏 所屬分類: Algorithm

          計算機科學論壇最近舉辦了一個閱讀樣章,提交書評的活動,具體內容請見http://www.ieee.org.cn/dispbbs.asp?boardID=42&ID=61162。

          這里我想針對樣章上的一個問題談談自己的理解。

          問題很簡單,求二進制中1的個數。對于一個字節(8bit)的變量,求其二進制表示中"1"的個數,要求算法的執行效率盡可能的高。

          先來看看樣章上給出的幾個算法:

          解法一,每次除二,看是否為奇數,是的話就累計加一,最后這個結果就是二進制表示中1的個數。

          解法二,同樣用到一個循環,只是里面的操作用位移操作簡化了。

          ?? 1:? int Count(int v)??
          ?? 2:? {??
          ?? 3:????? int num = 0;
          ?? 4:????? while (v) {??
          ?? 5:????????? num += v & 0x01;??
          ?? 6:????????? v >>= 1;??
          ?? 7:????? }??
          ?? 8:????? return num;??
          ?? 9:? }

          解法三,用到一個巧妙的與操作,v & (v -1 )每次能消去二進制表示中最后一位1,利用這個技巧可以減少一定的循環次數。

          解法四,查表法,因為只有數據8bit,直接建一張表,包含各個數中1的個數,然后查表就行。復雜度O(1)。

          ?? 1:? int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };??
          ?? 2:?????
          ?? 3:? int Count(int v) {??
          ?? 4:????? return countTable[v];??
          ?? 5:? }
          ??
          好了,這就是樣章上給出的四種方案,下面談談我的看法。

          首先是對算法的衡量上,復雜度真的是唯一的標準嗎?尤其對于這種數據規模給定,而且很小的情況下,復雜度其實是個比較次要的因素。

          查表法的復雜度為O(1),我用解法一,循環八次固定,復雜度也是O(1)。至于數據規模變大,變成32位整型,那查表法自然也不合適了。

          其次,我覺得既然是這樣一個很小的操作,衡量的尺度也必然要小,CPU時鐘周期可以作為一個參考。

          解法一里有若干次整數加法,若干次整數除法(一般的編譯器都能把它優化成位移),還有幾個循環分支判斷,幾個奇偶性判斷(這個比較耗時間,根據CSAPP上的數據,一般一個branch penalty得耗掉14個左右的cycle),加起來大概幾十個cycle吧。

          再看解法四,查表法看似一次地址計算就能解決,但實際上這里用到一個訪存操作,而且第一次訪存的時候很有可能那個數組不在cache里,這樣一個cache miss導致的后果可能就是耗去幾十甚至上百個cycle(因為要訪問內存)。所以對于這種“小操作”,這個算法的性能其實是很差的。

          這里我再推薦幾個解決這個問題的算法,以32位無符號整型為例。

          ?? 1:? int Count(unsigned x) {??
          ?? 2:???? x = x - ((x >> 1) & 0x55555555);???
          ?? 3:???? x = (x & 0x33333333) + ((x >> 2) & 0x33333333);???
          ?? 4:???? x = (x + (x >> 4)) & 0x0F0F0F0F;???
          ?? 5:???? x = x + (x >> 8);???
          ?? 6:???? x = x + (x >> 16);???
          ?? 7:???? return x & 0x0000003F;???
          ?? 8:? }
          ??
          這里用的是二分法,兩兩一組相加,之后四個四個一組相加,接著八個八個,最后就得到各位之和了。

          還有一個更巧妙的HAKMEM算法

          ?? 1:? int Count(unsigned x) {
          ?? 2:???? unsigned n;???
          ?? 3:?????
          ?? 4:???? n = (x >> 1) & 033333333333;???
          ?? 5:???? x = x - n;??
          ?? 6:???? n = (n >> 1) & 033333333333;??
          ?? 7:???? x = x - n;???
          ?? 8:???? x = (x + (x >> 3)) & 030707070707;??
          ?? 9:???? x = modu(x, 63);?
          ?? 10:???? return x;??
          ?? 11:? }
          ??
          首先是將二進制各位三個一組,求出每組中1的個數,然后相鄰兩組歸并,得到六個一組的1的個數,最后很巧妙的用除63取余得到了結果。

          因為2^6 = 64,也就是說 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63),這里的等號表示同余。

          這個程序只需要十條左右指令,而且不訪存,速度很快。

          由此可見,衡量一個算法實際效果不單要看復雜度,還要結合其他情況具體分析。

          關于后面的兩道擴展問題,問題一是問32位整型如何處理,這個上面已經講了。

          問題二是給定兩個整數A和B,問A和B有多少位是不同的。

          這個問題其實就是數1問題多了一個步驟,只要先算出A和B的異或結果,然后求這個值中1的個數就行了。

          總體看來這本書還是很不錯的,比較喜歡里面針對一個問題提出不同算法并不斷改進的風格。這里提出一點個人的理解,望大家指正 ;-)

          (by ZelluX?? http://www.aygfsteel.com/zellux)


          評論

          # re: 《編程之美》上的一道題目的討論  回復  更多評論   

          2008-04-15 02:15 by Lee.MaRS
          mod是一個異常慢的操作……

          # re: 《編程之美》上的一道題目的討論  回復  更多評論   

          2008-04-15 02:25 by stanleyxu
          You cannot judge the performance of an algorithm by calculating its time complexity. You should first convert code into opcode and then calculate. This is more fairer.

          # re: 《編程之美》上的一道題目的討論  回復  更多評論   

          2008-04-15 08:37 by ZelluX
          @Lee.MaRS
          十幾個cycle應該夠了吧?

          # re: 《編程之美》上的一道題目的討論  回復  更多評論   

          2008-04-15 08:39 by ZelluX
          @stanleyxu
          所以我主要看的是cycle數么。。。

          # re: 《編程之美》上的一道題目的討論  回復  更多評論   

          2008-04-15 09:11 by 如坐春風
          >>總體看來這本書還是很不錯的,比較喜歡里面針對一個問題提出不同算法并不斷改進的風格。

          有空找來看看.

          # re: 《編程之美》上的一道題目的討論  回復  更多評論   

          2008-04-15 11:15 by tumi
          博主,你好,我是《編程之美》的營銷編輯,你的這篇文章被我轉載到博文官方博客了http://blog.csdn.net/bvbook/archive/2008/04/15/2292823.aspx
          期待讀到你更多的感想。我的聯系方式是:tumi711@gmail.com msn:julybluekid@hotmail.com

          # re: 《編程之美》上的一道題目的討論  回復  更多評論   

          2008-04-16 23:33 by luohandsome
          思考得真周到!

          # re: 《編程之美》上的一道題目的討論  回復  更多評論   

          2008-04-21 12:39 by W3China
          恭喜你的書評入選 電子工業出版社博文視點與W3China聯合舉辦的“看獨家樣章,寫書評,贏取《編程之美—微軟技術面試心得》”第一期優秀書評。請速前往本站領獎。
          主站蜘蛛池模板: 汕头市| 清苑县| 安国市| 汉寿县| 威海市| 焉耆| 宝山区| 闻喜县| 泉州市| 德阳市| 普宁市| 大同县| 西青区| 元江| 阳山县| 荔浦县| 威海市| 无锡市| 西盟| 嵩明县| 安阳县| 永登县| 合川市| 巨鹿县| 张掖市| 宝鸡市| 新昌县| 屯留县| 临颍县| 会宁县| 天全县| 濉溪县| 正安县| 江城| 扎兰屯市| 定日县| 勐海县| 西青区| 吉木萨尔县| 农安县| 泰州市|