• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆-19  評論-21  文章-0  trackbacks-0
              置頂隨筆
            算法的過程很詳細,美中不足的是最基本最常用的那些算法其實是比較少的,花點時間多想想為什么,知其然還要知其所以然(12),這樣才能活學活用。

            1. 書
            1.1 編程珠璣
                言簡意賅,回味無窮。本書的網絡版在 http://netlib.bell-labs.com/cm/cs/pearls/ 上,附有源代碼。 這里有我的讀書總結。 受到此書的影響,我對代碼產生了很強的潔癖,堅信代碼還可以寫得更優美,更藝術。此外面對一個問題時分析的角度更多了。

            1.2 編程之美
                 書上的每個題都會仔細地做,并完成代碼。思考的樂趣是無窮的,時常會有樂趣。

            1.3 算法導論
               經典但是比較厚,適合系統地學習算法,而后每次遇到不懂的可以再查閱,
            算法的過程很詳細,美中不足的是沒有知其所以然的感覺。看此書第一遍時,是按照書的順序看的,對這些算法大致都有熟悉了。后來會偶爾查閱。現在為了準備算法,會時常查閱此書。

            2. 文章
            2.1 Do We Teach the Right Algorithm Design Techniques ?
               把算法按其通用程度提出了4個最基本的算法思想:Brute force , Divide & conquer , Decrease & conquer,  Transform & conquer。
               讀完后可以對算法的整體有更好的掌握。

            3. 網絡教程
            3.1 Top Coder的algorithm tutorial
            posted @ 2011-07-01 20:27 hex108 閱讀(635) | 評論 (0)編輯 收藏
              2011年8月24日
            為一個問題尋找算法的過程,有點像一個窮舉過程:搜索已有知識,并進行重組的過程。所以把常用的算法記住,然后一個一個試用,看是否可行,不失為一個好方法。
            如果這個方法不行呢?不妨寫出最直觀的解答(即用“蠻力法”),然后從中看出可以優化的地方在哪里,進而進行優化。


            如何確定該問題可以用哪類方法來解答呢?首先,需要對這些常用的算法的基本思想非常熟悉。
            常用的算法可以分為以下幾類:
            1. Divide & conquer
               分治算法:將問題分為兩個1/2規模大小的子問題,然后解決。如merge sort

            2. Decrease & conquer
               減治法 : 將問題規模從 n 變為 n - 1,然后在規模n-1的基礎上解決此問題。 如insertion sort  
               這不是遞歸么?

            3. Transform & conquer
               變治法 :變換結構。如heap sort   

            4. Brute force
               蠻力算法,可以說是必殺技吧,大部分問題都可以用此方法解決。 如selection sort
               使用蠻力法的優點是簡單不容易出錯,缺點是復雜度有時很高,所以我們可以在窮舉法的基礎上進行改進,這樣能達到一舉雙得的效果。
               Backtracking(回溯法) 是 Brute fore搜索算法的一種,它通常用最簡單的遞歸方法來實現,在最壞的情況下,回溯法會導致一次復雜度為指數時間的計算。其比較經典的運用是:N皇后問題。

            其次,數據結構有時候會決定算法,例 Transform & conquer。

            另外在TopLanguage上看到的一些有用的觀點:
            1. 算法里面極大一部分內容是如何有效地進行搜索,這里的"有效"可以分為:避免不必要的計算(如A*尋路以及所有的啟發式剪枝),緩存重復計算(如所有的動 態規劃)。
            2.本質上,練習并不產生新能力。然而練習最重要的一個作用就是將外顯記憶轉化為內隱記憶。用大白話來說就是將平時需要用腦子去想(參與)的東西轉化為內在的習慣。譬如我們一開始學騎自行車的時候需要不斷提醒自己注意平衡,但隨著不斷的聯系,這種技能就內化成了所謂的程序式記憶
               這就是熟能生巧吧。
            posted @ 2011-08-24 21:39 hex108 閱讀(598) | 評論 (0)編輯 收藏
            1. 動態規劃
               Dynamic programming, like the divideand-conquer method, solves problems by combinging the solutions to subproblems.
               1) 動態規劃適用于優化問題:從很多個解中找到最優解。(Dynamic progrmming is typicall applied to optimization problems.)

               2) 適合用動態規劃解決的問題有兩個特征:
                  a. optimal substructure(http://en.wikipedia.org/wiki/Optimal_substructure)
                     用一個公式化的式子把它的solution表示出來會更清晰。
                  b. overlapping subproblems
                     如果不是overlapping subproblems,用分治法就可以解決了。動態規劃正是利用了重復子問題這個特性,將子問題的解存起來以便重復利用。
               3) 如何劃分子問題
                  以問題 "An activity-selection problem"為例,CLRS劃分的方法和我的就不同。
                  注意:如果劃分的子問題之間存在依賴,那么該問題就不適合用動態規劃解決。(見CLRS 15.3 subtlties小節)

                4) reconsturcting an optimal solution     
                  用動態規劃有個問題就是在最后得到最優解時不能知道選擇的過程,有如下兩種方法可以解決:
                  a. 可以根據我們存下來的信息推導出前一步的選擇是什么,如:diff.java
                  b. 記下選擇。
                   如果選擇較少可以采用方法a,否則選擇方法2比較好。這是一個時空權衡問題。
                5)運用動態規劃有幾個需要注意的地方:
                   a.  We must ensure that when we search for the correct place to spilt the product, we have considered all possible places so that we are sure of         
                        having examined the optimal one.
                   b.  The subproblems are independent.
                   c.  不要形成困定思維: 一想到動態規劃,馬上聯想到LCS,然后覺得動態規劃的表結構就是一個二維數組
                6)思考
                   子問題有最優解,那么該問題得到的一定是最優解嗎? 如果不是,那么什么情況下是全局最優解,什么情況是局部最優解?
                    以<編程之美>上的一個例子舉例說明如下 :(有時間再補上)

            2. 貪心算法  
                  A greedy algorithm always makes the choice that looks best at the moment. That is , it makes a locally optimal choce in the hope that chis choce will lead to a globally optimal solution.

                 貪心法能解決的問題,動態規劃基本都能解決。(CLRS 16.2 Nevertheless, beneath every greedy algorithm, ther is almost always a more cumbersome dynamic-progrmming solution)。
                 但是:For many optimization problems, using dynamic programming to determine the best choices is overkill; Simpler, more effiiect algorithms will do. (eg: greedy algorithm)

                 1)適合用貪心法解決的問題
                     必須要有Greedy-choice property : a globally optiaml solution can be arrivedat by making a locally optimal (greedy) choice.
                     如:Huffman編碼,最小生成樹
             
                  2)貪心法的一般步驟      
                      a. 將原問題劃分為子2個子問題(非overlap的),此時就能用動態規劃求解了
                      b. 找到一個劃分點,讓其中一個子問題變為空,則只剩下一個子問題了,這就是貪心算法
             
                   3)使用貪心法時必須保證:
                       We must prove that a greedy choice at each step yields a golbally optimal solution, and this is where cleverness may be required.
                       這點也是最難的。所以有個問題“什么情況下,局部最優最終會產生全局最優的結果?”

                   4)適用貪心算法的問題有 greedy-choice propertty,需要找到一個貪心策略。

                   5)對于找不到全局最優解的問題(如NP問題),可以考慮貪心算法。

            3. 動態規劃與分治法的比較

                  分治法適合于那些能被分解為獨立子問題的問題;動態規劃更適用于子問題之間不是獨立的,而是會share subproblems。動態規劃的這個特點得益于它把子問題的結果都保存在一個表中了(動態規劃的英文名字是Dynamic Programming,這里的Programming可理解為a tabular method(表格方法)),這樣就能少去重復子問題的計算。 所以動態規劃可以算作是分治法在overlapping 子問題里的一個優化(這個優化在程序中是常見的優化方法Memoization(http://en.wikipedia.org/wiki/Memoization))

            4. 動態規劃與貪心法的比較
               1) 相同點
                 a. 問題要有optimal substructure 
                    A problem exhibits optimalsubstructure if an optimal solution to the problem contains within it optimal solutions to subproblems.       
                    這是能用貪心法與動態規劃解答的問題的關鍵因素。
                 b. 都需要劃分子問題,但是劃分子問題的方式有些區別,見下面的不同點。
             
               2)不同點
                 a.  劃分子問題
                    如果你把劃分的子問題有交集(overloapping subproblem),這就很顯然地將你引入了動態規劃的思維,以"An activity-selection problem"舉例說明:
                    對于問題 "An activity-selection problem",很容易就能想到動態規劃的解法
            int select_activity(int *a, int n, int i)
            {
                if(i >=n )
                    return 0;
                for(j= i + 1; j < n; j ++){
                    if(a[j].start >= a[i].end)
                        break;
                }
                int sum1 = select_activity(a, n, j) + 1;   //select the ith activity
                int sum2 = select_activity(a, n, i + 1);   //not select the ith activity
                
                if(sum1 > sum2)
                    return sum1;
                else
                    return sum2;
            }
                但是如何將它轉化為貪心算法呢?
                  答案是:由這種方法是不易轉化為貪心法的。上面這種劃分子問題的方式表明了它更適合于動態規劃,就像在CLRS 383頁里說到的0-1背包問題:The problem formulated in this way gives rise to many over-lapping subproblems - a hallmark of dynamic programming.
             
                b.  貪心法: make whaterver choice seems best a the moment and then solve the subproblem arising after the choice is made.
                    動態規劃:make a choice at each step, but the choice usually depends on the solutions to subproblems.

                c.  貪心法:top-down fashinon        
                    動態規劃:bottom-up manner

               
             
            posted @ 2011-08-24 20:51 hex108 閱讀(1015) | 評論 (0)編輯 收藏
             要找工作了,終于覺得是時候總結一下數據結構了(ps: 對于數組,鏈表這樣簡單常用的結構就不總結了,此文會持續更新),總結有助于更好地思考。

            1. 位圖
                位圖的威力可以在<編程珠璣>的開頭就體會到。另外在Find an integer not among four billion given ones中的運用也很精彩。

            2. 堆
               在<編程珠璣>里重點運用了該結構,直接導致我以后經常想到并使用該結構。
               不得不說,它真的很有用,如:找N個數中最大/最小的k個數。
               實現優先級隊列時也有用。

            3. 樹
                 二叉搜索樹:是一個很容易就能想到的結構,只要讓一棵二叉樹滿足以下一個特性就可以了:對于任一結點N,其左子樹結點left滿足key(x) <= key(N),其右子樹結點right滿足key(y) >= key(N),其優點是操作簡單,缺點是插入,刪除結點的復雜度高,為O(N)
                 二叉搜索樹復雜度高的原因為:樹的高度不確定/不穩定,有可能為n,所以問題的關鍵是:如何控制樹的高度
                 很多人靈機一動:產生了一系列平衡二叉樹,如:AVL樹,Red-Black樹,Treap
                 也產生了很多平衡二叉樹的變種,如:Weight balanced tree,k-neighbor tree等
                 Skip List 也是平衡二叉樹之外的另一種選擇
                 Trie樹 用來存儲一個字典,然后用來查找某個字符串還是很方便的(A trie can be seen as a deterministic finite automaton.) 另外可以看看Suffix_tree后綴樹。

            4. hash
                hash的兩個關鍵點在于:a. hash桶大小的設定(一般為一個素數) b. 沖突處理機制,如可以用一個鏈表處理hash值相同的元素。
                我很少考慮hash,覺得復雜度不好把握。以后倒是可以考慮用用,如:在問題“判斷兩個鏈表是否相交”有可以使用hash;“判斷鏈表有沒有環”用hash也很給力。
            posted @ 2011-08-24 20:15 hex108 閱讀(577) | 評論 (0)編輯 收藏
              2011年7月26日
            此文只簡單分析發送信號給用戶程序后,用戶堆棧和內核堆棧的變化。沒有分析實時信號,當然整個過程基本一致。很多參考了<情景分析>,所以有些代碼和現在的內核可能不同,比如RESTORE_ALL,但大體的機制是類似的。

            1. 一個信號小例子

            hex@Gentoo ~/signal $ cat sigint.c
            #include <stdio.h>
            #include <stdlib.h>
            #include <signal.h>

            void sig_int(int signo)
            {
                printf("hello\n");
            }

            int main()
            {
                if(signal(SIGINT, sig_int) == SIG_ERR){
                    printf("can't catch SIGINT\n");
                    exit(-1);
                }

                for(;;)
                    ;

                return 0;
            }

            2. 用戶堆棧里發生的故事

            2.1 編譯運行該程序,并設置斷點在sig_int函數開頭(0x80482e8),并設置SIGINT信號的處理方式
            hex@Gentoo ~/signal $ gdb ./sigint
            (gdb) b *0x80482e8
            Breakpoint 1 at 0x80482e8: file sigint.c, line 6.
            (gdb) handle SIGINT noprint pass
            SIGINT is used by the debugger.
            Are you sure you want to change it? (y or n) y
            Signal        Stop    Print    Pass to program    Description
            SIGINT        No    No    Yes        Interrupt
            (gdb) r
            Starting program: /home/gj/signal/sigint

            2.2 向該程序發送信號: kill -INT 此程序的pid號
            hex@Gentoo ~/signal $ kill -INT 4639

            2.3 該程序收到信號后停在斷點處
            Breakpoint 1, sig_int (signo=2) at sigint.c:6
            6    {
            (gdb) i r esp
            esp            0xbfffe7ec    0xbfffe7ec
            (gdb) x/40a 0xbfffe7ec
            0xbfffe7ec:    0xb7fff400    0x2    0x33    0x0
            0xbfffe7fc:    0x7b    0x7b    0x8048930 <__libc_csu_init>    0x80488f0 <__libc_csu_fini>
            0xbfffe80c:    0xbfffed58    0xbfffed40    0x0    0x0
            0xbfffe81c:    0xbfffec18    0x0    0x0    0x0
            0xbfffe82c:    0x8048336 <main+58>    0x73    0x213    0xbfffed40
            0xbfffe83c:    0x7b    0xbfffead0    0x0    0x0
            0xbfffe84c:    0x0    0x0    0x0    0x0
            0xbfffe85c:    0x0    0x0    0x0    0x0
            0xbfffe86c:    0x0    0x0    0x0    0x0
            0xbfffe87c:    0x0    0x0    0x0    0x0
            棧上的內容為信號棧sigframe:
            根據此結構可以知道:
            1). 返回地址0xb7fff400,它指向vdso里的sigreturn
            (gdb) x/10i 0xb7fff400
               0xb7fff400 <__kernel_sigreturn>:    pop    %eax
               0xb7fff401 <__kernel_sigreturn+1>:    mov    $0x77,%eax
               0xb7fff406 <__kernel_sigreturn+6>:    int    $0x80
            這個地址根據內核的不同而不同,我的內核版本是2.6.38。
            2). 信號處理程序完成后,會回到 eip = 0x8048336 的地址繼續執行。


            2.4 執行完sig_int函數后,進入了__kernel_sigreturn,接著回到了代碼0x8048336處,一切恢復了正常。
            (gdb) x/5i $pc
            => 0x8048336 <main+58>:    jmp    0x8048336 <main+58>
            (gdb) i r esp
            esp            0xbfffed40    0xbfffed40

            在用戶層我們能看到的只有上面這么多信息了,可能有一個地方不能理解:在上面過程c中 從0xbfffe7ec起那一塊棧上的內容從哪來的?(正常情況下堆棧esp應該一直指向在過程d中顯示的esp值0xbfffed40)

            現在來看看在上面這些現象之下,內核的堆棧發生了怎樣的變化。

            3. 內核堆棧里發生的故事
            3.1 發信號時
            在 2.2 里當執行kill -INT 4639后,pid為4639的程序(也就是我們運行的 ./sigint)會收到一個信號,但是信號實際都是在內核里實現的。每個進程(這里只講進程的情況,線程類似,線程有一個tid)都有一個pid,與此pid對應有一個結構 task_struct ,在task_struct里有一個變量 struct sigpending pending,當該進程收到信號時,并不會立即作出反應,只是讓內核把這個信號記在了此變量里(它里面是一個鏈表結構)。當然,此時與內核堆棧還沒有多大關系。

            3.2 檢測信號
              如果只記錄了信號,但沒有相應反應,那有什么用啊。一個進程在什么 情況下會檢測信號的存在呢?在<情景分析>里說到了:“在中斷機制中,處理器的硬件在每條指令結束時都要檢測是否有中斷請求的存在。信號機制是純軟件的,當然不能依靠硬件來檢測信號的到來。同時,要在每條指令結束時都來檢測顯然是不現實的,甚至是不可能的。所以對信號的檢測機制是:每當從系統調用,中斷處理或異常處理返回到用戶空間的前夕;還有就是當進程被從睡眠中喚醒(必定是在系統調用中)的時候,此時若發現有信號在等待就要提前從系統調用返回。總而言之,不管是正常返回還是提前返回,在返回到用戶空間的前夕總是要檢測信號的存在并作出反應。”

              因此,對收到的信號做出反應的時間是 從內核返回用戶空間的前夕,那么有那些情況會讓程序進入內核呢?答案是中斷,異常和系統調用。簡單了解一下它們發生時內核堆棧的變化。
              //-----中斷,異常,系統調用 : 開始
               1)在用戶空間發生中斷時,CPU會自動在內核空間保存用戶堆棧的SS, 用戶堆棧的ESP, EFLAGS, 用戶空間的CS, EIP, 中斷號 - 256
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 中斷號 - 256
               進入內核后,會進行一個SAVE_ALL,這樣內核棧上的內容為:
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 中斷號 - 256 | ES | DS | EAX | EBP | EDI | ESI | EDX | ECX | EBX

               好了,一切都處理完時,內核jmp到RESTORE_ALL(它是一個宏,例:在x86_32體系結構下,/usr/src/kernel/arch/286/kernel/entry_32.S文件里包含該宏的定義)

               RESTORE做的工作,從它的代碼里就可以看出來了:   
               首先把棧上的 ES | DS | EAX | EBP | EDI | ESI | EDX | ECX | EBX pop到對應的寄存器里
               然后將esp + 4 把 “中斷號 - 256” pop掉
               此時內核棧上的內容為:
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP
               最后執行iret指令,此時CPU會從內核棧上取出SS, ESP, ELFGAS, CS, EIP,然后接著運行。

               2) 在用戶空間發生異常時,CPU自動保存在內核棧的內容為:
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 出錯代碼 error_code
               (注:CPU只是在進入異常時才知道是否應該把出錯代碼壓入堆棧(為什么?),而從異常處理通過iret指令返回時已經時過境遷,CPU已經無從知當初發生異常的原因,因此不會自動跳過這一項,而要靠相應的異常處程序對堆棧加以調整,使得在CPU開始執行iret指令時堆棧頂部是返回地址)

               進入內核后,沒有進行SAVE_ALL,而是進入相應的異常處理函數(這個函數是包裝后的,真正的處理函數在后面)(在此函數里會把真正的處理函數的地址push到棧上),然后jmp到各種異常處理所共用的程序入口error_code,它會像SAVE_ALL那樣保存相應的寄存器(沒有保存ES),此時內核空間上的內容為:
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 出錯代碼 error_code | 相應異常處理函數入口 | DS | EAX | EBP | EDI | ESI | EDX | ECX | EBX
               (注:如果沒有出錯代碼,則此值為0)

               最后結束時與中斷類似(RESTORE_ALL)。

               3) 發生系統調用時,CPU自動保存在內核棧的內容為:
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP
               為了與中斷和異常的棧一致,在進入系統調用入口(ENTRY(system_call))后會首先push %eax,然后進行SAVE_ALL,此時內核棧上的內容為
               | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | EAX | ES | DS | EAX | EBP | EDI | ESI | EDX | ECX | EBX
             
               最后結束時與中斷類似(RESTORE_ALL)。
               //-----中斷,異常,系統調用 : 結束

               中斷,異常,系統調用這部分有一點遺漏的地方:檢測信號的時機就是緊挨著RESTORE_ALL之前發生的。

            3.3 對檢測到的信號做出反應
              如果檢測到有要處理的信號時,就要開始做一些準備工作了,此時內核里的內容為(進入內核現場時的內容)
              | 用戶堆棧的SS1 | 用戶堆棧的ESP1 | EFLAGS1 | 用戶空間的CS1 | EIP1 | ? | ES1 | DS1 | EAX1 | EBP1 | EDI1 | ESI1 | EDX1 | ECX1 | EBX1
              (注:?的值有三個選擇:中斷號 - 256/出錯代碼 error_code/出錯代碼 error_code)
              假設將要處理的信號對應的信號處理程序是用戶自己設置的,即本文中SIGINT對應的信號處理程序sig_int。
              現在要做的事情是讓cpu去執行信號處理程序sig_int,但是執行前需要做好準備工作:
              3.3.1  setup_frame
              在用戶空間設置好信號棧(struct sigframe)(假設設置好棧后esp的值為sigframe_esp,在本文中其值為0xbfffe7ec),即在2.3里看到的棧內容。
              注:struct sigframe里至少包含以下內容:
              用戶堆棧的SS1, 用戶堆棧的ESP1, EFLAGS1, 用戶空間的CS1, EIP1, ES1, DS1, EAX1, EBP1, EDI1, ESI1, EDX1, ECX1, EBX1

              3.3.2 設置即將運行的eip的值為信號處理函數sig_int的地址(為0x80482e8),并設置用戶ESP的值為sigframe_esp(為0xbfffe7ec),這是通過修改內核棧里的EIP和ESP的值實現的,因為在從系統調用里iret時,會從內核棧里取EIP,ESP。
              這時內核棧的內核為:
              | 用戶堆棧的SS1 | 0xbfffe7ec | EFLAGS1 | 用戶空間的CS1 | 0x80482e8 | ? | ES1 | DS1 | EAX1 | EBP1 | EDI1 | ESI1 | EDX1 | ECX1 | EBX1
             
              最后,進行RESTORE_ALL,內核棧上的內容為:
              | 用戶堆棧的SS1 | 0xbfffe7ec | EFLAGS1 | 用戶空間的CS1 | 0x80482e8
             
              RESTORE_ALL里執行完iret后,寄存器內容為: EIP為0x80482e8(即sig_int),esp為0xbfffe7ec 。 于是用戶空間到了步驟 2.3

            3.4 信號處理程序完成以后
              2.3 -> 2.4,進入了sig_return系統調用,在sig_return里,內核棧的內容為(每個名字后面加一個2以便與前面的1區分)
              | 用戶堆棧的SS2 | 用戶堆棧的ESP2 | EFLAGS2 | 用戶空間的CS2 | EIP2 | ? | ES2 | DS2 | EAX2 | EBP2 | EDI2 | ESI2 | EDX2 | ECX2 | EBX2
              sig_return要做的主要工作就是根據用戶棧里sigframe的值修改內核棧里的內容,使內核棧變為:
              | 用戶堆棧的SS1 | 用戶堆棧的ESP1 | EFLAGS1 | 用戶空間的CS1 | EIP1 | ? | ES1 | DS1 | EAX1 | EBP1 | EDI1 | ESI1 | EDX1 | ECX1 | EBX1
                                                              
              至此內核棧里的內容和進行信號處理前一樣了。經過RESTORE_ALL后,用戶堆棧里的內容也和以前一樣(主要指ESP的值一樣)。

              "kill -INT 4639" 只是一段小插曲。程序從原處開始運行。
            posted @ 2011-07-26 18:27 hex108 閱讀(4047) | 評論 (0)編輯 收藏
              2011年7月7日
                 讀的過程真是一種享受。看到好的代碼,好的思想,總會忍不住默記幾遍。

                 看到覺得有點意味的地方最好多想想來龍去脈,想想為什么,因為緊接著的會是令人驚喜的解說。 多寫寫書上的代碼,感覺不錯(寫完以后感覺忘了很久的算法又重新回來了)。 每章的“原理”部分是高度性的概括,"習題"是很好的,促使你去思考,做習題是很有必要的,不想“浪費”時間去“做習題”了的結果可能是以后會用更多的時間才能想清這些問題,還有不要只想著看答案,你會很失望,因為有些題目是沒有答案的 :)  ps:有很多面試題來自其中的習題

                 對一些算法有了更好的理解,也許是看第二遍的原因,也許是從不同的角度看會有不同的效果(所以好書要多讀,每重讀一次會有新的收獲)。比如:在動態規劃算法里,程序可以用遞歸算法和用表格化方法實現。遞歸算法的缺點是:有部分值會被重算,解決方法是用一個數組把已經計算過的值存起來,這樣就不會重復計算了。表格化的算法是:沒有遞歸算法好理解,解決辦法是:在代碼開頭加個注釋,注釋就是那幾條遞歸規則,大不了再加上說明“此代碼用的是動態規劃”。 ps:linux里diff的基本算法就是動態規劃吧,感覺和最長公共子串類似,自己實現了一個(diff.pl)(更新:今天在網上看到了關于diff用動態規劃實現的信息:Dynamic programming Creative Exercises 2 Unix diff, 其源碼為diff.java ,比我的好了N多倍,打印結果的那段代碼的思想相當好!代碼簡潔清淅。另外,我開始覺得用表格化的方法實現動態規劃更帥了。  --2011.7.22 )。

                讀這本書收獲很多,列舉幾個吧:
                1. 書里的“程序驗證” 技術很靠譜,讓程序看起來清晰易懂,還能從一定程度保證正確性。
                2. “哨兵”(Sentinel value )被幾次用到了,感覺還不錯,代碼看起來更簡單了,還能帶來一點小小效率。
                3. 時空折中與雙贏。在原始設計的算法并非最佳方案時,通過改善算法是可以達到雙贏的。
                4. 用只分配一個較大內存塊的方案來替換通用內存分配,這樣就消除了很多 開銷較大的調用,而且也使用空間的利用更加有效。
                5. 數學模型的建立是很重要的。把數a想成用集合[a,a + 1)表示是第9章中二分查找代碼調優的核心思想。數組旋轉那個算法也實在是太nb了。
                6. 一個寫得很好的代碼,在幾個地方看到過,總會忘,這次記下:
              鏈表里有一個哨兵元素,初始時: head = sentinel = new Node(value, 0);
              向鏈表插入元素:
              insert(v)
                  
            for(p = &head; (*p)->val < t; p = &((*p)->next))
                      ;
                 
            if  (*p)->val == v 
                     
            return
                 
            *= new node(v, *p)

              下面是我寫的:
              insert(v)
                    p 
            = head;
                    
            while(p->val < t)
                        p 
            = p->next
                    
            if(p-> val == v)
                        
            return
                    q 
            = node(t,p)
                    
            if(p == head)
                         head 
            = q;

                另外,注意到一本書<算法設計與分析基礎> ,用不同的方式講算法,把算法按其通用程度提出了4個最基本的算法思想:Brute force , Divide & conquer , Decrease & conquer,  Transform & conquer。

                最后摘錄一下 第1版跋 里給的幾個建議:
                1. 解決正確的問題。 首先徹底理解問題
                2. 探索所有可能的解決方案
                3. 觀察數據
                4. 使用粗略估算
                5. 得用對稱性
                6. 利用組件做設計  
                7. 建立原型
                8. 必要時進行權衡  
                9. 保持簡單  
                10.追求優美
            posted @ 2011-07-07 20:47 hex108 閱讀(570) | 評論 (0)編輯 收藏
              2011年7月1日
            算法的過程很詳細,美中不足的是最基本最常用的那些算法其實是比較少的,花點時間多想想為什么,知其然還要知其所以然(12),這樣才能活學活用。

            1. 書
            1.1 編程珠璣
                言簡意賅,回味無窮。本書的網絡版在 http://netlib.bell-labs.com/cm/cs/pearls/ 上,附有源代碼。 這里有我的讀書總結。 受到此書的影響,我對代碼產生了很強的潔癖,堅信代碼還可以寫得更優美,更藝術。此外面對一個問題時分析的角度更多了。

            1.2 編程之美
                 書上的每個題都會仔細地做,并完成代碼。思考的樂趣是無窮的,時常會有樂趣。

            1.3 算法導論
               經典但是比較厚,適合系統地學習算法,而后每次遇到不懂的可以再查閱,
            算法的過程很詳細,美中不足的是沒有知其所以然的感覺。看此書第一遍時,是按照書的順序看的,對這些算法大致都有熟悉了。后來會偶爾查閱。現在為了準備算法,會時常查閱此書。

            2. 文章
            2.1 Do We Teach the Right Algorithm Design Techniques ?
               把算法按其通用程度提出了4個最基本的算法思想:Brute force , Divide & conquer , Decrease & conquer,  Transform & conquer。
               讀完后可以對算法的整體有更好的掌握。

            3. 網絡教程
            3.1 Top Coder的algorithm tutorial
            posted @ 2011-07-01 20:27 hex108 閱讀(635) | 評論 (0)編輯 收藏
              2011年6月18日
                 二分查找法(Binary search algorithm)是一個很常見的算法,從<編程珠璣>里再次看到時又有新的收獲。
                 直接看代碼吧,下面是常見的實現代碼:
                
            int binary_search(int *a, int num, int t)
            {
                
            int start = 0, end = num - 1;
                
                
            while(end >= start){
                    
            int middle = (start + end) / 2;
                    
            int tmp = a[middle];
                    
            if(tmp < t){
                        start 
            = middle + 1;
                    }
            else if(tmp > t){
                        end 
            = middle - 1;
                    }
            else{
                        
            return middle;
                    }
                }

                
            return -1;
            }   

                  優化后的代碼為(這個優化的思想也挺好的,不知道有沒有一套系統的方法來思考出這個優化思路):
                 
            int binary_search(int *a, int num, int t)
            {
                
            int low = -1, high = num - 1;
                
                
            while(low + 1 != high){
                    
            int middle = (low + high) / 2;
                    
            if(a[middle] < t){
                        low 
            = middle;
                    }
            else{
                        high 
            = middle;
                    }
                }
                
                
            if(a[high] != t)
                    
            return -1;
                
            else
                    
            return high;
            }
             
                 如果直接看這段代碼,有可能不知道是怎么回事。但是運用書中提到的“程序驗證”的方法后,原理就顯而易見了,修改后的代碼為:

             1 int binary_search(int *a, int num, int t)
             2 {
             3     int low = -1, high = num - 1;
             4     
             5     //invariant: low < high && a[low] < t && a[high] >= t
             6     while(low + 1 != high){
             7         int middle = (low + high) / 2==>  int middle = low + (high - low) / 2;   //防止溢出
             8         if(a[middle] < t){
             9             low = middle;
            10         }else{
            11             high = middle;
            12         }
            13     }   
            14    //assert: low +1 = high && a[low] < t && a[high] >= t
            15   
            16     if(a[high] != t)
            17         return -1;
            18     else
            19         return high;
            20 }
            21 

                  “程序驗證” 的思想可以簡述為:不管是驗證一個函數,還是一條語句,一個控制結構(循環,if分支等),都可以采用兩個斷言(前置條件和后置條件)來達到這個目的。前置條件是在執行該處代碼之前就應該成立的條件,后置條件的正確性在執行完該處代碼后必須得到保證。(ps: 斷言也算是一種驗證的手段)

              上面這段代碼的原理是給定一段區間 (low, high] ,如果満足 a[low] < t  && a[high] >=t && high = low + 1,那么有兩種情況存在:1. a[high] = t ; 2.與t相等的元素不存在。由于數組a 肯定滿足條件a[low] < t  && a[high] >=t,所以該算法要做的就是把區間 (-1, num -1] 縮小到(low, low+1]。  
                  1. 在執行代碼6~17行時,始終保證low < high && a[low] < t && a[high] >= t 成立。
              
            2. 在執行完6~17行后,肯定滿足條件a[low] < t  && a[high] >=t && high = low + 1,因為循環退出的條件是 high = low + 1,而該循環始終保證上面第1條。
              經過這樣的分析后,我們能對程序的正確性有更好的掌握,同時程序也更易理解。

            參考:
              1. 基本上摘自<編程珠璣>,很不錯的一本書,讓我對算法有了新的思考,以前只是看看算法導論如何實現的,沒有思考該算法是如何想出來的,有沒有更簡單的算法(思考的過程類似劉未鵬的<知其所以然(續)>),要堅持這個思考過程需要很多功夫與時間,但效果也很明顯,能對算法有更好的掌握。
            posted @ 2011-06-18 15:02 hex108 閱讀(2843) | 評論 (3)編輯 收藏
              2011年5月17日
                 摘要: 主要想介紹一下.gdbinit文件。

            gdb運行時會首先加載 ~/.gdbinit文件
            例如:我在debug時,每次都需要進行handle SIGBUS noprint pass來處理SIGBUS信號,這種情況就可以把它寫入 .gdbinit文件。
            在.gdbinit里也可以定義函
            eg: 在.gdbinit里定義print_regs
            def print_regs
            i r eax ebx ecx edx
            end
            (gdb) print_regs
            eax 0xbffff4a4 -1073744732
            ebx 0x28bff4 2670580
            ecx 0x902c5562 -1876142750
            edx 0x1 1  閱讀全文
            posted @ 2011-05-17 21:14 hex108 閱讀(2651) | 評論 (3)編輯 收藏

                 debug可以幫助熟悉系統,可是時間長了會很疲卷,特別是機械的調試,如果還要面對雜亂的代碼,更是雪上加霜。所以要學著從debug中鉆探快樂,在系統的調試過程中發揮想象,嘗試不同的debug方法。

                最近看了《軟件調試實戰》,結合自己的經歷,總結了一下:

                1. 與測試用例相關

                   a. 如果不能達到“測試先行”,至少應該在寫完代碼后有相對完整的測試用例。對于正確性的保證和以后重構代碼都是有好處的。

                   b. 每次添加新功能或修復了一個bug時,都應該增加測試用例!A歷經千辛萬苦終于fix 了一個bug,很久很久以后,B覺得這段代碼需要改改,于是改了改,后來的結果還是改了,而且順利提交到了庫里(因為A當時遇到的bug 并沒有出現!)

                   c. 回歸測試

                     修改代碼后進行回歸測試。每次提交一個版本后自動進行回歸測試,保證庫里的代碼的正確性。

                   d. 簡化測試用例

                     好處:可以排除不起作用的因素;減少測試用例的運行時間;最重要的是,使用測試用例更容易調試(誰愿意處理那些填充了數百或數千項的數據容器呢?)

                     方法如: 如果測試例子比較好改,可以將其改小;將輸入集改小

                   e. 完成代碼,清理后重新運行所有測試用例。

                2. 關于程序的編譯

                  a. 重視編譯期間的warning,最好把warning數減為0. 不要忽略編譯器警告,即使它們可能是無害的。

            eg:

            int add(int a,int b){

                    return a +b ;

            }

            結果頭文件里聲明成了 extern int add(long a,int b)

            會調試死人啊,調程序的時候一看程序定義是對的啊,怎么傳的參數一下就變了;

            b. 如果出現莫名其妙的錯誤

                  如果是用Makefile組織工程時,考慮make clean,有可能修改數據結構或頭文件后改變了一些東西,但是由于一些未知原因該文件并未重新編譯。如果函數是C函數,有可能調用者和被 調用者的參數的成員和類型不同。如果一個類方法,則訪問任何類成員 都將發生錯誤,因為這兩個類的內存而已幾乎是完全不同的。這可能導致Segmentation falut,或是很久之后才能檢測到的內存破壞。

            3. 關于鏈接

            a. 鏈接器的基本工作原理

                   編譯器或匯編程序將源代碼轉換為機器代碼,并輸出對象誰的。對象文件中包含符號(函數或變量),這些符號有的在本模塊定義的,有的在其他模塊定義的,鏈接器就在鏈接對象文件時把這些未定義的符號與定義它的模塊對應起來。

            b. 鏈接順序

                 有庫和歸檔文件時 鏈接算法是不一樣的。    

                 鏈接器參數順序很重要,對于編譯單元(如對象文件和庫)和搜索路徑來說都是如此。

            c. C++中使用C代碼時,用extern c{} 把C代碼包裝一下。

                 關于 c++符號和名稱改編:C++允許重載函數,為了生成C++代碼元素的唯一符號,編譯器使一種稱為名稱改編(name mangling)的技術,它將對象的準確規格說明(如會員名空間和函數參數的個數及類型)編碼到符號中。(可以用c++filt解析出來~ eg: c++filt _Z9factoriali的結果為factorial(int))

            d. 環境變量

               LD_LIBRARY_PATH會影響動態加載的庫,用LDD可以看到程序依賴哪個動態庫

            4. 自動化測試

               讓一切自動化起來。如果重復的做一件事,就很有必要考慮自動化了。

            5. 關于那些怪異的錯誤

                在一些顯而易見有內存問題的情況下,如:間歇故障和無法解釋的隨機行為,這時考慮使用內存調試器了!

                如valgrind,很好用,也很簡單。

                valgrind –tool=massif your_program 進行內存剖析(檢測內存分配情況,優化內存使用)

                valgrind –tool=memcheck your_program 進行內存檢查(檢測無效的寫訪問,檢測對未初始化的內存的讀取操作,檢測內存泄露等)

                valgrind –tool=helgrind your_program 查找競爭條件,可以用來輔助調試多線程程序

                valgrid –-db-attac=yes的功能很好用,可以將內存高度器和源代碼測試器(如gdb)結合起來,這樣就可以即時查看當時的變量的值,很好用!

            6. 靜態檢查器

               作為常規軟件構建過程中的一部分運行,用于查找一些可通過靜態源代碼分析發現的特定bug。

            7. 關于運行時剖析工具

                 不要編寫自己的運行時剖析時工具:自己霞友云朋一的剖析 工具通常使用系統調用time()或ctime()來測量時間。這些系統調用的問題是開銷很高,而且準確度低。另處在剖析期間要收集大量數據,可能會影響程序本身的行為。

            8. 環境變量

              如程序的行為可能 依賴于當前工作目錄。在linux上,目錄被注冊到環境變量CWD上。這個bug碰到過,還導致了死鎖。

            9. 讀取恰當的錯誤消息

              某個地方出錯時,滿屏都是錯誤消息時,應該重點關注哪些消息?

              Answer: 首先出現的那些消息!因為后面的消息有可能是前面導致的。這和編譯出錯時的情景一致:編譯錯誤有很多,我們肯定會直覺地去尋找第一個出錯的 地方,誰知道是不是少了個括號導致后面一連串的錯誤。

            10. bug不會自動消失

                  如果某個版本有bug,update后,bug消失了,“真好!”,一定要弄清楚bug出現的原因是什么。以前遇到過一個bug,增加一條printf語句后,bug消失了!最后發現問題是數組越界了,而修改源代碼會導致代碼段,數據段的布局等改變,所以會導致偶爾對。(這種情況可以求助于內存調試工具或者靜態檢查的工具)

            11. 學習使用gcc, gdb,strace 等工具。(熟悉以后可以再挖掘挖掘,可能有驚喜)

            12. cvs/svn commit之前一定要diff一下,看做了哪些修改,以避免不小心刪掉一些東西后,然后”被提交”了。

            最后,最強大的工具不在計算機中,而是調試者的判斷力和分析技巧。

               參考資料:

               1. 《軟件調試實戰》:http://book.douban.com/subject/4231293/

            posted @ 2011-05-17 20:26 hex108 閱讀(459) | 評論 (0)編輯 收藏
              2011年4月23日
                    對shell不熟,偶爾會現一些我無法理解的現象。此時該進行debug了,可選的方法有:
                    a. echo變量的值 
                    b. shell –x
               
                    此外,Remember that the shell spends a lot of its life substituting text.(http://linuxcommand.org/wss0100.php)例如,對于下面的程序:
            hex108@Gentoo ~ $ cat test.sh 
            #!/bin/sh
            var=
            if [ $var = "y" ] ;then
                echo "yes"
            fi
                    if語句里的var變量經替換后變為 if [ = "y" ],些時當然會出錯。
            hex108@Gentoo ~ $ ./test.sh 
            ./test.sh: line 3: [: =: unary operator expected

                      
                    ps:現在寫腳本的時候傾向于使用perl,而較少使用shell ,因為對于經常使用的腳本,可能會經常需要對它不停地進行改進,慢慢的,程序越來越大,該考慮重構了,   此時才會發現perl(python等“真正的”腳本語言)比shell相對來說更好重構。

            posted @ 2011-04-23 00:23 hex108 閱讀(429) | 評論 (0)編輯 收藏
            僅列出標題  下一頁
            少妇熟女久久综合网色欲| 日本久久久久亚洲中字幕| 国产精品一区二区久久精品无码| 久久婷婷五月综合97色一本一本| 伊人久久大香线蕉精品| 久久国内免费视频| 国产精品久久成人影院| 热RE99久久精品国产66热| 性欧美丰满熟妇XXXX性久久久| www久久久天天com| 久久妇女高潮几次MBA| 日韩精品国产自在久久现线拍| 久久久久亚洲精品日久生情 | 97精品伊人久久大香线蕉| 久久发布国产伦子伦精品| 亚洲国产高清精品线久久 | 久久香蕉国产线看观看猫咪?v| 中文字幕精品久久久久人妻| 久久国产精品-国产精品| 97久久国产综合精品女不卡| 久久国产福利免费| 久久大香香蕉国产| 无码人妻久久一区二区三区蜜桃 | .精品久久久麻豆国产精品 | 国产成人精品综合久久久| 日韩欧美亚洲综合久久影院d3| 欧洲成人午夜精品无码区久久| 亚洲国产成人精品女人久久久| 久久久久中文字幕| 7777久久亚洲中文字幕| 久久精品99久久香蕉国产色戒 | 国产福利电影一区二区三区久久老子无码午夜伦不 | 国内精品久久久久影院网站| 国产婷婷成人久久Av免费高清 | 国产精品久久久久久久久久影院| 久久精品免费网站网| 精品久久综合1区2区3区激情| 国产精品久久久久久久久| 久久精品成人免费看| 99久久久精品| 99久久精品国产毛片|