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