顯示具有 知識水庫 標籤的文章。 顯示所有文章
顯示具有 知識水庫 標籤的文章。 顯示所有文章

星期二, 5月 19, 2009

神奇的鎖 - mutex

寫 C 的 pthread 時,經常會碰到一個問題:「如果有兩個以上的 thread 同時存取同一變數,該怎麼辦?」。有個很消極的作法是...不管它。

這樣的作法優點是,省事。可是一旦碰上問題,整個系統將因此錯亂。底下我將介紹一種在 multi threading 系統中,很常被使用的作法 - lock


在 pthread.h 中,提供了 pthread_mutex_t 變數型態及其相關 function 。為了解釋上的方便,這裡我把 pthread_mutex_t 看成是一個鎖。

這個鎖的用途是,當你想存取某些資源時,必須先取得這個鎖,然後進行資料處理,最後把鎖放回去。只要你沒拿到這個鎖,就必須不斷地等拿走這個鎖的人將它放回。整個流程如下:



所以,當一個 thread 存取某個(或某些)變數時,必須先呼叫 pthread_mutex_lock 取得該變數(或該群變數)的鎖,才能進行接下來的處理;而處理完之後,也必須呼叫 pthread_mutex_unlock 將鎖放回原位,讓其他需要這個鎖的 thread 也能順利完成工作。

至於一個 multi threading 的系統有幾個鎖,每個鎖分別管理哪些變數(資源),全都由 programmer 自行決定。鎖分得越多,雖然系統的效能會增加,但同時也該更加重視 deadlock 的問題。反之,若一個鎖管理全部的資源,則絕對不會有 deadlock 的問題,但缺點是會降低系統的效能(因為 thread 進行資料處理時,經常只用到一小部分的 global 變數,而一個鎖綁住全部資源就代表,不管 thread 需要存取多少 global 變數,都將拒絕其他 thread 存取它用不到的的變數,直到該 thread 把事情做完為止。)

有時候理論說了一大堆,還是不如實作來得有趣。
也只有下場實作時,才能體會理論的精隨

星期二, 4月 07, 2009

IP spoofing 轉址攻擊淺見

相關內容請參考阿碼外傳的「大規模網頁綁架轉址:威脅未解除,但專家都猜錯了


這起事件,經查證為利用 IP spoofing 發起的攻擊。攻擊模式如下圖:



以上是粗略的架構圖,介於 user 和 server 之間的 router 是整個網路中某個 router。
attacker 在 router 處進行竊聽,並針對特定封包發起攻擊。

當 attacker 偵測到 user 對某特定 web server 發出 HTTP GET 的請求時,便搶在 web server 回送 web 封包之前,送假封包至 user 端。儘管 web server 送出的封包最終仍會送至 user 端,但因為 user 已經收到所期望封包(某個特定的 sequence number),因此便會忽略掉 web server 送來的「真」封包。

attacker 送來的假封包,包含了另一個網頁的資訊,brower 收到後理所當然會呈現另一個網頁,偽造出 DNS 被入侵使得某網址被轉址的錯誤猜測。

再網頁資訊正確送至 user 端後,attacker 主動發出 FIN 封包,要求 user 結整與 web server 的連線。user 收到此封包後,理所當然會回到 FIN 封包給 web server。由於 web server 沒有送 FIN 封包給 user,因此 web server 收到回也會回送 FIN 封包。但 user 端早已中斷連線,因此 user 並不會對 web server 送出的 FIN 封包做處理,也因此整個攻擊並不會因為額外的封包而受阻。

這樣的攻擊手段可以將網頁轉址至惡意網站,可自動殖入木馬等惡意軟體。甚至在攻擊後期,attacker 嘗試讓 user 感覺不出任何異樣,卻能夠確實轉址並殖入木馬。

另外,這起攻擊的核心在於竊聽 router 上的封包。若 attacker 不能得知 user 與 web server 間來往的封包內容,attacker 便不能在正確的時機傳送正確的「假封包」。

IP spoofing 的攻擊源自 IP 封包的無安全性。這樣的漏洞讓 attacker 有機可乘。但以 TCP/IP 為核心的網路架構難以輕易變動,因此現階段只能憑藉 application 端的防護措施。

星期五, 7月 18, 2008

EDA - Electric Design Automation

原先因為雨太大,索性不想參與今天的課程,看了公告才知道今天暫停 XD

EDA 這塊領域,很偏硬體設計,但卻是在做軟體,而不是硬體。

--


抽象的硬體描述之後,緊接而來的便是實作,然而在實作上,往往有手動與自動兩種方式。手動的優點是可以考量很多,做到最佳化;而自動的優點在於能在短時間內處理大量資料。

最早的電腦,內部所用的電晶體,可能只有數百,或一兩千個。這樣的數量,手動製作還在可接收的範圍之內;然而當數量增加到 4 千 2 百萬,甚至更多呢?

試問,4200 萬塊的拼圖,需要多少時間才排完,你願不願意去排?

所以,讓硬體製程自動化是必需的。然而,這塊領與上要處理的資料量,往往是 10 的 7、8 次方起跳,在加上問題往往是 NP﹝簡單來說,不是在多項式複雜度的時間內能完成﹞。

想想,光是 N 平方的複雜度,處理10的8次方的資料,就必須花上 100 多天,這樣的時間都不可能接受了,更何況是指數或 N! 的複雜度呢!

舉個最簡單的例子: F = (a + b)(b + ~c)(a + c) ﹝這是個邏輯式﹞是否衡等於 1,要如何才能最精確檢驗?是不是列出所有可能,也就是 2 的 3 次方種可能。這是指數複雜度的問題阿!!!!當變數數目擴大至 10 的 5 次個,會是什麼樣的情況?恐怕電腦一輩子也跑不完。

可是,還是存在能夠在短短一分鐘之內解掉這樣問題的方法,而這樣的方法,往往需要強大的演算法能力,將演算法變形、複雜化,進而達到解題的需求。

當演算法複雜化,首當其衝便是 code 的行數。處理這樣的問題,5、6 千行的 code 是很平常的,甚至上萬行都有。如果寫幾千行的程式就弄得一個頭兩個大,那又如何在專業上立足?﹝不止這個領域,其他領域也是一樣的,幾千行的程式就像家常便飯,看看魔獸爭霸就好,我想恐怕不只幾千行了。﹞

除此之外,這塊領域往往和幾何運算脫離不了關係。如何安排電晶體的位置,使 cost 最小?如何接線,彼此不會干擾,又要衡量 cost?等等...這些都是需要高度複雜得演算法才能做到的。

所以這塊領域,往往將所面臨到的困難轉成一道程式問題,而如何解開問題,就是主要的研究方向了。

星期五, 7月 11, 2008

資安

不論懂不懂電腦,也不論學不學電腦,只要有用電腦,就應該看看這篇 :)

為己為人,請做好電腦保全

星期六, 7月 05, 2008

以 BigNumber 的概觀設計談 OO

如果你要設計一個新型別,有哪些事是你會考慮的呢?

--


撇開實作不談,最該先被考慮的是 - 「到底要提供哪些 operator」

class type 和 basic type 的差異在於:
basic type 的操作幾乎全建立在符號上(+, -, *, /, ...);而 class type 則能有類似 function call 的操作。

而以 BigNumber 的觀點來看,我們希望它操作上如同 basic type - int 般,那樣直觀。所以若能設計出建立在符號上的最基本的整數運算及 IO,這是首選。也就是說,這 class type 可以很自然透過加減乘除等符號,完成我們所要求的運算。
要實作出這樣的 type - BigNumber,必須使用有提供 operator overloading 的 programming language 才行。

若上述要求無法達成,就必須考慮類似 function call 的操作方式。
而這種方式又分為兩種:隸屬於 class 或 object 的 function,這兩者的差異可以用以下兩種 declaration 來分析。

static BigNumber add (BigNumber &n1, BigNumber &n2);

在使用上就像:

bignumber3 = BigNumber.add (bignumber1, bignumber2);

而另一種是

BigNumber add (BigNumber &big);

使用上如:

bignumber3 = bignumber1.add (bignumber2);

在這兩者的選擇上,我偏向使用前者,在使用上較於自然(很明確看出將兩個 BigNumber parameter 相加,並回傳相加後的結果 - 仍以 BigNumber 表示)

而在實作上,兩者的差異並不大,純粹看設計者偏好哪種方式。

--

說到這裡,已經顯現出 OO 最重要的特色。

在設計一個 type 之前,思考此型別該具備哪些操作,這就是 data abstraction。我們知道 BigNumber 應該具備加減乘除甚至 mod 等 operator,也考慮要以哪種方式實作這些 operator(以符號 +-*/,以 function belong to class,或 function belong to object)。

思考到此,我們已經掌握整個 type 的雛形,甚至懂得如何去使用這個 type。但「operator 是如何被設計的?」「是以何種方式去表示大數?」這些,我們都還不懂;也可以說,在實作階段前,我們不需要懂。

「實作」和「概觀」被分開了,在正式進入實作前,不希望去了解內部的結構,我們可以對它一無所知。但我們必須徹底了解 type 具備哪些 operator,該怎麼去使用等...

就好像站在使用者的角度,可以想像得到:「喔,這是個什麼樣的東西,它可以這樣被使用」,可是對「它是如何被設計出的」一概不了解。因為這些繁複的細節,對使用者來說是多餘的...

而這正是 data abstraction 的精義。

星期五, 8月 10, 2007

套件庫

最近玩 ubuntu ,被套件庫弄得很煩。原以為只要把某些網址註解拿掉就 ok,update 後用 apt 仍然找不到某些要的套件。後來發現不是註解有沒有拿掉的問題。

# deb http://tw.archive.ubuntu.com/ubuntu/ edgy-backport main restricted universe multiverse
# deb http://tw.archive.ubuntu.com/ubuntu/ edgy-security universe

這兩個註解,即時拿掉也不會增加新的套件,因為這是掌管安全性和一些支援的

要增加套件源,應該是將原先:

deb http://tw.archive.ubuntu.com/ubuntu/ edgy main restricted

改為:

deb http://tw.archive.ubuntu.com/ubuntu/ edgy main restricted universe multiverse

就好像代表同意來自位址下屬於 universe 及 multiverse 的套件

一直以來都認為網址後的一些英文就好比註解,告訴我們這網址內的套件是屬於哪類的,但事實上,那並不是註解,而是給 apt 解讀的。所以,套件庫不單單是網址,而存在著某些分門別類的語法。

--
附上套件查詢網址:

http://packages.ubuntu.com

星期二, 7月 10, 2007

Inheritance - IS-A

在《Fundamentals of Data Structures in C++》中看到一段話


Inheritance is used to express subtype relationships between ADTs. This is also referred to as the IS-A relationship. We say that a data object of Type B IS-A data object of Type A if B is more specialized than A or A is more general than B; that is, all Bs are As, but not all As are Bs; or the set of all objects of Type B is a subset of the set of all objects of Type A. For example, Chair IS-A Furniture, Lion IS-A Mammal, Rectangle IS-A Polygon.

IS-A 及 HAS-A 是 OO 兩個很特殊的關係。HAS-A 就好比組裝,如:汽車有四個輪子,這代表每一個汽車物件其內部皆有四個輪子物件。簡單說就是物件中包有物件的關係。

而 IS-A 就有點像在探討本質,像:圓形窗子雖然改造過了,但它還是個窗子;桌子雖然是眾多家具之一,然而,他仍是種家具。

而 IS-A 的關係正解釋了為什麼 pointer to base class 可以指向 object of derived class 。

星期日, 7月 08, 2007

The Knuth-Morris-Pratt Algorithm

最簡易的子字串搜尋法,是對於每一個字元開頭 Si,判斷字串 S(i)S(i + 1)...S(i + n - 1),是否與欲搜尋之字串 P(0)P(1)...P(n - 1)相同,然而,這樣的搜尋法複雜度為 O (n * m),當資料量極大時,將秏費相當多的時間。


因此,為加快子字串搜尋的速度,不斷改良後,出現了名為 Knuth-Morris-Pratt 的演算法。

此演算法的精隨在於,比對失敗時,能跳過不需再比對的部分,迅速找出下一次的比對點。這與 DP 的要旨相符,「做過的就不要再做」。

Knuth 演算法如下:

對於每次的比對,若比對成功,則原字串及子字串的 index 各加 1,繼續比對。

若比對失敗,則視情況決定位移:
(1)若子字串的 index 為 0,代表開頭便不符,因此只需把原字串的 index 加 1 繼續比對。
(2)若在其他位置比對失敗,則根據位移表決定子字串的 index 移至何處繼續比對。


位移概念如下:

當原字串在位置 i 和子字串在位置 j 比對失敗,代表 P(0) ~ P(j - 1) 與 S(i - j) ~ S(i - 1) 的比對皆成功。

若字串 P(j - n)...P(j - 1) 與 P(0)...P(n - 1) 相同 (n為可行值之最大值),再根據上述條件,可知字串 P(j - n)...P(j - 1) 與 S(i - n)...S(i - 1)相同,因此可知 P(0) ~ P(n - 1) 與 S(i - n) ~ S(i - 1) 的比對皆會成功。

既然如此,只需從 P(n) 與 S(i) 比對起便可(因為確保 P(0) ~ P(n - 1) 的比對一定成功)


至於如何建表,在此就不多做說明。

快速建表法之 Code 如下:

int LengthP = Length (); // LengthP 為子字串之長度
f[0] = -1; // f 為表
for (int j = 1 ; j < LengthP ; ++j) {
int i = f[j - 1];
// str 為子字串名稱
while ((*(str + j) != *(str + i + 1)) && (i >= 0))
i = f[i];
if (*(str + j) == *(str + i + 1))
f[j] = i + 1;
else
f[j] = -1;
}

星期五, 6月 01, 2007

Data structure - Array

最為基本的資料結構,正是 Array 。


在某些 programmer 眼中,Array 是一連串的記憶體空間,以一名稱加上 index 代表一變數,可省去宣告許多不同名變數的麻煩,也能藉由 loop 統一處理這些資料。

從另一個角度來看,Arry 是由許多 pair 所組成的 set(集合),每一個 index 都能對應到某個 value。最常見的 index 型態 int,但 index 並非局限於 int ,index 可以是 double、string、甚至是自定型別。

這就好像數學上的定義域和值域,是多對一的關係,但絕不會一對多(每一個 index 只會對應到一個 value)。

星期三, 5月 16, 2007

ADT - Abstract Data Type

受到 C# 的薰陶,一時間忘了 ADT 另一層的函意。今天在《Fundamentals of Data Structure in C++》中看到一段話:



The specification, which must be contained inside the public portion of the class definition of the ADT, consists of the names of every public member function, the type of its arguments, and the type of its result (This information about a function is known as its function prototype). There should also be a description of the function does, which does not refer to the internal representation or implementation details. This requirement is quite important because it implies that an abstract data type is implementation-independent.


一個完整的 ADT ,不僅要符合 Data abstraction 及 Encapsulation;更重要的是,它必須與實作無關。

ADT 著重於形態的抽象概念,而不是如何實踐此概念,因此 ADT 每一個 member function,只需說明此 function 能做什麼、該做什麼,而不必明定此 function 該如何做。

譬如說,一個 bignumber ADT 包含 add 此 member function。設計者只管以註解說明它的功用(對兩個 bignumber object 做相加),至於如何相加,相加後如何維護,皆與設計者無關。這些實作上的細節,是為實踐這些抽象概念的 programmer 才需關注的。

總之,ADT 是一種概念的陳述、一種規格的規範。它提供下一層設計者一些概念、一些介面標準,有助於設計者完成此 Type。但 ADT 絕不必提供任何實作上的資訊,就好像某 ADT 的使用者,絕不必了解它如何被實作出,只管此 ADT 代表什麼概念、提供了哪些功能。

星期一, 5月 07, 2007

delegate

delegate 是 C# 中宣告函式形態的機制。也就是說,我們可以自訂一種型態,用來儲存一個函式。這樣一來,我們就能把函式當成參數,在 function﹝method﹞ 之間傳遞。


在 C++ 中,是以 pointer to function 實踐,而函式引數稱之為 function object ﹝functor﹞。就這方面來說,C++ 比起 C# 要來的複雜些,但在概念上大同小異。

至於 delegate 的功用,主要在實踐 function 多樣性的同時,仍維護住 encapsulation。也就是說,不論外部有何更動,都不影響到這些 function 的運作﹝function 內容仍維持不變﹞。

思考以下狀況:沒有函式引數之前,要以一個 sort function 針對不同比對規則排序,該如何做?一個可行的方法是這樣的:先定義好許多 compare function,並給每個 compare function 相對應的代號(字元或整數)。而在使用此 sort function 時,多傳遞一作為代號的參數,而 sorting 時就根據此代號判斷要用哪個 compare function 來 sorting。如此一來,就能達到目的 - 一個 sort function 能針對不同比對規則做排序。

然而,這樣的方式有個重大的缺點:當我們創造出一新的比對方式時(也就是增加了一個代號),我們必須更改原函式(例:增加一個 if),讓它能識別此代號,並使用對應的 compare function 做排序。這樣一來,一旦有新的比對方式產生,不僅原程式需要更改,連 sort function 內部也必須更動,而這大大增加了 maintain 的難度。

因此,我們希望能有一種方法,不論增加了多少比對方式,原 sort function 都能維持不變,而 delegate 正回應了此要求。

delegate 的語法如下:

delegate return_type function_type_name ( parameter );


定義完 function_type 之後,就能以此 function_type 宣告 function 變數。只要某 function return type及 parameter 與 function_type 中的一致,此 function 就能被儲存在此變數中。因此,以 sort function 排序時,只要傳遞此 function_type 的變數,不必經由 if 判斷,就能得知要以哪個 compare function 來 sorting。

舉個例子,假設有個 sort function 要對字串排序,則我們的 compare function_type 應該如下:

delegate bool strcmp (string s1, string s2);


又假設我們有以下幾種 compare function:

bool ascii_cmp (string s1, string s2) { //... }
bool size_cmp (string s1, string s2) { //... }
bool other_cmp (string s1, string s2) { //... }


由於 ascii_cmp、size_cmp、other_cmp 的 return_type 及 parameter 都與 strcmp 一致,它們都可以被儲存在由 strcmp 宣告出的變數之中,如:

strcmp cmp1 = new strcmp (ascii_cmp);
strcmp cmp2 = new strcmp (size_cmp);
strcmp cmp3 = new strcmp (other_cmp);


接著,我們只要讓 sort function 能接收一 strcmp type 的變數,就能達成我們要的比對規則,如下(以簡單的 bubble sort為例):

void string_sort (string[] array, strcmp cmp) {
for (int i = 0 ; i < array.Length ; ++i) {
for (int j = 0 ; j < array.Length - i - 1 ; ++j) {
if (cmp (array[j], array[j + 1]))
swap (ref array[j], ref array[j + 1])
}
}
}


從以上可知,使用 function_type 宣告出的變數就如同使用一般 function。

星期四, 3月 08, 2007

Initialization VS Assignment

double d = 3.14;

double d;
d = 3.14;

以上這兩種寫法的表層意義是一樣的;然而,實質上卻完全不同。
前者稱為 Initialization,後者則是 Assignment。

前者只會出現在 Definition,而後者是隨時可用。就效率上來說,Initialization 大於 Assignment,原因在於 Initialization 是在配置出生硬空間時,就在該空間上賦值;而 Assignment 則是先找出該空間所在,再加以賦值。

就 class 來說, Initialization 是喚起 copy constructor;而 Assignment 則喚起 Assignment operator。

對所有 class object 來說,若沒有明確指明 Initialization 仍必然進行 Initialization,也就是喚起 default constructor。
而 built-in type 為 Local or Dynaic 若不指明要 Initialization 則不會進行 Initialization。

Declaration VS Definition

所謂 Declaration,只是告知程式(同時也是告訴我們)有這樣的東西存在,例如:

string s;
extern double d;
int gcd (int a, int b);

除了第一個是宣告也是定義外,後二個只是單純的宣告,而不包含定義。

所謂 Definition,是為該變數(函式)配置空間,並與宣告的名字與型態結合。例如:
vector vec (10);
int gcd (int a, int b) {
if (b == 0)
return a;
return gcd (b, a % b);
}

以上兩者皆是定義。

There must always be exactly one definition for each name in a C++ Program. However, there can be many declarations.

另一個特點在於,只要有宣告,就可以在該 scope 內使用它,但前提是 compiler 要能找到定義所在(需放在全域空間或單純宣告之前),舉個例子:

#include< iostream >
using namespace std;

int main () {
int gcd (int a, int b);
int test = 10;
extern int test;
cout << test << endl;
return 0;
}

int gcd (int a, int b) {
if (b == 0)
return a;
return gcd (b, a % b);
}

其中的 test 及 gcd 都有兩次宣告和一次定義,因為在很多時候,定義時宣告的過程是難以避免的。

星期三, 3月 07, 2007

implicit conversion

在書上看到以下程式碼(有經過微修)


class complex {
double re, im;
public:
complex (double r = 0, double i = 0) : re (r), im (i) {}
// following skip
};

void f (complex z) {
complex a = 2.3;
complex b = 1/a;
complex c = a + b * complex (1, 2.3);

//.....
}

標示為紅色的部分令我感到訝異,這真的能執行嗎?
因此我自行寫了 test code,果真可以。

每個變數都需以 constructor 初始化,但 complex並非 base type,因此宣告時的 =(assign)與 () (initialization) 是不同的。由於 complex a = 2.3; 的結果與 complex a (2.3); 相同,因此我最初假設這兩行 statament 的意義是一樣的。後來我想到在 constructor 前加上 explicit,預料中的事發生了,原先 compile OK 的 code 出現 error。

在短短一行 complex a = 2.3 牽涉到:

1、implicit conversion
把 double type 2.3 轉換成 complex(這中間呼叫了 constructor)

2、initialization
喚起 copy constructor 初始化 a;

加上 explicit 後 error 的原因在於,explicit 會禁止藉由此 constructor 做 implicit conversion,除非使用者明確要求轉換,也就是 complex a = static_cast < complex > (1.2);

--
還好還記得,不然會被向上學長吊起來 XD

星期二, 3月 06, 2007

Data Abstraction

在《The C++ Programming Language 2/e》中看到一段話:

We could implement this Stack in several ways. It is important that a user doesn't need to know how we do it. As long as we keep the interface unchanged, a user will not be affected if we decide to re-implement Stack.

這一小段話已大略闡述 Abstraction 的精隨,就 class 的層面來說,使用者只需要知道此 class 的用途、有哪些 public member function 可用、及這些 function的使用方式和功能。對於此 class 有哪些 private data member,甚至 member function 如何寫成一概不知,也可說完全沒必要知道。

若牽扯到維護層面,只要 class 的撰寫者不改變任何公開的介面(interface 只是個空殼,實體隨撰寫的考量而變,但功用需維持一致),使用者也就不用做任何變更。這也是 object-oriented programming 的分層維護,撰寫者只需針對自己的 code maintain。

以上只是 Data Abstraction 的一些要點,若進一步鑽研,可以請教向上學長 XD

星期一, 1月 01, 2007

complex declarations

char (* (*x ())[]) ();

x is a function returning pointer to array[] of pointer to function returning char.

char (* (*x[3]) ())[5];

x is a array[3] of pointer to function returning pointer to array[5] of char.

又看到以前看過的奇怪宣告,如今還是難以看出那是什麼
(還好會拆解)

--
出自 《The C Programming Language》

星期四, 10月 05, 2006

object-oriented programming

嗯,看完《Visual C# 2005 How to program》後,總算體會到什麼是「物件導向」。這本書對物件的著墨不錯。

學過 C++ 等語言的都知道 class 結合 data member 和 member function,成為一種新型態,也知道data abstraction 及 encapsulation 是落實物件導向很重要的概念。許多書藉把 OOP 和 inheritance 放在一塊(包括《C++ Primer 4/e》),容易讓人誤解為 OOP 和繼承習習相關,進而狹化 OO 概念。

在《Visual C# 2005 How to program》一書中,第一章很清楚地描述何謂物件,在日常生活上,人、球、計算機等等,都算是物件。這些物體除了本質外,還包含了許多行為,譬如說:人會「走」、「跑」、「跳」等;計算機會「顯示數字」、「計算結果」;球會滾。在程式裡,物件就是具有本質(data member),以行為(member function or method),我們可以藉由這些行為(方法)來操控(處理)本質,這就是物件。

那何謂物件導向?舉個簡單的例子:在沒有任何計算工具發明前,我們直接透過人腦來算術;但有了算盤、計算機等等後,我們是藉由這些工具來算術。算術,可以看待為處理數值,也就是資料。而差別僅在於,前者是直接處理資料,後者是藉由工具來處理。因此,物件導向是指「透過物件來管理、處理資料」,不同於以往直接處理資料。

以上是對於物件導向最淺層的描述

--
應該沒講錯吧!?

星期四, 9月 28, 2006

極限的嚴謹定義

「對於任意給定的ε,必能找到對應的δ,使得 0 < |x - a| < δ 則 |f(x) - L| < ε」。 L 是當 x 趨近於 a 時的極限值,若以上條件成立,則證明 L 的確為 x 趨近於 a 的極限值。

假設有一函式 f(x) = 2x + 3 ,證明 lim x->2 f(x) = 7 :
|f(x) - 7| < ε => |2x - 4| < ε => 2|x - 2| < ε
又|x - 2| < δ 故 2|x - 2| < 2δ,所以 2δ = ε
當 0 < |x - 2| < δ 則 2|x - 2| < 2δ,又 2δ = ε
因此 2|x - 2| = |2x - 4| = |2x + 3 - 7| = |f(x) - 7| < 2δ = ε

我只想問,這樣證有什麼意義嗎!?

--
「把積木拆掉再組裝回去」這個譬喻真棒...

星期二, 9月 26, 2006

copy & swap

copy & swap 是 exception handle 常用的技巧。處理資料的過程中,難免會遇到異常狀況,好的異常處理非 commit 則 rollback。前者保證「付諸行動」,也就是必完成使用者的要求;後者保證發生異常時,資料維持不變。copy & swap 用來實行後者,先處理副本,再與欲處理的資料交換。這樣一來,若處理過程中發生錯誤,原資料仍完好如一。

假設有個 class factory,其中有個 function process

class factory {
public:
/* constructor, destructor, and other function */
void process (factory &);
private:
/* some data members */
}

void factory::process (factory &obj) {
// process directly obj
}

process 直接對 obj 處理,若很不幸地發生異常,process 被迫停止,將留處理不完全的 obj

另一個 process 版本:

void factory::process (factory &obj) {
factory temp (obj);
// process the copy : temp
swap (obj, temp);
}

我們先拷貝 obj,之後對其副本做運算,處理完成後,再交換處理過的副本與原先資料。若異常發生,temp 的 destructor 將釋放 temp 佔用的記憶體,而 obj 保持不變,也就是rollback。

--
exceptional C++ 的寶藏真多:p

星期日, 9月 24, 2006

The Hacker Ethic, and the Spirit of the Information Age

偶然在圖書館內拾到此書之中譯本,被標題吸引的我,一口氣鑽了下去。
此書主要論述hacker的生活哲學(前半是如此),和資本主義者有何差異!

1、為何工作?
在清教徒的眼中,工作的本質並不重要,他們視工作為責任。沒有工作,就無法在社會上立足,生活的核心緊緊扣著工作。他們工作僅僅為了「生存」,工作是為了「禮拜日」。然而,對hacker來說,工作只是生活的一小部分,他們不把工作和休閒分開,工作不完全為了「生存」,還包含了自我實現、生活樂趣。

2、時間
「資本主義者隨著時鐘工作,但hacker隨著人性工作」。資本主義認為工作時不該懈怠,任何閒暇都不被允許,但一旦下班,他們宛如機器人般,立即放下手邊的事務。而對hacker來說,他們不會整天都專注在工作上,陪朋友吃個下午茶,寫個無意義的小程式等等..對他們來說,這是很正常的。他們生活不會過於緊湊,想工作時就工作,想休閒時就休閒。他們認為:「科技改善效率是為了增加休閒時間,而不是利益」。

3、freedom is not free
有些人認為hacker跟共產或烏托邦主義沒兩樣,因為他們喜好free的軟體。然而,free並不是指「免費」,而是「自由」。他們並不排斥賺錢行為,但他們反對「管制資訊流通的方式」來賺錢。況且,hacker不僅反對資本主義的工作態度,也反對共產主義相同的特質。

札記就先寫到這,目前只看完第三篇。
--
這是本好書:)