使用zlib读写gz文件

zlib is A Massively Spiffy Yet Delicately Unobtrusive Compression Library. The utility functions in zlib are very much like the stdandard I/O funtions in <stdio.h>.

Demo in short:

#include "zlib.h"

/* write buffer to gz file */

gzFile fp = gzopen("file.gz", "wb");
/* Writes the given number of uncompressed bytes into the compressed file.*/
gzwrite(fp, buffer, sizeof(buffer));
gzclose(fp);


/*  read gz file into buffer */

gzFile fp = gzopen("file.gz", "rb");
/* read the given number of uncompressed bytes from the compressed file */
gzread(fp, buffer, sizeof(buffer));
/* or read a line */
gzgets(fp, buffer, sizeof(buffer));
gzclose(fp);

Use option "-lz" to link with zlib library.

Read more:
http://www.zlib.net/manual.html

emacs浏览代码工具etags,gtags

global:
http://www.gnu.org/software/global/

装好后, 去到代码目录:
$ cd src
$ gtags

.emacs
;;global
(autoload 'gtags-mode "gtags" "" t)
(gtags-mode 1)
(global-set-key (kbd "C-]") 'gtags-find-tag-from-here)

C-] 跳到定义
M-* 跳回

global现在不支持python，浏览python代码用etags也足够了:
$ etags *.py

在emacs里,
M-. 第一次会提示你指定TAGS路径..然后会跳转到定义处.
M-* 跳回.

sicp习题解答1.3.2 - 1.3.3

上一节1.3.1

;;Exercise 1.34
(define (f g)
  (g 2))

;;Exercise 1.35
(define tolerance 0.00001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)



;;Exercise 1.36
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (display guess)
    (newline)
    (let ((next (f guess)))
      (if (close-enough? guess next)
          next
          (try next))))
  (try first-guess))

(define (average x y)
  (/ (+ x y) 2))


;take with average damping
(fixed-point (lambda (x)(average x (/ (log 1000) (log x)))) 5)
;without average damping
(fixed-point (lambda (x) (/ (log 1000) (log x))) 5)


Welcome to DrScheme, version 372 [3m].
Language: Standard (R5RS).
5
4.64601483711009
4.571611286076025
4.558294317536066
4.556006022881116
4.555615799731297
4.555549342575593
4.555538027101999
4.5555361005218895


5
4.29202967422018
4.741863119908242
4.438204569837609
4.635299887107611
4.50397811613643
4.589989462723705
4.53301150767844
4.570475672855484
4.545720389670642
4.562024936588171
4.551263234080531
4.55835638768598
4.553676852183342
4.55676216434628
4.554727130670954
4.556069054770006
4.555184018843625
4.5557676565438205
4.555382746639082
4.55563658243586
4.555469180245326
4.555579577900997
4.5555067722873686
4.5555547860484085
4.555523121789556
4.555544003742869
4.555530232469306
4.555539314360711
>

;;Exercise 1.37
(define (cont-frac n d k)
  (define (iter i)
    (if (= i k)
        (/ (n k) (d k))
        (/ (n i) (+ (d i)
                    (iteer (+ i 1))))))
  (iter 1))

(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           12)



;;Exercise 1.38
(define (e-2)
  (define (d i)
    (if (= (remainder i 3) 2)
        (* (/ (+ i 1) 3) 2)
        1))
  (cont-frac (lambda (i) 1.0)
             d
             12))
(e-2)



;;Exercise 1.39
(define (tan-cf x k)
  (cont-frac (lambda (i) (if (= i 1) x (- (square x))))
             (lambda (i) (- (* 2 i) 1))
             k))

给BBS添加一个显示文章信息的功能

本文说的BBS是逸仙时空系统telnet端(Puke Bulletin Board System Version 0.1.2 Beta, 由firebird 2000发展而来)

[功能解释]
在文章列表时,

按 * 键显示文章的信息 (url, 利于直接用web方式查看(比如说有人贴了ppmm的照片))
虽然已经有显示文章链接功能，可是有些文章会死活都显示不出来的 (此bug很牛b, 曾尝试跟踪, 搞不定)

在代码里有这样一个结构:

struct one_key {  /* Used to pass commands to the readmenu */
  int key;
  int (*fptr) ();
};

一个按键， 对应一个函数指针. 用户按一下那个键，就会跳到那个函数处执行。

用户进入版面这个过程对应的是bbs.c里Read()这个函数,
Read会用下面read_comms作为参数去调用read.c里的 i_read函数.
i_read里面进行一些处理后就会进入键盘指令循环: 获取键盘按键, 执行相应函数.

节选一些 read_comms, 如果你熟悉bbs操作， 就明白了。

struct one_key read_comms[] = {
{ '_', underline_post },            /* 设置不可回复标记 */
{ 'r', read_post },                 /* 阅读文章 */
{ 'K', skip_post },                 /* 跳过文章 */
{ 'd', d_action },                  /* 删除文章/解除匿名封禁 */
{ 'E', E_action },                  /* 编辑文章/清空回收站 */
{ 'D', del_range },                 /* 区段删除文章 */
{ 'm', mark_post },                 /* 标记文章 (m) */
{ 'g', digest_post },               /* 标记文章 (g) */
{ 'e', select_post },               /* 标记文章 ($) (monster) */
{ Ctrl('G'), digest_mode },         /* 文摘模式 */
{ '`', digest_mode },               /* 文摘模式 */
{ Ctrl('Y'), pure_mode },           /* 原作模式 (monster) */
{ Ctrl('T'), acction_mode },        /* 多种模式切换 */
{ 't', thesis_mode },               /* 主题模式 */
{ 'T', edit_title },                /* 更改文章标题 */
{ 's', do_select },                 /* 选择版面 */
{ Ctrl('C'), do_cross },            /* 转载文章 */
{ Ctrl('E'), process_select_post }, /* 处理选定文章 (monster) */
{ Ctrl('V'), x_lockscreen_silent }, /* 锁屏 (monster) */
{ 'h', mainreadhelp },              /* 显示帮助 */
{ Ctrl('J'), mainreadhelp },        /* 显示帮助 */
{ KEY_TAB, show_b_note },           /* 查看备忘录 */
{ 'z', show_b_secnote },            /* 查看秘密备忘录 */
{ 'x', currboard_announce },     /* 查看精华区 */
{ 'a', a_action },                  /* 向后搜索作者/封禁 */
{ '/', title_search_down },         /* 向后搜索标题 */
{ 'b', bmfuncs },                   /* 版主特殊功能 */
+ { '*', show_fileinfo },      /* 显示全文链接等, 这是我们要添加的*/
{ '\0', NULL }
};

这些函数的参数一般都是3个:
int ent, 是当前文章(即光标对应的那篇文章)的序号
struct fileheader *fileinfo, 是当前文章的文件头信息(文件名, 作者等)
char *direct 是当前版面索引文件路径(例如: $BBSHOME/boards/Joke/.DIR)


在bbs.c里添加上这个处理函数show_fileinfo:

int
show_fileinfo(int ent, struct fileheader *fileinfo, char *direct)
{
 /* get file size */
 struct stat st;
 char buf[512], filepath[512];
 char *t;
 
 strlcpy(buf, direct, sizeof(buf));
 if ((t = strrchr(buf, '/')) != NULL)
  *t = '\0';
 
 snprintf(filepath, sizeof(filepath), "%s/%s", buf, fileinfo->filename);
 if (stat(filepath, &st) != -1)
  fileinfo->size = st.st_size;
 
 clear();
 move(5, 0);
 prints("本文全文链接:\n");
 prints("http://%s/bbscon?board=%s&file=%s\n\n",
        BBSHOST, currboard, fileinfo->filename);
 prints("文章发表时间: %d\n\n", fileinfo->filetime);
 prints("文章大小: %d 字节\n\n", fileinfo->size);
 return FULLUPDATE;
}

在头文件 include/prototypes.h 里添加上这个函数的原型。
int show_fileinfo(int ent, struct fileheader *fileinfo, char *direct);

好了。
make update; 重启bbsd后就有这个功能了～

sicp习题解答sec_1.3.1

上一节

;;Exercise 1.29
(define (Simpson f a b n)
  (define h (/ (- b a) n)) ; n is an even number

  (define (y k)
    (f (+ a (* k h))))

  (define (iter i)
    (if (< i n)
        (if (even? i)
            (+ (* 2 (y i))
               (iter (+ i 1)))
            (+ (* 4 (y i))
               (iter (+ i 1))))
        0))

  (* (/ h 3)
     (+ (y 0)
        (y n)
        (iter 1))))


(define (cube x)
  (* x x x))

(Simpson cube 0 1 100)
(Simpson cube 0 1 1000)


;;Exercise 1.30
(define (sum term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (+ result (term a)))))
    (iter a 0))


;;Exercise 1.31
;a)
(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

(define (factorial n)
  (define (identity x) x)
  (define (inc x) (+ x 1))
  (product identity 1 inc n))

(define (pi n)
  (* 4 (product (lambda (x) (/ (* (- x 1.0) (+ x 1)) (* x x)))
                3
                (lambda (x) (+ x 2))
                n)))

(pi 1000000)


;b)
(define (product2 term a next b)
  (define (iter prod i)
    (if (> i b)
        prod
        (iter (* (term i) prod) (next i))))
  (iter 1 a))


;;Exercise 1.32
(define (accumulate combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner (term a) (accumulate combiner null-value term (next a) next b))))

(define (sum term a next b)
  (accumulate (lambda (x y) (+ x y)) 0 term a next b))

(define (product term a next b)
  (accumulate (lambda (x y) (* x y)) 1 term a next b))


;b)
(define (accumulate2 combiner null-value term a next b)
  (define (iter result i)
    (if (> i b)
        result
        (iter (combiner result (term i)) (next i))))
  (iter null-value a))



;;Exercise 1.33
(define (filtered-accumulate combiner null-value term a next b filter)
  (define (iter result i)
    (if (> i b)
        result
        (iter (combiner result
                        (if (filter i)
                            (term i)
                            null-value))
              (next i))))
  (iter null-value a))


;a) #中文版题目没平方.
(define (sum-of-squares-of-primes a b)
  (filtered-accumulate (lambda (x y) (+ x y))
                       0
                       square
                       a
                       inc
                       b
                       prime?))

;b)
(define (relatively-prime-to-n? i)
  (= 1 (gcd i n)))

(define (profuct-of-relaviely-prime-to-n n)
  (filtered-accumulate (lambda (x y) (* x y))
                       1
                       identity
                       1
                       inc
                       (- n 1)
                       relatively-prime-to-n?))

 

sicp习题解答1.2

上一节

;;Exercise 1.9.
The first one is recursive,
and the second one is iterative (tail recursive).


;;Exercise 1.10.
由(A x y)定义得出
(f n) = (2n)

(A 1 10)
(A 0 (A 1 9)) 得出
(g n) = (2^n)

(A 2 10)
(A 1 (A 2 9))
(A 2 1) = 2
得出

(h n) = (pow2 (h (- n 1)))
that is, 2 ^ (2 ^ (... 2)) ;; n times


;;Exercise 1.11.
(define (f-recur n)
(if (< n 3) n
    (+ (f-recur (- n 1))
       (* 2 (f-recur(- n 2)))
       (* 3 (f-recur(- n 3))))))

(define (f-iter n)
(define (iter a b c count)
  (if (= 0 count) c
      (iter b c
            (+ (* 3 a) (* 2 b) c)
            (- count 1))))
(if (< n 3) n
    (iter 0 1 2 (- n 2))))



;;Exercise 1.12.
(define (Yang-Hui-San-Jiao nline)
(define (Yang-Hui-cell row col)
  ;;; (assert (not (> col row)))

    (cond ((or (= row 1)
             (= col 1)
             (= row col)) 1)
        (else (+ (Yang-Hui-cell (- row 1) (- col 1))
                 (Yang-Hui-cell (- row 1) col)))))

(define (Yang-Hui-line row)
  (define (iter c)
    (display (cons (Yang-Hui-cell row c) '()))
    (if (< c row)
        (iter (+ c 1))))

  (iter 1)
  (newline))

(define (iter r)
  (Yang-Hui-line r)
  (if (< r nline)
      (iter (+ r 1))))

(iter 1))


;;test
(Yang-Hui-San-Jiao 10)


;;Exercise 1.13.
翻定义and归纳法证明.


;;Exercise 1.14.
O(amount + kinds-of-coins) in space.
O(result * amount) in time.
refer to this


;;Exercise 1.15.
a. 5 times.
b. O(log3(n)) in both time and space.


;;Exercise 1.16.

(define (fast-expt-iter B N)
;;; loop invariant: ab^n = B^N

  (define (iter a b n)
  (cond ((= 0 n) a)
        ((even? n) (iter a (* b b) (/ n 2)))
        (else (iter (* a b) b (- n 1)))))

(iter 1 B N))


;;Exercise 1.17
(define (fast-multi a b)
(define (double a) (+ a a))
(define (halve a) (/ a 2))
(cond ((= 0 b) 0)
      ((even? b) (fast-multi (double a) (halve b)))
      (else (+ a (fast-multi a (- b 1))))))

(fast-multi 10 15)
(fast-multi 100 16)



;;Exercise 1.18
(define (fast-multi-iter a b)
(define (iter a b res)
  (cond ((= 0 b) res)
        ((even? b) (iter (double a) (halve b) res))
        (else (iter a (- b 1) (+ res a)))))
(iter a b 0))



;;Exercise 1.19
;(b a) -> (a b+a)

;(b a) * [0, 1] = (a b+a)


;a <-  bq + aq + ap
;b <-  bp + aq


;(a, b) * [q+p, q] = (bq + aq + ap, bp + aq)


;[q+p, q] ^ 2  = [(q+p)^2 + q^2, (q+p)q+qp] = [q'+p', q']
;[q,   p]         [q(q+p) + pq  , q^2 + p^2] = [q'   , p']

(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
      ((even? count)
       (fib-iter a
                 b
                 (+ (* q q) (* p p))  ; compute p'

                   (+ (* q q) (* 2 p q)); compute q'
                   (/ count 2)))
      (else (fib-iter (+ (* b q) (* a q) (* a p))
                      (+ (* b p) (* a q))
                      p
                      q
                      (- count 1)))))

;;Exercise 1.20
(define (gcd a b)
(if (= b 0)
    a
    (gcd b (remainder a b))))


;; 正则序
http://eli.thegreenplace.net/2007/07/04/sicp-sections-124-125/
(gcd 206 40)
(gcd 40 (remainder 206 40))
->
(if (= (remainder 206 40) 0) ; 1 time
  40
(gcd (remainder 206 40)
  (remainder 40 (remainder 206 40))))
->
(if (= (remainder 40 (remainder 206 40)) 0) ; 2 times

  (remainder 206 40)
(gcd
  (remainder
    40
    (remainder 206 40))
  (remainder
    (remainder 206 40)
    (remainder
      40
      (remainder 206 40)))))
-> ...
18次

(gcd 206 40) ;; remainder 1
(gcd 40 6)   ;; remainder 2
(gcd 6 4)    ;; remainder 3
(gcd 4 2)    ;; remainder 4

(gcd 2 0)
4次


;;Exercise 1.21
(define (smallest-divisor n)
(define (find-divisor n test-divisor)
  (cond ((> (* test-divisor test-divisor) n) n)
        ((= (remainder n test-divisor) 0) test-divisor)
        (else (find-divisor n (+ 1 test-divisor)))))
(find-divisor n 2))

(smallest-divisor 199)   ;199

(smallest-divisor 1999)  ;1999
(smallest-divisor 19999) ;7


;;Exercise 1.22
(define (prime? n)
(= (smallest-divisor n) n))

(define (timed-prime-test n)
(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(newline)
(display n)
(start-prime-test n (runtime)))


(define (search-for-primes begin end)
(cond ((< begin end)
       (timed-prime-test begin)
       (search-for-primes (+ 2 begin) end))))

(search-for-primes 1001 1020)

;; 1009, 1013, 1019
(search-for-primes 10001 10038)
;; 10007, 10009, 10037
(search-for-primes 100001 100044)
;; 100003, 100019, 100043
(search-for-primes 1000001 1000038)
;; 1000003, 1000033, 1000037

;Curiously, timing the runs for 1,000 10,000 100,000 and 1,000,000
;doesn’t work because my computer is too fast
;(SICP was written in the 80s!) – all the runs
;just take 0 seconds, which means that the runtime is
;below the resolution of the timer used in the timing.


;;Exercise 1.23
(define (smallest-divisor n)
(define (next n)
  (if (= n 2)
      3
      (+ n 2)))
(define (find-divisor n test-divisor)
  (cond ((> (* test-divisor test-divisor) n) n)
        ((= (remainder n test-divisor) 0) test-divisor)
        (else (find-divisor n (next test-divisor)))))
(find-divisor n 2))



;;Exercise 1.24
(define (expmod base exp m)
(cond ((= exp 0) 1)
      ((even? exp)
       (remainder (square (expmod base (/ exp 2) m))
                  m))
      (else
       (remainder (* base (expmod base (- exp 1) m))
                  m))))

(define (fermat-test n)
(define (try-it a)
  (= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
(cond ((= times 0) true)
      ((fermat-test n) (fast-prime? n (- times 1)))
      (else false)))

(define (timed-prime-test n)
(define (start-prime-test n start-time)
  (if (fast-prime? n)
      (report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

(newline)
(display n)
(start-prime-test n (runtime)))



;;Exercise 1.25
It's correct if arbitary precision arithmetic is supported.
But it will be much slower than the implementation provided
by the authors.


;;Exercise 1.26.
粗略地：
2 ^ log2(m) = m


;;Exercise 1.27.
(define (Carmichael-test n)
(define (try-it a)
  (= (expmod a n n) a))
(define (iter i)
  (cond ((= i 1) #t)  ;; no need to test (1^n = 1 % n)
          ((not (try-it i)) #f)
        (else (iter (- i 1)))))
(and (not (prime? n))
     (iter (- n 1))))

(Carmichael-test 561)
(Carmichael-test 1105)
(Carmichael-test 1729)
(Carmichael-test 2465)
(Carmichael-test 2821)
(Carmichael-test 6601)


;;Exercise 1.28.
 ; ref: CLRS 31.6,31.8
(define (square x)
(* x x))

(define (Miller-Rabin n)
(define (check x)
  (define result
    (remainder (square x) n))
  (if (and
       (= result 1)
       (not (or (= x 1) (= x (- n 1)))))
      0
      result))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (check (expmod base (/ exp 2) m)))
         (else (remainder (* base (expmod base (- exp 1) m))
                          m))))

(define (try-it a)
  (cond ((= a 0) #t)
        ((= 1 (expmod a (- n 1) n))
         (try-it (- a 1)))
        (else #f)))
(try-it (- n 1)))


(Miller-Rabin 233)
(Miller-Rabin 9999)
(Miller-Rabin 561)
(Miller-Rabin 1105)
(Miller-Rabin 1729)
(Miller-Rabin 2465)
(Miller-Rabin 2821)
(Miller-Rabin 6601)

sicp习题解答1.1

;;Exercise.1.2
(/ (+ 5 4
     (- 2 (- 3 (+ 6 (/ 4 5)))))
  (* 3
     (- 6 2)
     (- 2 7)))

-37/150

;;Exercise 1.3.
(define (sum-of-max-two a b c)
 (cond ((and (> b a) (> c a)) (+ b c)) ;; no a

        ((and (> a b) (> c b)) (+ a c)) ;; no b
        (else (+ a b))))

;;[test]

(sum-of-max-two 4 5 5)
(sum-of-max-two 1 2 3)
(sum-of-max-two 3 2 1)
(sum-of-max-two 4 5 4)

;;Exercise 1.4.
(if (> b 0) + -) ;根据b的正负返回运算符+或-

;;Exercise 1.5.
应用序求值会死循环, 因为会先对参数求值, (p)不断调用自己.

正则序求值返回0, 因为(p)不会被展开.

;;Exercise 1.6.
如果把if定义成普通函数,则计算时,需要对实际参数进行求值,这会导致无限递归.


;;Exercise 1.7.
(define (good-enough? guess x)
 (< (/ (abs (- guess
               (improve guess x)))
       guess)
    0.000000000001))



;;Exercise 1.8.
(define (cube-root x)
 (define (cube-root-iter guess x)
   (if (good-enough? guess x)
       guess
       (cube-root-iter (improve guess x)
                       x)))
 (cube-root-iter 1.0 x))

(define (improve guess x)
 (/ (+ (/ x
          (* guess guess))
       (* guess 2))
    3))

平摊分析 (amortized analysis)

在平摊分析中，执行一系列数据结构操作所需要的时间是通过执行的所有操作求平均而得出的。平摊分析可以用来证明在一系列操作中，通过对所有操作求平均之后，即使其中单一的操作具有较大的代价，平均代价还是很小的。

平摊分析不牵涉到概率, 平摊分析保证在最坏情况下，每个操作具有的平均性能。

三中最常用的技术：

1．聚集分析(aggregate analysis)

证明对所有的n， 由n个操作所构成的序列的总时间在最坏情况下为T(n)

例子：

栈操作

PUSH(S, x):将x压入S

POP（S）：弹出栈顶

MULTIPOP（S, k）：弹出栈顶k个对象

由n个PUSH， POP和MULTIPOP操作序列，其作用于一个初始为空的栈。

分析：每个操作的最坏情况时间是O（n）. 因此n个操作的序列的代价是O (n^2)

虽然这一分析正确，但这个界不够紧确，利用聚集分析,可以获得更好的上界。

一个对象在每次被压入栈后，至多被弹出一次。所以，调用POP（包括MULTIPOP）的次数至多等于PUSH的次数，即至多为n.。对任意的n，包含n个PUSH, POP, MULTIPOP操作的序列的总时间为O(n). 每个操作的平均代价为O(n) / n = O(1).。 聚集分析中，将每个操作的平摊代价指派为平均代价。所以三个栈操作的平摊代价都是O(1)。



2．记帐方法

在平摊分析的记帐方法中，对不同的操作赋予不同的费用，某些操作的费用比它们的实际代价或多或少。

我们对一个操作的收费的数量称为平摊代价。当一个操作的平摊代价超过了它的实际代价时，两者的差值就被当作存款(credit)，并赋予数据结构中的一些特定对象，可以用来补偿那些平摊代价低于其实际代价的操作。这种方法与聚集分析不同的是，对后者，所有操作都具有相同的平摊代价。

数据结构中存储的总存款等于总的平摊代价和总的实际代价之差。注意：总存款不能是负的。



例子：栈操作

实际代价：

PUSH 1

POP 1

MULTIPOP min(k, s)

现在对它们赋予以下的平摊代价：

PUSH: 2

POP: 0

MULTIPOP 0

假设用1元钱来表示代价的单位。开始时栈时空的。

栈数据结构与餐厅中一堆叠放的盘子类似。当把一个盘子压入栈时，用1元钱来支付该动作的实际代价，还有1元的存款，将其放在盘子的顶上。盘子上面的钱时用来预付将盘子从栈中弹出所需代价的。当执行一个POP操作时，对该操作不收取任何费用，只需用盘中存放的存款来支付其实际代价即可。同理，也无需对MULTIPOP收取任何费用。

因为栈上的每个盘子上面都有1元钱，而且栈中总有非负个数的盘子。这就保证了存款的总量总是非负的。这样，对任意的包含n次PUSH, POP, MULTIPOP操作的序列，总的平摊代价就是总的实际代价的一个上界。总的平摊代价为O(n), 故总的实际代价也为O(n).



3．势能方法

在平摊分析中，势能方法（potential method）不是将已预付的工作作为存在数据结构特定对象中存款来表示，而是表示成一 种“势能”或“势”，它在需要时可以释放出来，以支付后面的操作。势是与整个数据结构而不是其中的个别对象发生联系的。

对一个初始数据结构D0 执行n个操作。对每个i，设ci为每个操作的实际代价，

Di 为对数据结构Di-1执行第i个操作的结果. 势函数Φ 将每个数据结构Di 映射为一个实数Φ(Di), 即与Di相联系的势. 第i个操作的平摊代价ai根据势函数Φ 定义为

ai ＝ ci ＋ Φ(Di) － Φ(Di-1)

每个操作的平摊代价为其实际代价ci加上由于该操作所增加的势。

n个操作的总的平摊代价为

∑ai ＝ ∑ci ＋Φ(Dn) － Φ(D0)

如果我们能定义一个势函数Φ使得对所有n，有Φ(Dn) ≥ Φ(D0), 则总的平摊代价∑ai就是总的实际代价∑ci的一个上界。通常为了方便起见定义Φ(D0) ＝ 0。

直观上看，如果第i个操作的势差Φ(Di) - Φ(Di-1)是正的，则平摊代价ai表示对第i个操作多收了费，同时数据结构的势也随之增加了。如果势差是负值，则平摊代价就表示对第i个操作的不足收费，这是通过减少势来支付该操作的实际代价。

平摊代价依赖于所选择的势函数Φ。不同的势函数可能会产生不同的平摊代价，但它们都是实际代价的上界。最佳势函数的选择取决于所需的时间界。



例子：栈操作

定义栈上的势函数Φ为栈中对象的个数。开始时要处理的空栈D0，且Φ(D0)＝0。因为栈中的对象数始终时非负的，故在第i个操作后，栈Di就具有非负的势。

以Φ表示的n个操作的平摊代价的总和就表示了总的实际代价的一个上界。

现在计算各个操作的平摊代价。

如果作用于一个包含s个对象的栈上的第i个操作是PUSH：

则势差为Φ(Di) － Φ(Di-1) = (s+1) – s = 1

这个PUSH操作的平摊代价为ai ＝ ci ＋ Φ(Di) － Φ(Di-1) = 1+1=2

假设栈上的第i个操作是MULTIPOP(S, k). 该操作的实际代价为min(s, k).

势差为Φ(Di) － Φ(Di-1) = - min(s, k)

因此MULTIPOP操作的平摊代价为

ai ＝ ci ＋ Φ(Di) － Φ(Di-1) ＝ min(s, k) - min(s, k) = 0

类似POP操作的平摊代价也是0。

三中栈操作的每一种的平摊代价都是O(1)， 这样包含n个操作的序列的总平摊代价就是O(n)。已经证明n个操作的平摊代价的总和是总的实际代价的一个上界。所以n个操作的最坏情况代价为O(n).



例子：

动态表，当向满的表插入一项时，将表扩大一倍，但当删除一项而引起表不足1/4满时（不是1/2），就将表缩写为原来的一半。

可以利用平摊分析，证明插入和删除操作的平摊代价均为O(1).


-- <<算法导论>> 笔记

Semantic配置C++自动补全

先上pp, 点击查看大图:

( 我输入了"v.pu" 自动补全为v.push_back, 按一下tab确认)

Semantic is part of cedet(Collection of Emacs Development Environment Tools)

下面内容主要参考这篇文章:

1. Check out the latest cedet src:

cvs -z3 -d:pserver:anonymous@cedet.cvs.sourceforge.net:/cvsroot/cedet co -P cedet

2. Build cedet:

cd cedet
touch `find -name "Makefile"`
make bootstrap

3. Install:
copy the cedet dir to your emacs site-lisp:
/usr/share/emacs/23.0.60/site-lisp/ (press 'ctrl-h v load-path' in emacs to see it)

4. 配置 (.emacs)

(require 'cedet)

• 通过下面方式查看g++ include paths:

freestyler@effarr:~/program$ touch dummy.cpp
freestyler@effarr:~/program$ gcc -v -E -P dummy.cpp
使用内建 specs。
目标：i486-linux-gnu
配置为：../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --with-gxx-include-dir=/usr/include/c++/4.2 --program-suffix=-4.2 --enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc --enable-mpfr --enable-targets=all --enable-checking=release --build=i486-linux-gnu --host=i486-linux-gnu --target=i486-linux-gnu
线程模型：posix
gcc 版本 4.2.3 (Ubuntu 4.2.3-2ubuntu7)
/usr/lib/gcc/i486-linux-gnu/4.2.3/cc1plus -E -quiet -v -P -D_GNU_SOURCE dummy.cpp -mtune=generic
忽略不存在的目录“/usr/local/include/i486-linux-gnu”
忽略不存在的目录“/usr/lib/gcc/i486-linux-gnu/4.2.4/../../../../i486-linux-gnu/include”
忽略不存在的目录“/usr/include/i486-linux-gnu”
头文件查找路径(用“:”分隔)：
头文件查找路径(用“:”分隔)：
/usr/include/c++/4.2
/usr/include/c++/4.2/i486-linux-gnu
/usr/include/c++/4.2/backward
/usr/local/include
/usr/lib/gcc/i486-linux-gnu/4.2.4/include
/usr/include
搜尋結果清單

• Add the following to your c++-mode-hook:

;;;;semantic
;;;;以下3个按机器适用的强劲程度排列，最下面的对机器需求最低。三选一。
;; (semantic-load-enable-gaudy-code-helpers)
;; (semantic-load-enable-code-helpers)

(semantic-load-enable-minimum-features)
(eval-after-load "semantic-c"
;;下面的路径是通过上面的方式查看到的
'(dolist (d (list
"/usr/include/c++/4.2"
"/usr/include/c++/4.2/i486-linux-gnu"
"/usr/include/c++/4.2/backward"
"/usr/local/include"
"/usr/lib/gcc/i486-linux-gnu/4.2.4/include"
"/usr/include"))
(semantic-add-system-include d)))

(eval-after-load "semantic-complete"
'(setq semantic-complete-inline-analyzer-displayor-class
semantic-displayor-ghost)) ;;; 这是补全弹出方式.

;;;建立这个目录先
(setq semanticdb-default-save-directory
(expand-file-name "~/.emacs.d/semanticdb"))

(local-set-key (kbd "M-/") 'semantic-complete-analyze-inline)
(local-set-key "." 'semantic-complete-self-insert)
(local-set-key ">" 'semantic-complete-self-insert)

附录: g++ option:

-v Print (on standard error output) the commands executed to run the stages of compilation. Also print the version number of the compiler driver program and of the preprocessor and the compiler proper.

-E Stop after the preprocessing stage; do not run the compiler proper. The output is in the form of preprocessed source code, which is sent to the standard output.

-P Inhibit generation of linemarkers in the output from the preprocessor. This might be useful when running the preprocessor on something that is not C code, and will be sent to a program which might be confused by the linemarkers.

用 C 实现一个变长数组中的技巧

在云风的博客 用 C 实现一个变长数组中提到:

"一般的 vector 的实现，需要记录三个数据：数据空间的地址，空间大小，数组里已存在的元素个数。
....
我这几天在写代码时发现，如果你遵照空间加倍这个策略来运作，其实并不需要三个变量来维持 vector 结构，两个就够了。那个表识容量大小的变量是多余的。:D"

有如下代码:

struct vector {
  int *data;
  int size;
};

void
vector_expand(struct vector *v, int s)
{
  int new_size=v->size + s;
  if ((new_size ^ v->size) > v->size) {
     v->data=(int *)realloc(v->data,sizeof(int)*(new_size * 2 - 1));
  }
}

一开始不理解, 后来想通了, 记录一下:
capacity表示分配的空间容量.
binary_len(i) 表示i的2进制位的长度.
那么
if ((new_size ^ v->size) > v->size) 这句等价于
if (binary_len(new_size) > binary_len(v->size))

为什么等价？
如果len(new_size) = len(v-size), 最高位1被异或掉了,
那么结果的位数就会小于v->size的位数.

这样,那句话的`深层'含义是说只有当new_size的(2进制位)长度比size的增加了,
才有可能发生new_size > capacity.

因为有个隐含的前置条件或者循环不变式:
capacity = last_size * 2 - 1 (其中last_size是上一次分配时已存在元素的个数)
只要size没有发生位数变化, 是不可能超过capacity的.

举个边界情况的例子:
假如上一次分配内存时, size = (10000), 则capacity = (11111),
那么new_size只要还是5位数, 异或结果就会小于 v->size. 就还不需要分配空间.

the First hello world in computer literature

Occured in Kernighan's 1972 Tutorial Introduction to the Language B

main( ) {
  extrn a, b, c;
  putchar(a); putchar(b); putchar(c); putchar('!*n');
}
a 'hell';
b 'o, w';
c 'orld';

http://en.wikipedia.org/wiki/Hello,_world

[Computer]为什么计数应该从0开始?

例如, 为了表达自然数序列 2, 3, ..., 12
有下面4种惯用表示法:
a) 2 ≤ i < 13
b) 1 < i ≤ 12
c) 2 ≤ i ≤ 12
d) 1 < i < 13

选择哪种好呢?

a)和b)有个优势: 上界跟下界的差 = 序列的长度,
因此两个相邻的序列会有这样的特点:一个序列的上界=另一个序列的下界.
比如a) 2 ≤ i < 13, 13 ≤ j < 69
好像这个理由还不足于我们选择a)或b).

我们知道, 数学上有一个最小的自然数m. 如果序列的表示法把下界排除掉的话,
比如b)和d), 考虑一个从最小的自然数开始的序列, 那么表示这个序列的下界就是一个非自然数了.这是多么丑陋阿, 在下界表示这点上, 我们选择 a)和c).

再来看看上界,如果序列表示法把上界包含进来的话,表示长度为0的序列应该只能是这样: p ≤ i ≤ p-1,
假如p是最小的自然数的话,那么上界p-1又会落在非自然数领域去了, 同样丑陋.
因此上界的表示,我们选择a)和d). 综上,我们选择a)表示法.

下一个问题是:对于一个N个元素的序列,给起始元素下标赋予哪个值?

由a)表示法得出, 如果从下标1开始, 下表范围是: 1 <= i < N+1,
然而下标从0开始的话, 将得到一个更nice的范围: 0 <= i < N,
让序数从0开始, 得出: 一个元素的序数 = 它之前的元素个数.

prof.dr. Edsger W. Dijkstra 的手迹: why numbering should start at zero

malloc和mmap

malloc(3)跟mmap(2)是有点关系的：
* mmap(2)可以替代malloc(3)的功能.
* malloc(3)的实现可能还用到了mmap(2).

mmap(2)是使一个磁盘文件与把存储空间的一个缓冲区相映射,那malloc(3)用mmap(2)实现时, 打开哪个文件?

好奇去下载了glibc src来看了下 [sudo apt-get source glibc-source]

下面的东西解决了我的疑问.

[malloc.c]

/*
   Nearly all versions of mmap support MAP_ANONYMOUS,
   so the following is unlikely to be needed, but is
   supplied just in case.
*/

#ifndef MAP_ANONYMOUS

static int dev_zero_fd = -1; /* Cached file descriptor for /dev/zero. */

#define MMAP(addr, size, prot, flags) ((dev_zero_fd < 0) ? \
 (dev_zero_fd = open("/dev/zero", O_RDWR), \
  mmap((addr), (size), (prot), (flags), dev_zero_fd, 0)) : \
   mmap((addr), (size), (prot), (flags), dev_zero_fd, 0))

#else

#define MMAP(addr, size, prot, flags) \
 (mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS, -1, 0))

#endif

/*
  The main properties of the algorithms are:
  * For large (>= 512 bytes) requests, it is a pure best-fit allocator,
    with ties normally decided via FIFO (i.e. least recently used).
  * For small (<= 64 bytes by default) requests, it is a caching
    allocator, that maintains pools of quickly recycled chunks.
  * In between, and for combinations of large and small requests,
    it does the best it can trying to meet both goals at once.
  * For very large requests (>= 128KB by default), it relies on system
    memory mapping facilities, if supported.

  For a longer but slightly out of date high-level description, see
     http://gee.cs.oswego.edu/dl/html/malloc.html
*/

[man mmap]

MAP_ANONYMOUS
The mapping is not backed by any file; its contents are initialized to zero. The fd and off-set arguments are ignored; however, some implementations require fd to be -1 if MAP_ANONYMOUS (or MAP_ANON) is specified, and portable applications should ensure this. The use of MAP_ANONYMOUS in conjunction with MAP_SHARED is only supported on Linux since kernel 2.4.

参考
http://en.wikipedia.org/wiki/Malloc

Funny C declarations

register voters;
short circuit;
short pants;
unsigned long letter;
union organizer;
void check;
unsigned check;
long long ago; /* in a galaxy far far away */

women() {
    goto bathroom;
bathroom:
    while (1) ;
}

快速排序快的原因

快速排序非常快，原因是：
一旦知道了某个元素比基准值小，它就不必再与那些大的元素进行比较了。

同样，大的元素也不必再与小的做比较。
这个性质使快速排序远比简单排序算法(如插入排序和起泡排序)快得多。
因为在简单排序算法中，每个元素都需要与所有其他元素进行比较。

From The Practice of Programming