|
一直關(guān)注的博主終于要出書了，滿心歡喜。 博主所關(guān)注的，大抵也都是我所關(guān)注的。同樣的問題，我大學(xué)時(shí)思考過，讀研時(shí)思考過，上班后也思考過，沒有答案；他也思考過，有了一些答案，就寫了出來，與大家分享，從大學(xué)至今。 博主要出的書名叫《暗時(shí)間》，來自所寫博文的歸納，所寫的東西，也不是一般登大雅之堂之書中所能見到的，它們來自平日里點(diǎn)點(diǎn)滴滴的思考和總結(jié)。這些思考的成果，談不上什么解決什么重大的科學(xué)難題或者社會(huì)焦點(diǎn)問題，卻很是迎合我這樣一類人的“特殊”需求：關(guān)于學(xué)習(xí)和思考的態(tài)度、方法和精神。 博客中內(nèi)容很多，每天看一點(diǎn)，看了幾天?？戳酥笥X得似懂非懂，似是非是，有時(shí)候覺得這些想法實(shí)在太精辟了，不敢相信，于是又看了幾遍，直到看出一些不認(rèn)同的地方才罷手——不能盲從嘛！
一、關(guān)于書寫的看法：書寫是為了更好的思考。 我的經(jīng)驗(yàn)似乎是這樣的：有些不成熟的想法（構(gòu)想、設(shè)計(jì)、方案等還好，特別是判斷），放在心里雖然咯得慌，老惦記著，但是時(shí)不時(shí)受到啟發(fā)、刺激，時(shí)不時(shí)拿出來想一想（這就是所謂的“暗時(shí)間”經(jīng)歷！），最后內(nèi)心謹(jǐn)慎猶豫的拿出來試驗(yàn)一下，還真行！這種感覺還是挺愜意的。換一種做法，寫出來，雖然只是寫出來，手似乎就給了內(nèi)心一個(gè)認(rèn)可的ACK信號，本來一個(gè)未決的事件就這么被默默從潛意識的TODO list中清除了，本來還需要更多思考，需要更多實(shí)踐、靈感來啟發(fā)的想法，還沒來得及得到一個(gè)合理的答案就從潛意識的Active任務(wù)中，沒了。 后來，我就不再隨意的把想法“書寫”出來了，寧可用個(gè)小紙條，故意寫一些只言片語，故意不用連貫的、自然的、合乎邏輯、便于理解方式輸出思維。 書寫，說成備忘更為合適一些。等到了想法基本連貫了，再書寫出來，成為可供查閱、可供交流、便于回憶的形式，似乎更適合我。 思考，就像是“在黑夜中打著手電筒前行，每一步推導(dǎo)都將我們往前挪一小步，然而電筒的光亮能照到的范圍是有限的，我們走了幾步發(fā)現(xiàn)后面又黑了，想到后面就忘了前面的，想到某個(gè)分支上去就忘了另一個(gè)分支，意識的微光就在一個(gè)很小的范圍內(nèi)打轉(zhuǎn)，始終無法往前走出很遠(yuǎn)。而將思維過程記錄下來，則給了我們完全的回溯自己的思維軌跡的可能”。
二、如果你手里有一把錘子，所有東西看上去都像釘子：錘子和釘子。 我想，這是對于程序員“眼高手低”最生動(dòng)、最精辟的解釋了。一位老師也曾這樣批評過我，我一直不理解、不認(rèn)可，覺得自己“眼高”沒錯(cuò)，如果有條件，我一定可以“眼高手高”。學(xué)術(shù)研究且不提，工作后對此才慢慢體會(huì)。 首先意識到的是，技術(shù)不是一切，需求大于技術(shù)。沒有需求，技術(shù)必然會(huì)被廢掉。后來又發(fā)現(xiàn)，需求也不是一切，沒有平臺，有需求也輪不到你上。技術(shù)的地位一再被貶低，實(shí)在是內(nèi)心無法認(rèn)可的?，F(xiàn)在反思起來，這是偏見?。⌒闹幸袗?，怎么會(huì)覺得所有東西都是釘子！既然工作了，就要?jiǎng)?wù)實(shí)，技術(shù)就是要為某一目標(biāo)服務(wù)。如果說要為錘子找一個(gè)安身立命之所，那就是要好好認(rèn)識自己，認(rèn)清形勢，選擇一個(gè)合適的目標(biāo)、平臺。接下來，錘子自然如魚得水，不必為無法施展、種種沖突而苦悶。
三、（算法）為什么（我）想不出來？：知其所以然（以算法學(xué)習(xí)為例）。 文中對現(xiàn)有算法書的批評，實(shí)在是大快人心：我們看到的是寥寥數(shù)行精妙絕倫的算法，然后仰天長嘆自己想不出來啊想不出來。為什么想不出來，因?yàn)槟悴恢滥嵌潭虜?shù)行算法背后經(jīng)歷的事怎樣漫長的思考過程，如果問題求解是一部偵探小說，那么算法只是結(jié)局而已，而思考過程才是情節(jié)。 當(dāng)年上學(xué)時(shí)，作為學(xué)生的我也只是敢怒不敢言呵！以為算法這樣的東西，如果講得那么清楚，那么直白，直白得如同我苦苦泡圖書館幾天、費(fèi)了無數(shù)張草稿紙、熬了幾個(gè)夜的代碼后才弄明白的那樣，豈不是貶低了我們計(jì)算機(jī)科班出身人的身價(jià)？！！于是，悄悄地合上書，把草稿紙裝訂起來，把代碼打包起來，在課本上畫個(gè)小小的勾，暗示自己：這塊確實(shí)弄懂了，不要聲張了。 還原算法本來的誕生過程，確實(shí)很重要，也很難，它本來的面目往往是可憎的、混亂的，里面有試錯(cuò)，有選擇，有牛B人物在關(guān)鍵部位依據(jù)獨(dú)特知識結(jié)構(gòu)和思維模式做出的構(gòu)造和判斷，也有牛B人物在孤立點(diǎn)之間迅猛的長途推理。把算法的設(shè)計(jì)與證明形容成一場與問題、不確定性、猜測的戰(zhàn)役，絲毫不過分。這里戰(zhàn)術(shù)關(guān)鍵字有：“ 1、注意你的未知數(shù)：一遍遍將你置于不同的問題場景下然后在該提醒你的時(shí)候提醒你，讓你醒悟到“哦，原來這個(gè)時(shí)候也應(yīng)該想到這個(gè)啊?！?/p> 2、重在分析推理，而不是聯(lián)想：學(xué)了一大通算法和數(shù)據(jù)結(jié)構(gòu)之后的一個(gè)副作用就是，看到一個(gè)問題之后，腦袋里立即不管三七二十一冒出一堆可能相干的數(shù)據(jù)結(jié)構(gòu)和算法來。 3、要將思維方法內(nèi)隱化，需要不斷練習(xí)，就像需要不斷練習(xí)才能無意識狀態(tài)下就能騎自行車一樣。 ”
四、思維體力：學(xué)習(xí)密度與專注力。 我不喜歡文中對于這種名詞的定義，意會(huì)就好……我很喜歡體力這個(gè)詞。還記得某個(gè)人跟我說起過，想不到你竟然能想出這個(gè)題的算法！其實(shí)，我也沒想到。其實(shí)，我想得也很累。其實(shí)，我就是在在最堵得慌的那個(gè)點(diǎn)上往上又頂了一把。這就是體力；體力不支的時(shí)候，這就是精神的力量。 所以，體力很重要，多多練習(xí)吧！在思路受阻的那個(gè)點(diǎn)上，別說累，別停，再頂一把。 --------------- to be continued ...2011.7.19
五、為什么算法這么難？：多做題！多總結(jié)！記住未知數(shù)?。╮ecall the unknown） 原文中說到的一個(gè)問題是，在算法推演/設(shè)計(jì)/構(gòu)造時(shí)，要注意解釋和轉(zhuǎn)換，比如：
文中舉了一個(gè)霍夫曼編碼的問題?？吹臅r(shí)候發(fā)現(xiàn)已經(jīng)忘了問題的準(zhǔn)確定義了，于是又wiki+百度了一把（wiki也不靠譜啊）： 霍夫曼編碼使用變長編碼表對源符號（如文件中的一個(gè)字母）進(jìn)行最優(yōu)前綴編碼，其中變長編碼表是通過一種評估來源符號出現(xiàn)機(jī)率的方法得到的，出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長的編碼，這便使編碼之后的字符串的平均長度、期望值降低，從而達(dá)到無損壓縮數(shù)據(jù)的目的。 下面是我的理解和思路： 霍夫曼編碼的問題輸入包括：一個(gè)源符號的出現(xiàn)頻率表，一個(gè)編碼元表；輸出：編碼表。這里，評估的屬性是：freq_i*len_i，目標(biāo)：最小。 算法的策略其實(shí)已經(jīng)給出，就是“出現(xiàn)機(jī)率高的字母使用較短的編碼，反之出現(xiàn)機(jī)率低的則使用較長的編碼”。當(dāng)然，這個(gè)策略也很顯然，什么時(shí)候編碼平均長度，或者sum^n_i(freq_i*len_i)，最??？數(shù)學(xué)地，即文中給出的計(jì)算方法，可以假設(shè)一個(gè)較小值方案，即{<freq_i, len_i>}序列，然后再alter一下，發(fā)現(xiàn)要更小的話，除非len小的freq大。也就是說，每個(gè)i都滿足len小的freq大的話，它就是最小值方案，沒有更小了。 直觀的，簡化編碼問題，一個(gè)字母對應(yīng)一個(gè)長度的編碼，那么，相當(dāng)于一個(gè)len一個(gè)權(quán)重（freq），那么要想平均長度小，len大的就要分配freq小的。 好了，策略明確，剩下的任務(wù)就是算法的構(gòu)造。這個(gè)有點(diǎn)專業(yè)，？？？？？，要想到用樹作為構(gòu)造的載體，源符號充當(dāng)結(jié)點(diǎn)，把編碼元指派到樹的枝上，然后通過遍歷樹來獲取每個(gè)結(jié)點(diǎn)的編碼串。 編碼問題，基于樹這個(gè)載體，抽象轉(zhuǎn)換為結(jié)點(diǎn)的布局和枝的（編碼元）指派。而枝的指派對于評估沒有影響（編碼長度一樣），剩下的事情就是結(jié)點(diǎn)布局。 說到這里，前面的問題描述還有一個(gè)隱含條件：并置使用的（源符號的連接直接用編碼串連接表示）變長編碼，要求每個(gè)編碼不能有相同的前綴——不然，同樣一個(gè)前綴，組成一個(gè)長一點(diǎn)的編碼對應(yīng)個(gè)源符號，組成一個(gè)短一點(diǎn)的編碼也對應(yīng)一個(gè)源符號，無法譯碼了；而滿足這個(gè)條件，譯碼時(shí)按照編碼流遍歷樹就是了。如何滿足這個(gè)條件？源符號只能掛在葉子結(jié)點(diǎn)上，（遍歷路徑的終點(diǎn)，只訪問一次），不能掛在枝結(jié)點(diǎn)上。這樣，我們只需要評估葉子結(jié)點(diǎn)的sum^n_i(freq_i*len_i)，即構(gòu)造葉子結(jié)點(diǎn)的遍歷路徑。 當(dāng)只考慮葉子結(jié)點(diǎn)的遍歷路徑時(shí)，可以從兩方面考慮。一種如原文中所述，嘗試從簡單情況開始構(gòu)造，1，2,3,4,個(gè)葉子結(jié)點(diǎn)，發(fā)現(xiàn)一些明顯的規(guī)律（同一層交換結(jié)點(diǎn)的構(gòu)造等價(jià)），遇到一個(gè)關(guān)鍵點(diǎn)：頻率第3大的結(jié)點(diǎn)放哪？平放（放同一層？）還是階梯放（放上層？），嘗試，然后考慮交換方案，一舉例具體計(jì)算，發(fā)現(xiàn)跟頻率和有關(guān)！另一種，比較靈異，考慮葉子結(jié)點(diǎn)的遍歷路徑時(shí)，就有兩種拓?fù)浣Y(jié)構(gòu)： / / \ / \ / \ d / \ / \ / \ c a b c d a b 此時(shí)，可以發(fā)現(xiàn)《Algorithms》中給出的另一種cost計(jì)算方法或者說解釋方法：底層葉子結(jié)點(diǎn)在計(jì)算freq_i*len_i時(shí)，那個(gè)len_I算起來很不漂亮，總是要從根結(jié)點(diǎn)數(shù)下來才知道現(xiàn)在在第幾層（用計(jì)算機(jī)的語言來說，這個(gè)求和計(jì)算過程是迭代的，雙層for循環(huán)，外層用于枚舉所有葉子結(jié)點(diǎn)，內(nèi)層用于計(jì)算其所在層數(shù)），因而，將這里的乘法轉(zhuǎn)換為加法……（見片頭），將兩葉子結(jié)點(diǎn)的freq值之和標(biāo)注到枝結(jié)點(diǎn)，遞推之，將所有非葉子結(jié)點(diǎn)標(biāo)注之（標(biāo)注的過程相當(dāng)于完成了原來求和計(jì)算中的乘法，因?yàn)樵谟?jì)算上層枝結(jié)點(diǎn)時(shí)下屬葉子freq被求和了多次），這樣處理之后，計(jì)算和的時(shí)候就再也不用管結(jié)點(diǎn)所在層數(shù)了，標(biāo)注完了，和就定了。這樣，構(gòu)造問題，基于評估屬性的新的解釋，抽象轉(zhuǎn)換為標(biāo)注問題。 標(biāo)注方法很簡單，就是將下屬（直接）結(jié)點(diǎn)求和。recall the unknown-如何使所有結(jié)點(diǎn)的和最?。炕氐轿覀円阎牟呗?，頻率最小的最深，一種思路是：舉例具體計(jì)算一把吧！先來個(gè)簡單的： / / \ / \ / \ 4 / \ / \ / \ 3 1 2 3 4 1 2 一個(gè)是2*(f1+f2)+2*(f3+f4)，一個(gè)是3*(f1+f2)+2*f3+f4，比較一下，判決式為f1+f2 - f4。此時(shí)，階梯狀的好；于是知道構(gòu)造一個(gè)反例f1+f2 > f4： / / \ / \ / \ 6 / \ / \ / \ 5 3 4 5 6 3 4 比較、歸納發(fā)現(xiàn)，判決式的本質(zhì)是結(jié)點(diǎn)和的大小關(guān)系。recall 第3個(gè)放哪的懸疑，就是看已經(jīng)選中的結(jié)點(diǎn)和與當(dāng)前剩余結(jié)點(diǎn)的大小關(guān)系。 至此，思路探索完畢。如何證明這是對的呢？這是上面問題的第二種思路：轉(zhuǎn)換為標(biāo)注問題后，在不考慮算法復(fù)雜度/優(yōu)化策略的前提下，僅從求解計(jì)劃或者說步驟來看，是否發(fā)生了變化？求解計(jì)劃是評估結(jié)點(diǎn)和的計(jì)劃，以前是兩層循環(huán)，計(jì)算求和序列兩個(gè)參數(shù)；現(xiàn)在的是：先遞歸標(biāo)注，再平面求和（所有結(jié)點(diǎn)只參算一次），原來一個(gè)內(nèi)層需要全局信息的迭代計(jì)算法，變成了一個(gè)遞歸的，也就是兩層計(jì)算法——標(biāo)注一個(gè)結(jié)點(diǎn)時(shí)，只需要直接下屬結(jié)點(diǎn)的信息——在第二步平面求和時(shí)，下屬結(jié)點(diǎn)跟父節(jié)點(diǎn)是平等的，都只算一次。也就是說，如果自底向上標(biāo)注的話，下下一層的結(jié)點(diǎn)可以扔掉。如何使全部結(jié)點(diǎn)和最小，這個(gè)問題，可見，是與遞歸歷史（n-2）無關(guān)的（無記憶性），也就是可以采納貪心策略，選取最小頻率兩個(gè)結(jié)點(diǎn)后，就可以扔掉，保留一個(gè)和結(jié)點(diǎn)，然后再重復(fù)該策略。 -------------------貪心策略 vs. 歷史無關(guān)性/無記憶性/時(shí)齊的/與節(jié)拍起點(diǎn)無關(guān)的/time-homogeneous----------------------- |
|
|
