效率（大數加法）——《C++程式設計風格》讀書筆記（五）

    C++的廣泛應用要得益于它的一些底層特性，例如内聯函數，它可以使我們編寫出效率更高的程式。編寫程式時，程式員必須知道将主要的精力放在程式的那個部分，才能使程式的運作效率更高。例如，在程式中，如果随意建立備援的對象，則可能會付出沉重的性能代價。在程式的源代碼中，我們不一定能夠看到所有的對象。例如，編譯器可能會建立臨時對象來作為函數參數。那些需要臨時對象的文法規則将使我們難以準确地估計執行開銷。是以，一些看上出不錯的源代碼将可能會編譯成執行開銷高昂的機器代碼。

   下面是一個大數加法的例子：

#include <iostream>

using namespace std;

class BigInt

{

private:

char* digits;

unsigned ndigits;

BigInt(char *d,unsigned n)

{

digits = d;

ndigits = n;

}

friend class DigitStream;

public:

BigInt(const char*);

BigInt(unsigned n = 0);

BigInt(const BigInt&);

void operator=(const BigInt&);

BigInt operator+(const BigInt&) const;

void print(FILE* f = stdout) const;

~BigInt() {delete digits;}

};

class DigitStream

{

private:

char* dp;

unsigned nd;

public:

DigitStream(const BigInt& n)

{

dp = n.digits;

nd = n.ndigits;

}

unsigned operator++()

{

if(nd == 0)

return 0;

else

{

nd--;

return *dp++;

}

}

};

void BigInt::print(FILE* f) const

{

for(int i = ndigits - 1;i >= 0;i --)

fprintf(f,"%c",digits[i]+'0');

}

void BigInt::operator=(const BigInt& n)

{

if (this == &n) return;

delete [] digits;

unsigned i = n.ndigits;

digits = new char[ndigits = i];

char* p = digits;

char* q = n.digits;

while(i--) *p++ = *q++;

}

BigInt BigInt::operator+(const BigInt& n) const

{

unsigned maxDigits = (ndigits > n.ndigits ? ndigits : n.ndigits) + 1;

char* sumPtr = new char[maxDigits];

BigInt sum(sumPtr,maxDigits);//類的私有構造函數隻能在類的内部使用

DigitStream a(*this);

DigitStream b(n);

unsigned i = maxDigits;

unsigned carry = 0;

while (i --)

{

*sumPtr = (++a) + (++b) + carry;

if(*sumPtr >= 10)

{

carry = 1;

*sumPtr -= 10;

}

else carry = 0;

sumPtr++;

}

return sum;

}

BigInt::BigInt(unsigned n)

{

char d[3*sizeof(unsigned)+1];//?

char *dp = d;

ndigits = 0;

do

{

*dp++ = n % 10;

n /= 10;

ndigits++;

} while(n > 0);

digits = new char[ndigits];

for(register i = 0;i < ndigits;i++)

digits[i] = d[i];

}

BigInt::BigInt(const BigInt& n)

{

unsigned i = n.ndigits;

digits = new char[ndigits = i];

char* p = digits;

char* q = n.digits;

while(i--) *p++ = *q++;

}

BigInt::BigInt(const char* digitString)

{

unsigned n = strlen(digitString);

if(n != 0)

{

digits = new char[ndigits=n];

char* p = digits;

const char* q = &digitString[n];

while(n--) *p++ = *--q - '0';

}

else

{

digits = new char[ndigits=1];

digits[0] = 0;

}

}

上述代碼中的不足之處和修正：

1.  DigitStream的作用是：通過成員函數operator++從BigInt對象中連續地提取數字，并在數字全部提取完時傳回零。DigitStream與BigInt非常緊密的耦合在一起，是以就成了BigInt實作的一部分。從友元關系和DigitStream的構造函數中的BigInt&類型參數，可以很清楚地看出這種耦合關系，對于簡單的問題來說，DigitStream是一種昂貴的解決方案。我們隻需在BigInt中使用一個私有成員函數就足夠了：

class BigInt

{

//……

char fetch(int i) const { return i < ndigits ? digits[i] : 0;}

//……

};

原則：降低耦合性——将類之間的互動最小化。

2.運算符的重載不是一緻和完整的。假設b是BigInt對象，而i是一個unsigned的值，程式中我們可以有b+i，但不能有i+b,這是不一緻的；在BigInt中定義了+，=，但卻沒有定義+=，是以BigInt是不完整的。

   在用fetch()來代替DigitStream後，通過一個小小的測試，我們可以深入的分析程式的效率問題。

void test()

{

BigInt b=1;

for(int i = 1；i<=1000;++i)

b=b+1;

}

    在16MHz的MC68030處理器上，這個函數需要6秒，也就是說平均每次加1運算需要6毫秒。那麼這些時間都消耗在了什麼地方呢？很明顯b=b+1消耗了大部分的時間。在這個簡單的表達式後面，大量的機器時間都被用于加法運算和指派運算。在每次執行b=b+1時，程式都要配置設定4個字元串。在+右邊操作數是一個整數，是以需要建立一個臨時的BigInt對象來比對operator+的參數類型，在這個臨時BigInt對象的構造函數中配置設定了第一個字元串；然後再operator+中為sumPtr配置設定了第二個字元串。operator+的傳回值是另一個BigInt對象，這個對象在return語句中建立，在建立對象時調用的是拷貝構造函數，并且參數就是sum。這樣，在拷貝構造函數中将配置設定第三個字元串。最後，在operator=中将配置設定第四個字元串。而每個動态配置設定的字元串都需要被删除，是以，這就導緻了在每次循環時總共需要八次記憶體配置設定器的調用。這耗費了大量的時間。

    通過進一步的分析，我們發現：maxDigits總是在最有意義的位置上為進位保留了一個位元組的空間，即使在運算中沒有發生進位時也是如此。在沒有進位時，operator+将在數值的最前面增加一個零。是以，當test()中的循環結束時，在b中總共有997個零，而有意義的隻是最後的四個十進制數字。程式的大部分時間都被浪費在處理含有大量零的字元串上了。

    另外，在BigInt中，一個邏輯狀态的數值可以用多個實體狀态來表示。例如數值123所對應的邏輯狀态就可以由3210、321、32100等實體狀态來表示。當多個實體狀态對應于同一個邏輯狀态時，類的設計者就必須格外小心。例如，如果我們将operator==增加到BigInt中，那個這個比較所針對的就必須是邏輯狀态而不是實體狀态。如果隻是簡單的對字元串digits進行比較，那麼就會導緻321不等于3210這樣的情況。

    上面的這兩個問題是由于動态字元串長度的無限增長導緻的。一個簡單的解決方法是：operator+在傳回結果之前，對和進行規範化即可。所需的代碼如下：

if(sum.digits[maxDigits - 1] == 0)

--sum.ndigits;

    為了進一步分析程式的性能，我們可以通過對全局運算符new和delete進行重載來收集統計資訊。如下，我們給出一個簡單的模闆類，在這個類中把統計new和delete的計數器，以及輸出、重置計數器的函數都封裝在一起。

class HeapStats

{

public:

static void report(FILE *f = stdout);

static void reset();

private:

friend void* operator new(size_t);

friend void operator delete(void*);

static int newN;

static int deleteN;

};

int HeapStats::newN = 0;

int HeapStats::deleteN = 0;

void HeapStats::report(FILE *f)

{

fprintf(f,"%d operator new calls/n",newN);

fprintf(f,"%d operator delete calls/n",deleteN);

fflush(f);

}

void HeapStats::reset()

{

newN = 0;

deleteN = 0;

}

void *operator new(size_t sz)

{

++HeapStats::newN;

return malloc(sz);

}

void operator delete(void* p)

{

++HeapStats::deleteN;

free(p);

}

    之是以我們把HeapStats類稱為模闆類，是因為這個類的作用與其它普通類的作用是不同的。類通常是被用來執行個體化對象的，而在HeapStats中隻是包含了靜态成員，是以用這個類來執行個體化對象是沒有意義的。HeapStats的目的是用來收集并封裝某個範圍之内的靜态成員。如果全局變量和非成員函數被作為類的靜态成員，那麼他們就可以有一個共同的辨別（即這個類的名字）。模闆類還可以改程序式的結構并加強封裝，在大型程式中，模闆類能夠減少全局變量沖突的可能性。

在主程式test()前後加入下面語句：

HeapStats::reset();

test();  

HeapStats::report();

輸出結果為：

4001 operator new calls

4001 operator delete calls

    首先，我們可以注意到程式中并沒有記憶體洩露：對new的調用次數等于對delete的調用次數。其次，我們并沒有辦法來避免需要配置設定如此之多的字元串，但可以通過為BigInt設計一個專門的記憶體器來改進性能。在選擇這條技術路線之前，我們可以首先對程式進行分析，看看能否在程式中減少對動态配置設定的字元串的需求。在目前的每次循環中，需配置設定4個字元串，這其中部分原因在于BigInt的實作，還有部分原因是表達式b=b+1的書寫方式。

    在BigInt的實作中，函數operator=中的字元串配置設定與釋放可以是不必要的。在函數中，即使舊字元串的大小等于新字元串的大小，operator=還是會配置設定一個新的字元串。而事實上，如果新舊字元串的大小相等，我們就不需要删除舊字元串并配置設定一個新字元串。下面給出了一個優化之後的operator=，如果在程式中，大多數的指派運算都是在位數不同的數值之間進行的，那麼這個優化并不會為程式帶來好處。

 void BigInt::operator= (const BigInt& n)

{

if (this == &n) return;

if (ndigits != i)//

{

delete [] digits;

digits = new char[i];

}

ndigits = i;//

char* p = digits;

char* q = n.digits;

while (i--) *p++ = *q++;

}

    在test()中共執行了1000次指派運算，其中997次指派運算中，左邊操作數的位數是不用改變的，是以這個優化起到了一定的作用。

優化後運作結果為：

3004 operator new calls

3004 operator delete calls

    到目前，所有的修改都是針對BigInt的實作，我們也可以對客戶代碼test()進行修改，也是可以提高性能的。在test()中，關鍵語句是b=b+1，容易的，我們可以想到做下面的修改：

 void test()

{

BigInt b = 1;

const BigInt one = 1;

for(int i = 1;i <= 1000;i++)

b = b + one;

}

改後結果為：

2005 operator new calls

2005 operator delete calls

最後修改下上面提到的其它問題，優化後的程式為：

#include <iostream>

#include<stdio.h>

#include<stdlib.h>

#include <string.h>

using namespace std;

class HeapStats

{

public:

static void report(FILE *f = stdout);

static void reset();

private:

friend void* operator new(size_t);

friend void operator delete(void*);

static int newN;

static int deleteN;

};

int HeapStats::newN = 0;

int HeapStats::deleteN = 0;

void HeapStats::report(FILE *f)

{

fprintf(f,"%d operator new calls/n",newN);

fprintf(f,"%d operator delete calls/n",deleteN);

fflush(f);

}

void HeapStats::reset()

{

newN = 0;

deleteN = 0;

}

void *operator new(size_t sz)

{

++HeapStats::newN;

return malloc(sz);

}

void operator delete(void* p)

{

++HeapStats::deleteN;

free(p);

}

class BigInt

{

private:

char* digits;

unsigned ndigits;

unsigned size;//size of allocated string

BigInt (const BigInt&, const BigInt&);

char fetch (unsigned i) const { return i < ndigits ? digits[i] : 0; }

public:

friend BigInt operator+(const BigInt&,const BigInt&);

BigInt (const char*);

BigInt (unsigned n = 0);

BigInt (const BigInt&);

BigInt& operator= (const BigInt&);

BigInt& operator+= (const BigInt&);

void print (FILE* f = stdout) const;

~BigInt() {delete digits;}

};

inline BigInt operator+(const BigInt& left, const BigInt& right)

{

return BigInt(left,right);

}

BigInt& BigInt::operator+=(const BigInt& rhs)

{

unsigned max = 1+(rhs.ndigits > ndigits ? rhs.ndigits : ndigits);

if(size < max)

{

char *d = new char[size = max];

for(unsigned i = 0;i < ndigits;++i)

d[i] = digits[i];

delete [] digits;

digits = d;

}

while(ndigits < max)

digits[ndigits++] = 0;

for(unsigned i = 0;i < ndigits;++i)

{

digits[i] += rhs.fetch(i);

if(digits[i]>=10)

{

digits[i] -= 10;

digits[i+1] += 1;

}

}

if(digits[ndigits - 1] ==0)

--ndigits;

return *this;

}

void BigInt::print (FILE* f) const

{

for (int i = ndigits - 1; i >= 0; i --)

fprintf (f, "%c", digits[i] + '0');

}

BigInt& BigInt::operator= (const BigInt& rhs)

{

if (this == &rhs) return *this;

ndigits = rhs.ndigits;

if (ndigits > size)//

{

delete [] digits;

digits = new char[size = ndigits];

}

for(unsigned i = 0;i < ndigits;++i)

digits[i] = rhs.digits[i];

return *this;

}

BigInt::BigInt(const BigInt& left, const BigInt& right)

{

size = 1 + (left.ndigits > right.ndigits ? left.ndigits : right.ndigits);

digits = new char[size];

ndigits = left.ndigits;

for (unsigned i = 0;i < ndigits;++i)

digits[i] = left.digits[i];

*this += right;

}

BigInt::BigInt (unsigned u)

{

char v = u;

for (ndigits = 1;(v/=10) > 0;++ndigits)

;

digits = new char[size = ndigits];

for(unsigned i = 0;i < ndigits;++ i)

{

digits[i] = u % 10;

u /=10;

}

}

BigInt::BigInt (const BigInt& copyFrom)

{

size = ndigits = copyFrom.ndigits;

digits = new char[size];

for(unsigned i = 0;i < ndigits;++i)

digits[i] = copyFrom.digits[i];

}

BigInt::BigInt (const char* digitString)

{

if(digitString[0] == '/0')

digitString = "0";

size = ndigits = strlen(digitString);

digits = new char[size];

for(unsigned i = 0;i < ndigits;++i)

digits[i] = digitString[ndigits - 1 - i] - '0';

}

void test()

{

BigInt b = 1;

const BigInt one = 1;

for(int i = 1;i <= 1000;i++)

b = b + one;

}

int main()

{

HeapStats::reset();

test();

HeapStats::report();

return 0;

}