步骤：1. 选择其中一个数，假设它是中间值

            2. 遍历一遍，比它小的放一段，大的放另一端，记录其中一段的数目

            3. 在记录的数目的下一位，将中间值插回去

            4. 于此位置，将要排序的数列分成两段，递归做

从上面的步骤可以看出，分治的过程是快排的核心。

一些优化：

1. 选中间值时，若选在最大或者最小，并恰好数列是有序的，都会是噩梦。故最好使用三点定位法

2. 遍历并分置两端时，为了节省空间开销，常用原地分割法。通过交换应置于位置的数，与当前实际位置的数，在同一个数列内部区分大小端。但是此交换存在过多中间操作，一个数可能要被交换多次。使用替换法可以有效缩短时间。替换法首先让中间值等于其中一端的值，然后从两端交替对中间值进行比较，并互相替换。最后多出一位赋回中间值

3. 用迭代替换递归。不过虽说如此，若中间值选择不当，依然还是会发生层数过多的情况。

代码留档：

class sort:
    def quicksort(self, num, start, end):
        while (start < end):                        #迭代改造后的递归
            p = sort().partition(num, start, end)
            #print num
            sort().quicksort(num, start, p)
            start = p + 1
        return num

    def partition(self, num, start, end):           #替换法下的排序过程
        sort().generatePivot(num, start, end)
        target = num[start]
        while( start < end - 1  ):
            while(start < end -1  and num[end-1] > target) :
                end -= 1
            num[start] = num[end - 1]
            while(start < end - 1  and num[start] < target):
                start += 1
            num[end - 1] = num[start]
        num[start] = target
        return start

    def generatePivot(self, num, start, end):       #三点定位，将中间值放到最左侧
        middle = start + (end -1- start)/2
        if num[start] > num[end-1]:
            num[start],num[end-1] = num[end-1],num[start]
        if num[middle] > num[end-1]:
            num[middle],num[end-1] = num[end-1],num[middle]
        if num[middle] > num[start]:
            num[middle],num[start] = num[start],num[middle]

    def sort(self, num):
        return sort().quicksort(num, 0, len(num))

#test case
print sort().sort([2,1,3,7,5,4,6])
print sort().sort(range(20)[::-1])
print sort().sort(range(20))
print sort().sort(range(200000)[::-1])
print sort().sort(range(200000))

编译内核后，发现开机时OPENRC报错，说udev-mount 不能加载啊失败啊之类的。这个问题上次遇到过了，后来上网查了后解决了的，然后又忘记了。于是这次又遇到了，又无解了，只能再查。

现在果断记一笔：

 CONFIG_ DEVTMPFS  = y

虽然说记笔记应该有更好的方式，不过懒得折腾了。先在这随便记下吧。

Lemma, Wordform  ： 一句话中的WORD可以用两种不同的标准来区分。一种是Lemma，一种是wordform。 wordform就是词的形状，而lemma则是词意。比如 am   is  are ，都是一个lemma，但是3个wordform。

Type, Token ：倘若以wordform的形式来界定一个词，那么一句话中WORD的数目还可以用两种不同的标准来区分。Type是相同的词都算一个，Token是每个词出现几次都算。所以 "no no no .... it is not possible" 这样的一句话，Type 有5个，Token 有7个。

token常用N来表示，(number of tokens)， type 常用V来表示，(|V| 就是 size of vocabulary)，Church and Gale 1990年有个统计公式  |V| > O(N ^1/2)

这里它还展示了一个 Tokenization, 统计莎士比亚作品中的Token数。 tr 这个命令看上去不错，虽然 依云 说给出的指令组合比较低效，不如awk版的。但是我问他awk版的长什么样，他让我自己去翻wiki……

(note: 翻了下wiki，在词频统计这里，发现了Awk的方法：

BEGIN {
    FS="[^a-zA-Z]+"
}
{
     for (i=1; i<=NF; i++)
          words[tolower($i)]++
}
END {
    for (i in words)
         print i, words[i]
}

  这个可能效率上会快些，不过我也没实际time过。但是思路上完全就是两个不同的方向，更类似于专门来解决一个词频统计问题，而不是在遇到一堆文字时顺手所做。tr 的这个结合了管道和多钟工具的方法在思路上就自然多了 )

简单的通过正则匹配的 Tokenization 方式 还存在很多问题，比如一些词不好切分，一些词中间带了杂七杂八的符号但却又是同一个。更不用说中文分词这个东西了。 关于中文分词，这边认为，使用Greedy的方式来匹配很有效，不过同样的方法对英文又不适用。

Normalization，就是把各种形状的词，按意义统一起来。实际上就是找Lemma。或者说，Lemmatization是一个很好的Normalization的方法。把am is are 都转换成be，那自然就normal了。具体Lemmatization的方法很复杂，不过也有些可以解决部分问题的手段。比如说对于那些一个主干加了不同前缀后缀的词，就可以去掉前后缀，抓住主干。主干叫Stem，各种缀叫Affix。对于英文，有个Porter's algorithm 用于处理各种Affix。可惜这个办法没有任何通用性，而且容易找到例外。

Sentence Segmentation, 就是断句。这里讲了一些常用的断句方法，不过我觉得只适用于严肃的英文文本中。它主要基于标点和大小写来判断。通过“决策树”的方式。 决策树是一堆嵌套的if ... else， 这个目测就知道效率不会高。所以实际中也会用到不少其他方法。决策树的效果直接取决于判断条件，也就是features，这里需要记住几个看上去比较有技术含量的Numeric features:

 Length of word with "."

 Probability(word with "." occurs at end-of-s)

 Probability(word after "." occurs at beginning-of-s)

To terminate an intentionally infinite loop in Oracle, we can use DBMS_PIPE.

First, create a pipe.

        DBMS_PIPE.create_pipe(pipename);

Then, insert message handling into loop block.  

        if DBMS_PIPE.receive_message(pipename,0) = 0 then

               DBMS_PIPE.unpack_message(pipebuf);

               Exit when pipebuf = 'stop';

        end if;

When needed, send a message which content is "stop" to the pipe.

    DBMS_PIPE.create_pipe(pipename);

   DBMS_PIPE.pack_message('stop');

So the whole example is:

DECLARE
   pipename CONSTANT VARCHAR2(12) := 'signaler';
   result INTEGER;
   pipebuf VARCHAR2(64); 
 BEGIN
   result := DBMS_PIPE.create_pipe(pipename);

   LOOP
      xxxxx
      DBMS_LOCK.sleep(10);

      IF DBMS_PIPE.receive_message(pipename,0) = 0
      THEN
         DBMS_PIPE.unpack_message(pipebuf);
         EXIT WHEN pipebuf = 'stop';
      END IF;
   END LOOP;
 END;





DECLARE 
   pipename VARCHAR2(12) := 'signaler';
   result INTEGER := DBMS_PIPE.create_pipe(pipename);
BEGIN
   DBMS_PIPE.pack_message('stop');
END;

Scope is the region of a program unit in which a variable can be referenced, without qualified identifiers.

Visibility: without qualified identifiers a variable is visible in its scope. With qualified identifiers it is visible everywhere.

 ed,行编辑器,现在看上去很简陋,但是一举一动却透显着各种辉煌后继的渊源.

使用ed,每次可以处理一行.用ed打开文件时,它会定位于最后一行,并显示文件中的字符数.

比如我在电脑上有一份安装时的log:

[root ~] ll

total 304

...

-rw-r--r-- 1 root root  44611 Feb 22 23:44 install.log

...

现在用ed打开:

[root ~] ed install.log

44611

没有任何提示符,甚至没有告诉你现在所处的行号.虽然说知道是最后一行,但是最后一行是第几行却不知道.直接输入数字,可以跳到相应的第几行,这个采用绝对行号;也可以使用"-","+"来使用相对行号,也就是相对当前行的行号.如"-3",就是往前数三行的内容,不带数字则等于数字为1.  要查看当前行的内容,可以使用"p"命令. man手册上说,"."能显示当前行的address,我实在不明白这个address是什么意思,因为我输入"."后,回显结果跟"p"没有任何区别.

	[root ~]$ed install.log
44611
.
Installing zsh - 4.2.6-1.i386
p
Installing zsh - 4.2.6-1.i386
 

ed既然作为sed跟grep的祖先,自然支持正则表达式,以及正则表达式下的查找替换删除等等操作,甚至连语法也基本一样.所不同的是,它默认只针对当前行进行操作,如果要扩大范围,则需要加地址.比如"g",比如正则表示的地址.它的替换命令"s"的完整格式是:

[address]s /pattern/replacement/flag

pattern是个正则表达式,replacement则是所要替换成的字符串,flag倘若为"g"的话,则表示会替换这一行内所有出现的pattern,如果没有"g",则默认只替换第一个.

grep实际上就是将"g/re/p"给抽离了出来,单独做成了一个工具."re"表示正则.

sed命令跟ed命令一个很大的不同就是,sed命令如同grep一样,默认带有"g"属性.它加的"[address]"是为了缩小操作范围,而ed的"[address]"是为了扩大操作范围. 当然,从结果上来看,两者可以说没有区别,除非未指定address.

完整的ed命令,都可以在man文档中找到.我个人觉得在vi,sed,awk大行其道的今天,单纯的ed编辑器本身并没有太大必要关注了.但是"行编辑"这个概念,倒是可以给刚开始学习grep,sed之类的人解决不少疑问.