第十三號艦隊
0%

Posted on Edited on In , ,

從C語言說起

在C語言的時候，const的用途很簡單，用來修飾變數的屬性。以下給個範例

1
2
3
4
5
6
void func(const int *v)
{
        int p;
        *v = 10;
        v = &p;
}

上面的*v = 10會被編譯器指出v是不能被修改的。 值得注意的是 const int *的寫法跟 int const *是一樣的，不過我比較偏好前者。

如果改寫成

1
2
3
4
5
6
void func(int * const v)
{
        int p;
        *v = 10;
        v = &p;
}

會告訴你v = &p這行錯了，由此可見int const *表示被指向的 內容 不可改，而指標是可以改變的，這邊的const是用來修飾int的。而int * const表示指向的 指標 不可改，而這邊的const是用來修飾int *的。
當然，如果要兩者間得，也可以寫成這樣

1
2
3
void func(const int * const v)
{
}

C++98

C++擴大const的使用範圍，允許const修飾Class的Member Function。表示這個函數是 Logic Constness，不影響外界看這物件的狀態。因此以下這段程式碼會出現問題。

1
2
3
4
5
6
7
class Test {
        int state;
public:
        void Func() const {
                state = 1;
        } 
};

由於C++支援Cast Overloading，支援Function Signature相同，但const屬性不同的Overload，因此這樣的是合法的，，

1
2
3
4
5
6
7
8
9
10
class Test {
        int state;
public:
        void NonConstFunc() {}
        void Func() {
                state = 0;
        }
        void Func() const {
        } 
};

寫個程式來測試一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
oid Test1(const Test &t)
{   
        t.NonConstFunc();  // Compile Error, 不能呼叫Non-const的Member Function
        t.Func(); 
}   
void Test2(Test &t)
{ 
        t.NonConstFunc();
        t.Func();
}
void Test3(Test &&t)
{
        t.NonConstFunc();
        t.Func();
}
Test t;
Test1(t);
Test2(t);
Test3(move(t));

除了Test1的Func是跑const版本之外，其他所有函數都是呼叫Non-const版本的Func
雖說const的Member function是不可修改 Logic Constness ，不過以下程式碼很難是合法的。

1
2
3
4
5
6
7
8
class Test {
        int *state;
public:
        void NonConstFunc() {}
        void Func() const {
            *state = 1;
        } 
};

Mutable

之前說過，從外界看到的類別狀態是 Logic Constness 的，這代表我們可以在 const函數裡面動手腳，只要外界看起來正常就好，因此就有了mutable的誕生。將上面的範例重新改寫。

1
2
3
4
5
6
7
class Test {
        mutable int state;
public:
        void Func() const {
                state = 1;
        } 
};

這樣就能正常使用了…初看之下好像很沒用，不過以這個範例來說

1
2
3
4
5
6
7
8
9
10
11
12
13
class Test {
        int state;
        mutable mutex obj_mutex;
public:
        void SetState() {
                unique_lock<mutex> lock(obj_mutex);
                state = 1;
        }
        int GetState() const {
                unique_lock<mutex> lock(obj_mutex);
                return state;
        }
};

在Multithread的情況之下，有人會呼叫SetState，而有人會想知道GetState的值，雖然state在GetState不會被改變，但是mutex會變。所以需要mutable的存在。
另外一種情形是當做Cache使用

1
2
3
4
5
6
7
8
9
10
11
12
class HashTable {
        mutable string lastKey, lastValue;
        ....
public:
        string lookup(string key) const {
                if (key == lastKey) return lastValue;
                string value = ookupInternal(key);
                lastKey = key;
                lastValue = value;
                return value;
        }
};

不過在C++11之後，又有新用法了 

1
2
3
4
int x = 30;
auto f1 = [=]() { x = 123; } // Compile error
auto f1 = [=]() mutable { x = 123; }
auto f2 = [&]() mutable { x = 123; }

f1在呼叫之後，x會變成123，不過離開f1之後，x又回到30，而f2呼叫之後就整個變成123了。
不過我看不懂第一個範例的用途是什麼。

constexpr

constexpr是C++11才有的觀念，原先就有Constant Expressions的觀念，不過還是有其不足之處。
假設我們要宣告個n*m的一維陣列，我們會這麼做。

1
2
3
const int n = 5;
const int m = 5;
int array[n * m];

假設我們已經有一個mul2的函數，試著編譯以下這段程式就會出現錯誤。

1
2
3
4
const int n = 5;
const int m = 5;
int mul2(int x, int y) { return x * y; }
int array[n * m];

結果我們只能藉由以下兩種方法解決，一是回到C語言的Preprocessor來做。

1
#define mul2(x, y) ((x) * (y))

這方式可行，不過缺乏型態資料。在Secure Coding的時候容易出錯。
另一種是在Runtime時算出一個常數。

1
2
3
4
5
int mul2(int x, int y) { return x * y; }
const int Mul2 = mul2(n, m);
void func() {
        int array[Mul2];
}

如果要把array儀到global scope，問題又出現了。導致不得不使用Preprocessor的解法。因此就有了constexpr的誕生。
有了constexpr之後，可以在編譯時期就算出答案，類似Template Metaprogramming，不過用途更廣。
上面的範例我們可以重新改寫

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
using namespace std;
const int n = 5;
const int m = 5;
constexpr int mul2(int x, int y) { return x * y; }
int array[mul2(n, m)];
int main() {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("arraySize = %lu\n", sizeof(array) / sizeof(array[0]));
        printf("mul2((x, y) = %d\n", mul2(x, y));
        return 0;
}

可以看到這邊的mul2不只可以用在compile-time，在runtime也可正常執行。
也可以在編譯時期使用物件，上面的範例我們可以用Functor在寫一次。

1
2
3
4
5
6
7
8
9
10
const int n = 5;
const int m = 5;
class Mul2 {
        int x, y;
public:
        constexpr Mul2(int x_, int y_) : x(x_), y(y_) {}
        constexpr int operator()() { return x * y; }    
};
constexpr Mul2 mul2(n, m);
int array[mul2()];

如果對constexpr有更多了解，可以參考Constexpr - Generalized Constant Expressions in C++11，目前支援constexpr的編譯器也不多。

結論

C++果然不愧是最難學的語言，每個環節都搞的特別複雜。我難過。

Posted on Edited on In , ,

看到了fasd之後發現真是相見恨晚啊。整天在那邊切換目錄真是麻煩。
安裝方法很簡單，下載之後只要

1
$ sudo make install

接著再自己的.bashrc之後加上這行

1
$ eval "$(fasd --init auto)"

然後就完成了…

如何使用

最簡單的情況，假設我們現在在home目錄下有foo跟bar兩個目錄，而foo目錄下有bar這個檔案。

1
2
3
4
5
~ $ cd foo
~/foo $ touch foo
~/foo $ touch bar
~/foo $ cd ~/bar
~/bar $

接著就可以用

1
2
~/bar $ z foo
~/foo $ z bar

跳到你想要的目錄，當然也支援 Tab complementation 。
也可以使用

1
$ zz

來使用交互式的方式來跳躍。
假設我們要修改~/foo/bar這個檔案，我們只需要

1
~/bar $ vim `f bar`

如果我們要把bar這個檔案複製到bar這個目錄，也只要

1
~/bar $ cp `d foo`/bar .

現在有兩個bar在兩個不同的目錄底下，如果要編輯的話，必須指定更多資訊供批配。

1
~/bar $ vim `f foo/bar`

其他更複雜的使用方法就參照網站上的範例使用。

Posted on Edited on In ,

看到C#的yield之後，上網查了一下，發現這是Generator的概念。根據Wiki上的寫法

A generator is a special routine that can be used to control the iteration behaviour of a loop

以C#為程式語言示範，假設沒有控制Iterator的話，印出一到一百間所有質數，我們會這麼寫。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static IList<int> GeneratorPrimes()
{
        var result = new List<int>();
        for (int i = 2; i <= 100; i++)
        {
            bool flag = true;
            for (int j = 2; j * j <= i && flag; j++)
                if (i % j == 0) flag = false;
            if (flag) result.Add(i);
        }
        return result;
 }
 
 IList<int> ans = GeneratorPrimes();
 foreach (var item in ans)
 {
        Console.WriteLine(" {0} ", item);
 }

假設我們想產生無限的質數列表，這方法就不適用，因此我們需要改變一個思緒，每次從中取得一個數，需要的時候在取下一個，因此，我們需要儲存狀態。

1
2
3
4
foreach (var item in GeneratorPrime())
{
        Console.WriteLine(" {0} ", item);
}

至於GeneratorPrime的作法就是我們要討論的部份

沒有語言支援的作法

沒有語言支援，只好再內部維護一個狀態機，記住當今狀態，以及如何移動狀態。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class PrimesGenerator : IEnumerator<int>
{
    int current, next;
    public PrimesGenerator()
    {
        Reset();
    }
    private void calcNext()
    {
        for (next++; ; next++)
        {
            bool flag = true;
            for (int i = 2; flag && i * i <= next; i++)
                if (next % i == 0) flag = false;
            if (flag) break;
        }
    }
    public bool MoveNext()
    {
        return current < 100;
    }
    public void Dispose()
    {
    }
    public int Current 
    { 
        get {
            int ret = current;
            current = next;
            calcNext();
            return ret;
        }  
    }
    object System.Collections.IEnumerator.Current
    {
        get {
            int ret = current;
            current = next;
            calcNext();
            return ret;
        }  
    }
    public void Reset()
    {
        current = 2;
        next = 3;
    }
}
public class IEnumerablePrimes : IEnumerable<int> 
{
    public IEnumerator<int> GetEnumerator()
    {
        return new PrimesGenerator();
    }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}
public static IEnumerable<int> GeneratorPrime()
{
    return new IEnumerablePrimes();
}

C++和Java的作法略有不同，不過重點是放在PrimesGenerator中各種狀態的保存及移轉。如果簡單的話還好，像是Tree Traversal這種複雜的情況就一個頭兩個大。

語言支援的作法

由於C#提供yield，yield表示江控制權教還給呼叫者，而Iterator保持在回傳時的那個狀態，當再一度被呼叫時，可以重剛剛那個狀態繼續運行下去，於是我們程式碼可以寫成這樣。

1
2
3
4
5
6
7
8
9
10
public static IEnumerable<int> GeneratorPrime()
{
        for (int i = 2; i <= 100; i++)
        {
            bool flag = true;
            for (int j = 2; j * j <= i && flag; j++)
                if (i % j == 0) flag = false;
            if (flag) yield return i;
        }
}

這邊的yield就是一個syntax sugar，透過編譯器的幫忙，將上面這段code改寫成類似上面的State Machine，有興趣的人可以透過Resharper來看看邊義氣幫你處理掉多少東西。

Haskell的解法

由於Haskell有Lazy evaluation，所有東西都是Generator，所以可以寫成這樣。

1
2
3
4
5
6
primes = 2 : 3 : nextprime 5  where
  nextprime n | b = n : nextprime (n+2)
              | otherwise = nextprime (n+2)
    where b = all ((/= 0).(rem n)) $ takeWhile ((<= n).(^2)) $ tail primes

printPrimes = mapM_ print $ takeWhile (<= 100) primes

前面的primes產生一個無限質數數列，而printPrimes印出這個數列中滿足條件的部份，

Posted on Edited on In ,

有時候有其需要，知道Shared Library當中有哪些符號，這時候可以這樣做。
以下是我們的測試程式

1
2
3
4
5
6
7
8
int bar;
void foo() {}
class Foo {
        static int value;
        void Bar(int);
};
int Foo::value = 0;
void Foo::Bar(int) {}

Linux

在Linux底下可以用nm來指令

1
$ nm -gC test.so
  • g 列出所有External symbols
  • c 由於C++支援Function overload，要區別同名的函數名稱的話，需要在後方加上一些符號以供區別，而Demangle就是讓這些奇形怪狀的符號變成人可以看懂得版本。
    以上的結果如下
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    000000000020102c B bar
    0000000000201028 B __bss_start
                     w __cxa_finalize@@GLIBC_2.2.5
    0000000000201028 D _edata
    0000000000201038 B _end
    00000000000006e4 T _fini
                     w __gmon_start__
    00000000000005a0 T _init
                     w _ITM_deregisterTMCloneTable
                     w _ITM_registerTMCloneTable
                     w _Jv_RegisterClasses
    00000000000006d0 T foo()
    00000000000006d6 T Foo::Bar(int)
    0000000000201030 B Foo::value

Windows

需要額外一個步驟，用一個Exporting from a DLL Using DEF Files倒出foo這個函數。
Windows底下可以用DLL Export Viewer。
而我們只看到foo，而沒有clas被輸出。輸出一個class不能用Def那種方式，如果需要的話，可以用dllexport這種方式。

這邊可見Windows跟Unix設計上的不同，Unix是預設把所有Symbols列出，然後需要的在隱藏。而Windows是需要的在列出。
至於如何隱藏，Binary Hacks有介紹，日後在補上。

Posted on Edited on In , , ,

同樣來自VC Blog的靈感，來測試一下三大編譯器的能耐。
如果對這技術有興趣的話，可以操考Wiki跟Code Optimizations:
Partial Dead Code Elimination和Dead Code Elimination這兩份PDF。
測試程式如下

1
2
3
4
5
6
int main()
{
	long long s = 0;
	for (long long i = 1; i <= 1000000000; i++) s += i;
	return 0;
}

Visual C++的結果

未開最佳化，如同VC Blog列的那樣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
	mov	QWORD PTR i$1[rsp], 1
	jmp	SHORT $LN3@main
$LN2@main:
	mov	rax, QWORD PTR i$1[rsp]
	inc	rax
	mov	QWORD PTR i$1[rsp], rax
$LN3@main:
	cmp	QWORD PTR i$1[rsp], 1000000000		; 3b9aca00H
	jg	SHORT $LN1@main
	mov	rax, QWORD PTR i$1[rsp]
	mov	rcx, QWORD PTR s$[rsp]
	add	rcx, rax
	mov	rax, rcx
	mov	QWORD PTR s$[rsp], rax
	jmp	SHORT $LN2@main
$LN1@main:

最佳化版本，結果相同，什麼都沒有

1
// Nothing

GCC的結果

未開最佳化

1
2
3
4
5
6
7
8
9
10
11
	movq	$1, -8(%rbp)
	jmp	.L2
.L3:
	movq	-8(%rbp), %rax
	addq	%rax, -16(%rbp)
	addq	$1, -8(%rbp)
.L2:
	cmpq	$1000000000, -8(%rbp)
	setle	%al
	testb	%al, %al
	jne	.L3

如同Visual C++的結果一樣，照實執行。
最佳化版

1
// Nothing

跟Visual C++的結果相同，完全沒有程式碼，證明了這段程式碼一樣被偵測到而被捨棄。根據這篇的說明，在-O2的設定終究有暗示Dead Code Elimination的使用。

Clang的結果

未開最佳化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	movq	$1, -24(%rbp)
.LBB0_1:                                # %for.cond
                                        # =>This Inner Loop Header: Depth=1
	cmpq	$1000000000, -24(%rbp)  # imm = 0x3B9ACA00
	jg	.LBB0_4
# BB#2:                                 # %for.body
                                        #   in Loop: Header=BB0_1 Depth=1
	movq	-24(%rbp), %rax
	movq	-16(%rbp), %rcx
	addq	%rax, %rcx
	movq	%rcx, -16(%rbp)
# BB#3:                                 # %for.inc
                                        #   in Loop: Header=BB0_1 Depth=1
	movq	-24(%rbp), %rax
	addq	$1, %rax
	movq	%rax, -24(%rbp)
	jmp	.LBB0_1
.LBB0_4:                                # %for.end

可以看出三大編譯器對做同一件事，產生的程式碼風格相差甚大。
最佳化版

1
// Nothing

大家都能偵測到Dead Code Elimination。

同場加映

在VC Blog的Option 2，在原來的程式碼後面，加上printf，使得Dead Code Elimination失效。
VC的結果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
       xor    edx, edx
       mov    eax, 1 
       mov    ecx, edx
       mov    r8d, edx
       mov    r9d, edx
       npad   13
$LL3@main:
       inc    r9
       add    r8, 2
       add    rcx, 3
       add    r9, rax                           ;; r9  = 2  8 18 32 50 ...
       add    r8, rax                           ;; r8  = 3 10 21 36 55 ...
       add    rcx, rax                          ;; rcx = 4 12 24 40 60 ...
       add    rdx, rax                          ;; rdx = 1  6 15 28 45 ...
       add    rax, 4                            ;; rax = 1  5  9 13 17 ...
       cmp    rax, 1000000000                   ;; i <= 1000000000 ?
       jle    SHORT $LL3@main                   ;; yes, so loop back

使用Loop unwinding的技巧加速。
不過GCC跟Clang更勝一籌，直接印答案了。

1
movabsq	$500000000500000000, %rsi # imm = 0x6F05B59F17F6500

如果把原先的程式碼改成這樣

1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
int main()
{
	long long s = 0;
	long long count;
	scanf("%lld", &count);
	for (long long i = 1; i <= count; i++) s += i;
	printf("%llu\n", s);
	return 0;
}

Visual C++跟GCC的產生結果就比較像了，VC原先的Loop Unwinding被拿掉了。

1
2
3
4
5
6
7
8
9
	movl	$1, %eax
	testq	%rdx, %rdx
	jle	.L3
.L6:
	addq	%rax, %rsi
	addq	$1, %rax
	cmpq	%rdx, %rax
	jle	.L6
.L3:

而Clang會根據x64指令集作最佳化一

1
2
3
4
5
6
7
8
9
10
11
12
	movq	8(%rsp), %rax
	testq	%rax, %rax
	jle	.LBB0_2
# BB#1:                                 # %for.body.lr.ph
	movl	$1, %ecx
	cmovgq	%rax, %rcx
	leaq	-1(%rcx), %rax
	leaq	-2(%rcx), %rdx
	mulq	%rdx
	shldq	$63, %rax, %rdx
	leaq	-1(%rdx,%rcx,2), %rbx
.LBB0_2:                                # %for.end

Posted on Edited on In , , ,

看了VC Blog的Constant-Folding之後，測試一下VC2012，GCC和Clang對最佳化的演繹程度為何。
比較基準，未開最佳化(VC是/Od，而GCC/Clang是-O0)，跟第二級最佳化(/O2和-O2)
第一個範例

1
int main() { return 7 + 8; }

不果是VC2012，GCC或是Clang都會直接將eax填入15，無論有沒有開最佳化。這邊的最佳化不需要後端Codegen的幫忙。
第二個範例

1
2
int bump(int n) { return n + 1; }
int main() { return 3 + bump(6); }

在未開最佳化的情況，VC產生的Assembly Code像這樣

1
2
3
mov     ecx, 6
call    ?bump@@YAHH@Z
add     eax, 3

而最佳化的Assembly Code則是

1
mov     eax, 10

這邊需要後端Codegen的幫忙，才能在編譯的時刻得到常數值。
而GCC跟Clang的表現也差不多，最大的差別是Intel語法跟AT&T對組合語言的表示方式不同。
未最佳化版本

1
2
3
movl	$6, %edi
call	_Z4bumpi
addl	$3, %eax

最佳化版本

1
movl	$10, %eax

在這種最簡單的最佳化大家都有一樣的能力，接著可以看其他部分的差異。

Posted on Edited on In ,

把目前看到的資訊做個總結，分幾篇文章來寫

從同步開始

假設我們要抓取Web Response，可以這樣寫。

lang: c#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static int BUFFER_SIZE = 1024;
static void getContentFromURI(string uri)
{
    WebRequest request = WebRequest.Create(uri);
    WebResponse response = request.GetResponse();
    Stream stream = response.GetResponseStream();
    byte[] buffer = new byte[BUFFER_SIZE];
    using (stream)
    {
        while (true)
        {
            int actualRead = stream.Read(buffer, 0, BUFFER_SIZE);
            if (actualRead != 0)
            {
                string partialContent = Encoding.Default.GetString(buffer, 0, actualRead);
                Console.WriteLine(partialContent);
            }
            else
            {
                break;
            }
        }
    }
}

以上都是同步動作，如果有個Thread呼叫此函數，外面的Thread必須等待這個函數執行結束，才能繼續往下走。如果是UI Thread的話，通常會出現漏斗符號，然後整個UI僵住的情形。

放到Thread

解決方案之一是把耗時的工作丟到Thread之後，外面呼叫的就能繼續向下執行。

lang: c#
1
2
3
4
5
6
7
static void ThreadStart()
{
    string uri = "http://www.facebook.com";
    getContentFromURI(uri);
}
Thread thd = new Thread(ThreadStart);
thd.Start();

更甚一點的是用ThreadPool來，減少Thread的開銷

lang: c#
1
ThreadPool.QueueUserWorkItem(state => ThreadStart());

不過這還是無法完全解決問題，這邊的行為是屬於IO Bounded Operation，不需要CPU計算能力，指需要完成之後，發個中斷通知CPU事件完成就好，使用Thread的解決方案還是不夠好。而.Net的IO Operation幾乎都有提供同步跟非同步的版本，就從這點開始。

.Net 1.0, BeginXXX / EndXXX

如同上面所說，幾乎所有IO operation都有非同步版本，而其命名都是BeginXXX / EndXXX開始，因此我們可以把程式改寫成這樣。

lang: c#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static void getContentFromURI(string uri)
{
    WebRequest myWebRequest = WebRequest.Create(uri);

    myWebRequest.BeginGetResponse(ar =>
    {
        WebResponse response = myWebRequest.EndGetResponse(ar);
        Stream stream = response.GetResponseStream();
        byte[] buffer = new byte[BUFFER_SIZE];
        using (stream)
        {
            while (true)
            {
                int actualRead = stream.Read(buffer, 0, BUFFER_SIZE);
                if (actualRead != 0)
                {
                    string partialContent = Encoding.Default.GetString(buffer, 0, actualRead);
                    Console.WriteLine(partialContent);
                }
                else
                {
                    break;
                }
            }
        }
    }, null);
}

程式碼被切成兩段，在GetResponse之前，跟GetResponse之後，相較於同步的版本，相差沒說很大。
談一下Exception部分，同步的版本指需要一個try-catch，而非同步的需要兩個，這邊變得很麻煩。
更進一步將Read的部份變成非同步的版本，程式碼會變成這樣。

lang: c#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static void ReadHelper(Stream stream)
{
	byte[] buffer = new byte[BUFFER_SIZE];
	stream.BeginRead(buffer, 0, BUFFER_SIZE, ar =>
	{
            int actualRead = stream.EndRead(ar);
            if (actualRead != 0)
            {
                string partialContent = Encoding.Default.GetString(buffer, 0, actualRead);
                Console.WriteLine(partialContent);
                ReadHelper(stream);
            }
            else
            {
                stream.Close();
            }
        }, null);
}
static void getContentFromURI(string uri)
{
	WebRequest myWebRequest = WebRequest.Create(uri);

	myWebRequest.BeginGetResponse(ar =>
	{
            WebResponse response = myWebRequest.EndGetResponse(ar);
            Stream stream = response.GetResponseStream();
            ReadHelper(stream);
	}, null);
}

這邊可以看到，用using釋放資源的方式已不可行，同樣的，用for/while的方式也不可行，必須使用Recursive的方式來持續讀取資料。而由於這樣，例外處理幾乎不可行。程式碼寫的支離破碎，難怪一堆人寧可寫同步版本。

Posted on Edited on In , ,

眾所週知，Java跟C#都是從C++演變而來。
既然C++有Template，Java在5.0，C#在2.0的時期分別引進了Generics，
雖然看起來很像，看其中差異還是不小，列出重要的幾點份來討論。

Generics不能接受Nontype Parameter

由於實作方式的不同，Generics拿掉了這個

lang: cpp
1
2
3
template <typename T, int MAXSIZE> class Stack {
	T stack[MAXSIZE];
};

Generic不支援Specialization

不管是Full Specialization或是 Partial Specialization，通通不行。所以也寫不出這樣的程式碼。

lang: cpp
1
2
template <typename T> class Foo {};
template <> class Foo<int> {};

Template不對Type作任何限制，而Generics能擁有Bound Type

這點才是最大的不同，假設我們要寫一個兩樹相加的Generic function。
在C++我們會這麼寫

lang: cpp
1
2
3
template <typename T> T sum2(T a, T b) { return a + b; }
sum2(100, 200);
sum2(string("Hello"), string("World"));

可以看到，只要有定義operator+，我們什麼東西都能相加。
同樣的Code，如果改寫成C#的話

lang: c#
1
2
3
4
public static T sum2<T>(T a, T b)
{
    return a + b;
}

連編譯都邊不過。原因出在Template是在Compile-Time完成的，在編譯的時刻就能檢查出operator+是否存在，而Java跟C#的Generics是在Runtime則否，必須對Type有其一定的限制，在這個範例裡面，我們需要這個Type要有相加的能力，才能作相加的動作。

lang: java
1
2
3
4
public <T extends Number> T sum(T a, T b) {
  T newValue = a.sum(b);
  return newValue;
 }

所有從Number衍生出來的子類別，Integer，Double等都可以使用，不過String不行。
不過.Net 4.0之後有更好的解法，掠過編譯時期的型別檢查，不過Java沒有此特性。

lang: c#
1
2
3
4
5
6
public static T sum2<T>(T a, T b)
{
    dynamic a_ = a;
    dynamic b_ = b;
    return a_ + b_;
}

Template不支援Covariance和Contravariance

這是另一個大題目，同樣在.Net 4.0之後，支援了Covariance和Contravariance。Java的版本有無支援也需要確認。
以後有時間再仔細描述。在C#可以寫這樣的Code

Covariance Example lang: c#
1
2
3
4
5
6
7
8
9
10
11
class Base
{
}
class Derived : Base
{
}
public static void Run(IEnumerable<Base> bases)
{
}
IEnumerable<Derived> derivedBases = new Derived[] { new Derived(), new Derived() };
Run(derivedBases);

類似的程式碼在C++就失敗了…

Covariance Example lang: c#
1
2
3
4
5
6
7
8
9
10
11
12
class Animal
{
    public void Feed() {}
}
class Frog : Animal {
}
static void DoSomethingToAFrog(Action<Frog> action, Frog frog)
{
        action(frog);
}
Action<Animal> feed = animal => { animal.Feed(); };
DoSomethingToAFrog(feed, new Frog());

其他Template高級技巧

例如SFINAE，Template Template Parameter等，由於學習門檻相當高，所以Generics都把它拿掉了。

Posted on Edited on In , ,

程式計算中有個技巧，叫做Memoization，避免重複計算相同的工作。
以下分別用C/Python/Haskell來當範例

C Language

以Fibonacci Number來說，遞迴的表示式這樣。

lang: c
1
2
3
4
5
int fib(int n)
{
	if (n < 2) return n;
	return fib(n - 1) + fib(n - 2);
}

加上Memoization的程式碼會變這樣

lang: c
1
2
3
4
5
6
7
8
int _fib[100];
int fib(int n)
{
	if (n < 2) return n;
	if (_fib[n] != -1) return _fib[n];
	return (_fib[n] = fib(n - 1) + fib(n - 2));
}
memset(_fib, -1, sizeof(fib));

Python

至於Python版Recursive的程式碼也相當相似

lang: python
1
2
3
4
5
def fib(n):
    if n in [0,1]:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

不過由於Python將Function當First-Class Function，可以寫出像這樣的程式碼。

lang: python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def memoize(fn):
    stored = {}
    def memoized(*args):
        try:
            return stored[args]
        except:
            result = fn(*args)
            stored[args] = result
            return result
    return memoized

def fib(n):
    if n in [0,1]:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

fib = memoize(fib)

更甚者可以使用Python的Decorator來簡化程式碼

lang: python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def memoize(fn):
    stored = {}
    def memoized(*args):
        try:
            return stored[args]
        except:
            result = fn(*args)
            stored[args] = result
            return result
    return memoized

@memoize
def fib(n):
    if n in [0,1]:
        return n
    else:
        return fib(n - 1) + fib(n - 2)

Haskell

Haskell反而是裡面最麻煩的，因為他是個純Pure Functional Language。同樣的先來看Recursive版本。

lang: haskell
1
2
3
4
fib :: Int -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

而Memorize版的方法不少，不過比起上面兩種反而難以理解。

lang: haskell
1
2
3
4
5
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib(n - 2) + memoized_fib(n - 1)

果然各種程式語言個有所長，看情況決定該用些什麼語言解決問題才是。