国产成人精品综合久久久,精品无码久久久久国产,国内精品久久久久久麻豆

置頂隨筆

算法的過程很詳細(xì)，美中不足的是最基本最常用的那些算法其實是比較少的，花點時間多想想為什么，知其然還要知其所以然(1，2)，這樣才能活學(xué)活用。

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

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

1.3 算法導(dǎo)論
經(jīng)典但是比較厚，適合系統(tǒng)地學(xué)習(xí)算法，而后每次遇到不懂的可以再查閱，

算法的過程很詳細(xì)，美中不足的是沒有知其所以然的感覺。看此書第一遍時，是按照書的順序看的，對這些算法大致都有熟悉了。后來會偶爾查閱。現(xiàn)在為了準(zhǔn)備算法，會時常查閱此書。

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

3. 網(wǎng)絡(luò)教程
3.1 Top Coder的algorithm tutorial

posted @ 2011-07-01 20:27 hex108 閱讀(642) | 評論 (0) | 編輯收藏

2011年8月24日

[找工作]算法小結(jié)

為一個問題尋找算法的過程，有點像一個窮舉過程：搜索已有知識，并進行重組的過程。所以把常用的算法記住，然后一個一個試用，看是否可行，不失為一個好方法。

如果這個方法不行呢？不妨寫出最直觀的解答（即用“蠻力法”），然后從中看出可以優(yōu)化的地方在哪里，進而進行優(yōu)化。

如何確定該問題可以用哪類方法來解答呢？首先，需要對這些常用的算法的基本思想非常熟悉。
常用的算法可以分為以下幾類：

1. Divide & conquer
   分治算法：將問題分為兩個1／2規(guī)模大小的子問題，然后解決。如merge sort

2. Decrease & conquer
   減治法 : 將問題規(guī)模從 n 變?yōu)?n - 1，然后在規(guī)模n-1的基礎(chǔ)上解決此問題。如insertion sort
   這不是遞歸么？

3. Transform & conquer
   變治法：變換結(jié)構(gòu)。如heap sort

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

其次，數(shù)據(jù)結(jié)構(gòu)有時候會決定算法，例 Transform & conquer。

另外在TopLanguage上看到的一些有用的觀點：
1. 算法里面極大一部分內(nèi)容是如何有效地進行搜索，這里的"有效"可以分為：避免不必要的計算（如A*尋路以及所有的啟發(fā)式剪枝），緩存重復(fù)計算（如所有的動態(tài)規(guī)劃）。
2.本質(zhì)上，練習(xí)并不產(chǎn)生新能力。然而練習(xí)最重要的一個作用就是將外顯記憶轉(zhuǎn)化為內(nèi)隱記憶。用大白話來說就是將平時需要用腦子去想（參與）的東西轉(zhuǎn)化為內(nèi)在的習(xí)慣。譬如我們一開始學(xué)騎自行車的時候需要不斷提醒自己注意平衡，但隨著不斷的聯(lián)系，這種技能就內(nèi)化成了所謂的程序式記憶
這就是熟能生巧吧。

posted @ 2011-08-24 21:39 hex108 閱讀(603) | 評論 (0) | 編輯收藏

[找工作]動態(tài)規(guī)劃與貪心算法

1. 動態(tài)規(guī)劃

Dynamic programming, like the divideand-conquer method, solves problems by combinging the solutions to subproblems.

1) 動態(tài)規(guī)劃適用于優(yōu)化問題：從很多個解中找到最優(yōu)解。(Dynamic progrmming is typicall applied to optimization problems.)

   2) 適合用動態(tài)規(guī)劃解決的問題有兩個特征：
      a. optimal substructure(http://en.wikipedia.org/wiki/Optimal_substructure)
         用一個公式化的式子把它的solution表示出來會更清晰。
      b. overlapping subproblems
         如果不是overlapping subproblems，用分治法就可以解決了。動態(tài)規(guī)劃正是利用了重復(fù)子問題這個特性，將子問題的解存起來以便重復(fù)利用。

   3) 如何劃分子問題
      以問題 "An activity-selection problem"為例，CLRS劃分的方法和我的就不同。
      注意：如果劃分的子問題之間存在依賴，那么該問題就不適合用動態(tài)規(guī)劃解決。（見CLRS 15.3 subtlties小節(jié)）

    4) reconsturcting an optimal solution
      用動態(tài)規(guī)劃有個問題就是在最后得到最優(yōu)解時不能知道選擇的過程，有如下兩種方法可以解決：

      a. 可以根據(jù)我們存下來的信息推導(dǎo)出前一步的選擇是什么，如：diff.java
      b. 記下選擇。
   如果選擇較少可以采用方法a，否則選擇方法2比較好。這是一個時空權(quán)衡問題。

    5）運用動態(tài)規(guī)劃有幾個需要注意的地方：
       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. 不要形成困定思維: 一想到動態(tài)規(guī)劃，馬上聯(lián)想到LCS，然后覺得動態(tài)規(guī)劃的表結(jié)構(gòu)就是一個二維數(shù)組

6)思考
子問題有最優(yōu)解，那么該問題得到的一定是最優(yōu)解嗎？如果不是，那么什么情況下是全局最優(yōu)解，什么情況是局部最優(yōu)解?

以＜編程之美＞上的一個例子舉例說明如下 :(有時間再補上)

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.

貪心法能解決的問題，動態(tài)規(guī)劃基本都能解決。（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的），此時就能用動態(tài)規(guī)劃求解了

b. 找到一個劃分點，讓其中一個子問題變?yōu)榭眨瑒t只剩下一個子問題了，這就是貪心算法

3）使用貪心法時必須保證：

We must prove that a greedy choice at each step yields a golbally optimal solution, and this is where cleverness may be required.
這點也是最難的。所以有個問題“什么情況下，局部最優(yōu)最終會產(chǎn)生全局最優(yōu)的結(jié)果？”

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

       5）對于找不到全局最優(yōu)解的問題（如NP問題），可以考慮貪心算法。

3. 動態(tài)規(guī)劃與分治法的比較

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

4. 動態(tài)規(guī)劃與貪心法的比較
   1) 相同點
     a. 問題要有optimal substructure

        A problem exhibits optimalsubstructure if an optimal solution to the problem contains within it optimal solutions to subproblems.
        這是能用貪心法與動態(tài)規(guī)劃解答的問題的關(guān)鍵因素。
     b. 都需要劃分子問題，但是劃分子問題的方式有些區(qū)別，見下面的不同點。

   2）不同點
     a. 劃分子問題

如果你把劃分的子問題有交集(overloapping subproblem)，這就很顯然地將你引入了動態(tài)規(guī)劃的思維，以"An activity-selection problem"舉例說明：

對于問題 "An activity-selection problem"，很容易就能想到動態(tài)規(guī)劃的解法

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;

}

但是如何將它轉(zhuǎn)化為貪心算法呢？
答案是：由這種方法是不易轉(zhuǎn)化為貪心法的。上面這種劃分子問題的方式表明了它更適合于動態(tài)規(guī)劃，就像在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.

動態(tài)規(guī)劃：make a choice at each step, but the choice usually depends on the solutions to subproblems.

c. 貪心法：top-down fashinon
動態(tài)規(guī)劃：bottom-up manner

posted @ 2011-08-24 20:51 hex108 閱讀(1019) | 評論 (0) | 編輯收藏

[找工作]數(shù)據(jù)結(jié)構(gòu)小結(jié)

要找工作了，終于覺得是時候總結(jié)一下數(shù)據(jù)結(jié)構(gòu)了（ps: 對于數(shù)組，鏈表這樣簡單常用的結(jié)構(gòu)就不總結(jié)了，此文會持續(xù)更新），總結(jié)有助于更好地思考。

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

2. 堆

   在＜編程珠璣＞里重點運用了該結(jié)構(gòu)，直接導(dǎo)致我以后經(jīng)常想到并使用該結(jié)構(gòu)。
   不得不說，它真的很有用，如：找N個數(shù)中最大／最小的k個數(shù)。
   實現(xiàn)優(yōu)先級隊列時也有用。

3. 樹

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

4. hash
    hash的兩個關(guān)鍵點在于：a. hash桶大小的設(shè)定（一般為一個素數(shù)） b. 沖突處理機制，如可以用一個鏈表處理hash值相同的元素。
    我很少考慮hash，覺得復(fù)雜度不好把握。以后倒是可以考慮用用，如：在問題“判斷兩個鏈表是否相交”有可以使用hash；“判斷鏈表有沒有環(huán)”用hash也很給力。

posted @ 2011-08-24 20:15 hex108 閱讀(582) | 評論 (0) | 編輯收藏

2011年7月26日

linux信號機制－用戶堆棧和內(nèi)核堆棧的變化

此文只簡單分析發(fā)送信號給用戶程序后，用戶堆棧和內(nèi)核堆棧的變化。沒有分析實時信號，當(dāng)然整個過程基本一致。很多參考了＜情景分析＞，所以有些代碼和現(xiàn)在的內(nèi)核可能不同，比如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. 用戶堆棧里發(fā)生的故事

2.1 編譯運行該程序,并設(shè)置斷點在sig_int函數(shù)開頭(0x80482e8)，并設(shè)置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 向該程序發(fā)送信號: 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
棧上的內(nèi)容為信號棧sigframe：
根據(jù)此結(jié)構(gòu)可以知道：
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
這個地址根據(jù)內(nèi)核的不同而不同，我的內(nèi)核版本是2.6.38。
2). 信號處理程序完成后，會回到 eip = 0x8048336 的地址繼續(xù)執(zhí)行。

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

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

現(xiàn)在來看看在上面這些現(xiàn)象之下，內(nèi)核的堆棧發(fā)生了怎樣的變化。

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

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

因此，對收到的信號做出反應(yīng)的時間是從內(nèi)核返回用戶空間的前夕，那么有那些情況會讓程序進入內(nèi)核呢？答案是中斷，異常和系統(tǒng)調(diào)用。簡單了解一下它們發(fā)生時內(nèi)核堆棧的變化。

//-----中斷，異常，系統(tǒng)調(diào)用 : 開始
   1)在用戶空間發(fā)生中斷時，CPU會自動在內(nèi)核空間保存用戶堆棧的SS，用戶堆棧的ESP， EFLAGS, 用戶空間的CS, EIP, 中斷號 - 256
   | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 中斷號－ 256
   進入內(nèi)核后，會進行一個SAVE_ALL，這樣內(nèi)核棧上的內(nèi)容為：
   | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 中斷號－ 256 | ES | DS | EAX | EBP | EDI | ESI | EDX | ECX | EBX

   好了，一切都處理完時，內(nèi)核jmp到RESTORE_ALL（它是一個宏，例：在x86_32體系結(jié)構(gòu)下，/usr/src/kernel/arch/286/kernel/entry_32.S文件里包含該宏的定義）

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

   2) 在用戶空間發(fā)生異常時，CPU自動保存在內(nèi)核棧的內(nèi)容為：
   | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | 出錯代碼 error_code
   （注：CPU只是在進入異常時才知道是否應(yīng)該把出錯代碼壓入堆棧（為什么?），而從異常處理通過iret指令返回時已經(jīng)時過境遷，CPU已經(jīng)無從知當(dāng)初發(fā)生異常的原因，因此不會自動跳過這一項，而要靠相應(yīng)的異常處程序?qū)Χ褩＜右哉{(diào)整，使得在CPU開始執(zhí)行iret指令時堆棧頂部是返回地址）

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

   最后結(jié)束時與中斷類似（RESTORE_ALL）。

   3) 發(fā)生系統(tǒng)調(diào)用時，CPU自動保存在內(nèi)核棧的內(nèi)容為:
   | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP
   為了與中斷和異常的棧一致，在進入系統(tǒng)調(diào)用入口（ENTRY(system_call)）后會首先push %eax，然后進行SAVE_ALL，此時內(nèi)核棧上的內(nèi)容為
   | 用戶堆棧的SS | 用戶堆棧的ESP | EFLAGS | 用戶空間的CS | EIP | EAX | ES | DS | EAX | EBP | EDI | ESI | EDX | ECX | EBX

   最后結(jié)束時與中斷類似（RESTORE_ALL）。
   //-----中斷，異常，系統(tǒng)調(diào)用 : 結(jié)束

中斷，異常，系統(tǒng)調(diào)用這部分有一點遺漏的地方：檢測信號的時機就是緊挨著RESTORE_ALL之前發(fā)生的。

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

3.3.2 設(shè)置即將運行的eip的值為信號處理函數(shù)sig_int的地址（為0x80482e8），并設(shè)置用戶ESP的值為sigframe_esp(為0xbfffe7ec)，這是通過修改內(nèi)核棧里的EIP和ESP的值實現(xiàn)的，因為在從系統(tǒng)調(diào)用里iret時，會從內(nèi)核棧里取EIP，ESP。
這時內(nèi)核棧的內(nèi)核為:
| 用戶堆棧的SS1 | 0xbfffe7ec | EFLAGS1 | 用戶空間的CS1 | 0x80482e8 | ? | ES1 | DS1 | EAX1 | EBP1 | EDI1 | ESI1 | EDX1 | ECX1 | EBX1

最后，進行RESTORE_ALL，內(nèi)核棧上的內(nèi)容為：
| 用戶堆棧的SS1 | 0xbfffe7ec | EFLAGS1 | 用戶空間的CS1 | 0x80482e8

RESTORE_ALL里執(zhí)行完iret后，寄存器內(nèi)容為： EIP為0x80482e8(即sig_int),esp為0xbfffe7ec 。于是用戶空間到了步驟 2.3

3.4 信號處理程序完成以后
2.3 -> 2.4，進入了sig_return系統(tǒng)調(diào)用，在sig_return里，內(nèi)核棧的內(nèi)容為（每個名字后面加一個2以便與前面的1區(qū)分）
| 用戶堆棧的SS2 | 用戶堆棧的ESP2 | EFLAGS2 | 用戶空間的CS2 | EIP2 | ? | ES2 | DS2 | EAX2 | EBP2 | EDI2 | ESI2 | EDX2 | ECX2 | EBX2
sig_return要做的主要工作就是根據(jù)用戶棧里sigframe的值修改內(nèi)核棧里的內(nèi)容，使內(nèi)核棧變?yōu)?
| 用戶堆棧的SS1 | 用戶堆棧的ESP1 | EFLAGS1 | 用戶空間的CS1 | EIP1 | ? | ES1 | DS1 | EAX1 | EBP1 | EDI1 | ESI1 | EDX1 | ECX1 | EBX1

至此內(nèi)核棧里的內(nèi)容和進行信號處理前一樣了。經(jīng)過RESTORE_ALL后，用戶堆棧里的內(nèi)容也和以前一樣（主要指ESP的值一樣）。

"kill -INT 4639" 只是一段小插曲。程序從原處開始運行。

posted @ 2011-07-26 18:27 hex108 閱讀(4057) | 評論 (0) | 編輯收藏

2011年7月7日

讀<編程珠璣>，不要忘了還有這本經(jīng)典

     讀的過程真是一種享受。看到好的代碼，好的思想，總會忍不住默記幾遍。

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

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

    讀這本書收獲很多，列舉幾個吧：
    1. 書里的“程序驗證” 技術(shù)很靠譜，讓程序看起來清晰易懂，還能從一定程度保證正確性。
    2. “哨兵”(Sentinel value )被幾次用到了，感覺還不錯，代碼看起來更簡單了，還能帶來一點小小效率。
    3. 時空折中與雙贏。在原始設(shè)計的算法并非最佳方案時，通過改善算法是可以達(dá)到雙贏的。
    4. 用只分配一個較大內(nèi)存塊的方案來替換通用內(nèi)存分配，這樣就消除了很多開銷較大的調(diào)用，而且也使用空間的利用更加有效。
    5. 數(shù)學(xué)模型的建立是很重要的。把數(shù)a想成用集合[a,a + 1)表示是第9章中二分查找代碼調(diào)優(yōu)的核心思想。數(shù)組旋轉(zhuǎn)那個算法也實在是太nb了。
    6. 一個寫得很好的代碼，在幾個地方看到過，總會忘，這次記下：

鏈表里有一個哨兵元素，初始時: head = sentinel = new Node(value, 0);
  向鏈表插入元素：
  insert(v)
      for(p = &head; (*p)->val < t; p = &((*p)->next))
      ;
      if (*p)->val == v
          return
      *p = 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;

    另外，注意到一本書＜算法設(shè)計與分析基礎(chǔ)＞，用不同的方式講算法，把算法按其通用程度提出了4個最基本的算法思想：Brute force ， Divide & conquer ， Decrease & conquer， Transform & conquer。

    最后摘錄一下第1版跋里給的幾個建議:
    1. 解決正確的問題。首先徹底理解問題
    2. 探索所有可能的解決方案
    3. 觀察數(shù)據(jù)
    4. 使用粗略估算
    5. 得用對稱性
    6. 利用組件做設(shè)計
    7. 建立原型
    8. 必要時進行權(quán)衡
    9. 保持簡單
    10.追求優(yōu)美

posted @ 2011-07-07 20:47 hex108 閱讀(573) | 評論 (0) | 編輯收藏

2011年7月1日

關(guān)于算法的一些資料

算法的過程很詳細(xì)，美中不足的是最基本最常用的那些算法其實是比較少的，花點時間多想想為什么，知其然還要知其所以然(1，2)，這樣才能活學(xué)活用。

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

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

1.3 算法導(dǎo)論
經(jīng)典但是比較厚，適合系統(tǒng)地學(xué)習(xí)算法，而后每次遇到不懂的可以再查閱，

算法的過程很詳細(xì)，美中不足的是沒有知其所以然的感覺。看此書第一遍時，是按照書的順序看的，對這些算法大致都有熟悉了。后來會偶爾查閱。現(xiàn)在為了準(zhǔn)備算法，會時常查閱此書。

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

3. 網(wǎng)絡(luò)教程
3.1 Top Coder的algorithm tutorial

posted @ 2011-07-01 20:27 hex108 閱讀(642) | 評論 (0) | 編輯收藏

2011年6月18日

二分查找 -- 來自編程珠璣

     二分查找法（Binary search algorithm）是一個很常見的算法，從＜編程珠璣＞里再次看到時又有新的收獲。
   直接看代碼吧，下面是常見的實現(xiàn)代碼：

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;
}

優(yōu)化后的代碼為（這個優(yōu)化的思想也挺好的，不知道有沒有一套系統(tǒng)的方法來思考出這個優(yōu)化思路）：

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

“程序驗證” 的思想可以簡述為：不管是驗證一個函數(shù)，還是一條語句，一個控制結(jié)構(gòu)（循環(huán)，if分支等），都可以采用兩個斷言（前置條件和后置條件）來達(dá)到這個目的。前置條件是在執(zhí)行該處代碼之前就應(yīng)該成立的條件，后置條件的正確性在執(zhí)行完該處代碼后必須得到保證。（ps: 斷言也算是一種驗證的手段）

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

參考：
　　１. 基本上摘自＜編程珠璣＞，很不錯的一本書，讓我對算法有了新的思考，以前只是看看算法導(dǎo)論如何實現(xiàn)的，沒有思考該算法是如何想出來的，有沒有更簡單的算法（思考的過程類似劉未鵬的＜知其所以然（續(xù)）＞），要堅持這個思考過程需要很多功夫與時間，但效果也很明顯，能對算法有更好的掌握。

posted @ 2011-06-18 15:02 hex108 閱讀(2852) | 評論 (3) | 編輯收藏

2011年5月17日

gdb,strace那些不常用的功能

摘要: 主要想介紹一下.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 閱讀(2661) | 評論 (3) | 編輯收藏

Debug

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

最近看了《軟件調(diào)試實戰(zhàn)》，結(jié)合自己的經(jīng)歷，總結(jié)了一下：

1. 與測試用例相關(guān)

a. 如果不能達(dá)到“測試先行”，至少應(yīng)該在寫完代碼后有相對完整的測試用例。對于正確性的保證和以后重構(gòu)代碼都是有好處的。

b. 每次添加新功能或修復(fù)了一個bug時，都應(yīng)該增加測試用例！A歷經(jīng)千辛萬苦終于fix 了一個bug，很久很久以后，B覺得這段代碼需要改改，于是改了改，后來的結(jié)果還是改了，而且順利提交到了庫里（因為A當(dāng)時遇到的bug 并沒有出現(xiàn)！）

c. 回歸測試

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

d. 簡化測試用例

好處：可以排除不起作用的因素；減少測試用例的運行時間；最重要的是，使用測試用例更容易調(diào)試（誰愿意處理那些填充了數(shù)百或數(shù)千項的數(shù)據(jù)容器呢？）

方法如：如果測試?yán)颖容^好改，可以將其改小；將輸入集改小

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

2. 關(guān)于程序的編譯

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

eg：
int add(int a,int b){
        return a +b ;
}
結(jié)果頭文件里聲明成了 extern int add(long a,int b)
會調(diào)試死人啊，調(diào)程序的時候一看程序定義是對的啊，怎么傳的參數(shù)一下就變了；
b. 如果出現(xiàn)莫名其妙的錯誤
      如果是用Makefile組織工程時，考慮make clean，有可能修改數(shù)據(jù)結(jié)構(gòu)或頭文件后改變了一些東西，但是由于一些未知原因該文件并未重新編譯。如果函數(shù)是C函數(shù)，有可能調(diào)用者和被調(diào)用者的參數(shù)的成員和類型不同。如果一個類方法，則訪問任何類成員都將發(fā)生錯誤，因為這兩個類的內(nèi)存而已幾乎是完全不同的。這可能導(dǎo)致Segmentation falut,或是很久之后才能檢測到的內(nèi)存破壞。
3. 關(guān)于鏈接
a. 鏈接器的基本工作原理
       編譯器或匯編程序?qū)⒃创a轉(zhuǎn)換為機器代碼，并輸出對象誰的。對象文件中包含符號（函數(shù)或變量），這些符號有的在本模塊定義的，有的在其他模塊定義的，鏈接器就在鏈接對象文件時把這些未定義的符號與定義它的模塊對應(yīng)起來。
b. 鏈接順序
     有庫和歸檔文件時鏈接算法是不一樣的。
     鏈接器參數(shù)順序很重要，對于編譯單元（如對象文件和庫）和搜索路徑來說都是如此。
c. C++中使用C代碼時，用extern c{} 把C代碼包裝一下。
     關(guān)于 c++符號和名稱改編：C++允許重載函數(shù)，為了生成C++代碼元素的唯一符號，編譯器使一種稱為名稱改編（name mangling）的技術(shù)，它將對象的準(zhǔn)確規(guī)格說明（如會員名空間和函數(shù)參數(shù)的個數(shù)及類型）編碼到符號中。（可以用c++filt解析出來~ eg: c++filt _Z9factoriali的結(jié)果為factorial(int)）
d. 環(huán)境變量
   LD_LIBRARY_PATH會影響動態(tài)加載的庫，用LDD可以看到程序依賴哪個動態(tài)庫
4. 自動化測試
   讓一切自動化起來。如果重復(fù)的做一件事，就很有必要考慮自動化了。
5. 關(guān)于那些怪異的錯誤
    在一些顯而易見有內(nèi)存問題的情況下，如：間歇故障和無法解釋的隨機行為，這時考慮使用內(nèi)存調(diào)試器了！
    如valgrind，很好用，也很簡單。
    valgrind –tool=massif your_program 進行內(nèi)存剖析（檢測內(nèi)存分配情況，優(yōu)化內(nèi)存使用）
    valgrind –tool=memcheck your_program 進行內(nèi)存檢查（檢測無效的寫訪問，檢測對未初始化的內(nèi)存的讀取操作，檢測內(nèi)存泄露等）
    valgrind –tool=helgrind your_program 查找競爭條件，可以用來輔助調(diào)試多線程程序
    valgrid –-db-attac=yes的功能很好用，可以將內(nèi)存高度器和源代碼測試器（如gdb）結(jié)合起來，這樣就可以即時查看當(dāng)時的變量的值，很好用！
6. 靜態(tài)檢查器
   作為常規(guī)軟件構(gòu)建過程中的一部分運行，用于查找一些可通過靜態(tài)源代碼分析發(fā)現(xiàn)的特定bug。
7. 關(guān)于運行時剖析工具
     不要編寫自己的運行時剖析時工具：自己霞友云朋一的剖析工具通常使用系統(tǒng)調(diào)用time()或ctime()來測量時間。這些系統(tǒng)調(diào)用的問題是開銷很高，而且準(zhǔn)確度低。另處在剖析期間要收集大量數(shù)據(jù)，可能會影響程序本身的行為。
8. 環(huán)境變量
如程序的行為可能依賴于當(dāng)前工作目錄。在linux上，目錄被注冊到環(huán)境變量CWD上。這個bug碰到過，還導(dǎo)致了死鎖。
9. 讀取恰當(dāng)?shù)腻e誤消息
某個地方出錯時，滿屏都是錯誤消息時，應(yīng)該重點關(guān)注哪些消息？
Answer: 首先出現(xiàn)的那些消息！因為后面的消息有可能是前面導(dǎo)致的。這和編譯出錯時的情景一致：編譯錯誤有很多，我們肯定會直覺地去尋找第一個出錯的地方，誰知道是不是少了個括號導(dǎo)致后面一連串的錯誤。
10. bug不會自動消失
      如果某個版本有bug，update后，bug消失了，“真好！”，一定要弄清楚bug出現(xiàn)的原因是什么。以前遇到過一個bug，增加一條printf語句后，bug消失了！最后發(fā)現(xiàn)問題是數(shù)組越界了，而修改源代碼會導(dǎo)致代碼段，數(shù)據(jù)段的布局等改變，所以會導(dǎo)致偶爾對。（這種情況可以求助于內(nèi)存調(diào)試工具或者靜態(tài)檢查的工具）
11. 學(xué)習(xí)使用gcc, gdb,strace 等工具。（熟悉以后可以再挖掘挖掘，可能有驚喜）
12. cvs/svn commit之前一定要diff一下，看做了哪些修改，以避免不小心刪掉一些東西后，然后”被提交”了。
最后，最強大的工具不在計算機中，而是調(diào)試者的判斷力和分析技巧。

參考資料：

1. 《軟件調(diào)試實戰(zhàn)》：http://book.douban.com/subject/4231293/

posted @ 2011-05-17 20:26 hex108 閱讀(464) | 評論 (0) | 編輯收藏

2011年4月23日

shell編程 : Remember that the shell spends a lot of its life substituting text

        對shell不熟，偶爾會現(xiàn)一些我無法理解的現(xiàn)象。此時該進行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變量經(jīng)替換后變?yōu)?if [ = "y" ]，些時當(dāng)然會出錯。

hex108@Gentoo ~ $ ./test.sh 
./test.sh: line 3: [: =: unary operator expected

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

posted @ 2011-04-23 00:23 hex108 閱讀(434) | 評論 (0) | 編輯收藏

常用鏈接

留言簿(3)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜