開始用Word 2007發(fā)布日志
發(fā)現(xiàn)書上很多加了星號(hào)的題目我都得看Instructor's Manual才會(huì)做? =_=
Problem: Show how to solve the fractional knapsack problem in O(n) time. Assume that you have a solution to Problem 9-2.
Problem 9-2就是在最差情況下也能在O(n)時(shí)間內(nèi)求出第k大元素的算法。
解答：
使用線性算法找出Vi / Wi的中位數(shù)
將物體分成三個(gè)集合，G = { i : Vi / Wi > m }??? E = { i : Vi / Wi = m}?? L : { i : Vi / Wi < m}，同樣能在線性時(shí)間內(nèi)完成
計(jì)算WG = Sigma(Wi), i ∈ G; WE = Sigma(Wi), i ∈ E
-
如果WG > W，則不在G中取出任何物體，而是繼續(xù)遞歸分解G
-
如果WG <= W，取出G中所有物體，并盡可能多得取出E中物體
-
如果WG + WE >= W，也就是說步驟2以后背包已經(jīng)放滿，則問題解決
-
否則如果尚未放滿，則繼續(xù)在L上遞歸調(diào)用查找W – WG - WE的方案
以上所有調(diào)用都在線性時(shí)間內(nèi)完成，每次遞歸調(diào)用都能減少一半的數(shù)據(jù)規(guī)模
因此運(yùn)行時(shí)間的遞歸式為
T(n) <= T(n/2) + Omega(n)
有Master Theorem可得
T(n) = O(n)
問題：
已知一些活動(dòng)的起止時(shí)間{Si}, {Fi}，把它們安排在若干個(gè)大廳中進(jìn)行，要求任一大廳任意時(shí)間段內(nèi)不能有兩項(xiàng)活動(dòng)同時(shí)進(jìn)行，求出所需的最少的大廳數(shù)。
分析：(from CLRS Instructor's Manual)
這是一個(gè)區(qū)間圖的著色問題(Interval-graph Coloring Problem)，用點(diǎn)表示活動(dòng)，把時(shí)間沖突的活動(dòng)連起來，然后進(jìn)行點(diǎn)的著色，要求同一線段的兩端不能有相同顏色的點(diǎn)。
首先最容易想到的就是用書上的Greedy-Activity-Selector找出可安排在大廳1的最長(zhǎng)序列，然后刪去這些活動(dòng)，再次調(diào)用該方法，找出安排在大廳2的活動(dòng)，以此類推。
復(fù)雜度O(n*n)
還有一個(gè)O(n*logn)的算法，甚至在起止時(shí)間都是比較小的數(shù)字時(shí)復(fù)雜度只有O(n)。
主要思想是依次遍歷每個(gè)活動(dòng)，把它們安排到不同的大廳中。
維護(hù)兩張表，一張記錄當(dāng)前時(shí)間t已經(jīng)安排了活動(dòng)的大廳，另一張記錄當(dāng)前時(shí)間空閑的大廳
然后從頭掃描排序后的時(shí)間點(diǎn)序列（如果事件a的結(jié)束時(shí)間等于時(shí)間b的開始時(shí)間，那么前者應(yīng)該排在后者后面）
碰到開始時(shí)間t，把該活動(dòng)放到空閑列表的第一個(gè)大廳中（如果空閑列表為空則新加一個(gè)大廳），然后把該大廳放入已安排的大廳列表中；
碰到結(jié)束時(shí)間t，從已安排的大廳列表中移出相應(yīng)大廳到空閑列表。
復(fù)雜度分析：
排序：O(n logn)，如果時(shí)間范圍有限制還可以做到O(n)
處理：O(n)
發(fā)信人: CJC (藍(lán)色雪狐), 信區(qū): 05SS
標(biāo) 題: OS_Lab3 指南 List
發(fā)信站: 復(fù)旦燕曦BBS (2007年10月11日03:55:12 星期四), 轉(zhuǎn)信
先寫點(diǎn)List的東西吧，這個(gè)其實(shí)在以前并不作為重點(diǎn)講，不過好像大家對(duì)它還是有些偏
見，所以這次稍微講下吧。作用是為到時(shí)候建立進(jìn)程關(guān)系列表做準(zhǔn)備。
講的內(nèi)容都在/usr/src/linux.../include/linux/list.h中，大家只要把一些不必要的
ifdef和一些prefetch的東西刪掉就好了。
首先講講歷史。在沒有范型的Java里面我們用的鏈表往往會(huì)這樣（如果轉(zhuǎn)成C的話）：
typedef struct list_head {
struct list_node *prev;
void *data;
struct list_node *next;
} list_t;
通過這個(gè)結(jié)構(gòu)，我們就能完成鏈表的功能了。但是我覺得這個(gè)數(shù)據(jù)結(jié)構(gòu)不好，原因有二
：
第一：這個(gè)結(jié)構(gòu)比較容易引起內(nèi)存碎片。
┌──┬─┬──┐
│prev│ │next│<----多余內(nèi)存消耗
└──┴┼┴──┘
│ ┌───┐
└─>│ data │
└───┘
這種設(shè)計(jì)每一個(gè)節(jié)點(diǎn)都會(huì)引起一塊多余的內(nèi)存消耗。
第二：類型不明確，因?yàn)楝F(xiàn)在沒辦法用范型。如果寫明了類型，那么還要為每種類型的
list自己再做一整套函數(shù)，得不償失。
當(dāng)然，還會(huì)考慮類似于我們希望用別人寫得比較好的代碼之類的原因。
那讓我們來看看我們版本里的list_t是怎么定義的
typedef struct list_head {
struct list_head *next, *prev;
} list_t;
乍一看，這個(gè)list_head里面什么都沒包含，只有一對(duì)前后指針，沒有指向數(shù)據(jù)的指針
。那怎么用呢？這里的做法我叫做：反包含。我們來看一個(gè)具體的使用例子：
typedef struct test_struct {
int val1;
int val2;
char vals[4];
list_t all_tests; //千萬(wàn)注意，這里是list_t，不是list_t *
} test_t;
那么我們聲明了這個(gè)數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中是什么樣的呢？
(test_list) ┌─────┐┬ <--my_test_struct_p(test_t *)
┌──┬──┐ │ val1 ││
│prev│next├┐ ├─────┤│
└──┴──┘│ │ val2 ││h
│ ├─────┤│
│ │ vals ││
表示指向首地址└──>├──┬──┤┴ <--my_list_p(list_t *)
│prev│next│ //這里如果是list_t *就不是這樣畫了！
└──┴──┘
上圖就是一個(gè)test_t的結(jié)構(gòu)圖。小地址在上，大地址在下，val1上面的那條分界線作為
val1的起始地址（請(qǐng)注意我my_test_struct_p及其它指針的畫法，是指向上面那根線，表示
為那個(gè)東西的起始地址，為清楚起見推薦大家以后這樣畫）
然后為了把所有的test_t數(shù)據(jù)結(jié)構(gòu)串起來，我們需要一個(gè)全局變量：test_list，類行
為list_t（如果這里聲明list_t *的話一定要為它分配空間！如果是死的全局變量、全局?jǐn)?shù)
組和一些臨時(shí)數(shù)組，推薦直接聲明成類型而不是指針，因?yàn)榫幾g器會(huì)放在dat/bss和stack段
里。但是如果這個(gè)數(shù)據(jù)結(jié)構(gòu)是返回類型的分配空間，一定要malloc!否則回去就會(huì)錯(cuò)。這里
也提醒一下）
我們可以看到test_list.next是指向my_test_struct_p->all_tests，而不是my_test_s
truct。但是對(duì)我有用的應(yīng)該是my_test_struct。所以一般處理方法有二，
第一種比較死板，就是在數(shù)據(jù)結(jié)構(gòu)的一開始就放一個(gè)list_t（命名為list），那么&lis
t=&stru，可以直接(xxx *)list_p。但是問題是如果一個(gè)數(shù)據(jù)結(jié)構(gòu)可以同屬兩個(gè)鏈表，如pc
b，又要是run_list的成員，又要是all_tasks的成員，還要是父進(jìn)程children的成員……這
種方法顯然是不夠的。
第二種方法就相對(duì)好些。大家可以看，
((unsigned int)my_list_p)-h=(unsigned int)my_test_struct_p
而怎么得到h呢？是不是需要每個(gè)數(shù)據(jù)結(jié)構(gòu)都定義一個(gè)h呢？不需要，可以這樣看
h=(unsigned int)(&(((test_t *)0)->all_tests))
就是把0地址當(dāng)作是test_t數(shù)據(jù)結(jié)構(gòu)的開始地址，那么這個(gè)數(shù)據(jù)結(jié)構(gòu)的all_tests所在的
地址就是h了。
通過把這兩個(gè)算式結(jié)合，我們可以得到一個(gè)宏：
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
在這里的用法就是：
my_test_struct_p = list_entry(test_list.next, test_t, all_tests);
（如果使用類似于Simics的編輯器的話，all_tests的顯示會(huì)是類似于沒有定義變量，
不用管它，的確是這樣的。最后編譯成功就對(duì)了）。
看過了最精妙的list_entry之后我們就可以來看一些簡(jiǎn)單的操作了
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
為什么要加while(0)可以參見lab2指南里面的一些define幫助。其大致概念如下：
┌─────────┐
│ │
└->┌──┬──┐ │
┌─┤prev│next├─┘ //這里為了畫清邏輯，不把指針放在首地址
│ └──┴──┘<-┐
│ │
└─────────┘
這是一個(gè)環(huán)狀鏈表。一般這個(gè)作為頭指針，鏈表為空的判斷依據(jù)就是：
static inline int list_empty(struct list_head *head)
{
return head->next == head;
}
然后是添加，先有一個(gè)輔助函數(shù)：
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
這個(gè)是添加在第一個(gè)：
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
┌───────────────────┐
│ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├-─┘ //這里的數(shù)據(jù)結(jié)構(gòu)就省略畫了
│ └──┴──┘<─┘├──┴──┤ <-┐
│ └─────┘ │
└───────────────────┘
ori_first
┌────────────────────────────┐
│ ┌─────┐ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├┘ ┌┤prev│next├─┘
│ └──┴──┘<─┘├──┴──┤<─┘├──┴──┤<-┐
│ └─────┘ └─────┘ │
└────────────────────────────┘
new ori_first
這個(gè)是添加在head->prev，由于是環(huán)狀的，那么就是添在了最后一個(gè)
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
┌────────────────────────────┐
│ ┌─────┐ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├┘ ┌┤prev│next├─┘
│ └──┴──┘<─┘├──┴──┤<─┘├──┴──┤<-┐
│ └─────┘ └─────┘ │
└────────────────────────────┘
ori_first new
接下來是刪除：
這是輔助方法
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
next->prev = prev;
prev->next = next;
}
這個(gè)是用了輔助方法__list_del并且把entry的前后都設(shè)為NULL，是為了安全起見
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = (void *) 0;
entry->prev = (void *) 0;
}
個(gè)人覺得list_del_init, list_move, list_move_tail, list_splice沒啥太大作用…
…不過后面兩個(gè)非常重要：
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
pos = pos->prev, prefetch(pos->prev))
使用方法：
list_t *pos;
list_for_each(pos, &test_list) {
test_t *tmp = list_entry(pos, test_t, all_tests);
//do something on tmp
}
=======================================================================
list_t *pos, *n;
list_for_each_safe(pos, n, &test_list) {
test_t *tmp = list_entry(pos, test_t, all_tests);
//do something on tmp
}
======================================================================
那么這兩個(gè)有什么差別呢？我們可以來看這個(gè)例子：
list_for_each(pos, &test_list) {
list_del(pos);
}
首先，我們得到pos=test_list.next，然后刪除，此時(shí)pos->next=0，如果按照l(shuí)ist_fo
r_each的話下一個(gè)循環(huán)的pos就是NULL，再訪問下去就出錯(cuò)了！同樣的，修改位置也是。所
以在需要修改隊(duì)列結(jié)構(gòu)的時(shí)候，一定要使用list_for_each_safe。如果只修改對(duì)應(yīng)的數(shù)據(jù)結(jié)
構(gòu)其他字段，可以用list_for_each，因?yàn)檫@個(gè)效率比較高。
有了這些方法基本上就可以使用了。我們可以來看一個(gè)物理內(nèi)存管理的例子：
#define USER_MEM_SIZE (256*1024*1024)
#define USER_MEM_START (16*1024*1024)
#define PAGE_SHIFT 12
#define PAGE_SIZE (1<<(PAGE_SHIFT))
#define PAGE_COUNT (((USER_MEM_SIZE)-(USER_MEM_START))>>(PAGE_SHIFT))
#define PAGE_START(ptr) (((ptr)-(all_pages))<<(PAGE_SHIFT)+(USER_MEM_START))
//獲取這個(gè)page數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)的起始地址
#define PAGE_STRU(addr) (&all_pages[((addr)-(USER_MEM_START))<<(PAGE_SHIFT)])
typedef struct page_struct {
unsigned long use_count;
list_t mem_list;
} page_t;
list_t free_list, lru_list; //lru是用作換出的，最近使用在隊(duì)首，換出隊(duì)尾頁(yè)
//如果編譯器不肯讓我們這樣定義的話用lmm_alloc或者out_alloc也可以。
page_t all_pages[PAGE_COUNT];
void init()
{
int i;
INIT_LIST_HEAD(&free_list);
INIT_LIST_HEAD(&lru_list); //初始化兩個(gè)鏈表
for (i = 0; i < PAGE_COUNT; i++) {
all_pages[i] = 0;
list_add_tail(&all_pages[i].mem_list, &free_list); //加入free_list
}
}
//此處返回值作為錯(cuò)誤信息，addr作為所需返回的物理內(nèi)存起始地址
int get_page(unsigned int *addr)
{
if (list_empty(&free_list)) //沒有空頁(yè)
return -1;
list_t *lst = free_list.next;
list_del(lst);
list_add(lst, &lru_list); //最近使用，放到隊(duì)首
*addr = PAGE_START(list_entry(lst, page_t, mem_list);
return 0;
}
void use_page(unsigned int addr)
{
page_t *pg = PAGE_STRU(addr);
list_del(&pg->mem_list);
list_add(&pg->mem_list, &lru_list); //將頁(yè)面放到lru隊(duì)列首
}
void return_page(unsigned int addr)
{
page_t *pg = PAGE_STRU(addr);
list_del(&pg->mem_list);
list_add(&pg->mem_list, &free_list); //將頁(yè)面放到free隊(duì)列首，下次取時(shí)用
}
物理頁(yè)面管理基本上就類似于此。我們接下來來看一個(gè)稍微復(fù)雜些的例子，就是進(jìn)程父
子關(guān)系的例子，去年又同學(xué)跟我反映這是一個(gè)交錯(cuò)鏈接或者說是嵌套鏈接，其實(shí)不然。我們
拆分開來看：
┌─────────-┐
│┌-────────┼───┐
│ ↘ A->children │ │
┌───-┼─>┌──┬──┐ │ │
│ └-─┤prev│next├┐│ │
│ └──┴──┘││ │
│┌────────────┘│ │
││ ┌-───┘ │
││ ┌─────┐ ↘┌─────┐│
│└>├──┬──┤┌─>├──┬──┤│
└-─┤prev│next├┘ ┌┤prev│next├┘
├──┴──┤<─┘├──┴──┤
└─────┘ └─────┘
B C
由圖可知，A有BC兩個(gè)子進(jìn)程，分別連接到A進(jìn)程的children上。此時(shí)，處理A的childre
n又有兩種方法，第一種是增加指針，第二種是作為A進(jìn)程的一部分。利用上面的思考方法，
我們可以知道，如果按照第一種做法，那么勢(shì)必會(huì)引起更多的內(nèi)存碎片，不方便。于是我們
把children作為pcb的一個(gè)field。那么B和C里面的prev/next該叫什么呢？因?yàn)锽和C也是pc
b的數(shù)據(jù)結(jié)構(gòu)，已經(jīng)不可能再叫children了（而且他們也應(yīng)該有children節(jié)點(diǎn)，因?yàn)樗麄円?br />
可能有子進(jìn)程）。那么我們就叫它為sibling吧。因?yàn)樵谶@個(gè)鏈表里，除了A是父進(jìn)程，其余
的都是兄弟進(jìn)程。
所以pcb的父子關(guān)系可以這樣寫：
#define TASK_STATE_RUNNING 0
#define TASK_STATE_ZOMBIE 1
//調(diào)用了wait指令，等待子進(jìn)程結(jié)束
#define TASK_STATE_WAIT_CHILD 2
typedef struct pcb_struct{
struct pcb_struct *parent; 父進(jìn)程
unsigned long state;
list_t children;
list_t sibling;
list_t all_tasks;
} pcb_t;
//init是一個(gè)非常特殊的進(jìn)程，一般我們的kernel一起來，就只負(fù)責(zé)兩個(gè)進(jìn)程：init和idle
//init的作用是先f(wàn)ork，子進(jìn)程運(yùn)行shell，它自身while(1) {wait(...);}就是負(fù)責(zé)回收
//孤兒進(jìn)程。
//并且在此，我們可以把所有的進(jìn)程都連接在init的all_tasks上面，這樣又可以節(jié)省一個(gè)
//相當(dāng)于前例test_list的全局變量。找所有進(jìn)程只須遍歷init->all_tasks即可。
//所以在生成init的時(shí)候應(yīng)該是INIT_LIST_HEAD(&task->all_tasks)
void init_pcb(pcb_t *task, pcb_t *init)
{
INIT_LIST_HEAD(&task->children);
INIT_LIST_HEAD(&task->sibling);
task->parent = NULL;
task->state = TASK_STATE_RUNNING;
list_add_tail(&task->all_tasks, &init->all_tasks);
}
void add_child(pcb_t *parent, pcb_t *child)
{
child->parent = parent;
list_add_tail(&child->sibling, &parent->children); //想想為什么
}
void do_exit(pcb_t *task, pcb_t *init)
{
//exit_mem_first_part
list_t *pos, *n;
list_for_each_safe(pos, n, &task->children) //將所有子進(jìn)程交給init
{ //~~~~
task_t *child = list_entry(pos, task_t, sibling); //這里是sibling
child->parent = init;
list_del(&child->sibling);
list_add_tail(&child->sibling, &init_children);
if (child->state == TASK_STATE_ZOMBIE && init->state != TASK_STATE_WAIT_
CHILD)
{
//這里激活init，并把init放到進(jìn)程列表的尾端
}
}
//然后切換到父進(jìn)程運(yùn)行
}
如果看懂了以上的所有例子，那么鏈表結(jié)構(gòu)應(yīng)該就差不多了。由于篇幅關(guān)系，PCB的構(gòu)
建就單列開來吧。這里專門講LIST好了。:)
如果有代碼覺得看的郁悶的，拿張紙畫畫對(duì)應(yīng)的內(nèi)存結(jié)構(gòu)應(yīng)該就會(huì)好些了
--
※ 修改:·CJC 于 Oct 11 03:57:46 修改本文·[FROM: 穿梭而來]
※ 來源:·復(fù)旦燕曦BBS yanxibbs.cn·[FROM: 穿梭而來]
http://10.132.140.73/lxr/http/blurb.html
在機(jī)房搭了一個(gè)，原本以為有筆記的功能，裝好以后才發(fā)現(xiàn)只能閱讀用，不過搜索功能還是很強(qiáng)大的。
轉(zhuǎn)載，部分修改（標(biāo)為紅色）
我們?cè)陂喿xlinux源代碼時(shí)都有這樣的體會(huì):核心的組織相對(duì)松散，在看一個(gè)文件時(shí)往往要牽涉到其他的頭文件、源代碼文件。如此來回跳轉(zhuǎn)尋找變量、常量、函數(shù)的定義十分不方便，這樣折騰幾次，便使讀代碼的心情降到了低點(diǎn)。
lxr(linux cross reference)就是一個(gè)解決這個(gè)問題的工具：他對(duì)你指定的源代碼文件建立索引數(shù)據(jù)庫(kù)，利用perl腳本CGI動(dòng)態(tài)生成包含源碼的web頁(yè)面，你可以用任何一種瀏覽器查閱。在此web頁(yè)中，所有的變量、常量、函數(shù)都以超連接的形式給出，十分方便查閱。比如你在閱讀/usr/src/linux/net/socket.c的源代碼，發(fā)現(xiàn)函數(shù) get_empty_inode不知道是如何以及在哪里定義的，這時(shí)候你只要點(diǎn)擊get_empty_inode,lxr將返回此函數(shù)的定義、實(shí)現(xiàn)以及各次引用是在什么文件的哪一行，注意，這些信息也是超連接，點(diǎn)擊將直接跳轉(zhuǎn)到相應(yīng)的文件相應(yīng)的行。另外lxr還提供標(biāo)識(shí)符搜索、文件搜索，結(jié)合程序 glimpse還可以提供對(duì)所有的源碼文件進(jìn)行全文檢索，甚至包括注釋！
下面將結(jié)合實(shí)例介紹一下lxr和glimpse的基本安裝和使用，由于glimpse比較簡(jiǎn)單，就從它開始：
首先訪問站點(diǎn)： http://glimpse.cs.arizona.edu/ 得到glimpse的源碼
,比如我得到的是glimpse-4.12.5.tar.gz . 用root登錄，在任一目錄下用tar zxvf glimpse-4.12.5.tar.gz解開壓縮包，在當(dāng)前目錄下出現(xiàn)新目錄glimpse-4.12.5 .
進(jìn)入該目錄，執(zhí)行
./configure
make
make install
如果單獨(dú)使用glimpse，那么只要簡(jiǎn)單的執(zhí)行g(shù)limpseindex foo即可，其中foo是你想要索引的目錄，比如說是/usr/src/linux .glimpseindex的執(zhí)行結(jié)果是在你的起始目錄下產(chǎn)生若干.glimpse*的索引文件。
然后你只要執(zhí)行g(shù)limpse yourstring即可查找/usr/src/linux下所有包含字符串yourstring的文件。
對(duì)于lxr，你可以訪問lxr.linux.no得到它的源代碼解包后，遵循如下步驟：
/*下面的文字來源于lxr的幫助文檔以及本人的安裝體會(huì)*/
1)修改Makefile中的變量PERLBIN和INSTALLPREFIX,使它們分別為 perl程序的位置和你想lxr安裝的位置.在我的機(jī)器上，PERLBIN的值為/usr/bin/perl .至于INSTALLPREFIX，有如下原則，lxr的安裝路徑必須是web服務(wù)器能有權(quán)限訪問。因此它的值簡(jiǎn)單一點(diǎn)可取 /home/httpd/html/lxr (對(duì)于Apache web server)。
2)執(zhí)行 make install
3)修改$INSTALLPREFIX/http/lxr.conf :
baseurl : http://yourIP/lxr/http/
htmlhead: /home/httpd/html/lxr/http/template-head
htmltail: /home/httpd/html/lxr/http/template-tail
htmldir: /home/httpd/html/lxr/http/template-dir
sourceroot : /usr/src/linux # 假如對(duì)linux核心代碼索引
dbdir : /home/httpd/html/lxr/dbdir/ #dbdirk可任意起名，且位置任意 glimpsebin: /usr/bin/glimpse #可執(zhí)行程序glimpse的位置
4)在$INSTALLPREFIX/http/下增加一個(gè)文件.htaccess內(nèi)容：
<Files ~ (source|search|ident|diff|find)$> ***
SetHandler cgi-script
</Files>
上面這個(gè)文件保證Apache server將幾個(gè)perl文件作為cgi-script.
5)按照l(shuí)xr.conf中的設(shè)置建立dbdir ,按照上例,建立目錄
/home/httpd/html/lxr/dbdir
進(jìn)入這個(gè)目錄執(zhí)行$INSTALLPREFIX/bin/genxref yourdir
其中yourdir是源碼目錄，比如/usr/src/linux
如果要結(jié)合glimpse，則執(zhí)行g(shù)limpseindex -H . yourdir
6)修改 /etc/httpd/conf/
httpd.conf ,加入
<Directory /home/httpd/html/lxr/http>
Options All
AllowOverride All
order allow,deny
allow from all
</Directory>
7)進(jìn)入/etc/rc.d/init.d/ 執(zhí)行
killall httpd
./httpd start
進(jìn)入X ，用瀏覽器
http://yourIP/lxr/http/blurb.html
大功告成 ，這下你可以舒心的讀源碼了。
Problem: You are given n real numbers - they are NOT sorted. Develop a linear time（O(n)）algorithm to find the largest gap between consecutive numbers when the n numbers are sorted. For example, given:
10 23 7 1 35 27 50 41
the algorithm should produce 13 as its result, since the sorted list is:
1 7 10 23 27 35 41 50
and the largest gap is 13 (between 10 and 23).
Please note that your algorithm cannot actually sort the n numbers.
Macsy (真心) 于 (Fri Oct 5 11:59:16 2007) 提到:
有一個(gè)方法需要額外的O(n)的空間。
首先找到最大最小數(shù)max,min
max gap 肯定不小于 (max-min)/n 。
然后以(max-min)/n為步長(zhǎng)，建立n個(gè)桶
每個(gè)桶里面記錄落在這個(gè)桶中的最大最小值。
最后順序掃描這n個(gè)桶中的值就可以了。
大概代碼是
input: a[n];
min=min_of(a[1..n]);
max=max_of(a[1..n]);
step=(max-min)/n;
b[0..n].min=maxfloat; b[0..n].max=-maxfloat;
for i=1 to n
ind = (a[i]-min)/step;
b[ind].min=min(b[ind].min, a[i]);
b[ind].max=max(b[ind].max, a[i]);
maxgap=step;
last=b[0].max;
for i=1 to n
if (b[i].min != maxfloat)
maxgap=max(maxgap, b[i].min-last);
last=b[i].max;
output maxgap
proftpd.conf中增加兩行設(shè)置：
UseReverseDNS off
IdentLookups off
Come From Alacner Blog：http://blog.alacner.com/post/168.htm
同目錄下包含這三個(gè)文件即可
mingwm10.dll
QtCore4.dll
QtGui4.dll
以下轉(zhuǎn)載自《Linux kernel》
核心源碼的頂層是/usr/src/linux目錄，在此目錄下你可以看到大量子目錄：
arch
這個(gè)子目錄包含了所有體系結(jié)構(gòu)相關(guān)的核心代碼。它還包含每種支持的體系結(jié)構(gòu)的子目錄，如i386。
include
這個(gè)目錄包括了用來重構(gòu)核心的大多數(shù)include文件。對(duì)于每種支持的體系結(jié)構(gòu)分別有一個(gè)子目錄。 此目錄中的asm子目錄中是對(duì)應(yīng)某種處理器的符號(hào)連接，如include/asm-i386。要修改處理器結(jié)構(gòu) 則只需編輯核心的makefile并重新運(yùn)行Linux核心配置程序。
init
此目錄包含核心啟動(dòng)代碼。
mm
此目錄包含了所有的內(nèi)存管理代碼。與具體體系結(jié)構(gòu)相關(guān)的內(nèi)存管理代碼位于arch/*/mm目錄下， 如arch/i386/mm/fault.c 。
drivers
系統(tǒng)中所有的設(shè)備驅(qū)動(dòng)都位于此目錄中。它又進(jìn)一步劃分成幾類設(shè)備驅(qū)動(dòng)，如block。
ipc
此目錄包含了核心的進(jìn)程間通訊代碼。
modules
此目錄僅僅包含已建好的模塊。
fs
所有的文件系統(tǒng)代碼。它也被劃分成對(duì)應(yīng)不同文件系統(tǒng)的子目錄，如vfat和ext2。
kernel
主要核心代碼。同時(shí)與處理器結(jié)構(gòu)相關(guān)代碼都放在arch/*/kernel目錄下。
net
核心的網(wǎng)絡(luò)部分代碼。
lib
此目錄包含了核心的庫(kù)代碼。與處理器結(jié)構(gòu)相關(guān)庫(kù)代碼被放在arch/*/lib/目錄下。
scripts
此目錄包含用于配置核心的腳本文件（如awk和tk腳本）。
主要是做DS Project 1時(shí)碰到的問題
1. 泛型方法push(elemType &x)無法接受常數(shù)等const類型，必須將形參聲明為const elemType &x
2. 在給泛型類SimpleList增加operator<<方法時(shí)，把實(shí)現(xiàn)代碼放在類的聲明外部會(huì)報(bào)錯(cuò)，直接放在里面就可以，不知道是不是必須是內(nèi)聯(lián)inline的才可以。
水木問了下，答案是
除非在友元聲明中顯式指定了模板參數(shù)，否則與函數(shù)模板同名的友元函數(shù)的聲明不會(huì)引用該函數(shù)模板.如果未指定模板參數(shù)，則友元聲明將聲明一個(gè)非模板函數(shù)。
3. C++中可以throw很多東西，比如String, int等。catch (...)表示把所有的異常都捕捉到。
from 水木
1. 兩兩比較，找出最大的，n-1次
2. 從找最大的這條路線回溯，次大的必然在這條路線上，找到它需要logn - 1次（敗者樹的最大高度為logn）
其實(shí)就是一個(gè)錦標(biāo)賽排序