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

          Problem

          Every bus in the Ekaterinburg city has a special man (or woman) called conductor. When you ride the bus, you have to give money to the conductor. We know that there are more then P% conductors and less then Q% conductors. Your task is to determine a minimal possible number of Ekaterinburg citizens.


          我只能說太挫了。。。精度問題搞了半天,看來浮點還是要盡量化成整型再算啊。


          還有個問題就是q*i是開區(qū)間還是閉區(qū)間,總之Wrong Answer了無數(shù)次后總算過了。。。

          posted @ 2008-04-23 22:44 ZelluX 閱讀(822) | 評論 (10)編輯 收藏

               摘要: 算法導(dǎo)論第27章,在并行處理的條件下高效的排序算法。  閱讀全文

          posted @ 2008-04-23 20:22 ZelluX 閱讀(1757) | 評論 (2)編輯 收藏

          因為MSN一開始會嘗試連接crl.microsoft.com,把這個網(wǎng)站屏蔽了就行。
          在hosts文件中加入
          127.0.0.1?? crl.microsoft.com

          posted @ 2008-04-20 17:10 ZelluX 閱讀(1190) | 評論 (3)編輯 收藏

          貼幾個鏈接,以后有空再看

          Microsoft Live Mail? http://securitylabs.websense.com/content/Blogs/3063.aspx#
          http://securitylabs.websense.com/content/Blogs/2907.aspx

          Google http://securitylabs.websense.com/content/Blogs/2919.aspx#

          posted @ 2008-04-18 00:30 ZelluX 閱讀(429) | 評論 (1)編輯 收藏

          http://www.nocow.cn/index.php

          抽時間多做做,提高下我可憐的算法功底 >,<

          posted @ 2008-04-17 11:48 ZelluX 閱讀(713) | 評論 (2)編輯 收藏

          ~/.vim/ftplugin/ 下有c.vim和cpp.vim
          但是vim打開cpp和c文件時使用的配置都是c.vim中指定的

          使用vim xxx.cpp -V跟蹤了打開的配置列表,發(fā)現(xiàn)有這么一段

          line 17: sourcing "/usr/share/vim/ftplugin/cpp.vim"
          Searching for "ftplugin/c.vim ftplugin/c_*.vim ftplugin/c/*.vim" in "/home/wyx/.vim,/usr/share/vim,/usr/share/vim,
          /usr/share/vim/after,/home/wyx/.vim/after"
          Searching for "/home/wyx/.vim/ftplugin/c.vim"
          line 12: sourcing "/home/wyx/.vim/ftplugin/c.vim"

          原來/usr/share/vim/ftplugin/cpp.vim中直接調(diào)用了c.vim
          runtime! ftplugin/c.vim ftplugin/c_*.vim ftplugin/c/*.vim
          把這行注釋掉,問題解決

          posted @ 2008-04-17 00:48 ZelluX 閱讀(1940) | 評論 (0)編輯 收藏

          要提高效率果然得遠(yuǎn)離網(wǎng)絡(luò),躺床上看paper理解起來快多了
          總算把晚上要講的ppt做出來了,囧

          posted @ 2008-04-16 14:57 ZelluX 閱讀(351) | 評論 (1)編輯 收藏

          下午打球直到體力極限,一路淋雨跑回寢室,洗澡,感冒,低落。想回家。

          有時候會想,幾年后,真的就要在上海這個地方工作立足嗎?

          我想看一堆電影 想讀一堆書 想學(xué)C# Lisp Python 想上ACM OJ網(wǎng)站切題 想?yún)⒓右淮蜹opCoder比賽 想學(xué)塤 想學(xué)鋼琴 想睡覺 想看微經(jīng) 想練英語 想看內(nèi)核 想到處旅游

          終會和現(xiàn)實沖突。于是我想退實驗室。幾個小時后又放棄這個決定。

          終究是怕這怕那保守著緩慢前進(jìn)的人。

          posted @ 2008-04-15 22:23 ZelluX 閱讀(367) | 評論 (1)編輯 收藏

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

          這里我想針對樣章上的一個問題談?wù)勛约旱睦斫狻?/p>

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

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

          解法一,每次除二,看是否為奇數(shù),是的話就累計加一,最后這個結(jié)果就是二進(jìn)制表示中1的個數(shù)。

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

          ?? 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 )每次能消去二進(jìn)制表示中最后一位1,利用這個技巧可以減少一定的循環(huán)次數(shù)。

          解法四,查表法,因為只有數(shù)據(jù)8bit,直接建一張表,包含各個數(shù)中1的個數(shù),然后查表就行。復(fù)雜度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:? }
          ??
          好了,這就是樣章上給出的四種方案,下面談?wù)勎业目捶ā?/p>

          首先是對算法的衡量上,復(fù)雜度真的是唯一的標(biāo)準(zhǔn)嗎?尤其對于這種數(shù)據(jù)規(guī)模給定,而且很小的情況下,復(fù)雜度其實是個比較次要的因素。

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

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

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

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

          這里我再推薦幾個解決這個問題的算法,以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:? }
          ??
          首先是將二進(jìn)制各位三個一組,求出每組中1的個數(shù),然后相鄰兩組歸并,得到六個一組的1的個數(shù),最后很巧妙的用除63取余得到了結(jié)果。

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

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

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

          關(guān)于后面的兩道擴(kuò)展問題,問題一是問32位整型如何處理,這個上面已經(jīng)講了。

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

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

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

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

          posted @ 2008-04-15 00:23 ZelluX 閱讀(4270) | 評論 (8)編輯 收藏

          http://www.25hoursaday.com/CsharpVsJava.html#wishlist

          有點長,不過寫得很不錯

          posted @ 2008-04-14 12:27 ZelluX 閱讀(369) | 評論 (0)編輯 收藏

          僅列出標(biāo)題
          共39頁: 上一頁 1 2 3 4 5 6 7 8 9 下一頁 Last 
          主站蜘蛛池模板: 扶余县| 乌拉特后旗| 株洲市| 罗田县| 北安市| 玛曲县| 南召县| 万荣县| 崇州市| 西藏| 无极县| 鄄城县| 昆明市| 容城县| 阳原县| 大田县| 临西县| 昌黎县| 沧州市| 台东市| 清水河县| 北流市| 犍为县| 林芝县| 蒲江县| 双鸭山市| 昌平区| 北海市| 茌平县| 吕梁市| 乌兰察布市| 咸阳市| 常熟市| 陆川县| 苏尼特左旗| 吴川市| 松潘县| 蒙阴县| 衡阳县| 宝兴县| 南岸区|