C++博客-hex108

[找工作]算法小结

hex108 — Wed, 24 Aug 2011 13:39:00 GMT

为一个问题寻找算法的过程，有点像一个穷举过程：搜索已有知识，并进行重组的过程。所以把常用的算法记住，然后一个一个试用，看是否可行，不失为一个好方法。

如果这个方法不行呢？不妨写出最直观的解答（即用“蛮力法”），然后从中看出可以优化的地方在哪里，进而进行优化。

如何确定该问题可以用哪类方法来解答呢？首先，需要对这些常用的算法的基本思想非常熟悉。
常用的算法可以分为以下几类：

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.本质上，练习并不产生新能力。然而练习最重要的一个作用就是将外显记忆转化为内隐记忆。用大白话来说就是将平时需要用脑子去想（参与）的东西转化为内在的习惯。譬如我们一开始学骑自行车的时候需要不断提醒自己注意平衡，但随着不断的联系，这种技能就内化成了所谓的程序式记忆
这就是熟能生巧吧。

hex108 2011-08-24 21:39 发表评论

[找工作]动态规划与贪心算法

hex108 — Wed, 24 Aug 2011 12:51:00 GMT

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

hex108 2011-08-24 20:51 发表评论

[找工作]数据结构小结

hex108 — Wed, 24 Aug 2011 12:15:00 GMT

要找工作了，终于觉得是时候总结一下数据结构了（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也很给力。

hex108 2011-08-24 20:15 发表评论

linux信号机制－用户堆栈和内核堆栈的变化

hex108 — Tue, 26 Jul 2011 10:27:00 GMT

此文只简单分析发送信号给用户程序后，用户堆栈和内核堆栈的变化。没有分析实时信号，当然整个过程基本一致。很多参考了＜情景分析＞，所以有些代码和现在的内核可能不同，比如RESTORE_ALL，但大体的机制是类似的。

1. 一个信号小例子

hex@Gentoo ~/signal $ cat sigint.c
#include
#include
#include

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    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 :   jmp    0x8048336
(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" 只是一段小插曲。程序从原处开始运行。

hex108 2011-07-26 18:27 发表评论

读<编程珠玑>，不要忘了还有这本经典

hex108 — Thu, 07 Jul 2011 12:47:00 GMT

     读的过程真是一种享受。看到好的代码，好的思想，总会忍不住默记几遍。

     看到觉得有点意味的地方最好多想想来龙去脉，想想为什么，因为紧接着的会是令人惊喜的解说。多写写书上的代码，感觉不错（写完以后感觉忘了很久的算法又重新回来了）。每章的“原理”部分是高度性的概括，"习题"是很好的，促使你去思考，做习题是很有必要的，不想“浪费”时间去“做习题”了的结果可能是以后会用更多的时间才能想清这些问题，还有不要只想着看答案，你会很失望，因为有些题目是没有答案的 :) 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
      *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;

    另外，注意到一本书＜算法设计与分析基础＞，用不同的方式讲算法，把算法按其通用程度提出了4个最基本的算法思想：Brute force ， Divide & conquer ， Decrease & conquer， Transform & conquer。

    最后摘录一下第1版跋里给的几个建议:
    1. 解决正确的问题。首先彻底理解问题
    2. 探索所有可能的解决方案
    3. 观察数据
    4. 使用粗略估算
    5. 得用对称性
    6. 利用组件做设计
    7. 建立原型
    8. 必要时进行权衡
    9. 保持简单
    10.追求优美

hex108 2011-07-07 20:47 发表评论

关于算法的一些资料

hex108 — Fri, 01 Jul 2011 12:27:00 GMT

算法的过程很详细，美中不足的是最基本最常用的那些算法其实是比较少的，花点时间多想想为什么，知其然还要知其所以然(1，2)，这样才能活学活用。

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

hex108 2011-07-01 20:27 发表评论

二分查找 -- 来自编程珠玑

hex108 — Sat, 18 Jun 2011 07:02:00 GMT

     二分查找法（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，而该循环始终保证上面第１条。
　　经过这样的分析后，我们能对程序的正确性有更好的掌握，同时程序也更易理解。

参考：
　　１. 基本上摘自＜编程珠玑＞，很不错的一本书，让我对算法有了新的思考，以前只是看看算法导论如何实现的，没有思考该算法是如何想出来的，有没有更简单的算法（思考的过程类似刘未鹏的＜知其所以然（续）＞），要坚持这个思考过程需要很多功夫与时间，但效果也很明显，能对算法有更好的掌握。

hex108 2011-06-18 15:02 发表评论

gdb,strace那些不常用的功能

hex108 — Tue, 17 May 2011 13:14:00 GMT

摘要: 主要想介绍一下.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 阅读全文

hex108 2011-05-17 21:14 发表评论

Debug

hex108 — Tue, 17 May 2011 12:26:00 GMT

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/

hex108 2011-05-17 20:26 发表评论

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

hex108 — Fri, 22 Apr 2011 16:23:00 GMT

        对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相对来说更好重构。

hex108 2011-04-23 00:23 发表评论