|
|
10.31: CLRS 22.1-22.3 Elementary Graph Algorithms
10.25: CLRS 18.2 Operations on B-trees
10.22: CLRS 18.1 Definition of B-trees
10.15: CLRS 16.3 Huffman codes
10.14: CLRS 16.2 Elements of the greedy strategy
10.13: CLRS 16.1 An activity-selection problem
10.11-12: LKD 調度 O(1)調度算法
10.10: 虎書 看完Abstract Syntax
10.7~9: LKD 第二章進程管理看完，不過還是沒什么感覺，看來代碼讀的不夠多
10.3: 虎書 LR Parsing 看到Error Recovery之前
9.24-25: CLRS 15 Dynamic Programming 看完，習題未做
9.22: CSAPP Chapter1 除浮點部分回顧了一遍
9.19: CSAPP 6.3 The Memory Hierarchy
9.18: CSAPP 6.2 Locality
總進度：
CS: APP
Chapter1(Tour) 泛讀一遍
Chapter2(Representing and Manipulating) 除浮點部分已看完
Chapter3(Machine-Level Representation of Programs) 除*部分已看完
Chapter6(The Memory Hierarchy) 正在看，跳過第一節Storage Technologies
Chapter7(Linking) 看過一遍，Symbols and Symbol Tables, Relocation部分還不怎么清楚
Chapter8(Exceptional Control Flow) 看完
Chapter10(Virtual Memory) 看過一點，發現不知道Locality后跳到第6章
CLRS
Part I: Foundation 粗略的看了一遍，主要了解了下Big-Oh Big-Omega Big-Theta的概念，Master Method的應用和簡單的Generation Function
Part II: Sorting and Order Statistics 除復雜度證明部分外看了一遍，大多數習題都看過
Part III: Data Structures 翻過一遍，*部分都沒看，習題看的不多，紅黑書相關的操作還不怎么熟練，后面兩章還要再看一下
Part IV: Advanced Design and Analysis Techniques 跳過Amortized Analysis，做了部分習題
Part V: Advanced Data Structures 看了一點B-Tree，二分堆、Fibonacci堆和并查集先跳過了
PartVI: Graph Algorithms 正在看
Modern Compilers Implementation in C
從頭看到第四章 Abstract Syntax，略過Burke-Fisher錯誤恢復
Linux Kernel Development 中文版
剛開始看
1. 安裝后reboot，選擇Arch Linux Fallback，出現登錄提示后鍵盤無響應，按Num Lock鍵指示燈也沒有變化，此時拔掉鍵盤再插上即可。
2. Network IP, Gateway, Mask設置都正常，但無法ping到網關，翻了wiki后終于發現是Windows在搗鬼
Windows中關機后會自動將Realtek 8168 8169 8101 8111網卡禁用，直到再次進入Windows后才會恢復
解決方法是在設備管理器->網絡適配器->Realtek xxx->高級中把"Wake-On-Lan After Shutdown"設為Enable
3. 幾個pacman常用的參數
pacman -Sy 更新本地包的數據庫
pacman -S package_name1 package_name2 ... 安裝包
pacman -S extra/package_name 指定安裝某個版本的包
pacman -Su 更新所有安裝的包，通常和Sy參數合并為-Syu
pacman -Ss 搜索
pacman -U *.pkg.tar.gz 安裝本地包
4. 好不容易+莫名奇妙地配好了顯卡，startx可以跑起來了
然后運行gnome-session，提示Gtk WARNING **: Cannot open display:
找了一堆解決方法，總算有一個可行的：
在~/.xinitrc中增加gnome-session，然后啟動startx
http://jefke.free.fr/soft/texttable/
dl: http://jefke.free.fr/soft/texttable/texttable.py
NAME
texttable - module for creating simple ASCII tables
FILE
/usr/lib/python2.3/site-packages/texttable.py
DESCRIPTION
Example:
table = Texttable()
table.header(["Name", "Age"])
table.set_cols_align(["l", "r"])
table.add_row(["Xavier\nHuon", 32])
table.add_row(["Baptiste\nClement", 1])
table.draw()
Result:
+----------+-----+
| Name | Age |
+==========+=====+
| Xavier | 32 |
| Huon | |
+----------+-----+
| Baptiste | 1 |
| Clement | |
+----------+-----+
CLASSES
exceptions.Exception
ArraySizeError
Texttable
class ArraySizeError(exceptions.Exception)
| Exception raised when specified rows don't fit the required size
|
| Methods defined here:
|
| __init__(self, msg)
|
| __str__(self)
|
| ----------------------------------------------------------------------
| Methods inherited from exceptions.Exception:
|
| __getitem__(...)
class Texttable
| Methods defined here:
|
| __init__(self, max_width=80)
| Constructor
| - max_width is an integer, specifying the maximum width of the t
able
| - if set to 0, size is unlimited, therefore cells won't be wrapp
ed
|
| add_row(self, array)
| Add a row in the rows stack
|
| Cells can contain newlines.
|
| draw(self)
| Draw the table
|
| header(self, array)
| Specify the header of the table
|
| reset(self)
| Reset the instance:
| - reset rows and header
|
| set_chars(self, array)
| Set the characters used to draw lines between rows and
| columns.
|
| The array should contain 4 fields:
|
| [horizontal, vertical, corner, header]
|
| Default is set to:
|
| ['-', '|', '+', '=']
|
| set_cols_align(self, array)
| Set the desired columns alignment
|
| The elements of the array should be either "l", "c" or "r"
| - "l": column flushed left
| - "c": column centered
| - "r": column flushed right
|
| set_cols_width(self, array)
| Set the desired columns width
|
| The elements of the array should be integers, specifying the
| width of each column. For example:
|
| [10, 20, 5]
|
| set_deco(self, deco)
| Set the table decoration. 'deco' can be a combinaison of:
|
| Texttable.BORDER: Border around the table
| Texttable.HEADER: Horizontal line below the header
| Texttable.HLINES: Horizontal lines between rows
| Texttable.VLINES: Vertical lines between columns
|
| Example:
|
| Texttable.BORDER | Texttable.HEADER
|
| All of them are enabled by default.
|
| --------------------------------------------------------------------
--
| Data and other attributes defined here:
|
| BORDER = 1
|
| HEADER = 4
|
| HLINES = 8
|
| VLINES = 16
DATA
__all__ = ['Texttable', 'ArraySizeError']
__author__ = 'Gerome Fournier <jefke(at)free.fr>'
__credits__ = 'Jeff Kowalczyk:\n - textwrap improved import\n - ..
.
__license__ = 'GPL'
__revision__ = '$Id: texttable.py,v 1.3 2003/10/05 13:53:39 jef Exp je..
.
__version__ = '0.3'
VERSION
0.3
AUTHOR
Gerome Fournier <jefke(at)free.fr>
CREDITS
Jeff Kowalczyk:
- textwrap improved import
- comment concerning header output
connector.py
 import urllib, urllib2, cookielib
class MyConnector:
def __init__(self):
pass
def login(self, url):
cookie = cookielib.CookieJar()
opener = urllib2.build_opener(urllib2.HTTPCookieProcessor(cookie))
urllib2.install_opener(opener)
str = urllib.urlencode({'id': 'guest', 'passwd': ''})
self.sock = urllib2.urlopen(url, str)
def getHTML(self, url):
self.sock = urllib2.urlopen(url)
return self.sock.read()
yanxiparser.py
from sgmllib import SGMLParser
import re
class YanxiURLParser(SGMLParser):
def reset(self):
self.result = []
SGMLParser.reset(self)
def start_a(self, attrs):
for (k, v) in attrs:
if (k == 'href' and (v.find('bbsanc') >= 0)):
self.result.append(v)
class YanxiHTMLParser:
def parse(self, html):
uid = ufrom = ubirth = ufav = ''
html = html.replace(r' ', ' ')
html = html.replace(r'<br />', '')
pattern = '\xbe\xcd\xca\xc7(.*)\xc0\xb2'
matchObject = re.search(pattern, html)
uid = matchObject.group(1)
uid = uid.strip()
pattern = '\xc0\xb4\xd7\xd4(.*)\xa3(\xac|xa1)'
matchObject = re.search(pattern, html)
ufrom = matchObject.group(1)
ufrom = ufrom.strip()
pattern = '\xcf\xb2\xbb\xb6(.*)\n'
matchObject = re.search(pattern, html)
ufav = matchObject.group(1)
ufav = ufav.strip()
pattern = '\n(.*)\xca\xc7\xce\xd2\xb5\xc4\xc9\xfa\xc8\xd5'
matchObject = re.search(pattern, html)
ubirth = matchObject.group(1)
ubirth = ubirth.strip()
return {"id" : uid, "from" : ufrom, "birth" : ubirth, "fav" : ufav}
runner.py
from connector import MyConnector
from yanxiparser import *
rootURL = 'http://yanxibbs.cn'
loginURL = 'http://yanxibbs.cn/bbslogin.php'
url1 = 'http://yanxibbs.cn/cgi-bin/bbs/bbs0an?path=%2Fgroups%2FGROUP%5F3%2F06SS%2Fbyxx%2Fbjcy'
url2 = 'http://yanxibbs.cn/cgi-bin/bbs/bbs0an?path=%2Fgroups%2FGROUP%5F3%2F06SS%2Fbyxx%2Fbjyr'
conn = MyConnector()
conn.login(loginURL)
def printInfo(url):
html = conn.getHTML(url)
urlParser = YanxiURLParser()
htmlParser = YanxiHTMLParser()
urlParser.feed(html)
for targetURL in urlParser.result:
html = conn.getHTML(rootURL + targetURL)
info = htmlParser.parse(html)
print "%(id)s\t%(from)s\t%(birth)s\t%(fav)s" % info
printInfo(url1)
printInfo(url2)
1. 寫了個測試腳本，逐個測試testcases目錄下的各個tiger程序，并統計出錯數
#!/usr/bin/python
from commands import *
countOk = countError = 0
for i in range(1,50):
result = getstatusoutput('./lextest ../testcases/test%s.tig' % i)
if (result[0] == 0):
print('Test case %s: OK' % i)
countOk += 1
else:
print('Error on test case %s with errorno %s' % (i, result[0]))
countError += 1
print("Total cases: %s" % (countOk + countError))
print("Passed cases: %s" % (countOk))
print("Failed cases: %s" % (countError))
2. 狀態：
定義的狀態名不能與已經定義的變量/宏名沖突。在處理字符串的時候定義了個<STRING>狀態，和tokens.h中的STRING沖突了，結果解析的時候被認成了BAD_TOKEN。
發信人: laye (Addict to Goth >_<), 信區: Unix
標 題: 我的 Ubuntu 7.04 Cookbook
發信站: 日月光華 (2007年09月09日09:19:35 星期天), 站內信件
最近裝了 Ubuntu 7.04，寫了一個簡單的 Cookbook，記錄了自己遇到的一些問題和解決
方法，希望對大家有幫助。
cook01 中文字體美化
(1) 得到 simsun.ttc tahoma.ttf tahomabd.ttf verdana.ttf verdanab.ttf
verdanai.ttf verdanaz.ttf 幾個個字體文件 （可以從 Windows 的 Fonts 文件夾中獲
取)
(2) 用 nautilus 打開系統的字體文件夾：nautilus fonts:///
(3) 將第 (1) 步中的幾個個字體復制進第 (2) 步打開的字體文件夾中
(4) 創建 /etc/fonts/local.conf 文件，內容如 [附錄1] (本文最底端)
(5) 重新啟動 X: Ctrl + Alt + Backspace
(6) 打開 gnome 字體設置：gnome-font-properties，設置前四個字體為 Tahoma
(7) 打開 firefox 字體設置：將 Serif 設置為 SimSun，Sans-serif 設置為 Tahoma，
Monospace 設置為 SimSun，并且允許網頁自由選擇字體
(8) 重新啟動 X, enjoy~
點評：該優化方案用 Windows 的 SimSun (襯線) 和 Tahoma (無襯線) 作為 UI 和
Web 中的主要字體使用。并且，解決了字體替換后的幾個問題：
(1) 針對中文選字混亂問題 (同一句話中的不同漢字可能用不同字體進行渲染)，我將所
有亞洲字符都強制使用 SimSun 顯示。
(2) 由于 SimSun 的小字體為點陣字體，所以關閉了 8-17px 字體的抗鋸齒以達到理想
的顯示效果。
(3) 設置了 SimSun 和 Tahoma 的最小字體尺寸以保證顯示效果
已知 Bug: SimSun 英文和數字粗體效果不佳，可以下載網友制作的 SimSunbd 拷貝入
字體目錄 （SimSunbd 的英文和數字用的好像是 Tahoma）
cook02 連接 windows 的遠程桌面
安裝 rdesktop:
sudo apt-get install rdesktop
使用：
rdesktop ip
rdesktop -f ip (全屏)
cook03 使 ntfs 分區可寫
安裝 ntfs-config:
sudo apt-get install ntfs-config
配置：
sudo ntfs-config
勾選兩個選項 (或根據需要勾選)
cook04 訪問 Windows 共享文件夾
執行：nautilus-connect-server
填寫你要訪問的 Windows 共享文件夾的相關信息，這個文件夾就會被 mount 到你的
Desktop 下。同樣的方法可以 mount FTP 文件夾等等。
cook05 使 Windows 能訪問 ubuntu 的文件 (samba)
執行：shares-admin
按需要設置
cook06 播放各種視頻
(1) 下載 mplayer 的 Codec Package：
http://www.mplayerhq.hu/design7/dload.html#binary_codecs
(2) 將下載的 Codec Package 解壓到 /usr/lib/win32
(3) 安裝 mplayer 或各種 mplayer 的前端程序，我用的是 mplayer 的一個前端：
smplayer
(4) 如果你的 mplayer 的播放畫面不正常，請檢查你的 Video Output Driver 是否為
x11
(5) 若要顯示中文字幕，需要在播放器內設置字幕用字體和字幕編碼
cook07 使用 fcitx 替換 scim
由于使用習慣和兼容性原因，許多人不得不使用 fcitx，安裝方法如下：
sudo apt-get install im-switch fcitx
im-switch -s fcitx -z default
如果你要在 en 的 locale 下使用 fcitx，請將 /etc/gtk-2.0/gtk.immodules 中的：
“xim” “X Input Method” “gtk20″ “/usr/share/locale” “ko:ja:th:zh”
替換為
“xim” “X Input Method” “gtk20″ “/usr/share/locale” “en:ko:ja:th:zh”
cook08 Panel 中的好東東
ubuntu 桌面上下各有一個 Panel。其實，我們可以自定義 Panel 上面的內容，比如說
：
天氣預報，本本的電量顯示、亮度調節，CPU 頻率監視，系統負載監視，還有一個強制
終止程序的按鈕 (Force Quit)等等。
你也可以把自己建立的 Laucher 拖動到 Panel 上，當然，你也可以在別的位置建立自
己的 Panel。
cook09 使用 HP 打印機
ubuntu 自帶了 HP 系列打印機的驅動 oo2zjs，但奇怪的是，這個驅動居然是不能用的
。
用戶需要卸載掉 ubuntu 自帶的 oo2zjs，安裝新的 oo2zjs。
具體過程如下：
確認編譯環境已安裝：
sudo apt-get install build-essential
下載 oo2zjs：
wget -O foo2zjs.tar.gz http://foo2zjs.rkkda.com/foo2zjs.tar.gz
解壓：
tar zxf foo2zjs.tar.gz
cd foo2zjs
卸載原有 foo2zjs：
make uninstall
編譯，安裝：
make
./getweb 1020 這里是你的打印機型號
sudo make install install-hotplug cups
在 ubuntu 的打印機管理中添加你的打印機 (不要選 suggest 的那個驅動):
sudo gnome-cups-manager
最后，重啟 cups:
sudo make cups
cook10 開啟 Vim 的“簡易模式”
ubuntu 中 Vim 只有 console 的版本，且是傳統 Unix 的行為模式，即在 INSERT
MODE 下，方向鍵和退格鍵是不起作用的。可以手動開啟“類 Windows”模式，即在
COMMAND MODE 下輸入：
:behave mswin
[附錄1]
<?xml version="1.0"?>
<!DOCTYPE fontconfig SYSTEM "fonts.dtd">
<fontconfig>
<!-- use SimSun to display all Asia character -->
<match target="font">
<test compare="contains" name="lang" >
<string>zh-cn</string>
<string>zh-tw</string>
<string>ja</string>
<string>ko</string>
</test>
<edit name="family"><string>SimSun</string></edit>
</match>
<!-- open anti-alias for all font -->
<match target="font" >
<edit mode="assign" name="antialias"><bool>true</bool></edit>
<edit mode="assign"
name="hintstyle"><const>hintslight</const></edit>
<edit mode="assign" name="hinting"><bool>true</bool></edit>
<edit mode="assign" name="autohint"><bool>false</bool></edit>
</match>
<!-- disable anti-alias for fonts between 8 to 17 pixels -->
<match target="font" >
<test compare="more_eq" name="pixelsize"
qual="any"><double>8</double></test>
<test compare="less_eq" name="pixelsize"
qual="any"><double>17</double></test>
<edit mode="assign" name="antialias"><bool>false</bool></edit>
</match>
<!-- set the minimum size for SimSun and Tahoma -->
<match target="font" >
<test name="family" qual="any">
<string>SimSun</string>
<string>NSimSun</string>
<string>Tahoma</string>
</test>
<test compare="more_eq" name="pixelsize"><int>8</int></test>
<test compare="less_eq" name="pixelsize"><int>12</int></test>
<edit compare="eq" name="pixelsize"><int>12</int></edit>
</match>
</fontconfig>
DFA(deterministic finite automaton): 從同一狀態出發的邊都標記有不同的符號
可以把一個DFA用一個轉置矩陣(transition matrix)表示，矩陣的第i行記錄狀態i向其他狀態跳轉的情況，edges[i][j]表示狀態i時吃掉一個j符號后跳轉到edges[i][j]狀態。
DFA的一個好處就是可以識別最長的匹配，比如對于IF8這個字符串，可以被識別為一個變量而不是一個關鍵字加數字。
處理方法是保留最后一次自動機的終結狀態Last-Final及其相對應的字符位置Input-Position-at-Last-Final。
每次進入一個終結狀態，就更新這兩個變量。
遇到死路(dead state, a nonfinal state with no output transitions)，通過這兩個變量回復到上一個終結狀態。
NFA(nondeterministic finite automaton): 從同一狀態出發的邊可能標記有相同的符號
由于從同一狀態出發選擇的路徑可能有多條，非確定性自動機總是需要進行“猜測”，而且總要做出正確的猜測。
看了半天總算對這節有了個大致的感覺，首先看幾個和sigprocmask相關的函數：
#include <signal.h>
int sigprocmask(int how, const sigset_t *set, sigset_t *oldset);
int sigemptyset(sigset_t *set);
int sigfillset(sigset_t *set);
int sigaddset(sigset_t *set, int signum);
int sigdelset(sigset_t *set, int signum); // Return: 0 if OK, -1 on error
int sigismember(const sigset_t *set, int signum); // Return: 1 if member, 0 if not, -1 on error
sigprocmask用于改變當前blocked signals的集合，how參數指定了具體的行為：
SIG_BLOCK 把set中的信號添加到blocked列表(blocked = blocked | set)
SIG_UNBLOCK 把set中的信號從blocked列表中移出(blocked = blocked & ~set)
SIG_SETMASK blocked = set
另外，如果oldset的值不是NULL的話，之前的blocked列表會保存在oldset中。
而sigaddset sigdelset sigfillset sigemptyset都是用于操作sigset_t列表的函數。
sigprocmask適用于在父子進程間同步的情況，以一個典型的UNIX shell程序為例，父進程需要在一個job
list中記錄它所有的子進程，當父進程創建一個子進程時，它把子進程加入到job list中；當父進程reap一個子進程時，就從job
list中移出這個進程。
如果不同步父子進程，有可能發生這種情況：
1. 父進程執行fork函數，內核調度新創建的子進程替換父進程運行
2. 在父進程能夠再次運行前，子進程終止，成為一個zombie，內核發送SIGCHLD信號給父進程
3. 父進程可以運行前，內核發現了未處理的(pending)SIGCHLD信號，讓它由父進程的handler處理
4. handler reap了終止的進程，調用deletejob函數，實際上沒有任何作用，因為父進程還沒有把該子進程加入列表
5. handler完成后，內核繼續運行父進程，后者調用fork完成后繼續，錯誤地把不存在的子進程加入了job list
一種做法是用最差情況下復雜度也是O(n)的算法求出第k大的數，然后把這個數作為pivot進行一次paritition，再排序該數左邊的部分。復雜度為O(n + klgk)
http://en.wikipedia.org/wiki/Selection_algorithm
另外，CLRS上Selection in worst-case linear time算法實際上對in expected linear time在選數時做了一個優化，這樣在最差情況下也有O(n)的復雜度了，實際應用中沒什么用 (thx to Peter大牛 ^_^)
搬到張江了
1. 比較排序法最差情況下至少需要omega(n lgn)
證明：
通過決策樹(decision tree)分析比較排序，n!種可能情況都要被該決策樹的葉子覆蓋。
設樹深度為h，有
n! <= l <= 2h
得h >= lg(n!) = omega(n lgn)
2. 計數排序
很簡單的排序算法，不過后面的C數組的運用比較技巧。
for i = 1 to k
do c[i] = 0
for j = 1 to length(a)
do c[a[j]] = c[a[j]] + 1
// c 數組記錄了各個元素的出現次數
for i = 1 to k
do c[i] = c[i] + c[i - 1]
// c[i] 記錄了小于或等于i的元素個數
for j = length(a) downto 1
do b[c[a[j]]] = a[j]
c[a[j]] = c[a[j]] - 1
復雜度： k = O(n)時，復雜度為theta(n)
|