|
|
與在前面:++(--)有太多讓人困惑的地方,(i++)+(i++)與(++i)+(++i)有什么不同?為什么不同?如果從機器的角度去理解，就會豁然開朗。
先來看段程序:
int main()
{
int i=3;
int j=(i++)+(i++);
// int j=(++i)+(++i);
printf("%d,%d\n",i,j);
}
(1)在VC 6.0下：
對于(i++)+(i++):
結果：i=5,j=6
相應的匯編代碼為(有詳細注釋)：
8B 45 FC mov eax,dword ptr [ebp-4] ;i->eax
03 45 FC add eax,dword ptr [ebp-4] ;i+i=6
89 45 F8 mov dword ptr [ebp-8],eax ;6->j
8B 4D FC mov ecx,dword ptr [ebp-4] ;i->ecx(=3)
83 C1 01 add ecx,1 ;ecx=4
89 4D FC mov dword ptr [ebp-4],ecx ;4->i
8B 55 FC mov edx,dword ptr [ebp-4] ;i->edx
83 C2 01 add edx,1 ;edx=5
89 55 FC mov dword ptr [ebp-4],edx ;5->i
對于(++i)+(++i)：
結果：i=5,j=10
相應的匯編代碼為：
8B 45 FC mov eax,dword ptr [ebp-4] ;i->eax (=3)
83 C0 01 add eax,1 ;eax=4
89 45 FC mov dword ptr [ebp-4],eax ;4->i
8B 4D FC mov ecx,dword ptr [ebp-4] ;i->ecx
83 C1 01 add ecx,1 ;ecx=5
89 4D FC mov dword ptr [ebp-4],ecx ;5->i
8B 55 FC mov edx,dword ptr [ebp-4] ;i->edx
03 55 FC add edx,dword ptr [ebp-4] ;edx=10 ,即i+i
89 55 F8 mov dword ptr [ebp-8],edx ;10->j
(2)在gcc 3.2.2下:
對于(i++)+(i++):
結果：i=5,j=6相應的匯編代碼為：
c7 45 fc 03 00 00 00 movl $3, -4(%ebp） ;3->i 8b 55 fc movl -4(%ebp), %edx ;i->edx (=3) 8b 45 fc movl -4(%ebp), %eax ;i->eax (=3) 8d 04 10 leal (%eax,%edx), %eax ;i+i=6 ->eax 89 45 f8 movl %eax, -8(%ebp) ;6->j 8d 45 fc leal -4(%ebp), %eax ;&i->eax ff 00 incl (%eax) ;i++ ,即i=4,注意這里為寄存器間接尋址 8d 45 fc leal -4(%ebp), %eax ;&i->eax ff 00 incl (%eax) ;i++,即i=5
對于(++i)+(++i)：
結果：i=5,j=10
相應的匯編代碼為：
movl $3, -4(%ebp) ;3->i leal -4(%ebp), %eax ;&i->eax incl (%eax) ;i++,即i=4 leal -4(%ebp), %eax ;&i->eax incl (%eax) ;i++, i=5 movl -4(%ebp), %eax ;i->eax, eax=5 addl -4(%ebp), %eax ;i+i ->eax ,eax=10 movl %eax, -8(%ebp) ;10->j
可見，對于VC6.0和gcc，二者的結果一致，但是gcc 3.2.2生成的匯編代碼明顯比VC6.0高效、簡潔。這也許是因為VC 6.0出現較早的原因吧。
(3)如果這段代碼用java實現，結果會怎樣呢？
程序:
public class TestAdd {
public static void main(String[] args) {
int i=3;
int j=(i++)+(i++); //5,7
//int j=(++i)+(++i); //5,9
System.out.println(i+","+j);
}
}
對于(++i)+(++i):
i=5,j=9。結果點意外!
來看看它的字節碼吧:
//j=(++i)+(++i)
//5,9
0: iconst_3 ;常量3入棧
1: istore_1 ;從棧中彈出3,存入i,i=3
2: iinc 1, 1 ;i++, i=4
5: iload_1 ;將i壓入棧,即4入棧
6: iinc 1, 1 ; i++,i=5
9: iload_1 ;i入棧,即5入棧
10: iadd ;從棧中彈出兩個int類型的數相加,結果入棧,即9入棧
11: istore_2 ;從棧中彈出9,存入j,即j=9
對于(i++)+(i++):
i=5,j=7。結果也很意外!
也來看看它的字節碼吧:
//j=(i++)+(i++)
//5,7
0: iconst_3 ;常量3入棧
1: istore_1 ;從棧中彈出3,存入i,i=3
2: iload_1 ;i入棧,即3入棧
3: iinc 1, 1 ;i++,即i=4
6: iload_1 ;i入棧,即4入棧
7: iinc 1, 1 ;i++,即i=5;注意：5沒有入棧,所以此時棧中的數為3和4
10: iadd ;從棧彈出兩個int類型數相加，結果入棧,即7入棧
11: istore_2 ;從棧中彈出7，存入j,即j=7
Java與VC/gcc為什么會有如此的區別呢？其實原因很簡單，VC/gcc生成的是本地代碼，而X86處理器是基于寄存器的架構，也就是如果它要進行了兩個數相加，它會先把兩個數移到寄存器，再進行加法運算。而Java虛擬機是一種基于棧的架構，如果它要進行兩個數相加，它會先彈出兩個數，再進行加法運算，再將結果入棧。
將 cout 的 flag 保存到變量, 以便修改后的恢復
ostream::fmtflags old = cout.flag() ; // 無參將返回當前 flag 值
cout.flag(old) ; // 恢復到原先保存的值
將 bool 值以 literals 輸出
cout <<"numeric : " <<true <<" or " <<false <<endl ; // 1 or 0
cout <<"literals : " <<boolalpha <<true <<" or " <<false <<endl ; // true or false
cout <<"literals : " <<boolalpha <<0 <<endl ; // 0 原因: 0 在cout中不等價于 false
一旦我們使用 boolalpha 將改變 cout 對 bool 值的輸出格式. 此后的 cout 都會將 bool 輸出為 literals.
將 bool 值以 numeric 輸出
cout <<"numeric : " <<noboolalpha <<true <<" or " <<false <<endl ;// 1 or 0
從此以后, cout 對 bool 值的輸出將恢復 numeric 格式
指定 Integral Values 的 Base
const int ival = 17 ; // 'ival' is constant, so value never change
cout <<"oct : " <<oct <<ival <<endl ; // 21 : 8 進制
cout <<"dec : " <<dec <<ival <<endl ; // 17 : 10 進制
cout <<"hex : " <<hex <<ival <<endl ; // 11 : 16 進制
cout <<"hex : " <<hex <<17.01 <<endl ; // 17.01 : 不受影響
如 boolalpha 一樣, oct, dec, hex 也是 persistent. 一旦改變, 將影響后續的輸出格式.
顯示表明 Integer Values 的 Base
cout <<showbase ; // Show base when printing integral values
cout <<"oct : " <<oct <<ival <<endl ; // 21 : 8 進制
cout <<"dec : " <<dec <<ival <<endl ; // 017 : 10 進制
cout <<"hex : " <<hex <<ival <<endl ; // 0x11 : 16 進制
cout <<"hex : " <<hex <<17.01 <<endl ; // 17.01 : 不受影響
cout <<noshowbase ; // Reset state of the stream
若想改變16進制字母的大小, 可以結合 uppercase/nouppercase cout <<showbase <<uppercase ;
cout <<"hex : " <<hex <<15 <<endl ; // 0XF 大寫形式
cout <<nouppercase ;
cout <<"hex : " <<hex <<15 <<endl ; // 0xf 小寫形式
showbase 與 noshowbase 的作用周期也是 persistent
對于 float/double 型, 有三種格式化控制
一: 輸出精度 precision : by default is 6 pricision
控制了至多一共會輸出多少個數字.
當要輸出的數字多余指定的值時, 將發生 四舍五入(rounded);
當要輸出的數字少于指定的值時, 則實際輸出的數字個數將少于指定值.
// cout.pricision(4) ; // 等價于 cout <<setprecision(4) ;
cout <<setprecision(4) <<12.345678 <<endl ; // 12.35 rounded!
cout <<setprecision(10) <<12.345678 <<endl ; // 12.345678 其實內部發生了 rounded, 而結果正好進位, 與原值相同
cout <<cout.precision() <<endl ; // 輸出當前精度
二: 表現形式 notation : 'very large and very small values are printed using scientific notation. other values use fixed decimal.'
notation 控制了輸出的形式 : 科學計數法(scientific) 和 定點小數(fixed)
float f = 101 / 6.0 ;
cout <<fixed <<f <<endl ; // 16.83334 : 小數點后共6位
cout <<scientific <<f <<endl ; // 1.683333e+001 : 小數點后共6位
cout.unsetf(ostream::floatfield) ; // Retrieve to default handling for notation
cout <<f <<endl ; // 16.8333 : 所有數字共6位
三: 輸出十進制浮點 'By default, when the fractional part of a floating-point value is 0, the decimal point is not displayed. The showpoint manipulator forces the decimal point ot be printed.'
cout <<10.0 <<endl ; // 10
cout <<showpoint <<10.0 <<endl ; // 10.0000
cout <<noshowpoint <<endl ; // Revert to default handling of decimal
輸出填充 Padding the Output
setw to specify the minimum space for the next numeric or string value.
cout <<setw(10) <<12.3 <<endl ; // ______12.3
cout <<setw(10) <<12 <<3 <<endl ; // ________123
cout <<setw(3) <<12.345 <<endl ; // If the total output is more than 3, it can be extended
 left to left-justify the output.
cout <<left ; // left-justify
cout <<setw(5) <<12 <<setw(5) <<34 <<endl ; // 12___34___
 right to right-justify the output. Output is right-justified bu default.
cout <<right ; // By default
cout <<setw(5) <<12 <<setw(5) <<34 <<endl ; // 12___34___
 internal controls placement of the sign on negative value. internal left-justifies the sign and right-justifies the value, padding any intervening space with blanks.(if setfill not set)
cout <<internal ; // By default
cout <<setw(5) <<-12 <<endl ; // 12___34___
 setfill lets us specify an alternative character to use when padding the output. By default, the value is a space.
cout <<setfill('*') ; // By default
cout <<setw(5) <<12 <<endl ; // 12___34___
Header Files Manipulators Defined in <iomanip>
setfill(char ch) Fill whitespace with 'ch'
setprecision(int n) Set floating-point precision to 'n'
setw(int w) Read or write value to 'w' characters
setbase(int b) Output integers in base 'b'(only 'b' is 8/10/16 could the function work)
摘要: 程序員編程藝術：第二章、字符串是否包含及匹配/查找/轉換/拷貝問題作者：July，yansha。時間：二零一一年四月二十三日。致謝：老夢，nossiac，Hession，Oliver，luuillu，雨翔，啊菜，及微軟10... 閱讀全文
摘要: 第一章、左旋轉字符串作者：July，yansha。時間：二零一一年四月十四日。微博：http://weibo.com/julyweibo。出處：http://blog.csdn.net/v_JULY_v。-----------------------------... 閱讀全文
當使用讀/寫自旋鎖時，內核控制路徑發出的執行read_lock或write_lock操作的請求具有相同的優先權：讀者必須等待，直到寫操作完成。同樣地，寫者也必須等待，直到讀操作完成。
Linux 2.6中引入了順序鎖（seqlock），它與讀/寫自旋鎖非常相似，只是它為寫者賦予了較高的優先級：事實上，即使在讀者正在讀的時候也允許寫者繼續運行。這種策略的好處是寫者永遠不會等待讀（除非另外一個寫者正在寫），缺點是有些時候讀者不得不反復讀多次相同的數據直到它獲得有效的結果。
每個順序鎖都是包括兩個字段的seqlock_t結構：
typedef struct {
unsigned sequence;
spinlock_t lock;
} seqlock_t;
一個類型為spinlock_t的lock字段和一個整型的sequence字段，第二個字段sequence是一個順序計數器。
每個讀者都必須在讀數據前后兩次讀順序計數器，并檢查兩次讀到的值是否相同，如果不相同，說明新的寫者已經開始寫并增加了順序計數器，因此暗示讀者剛讀到的數據是無效的。
通過把SEQLOCK_UNLOCKED賦給變量seqlock_t或執行seqlock_init宏，把seqlock_t變量初始化為“未上鎖”，并把sequence設為0：
#define __SEQLOCK_UNLOCKED(lockname) /
{ 0, __SPIN_LOCK_UNLOCKED(lockname) }
#define SEQLOCK_UNLOCKED /
__SEQLOCK_UNLOCKED(old_style_seqlock_init)
# define __SPIN_LOCK_UNLOCKED(lockname) /
(spinlock_t) { .raw_lock = __RAW_SPIN_LOCK_UNLOCKED, /
SPIN_DEP_MAP_INIT(lockname) }
#define __RAW_SPIN_LOCK_UNLOCKED { 1 }
寫者通過調用write_seqlock()和write_sequnlock()獲取和釋放順序鎖。write_seqlock()函數獲取seqlock_t數據結構中的自旋鎖，然后使順序計數器sequence加1；write_sequnlock()函數再次增加順序計數器sequence，然后釋放自旋鎖。這樣可以保證寫者在整個寫的過程中，計數器sequence的值是奇數，并且當沒有寫者在改變數據的時候，計數器的值是偶數。讀者進程執行下面的臨界區代碼：
unsigned int seq;
do {
seq = read_seqbegin(&seqlock);
/* ... CRITICAL REGION ... */
} while (read_seqretry(&seqlock, seq));
read_seqbegin()返回順序鎖的當前順序號；如果局部變量seq的值是奇數（寫者在read_seqbegin()函數被調用后，正更新數據結構），或seq的值與順序鎖的順序計數器的當前值不匹配（當讀者正執行臨界區代碼時，寫者開始工作），read_seqretry()就返回1：
static __always_inline int read_seqretry(const seqlock_t *sl, unsigned iv)
{
smp_rmb();
return (iv & 1) | (sl->sequence ^ iv);
}
注意在順序鎖機制里，讀者可能反復讀多次相同的數據直到它獲得有效的結果（read_seqretry返回0）。另外，當讀者進入臨界區時，不必禁用內核搶占；另一方面，由寫者獲取自旋鎖，所以它進入臨界區時自動禁用內核搶占。
并不是每一種資源都可以使用順序鎖來保護。一般來說，必須在滿足下述條件時才能使用順序鎖：
（1）被保護的數據結構不包括被寫者修改和被讀者間接引用 的指針（否則，寫者可能在讀者的眼皮子底下就修改指針）。
（2）讀者的臨界區代碼沒有副作用（否則，多個讀者的操作會與單獨的讀操作有不同的結果）。
此外，讀者的臨界區代碼應該簡短，而且寫者應該不常獲取順序鎖，否則，反復的讀訪問會引起嚴重的開銷。在Linux 2.6中，使用順序鎖主要是保護一些與系統時間處理相關的數據結構。
自旋鎖可分為用在單核處理器上和用在多核處理器上。單核處理器： 用在單核處理器上，又可分為兩種： 1.系統不支持內核搶占 此時自旋鎖什么也不做，確實也不需要做什么，因為單核處理器只有一個線程在執行，又不支持內核搶占，因此資源不可能會被其他的線程訪問到。 2.系統支持內核搶占 這種情況下，自旋鎖加鎖僅僅是禁止了內核搶占，解鎖則是啟用了內核搶占。 在上述兩種情況下，在獲取自旋鎖后可能會發生中斷，若中斷處理程序去訪問自旋鎖所保護的資源，則會發生死鎖。因此，linux內核又提供了spin_lock_irq()和spin_lock_irqsave()，這兩個函數會在獲取自旋鎖的同時（同時禁止內核搶占），禁止本地外部可屏蔽中斷，從而保證自旋鎖的原子操作。 多核處理器： 多核處理器意味著有多個線程可以同時在不同的處理器上并行執行。舉個例子： 四核處理器，若A處理器上的線程1獲取了鎖,B、C兩個處理器恰好這個時候也要訪問這個鎖保護的資源，因此他倆CPU就一直自旋忙等待。D并不需要這個資源，因此它可以正常處理其他事情。 自旋鎖的幾個特點： 1.被自旋鎖保護的臨界區代碼執行時不能睡眠。單核處理器下，獲取到鎖的線程睡眠，若恰好此時CPU調度的另一個執行線程也需要獲取這個鎖，則會造成死鎖；多核處理器下，若想獲取鎖的線程在同一個處理器下，同樣會造成死鎖，若位于另外的處理器，則會長時間占用CPU等待睡眠的線程釋放鎖，從而浪費CPU資源。 2.被自旋鎖保護的臨界區代碼執行時不能被其他中斷打斷。原因同上類似。 3.被自旋鎖保護的臨界區代碼在執行時，內核不能被搶占，亦同上類似。
對于一個c/c++程序員來說，內存泄漏是一個常見的也是令人頭疼的問題。已經有許多技術被研究出來以應對這個問題，比如 Smart Pointer，Garbage Collection等。Smart Pointer技術比較成熟，STL中已經包含支持Smart Pointer的class，但是它的使用似乎并不廣泛，而且它也不能解決所有的問題；Garbage Collection技術在Java中已經比較成熟，但是在c/c++領域的發展并不順暢，雖然很早就有人思考在C++中也加入GC的支持。現實世界就是這樣的，作為一個c/c++程序員，內存泄漏是你心中永遠的痛。不過好在現在有許多工具能夠幫助我們驗證內存泄漏的存在，找出發生問題的代碼。 內存泄漏的定義 一般我們常說的內存泄漏是指堆內存的泄漏。堆內存是指程序從堆中分配的，大小任意的（內存塊的大小可以在程序運行期決定），使用完后必須顯示釋放的內 存。應用程序一般使用malloc，realloc，new等函數從堆中分配到一塊內存，使用完后，程序必須負責相應的調用free或delete釋放該 內存塊，否則，這塊內存就不能被再次使用，我們就說這塊內存泄漏了。以下這段小程序演示了堆內存發生泄漏的情形：void MyFunction(int nSize)
{
char* p= new char[nSize];
if( !GetStringFrom( p, nSize ) ){
MessageBox(“Error”);
return;
}
…//using the string pointed by p;
delete p;
} |
例一 當函數GetStringFrom()返回零的時候，指針p指向的內存就不會被釋放。這是一種常見的發生內存泄漏的情形。程序在入口處分配內存，在出口處釋放內存，但是c函數可以在任何地方退出，所以一旦有某個出口處沒有釋放應該釋放的內存，就會發生內存泄漏。 廣義的說，內存泄漏不僅僅包含堆內存的泄漏，還包含系統資源的泄漏(resource leak)，比如核心態HANDLE，GDI Object，SOCKET， Interface等，從根本上說這些由操作系統分配的對象也消耗內存，如果這些對象發生泄漏最終也會導致內存的泄漏。而且，某些對象消耗的是核心態內 存，這些對象嚴重泄漏時會導致整個操作系統不穩定。所以相比之下，系統資源的泄漏比堆內存的泄漏更為嚴重。 GDI Object的泄漏是一種常見的資源泄漏：void CMyView::OnPaint( CDC* pDC )
{
CBitmap bmp;
CBitmap* pOldBmp;
bmp.LoadBitmap(IDB_MYBMP);
pOldBmp = pDC->SelectObject( &bmp );
…
if( Something() ){
return;
}
pDC->SelectObject( pOldBmp );
return;
} |
例二 當函數Something()返回非零的時候，程序在退出前沒有把pOldBmp選回pDC中，這會導致pOldBmp指向的HBITMAP對象發生泄 漏。這個程序如果長時間的運行，可能會導致整個系統花屏。這種問題在Win9x下比較容易暴露出來，因為Win9x的GDI堆比Win2k或NT的要小很 多。 內存泄漏的發生方式： 以發生的方式來分類，內存泄漏可以分為4類： 1. 常發性內存泄漏。發生內存泄漏的代碼會被多次執行到，每次被執行的時候都會導致一塊內存泄漏。比如例二，如果Something()函數一直返回True，那么pOldBmp指向的HBITMAP對象總是發生泄漏。 2. 偶發性內存泄漏。發生內存泄漏的代碼只有在某些特定環境或操作過程下才會發生。比如例二，如果Something()函數只有在特定環境下才返回 True，那么pOldBmp指向的HBITMAP對象并不總是發生泄漏。常發性和偶發性是相對的。對于特定的環境，偶發性的也許就變成了常發性的。所以 測試環境和測試方法對檢測內存泄漏至關重要。 3. 一次性內存泄漏。發生內存泄漏的代碼只會被執行一次，或者由于算法上的缺陷，導致總會有一塊僅且一塊內存發生泄漏。比如，在類的構造函數中分配內存，在析 構函數中卻沒有釋放該內存，但是因為這個類是一個Singleton，所以內存泄漏只會發生一次。另一個例子：char* g_lpszFileName = NULL;
void SetFileName( const char* lpcszFileName )
{
if( g_lpszFileName ){
free( g_lpszFileName );
}
g_lpszFileName = strdup( lpcszFileName );
} |
例三 如果程序在結束的時候沒有釋放g_lpszFileName指向的字符串，那么，即使多次調用SetFileName()，總會有一塊內存，而且僅有一塊內存發生泄漏。 4. 隱式內存泄漏。程序在運行過程中不停的分配內存，但是直到結束的時候才釋放內存。嚴格的說這里并沒有發生內存泄漏，因為最終程序釋放了所有申請的內存。但 是對于一個服務器程序，需要運行幾天，幾周甚至幾個月，不及時釋放內存也可能導致最終耗盡系統的所有內存。所以，我們稱這類內存泄漏為隱式內存泄漏。舉一 個例子： class Connection
{
public:
Connection( SOCKET s);
~Connection();
…
private:
SOCKET _socket;
…
};
class ConnectionManager
{
public:
ConnectionManager(){}
~ConnectionManager(){
list::iterator it;
for( it = _connlist.begin(); it != _connlist.end(); ++it ){
delete （*it）;
}
_connlist.clear();
}
void OnClientConnected( SOCKET s ){
Connection* p = new Connection(s);
_connlist.push_back(p);
}
void OnClientDisconnected( Connection* pconn ){
_connlist.remove( pconn );
delete pconn;
}
private:
list _connlist;
}; |
例四 假設在Client從Server端斷開后，Server并沒有呼叫OnClientDisconnected()函數，那么代表那次連接的 Connection對象就不會被及時的刪除（在Server程序退出的時候，所有Connection對象會在ConnectionManager的析 構函數里被刪除）。當不斷的有連接建立、斷開時隱式內存泄漏就發生了。 從用戶使用程序的角度來看，內存泄漏本身不會產生什么危害，作 為一般的用戶，根本感覺不到內存泄漏的存在。真正有危害的是內存泄漏的堆積，這會最終消耗盡系統所有的內存。從這個角度來說，一次性內存泄漏并沒有什么危 害，因為它不會堆積，而隱式內存泄漏危害性則非常大，因為較之于常發性和偶發性內存泄漏它更難被檢測到。 檢測內存泄漏 檢測內存泄漏的關鍵是要能截獲住對分配內存和釋放內存的函數的調用。截獲住這兩個函數，我們就能跟蹤每一 塊內存的生命周期，比如，每當成功的分配一塊內存后，就把它的指針加入一個全局的list中；每當釋放一塊內存，再把它的指針從list中刪除。這樣，當 程序結束的時候，list中剩余的指針就是指向那些沒有被釋放的內存。這里只是簡單的描述了檢測內存泄漏的基本原理，詳細的算法可以參見Steve Maguire的<<Writing Solid Code>>。 如果要檢測堆內存的泄漏，那么需要截獲住 malloc/realloc/free和new/delete就可以了（其實new/delete最終也是用malloc/free的，所以只要截獲前 面一組即可）。對于其他的泄漏，可以采用類似的方法，截獲住相應的分配和釋放函數。比如，要檢測BSTR的泄漏，就需要截獲 SysAllocString/SysFreeString；要檢測HMENU的泄漏，就需要截獲CreateMenu/ DestroyMenu。（有的資源的分配函數有多個，釋放函數只有一個，比如，SysAllocStringLen也可以用來分配BSTR，這時就需要 截獲多個分配函數） 在Windows平臺下，檢測內存泄漏的工具常用的一般有三種，MS C-Runtime Library內建的檢測功能；外掛式的檢測工具，諸如，Purify，BoundsChecker等；利用Windows NT自帶的Performance Monitor。這三種工具各有優缺點，MS C-Runtime Library雖然功能上較之外掛式的工具要弱，但是它是免費的；Performance Monitor雖然無法標示出發生問題的代碼，但是它能檢測出隱式的內存泄漏的存在，這是其他兩類工具無能為力的地方。 以下我們詳細討論這三種檢測工具： VC下內存泄漏的檢測方法 用MFC開發的應用程序，在DEBUG版模式下編譯后，都會自動加入內存泄漏的檢測代碼。在程序結束后，如果發生了內存泄漏，在Debug窗口中會顯示出所有發生泄漏的內存塊的信息，以下兩行顯示了一塊被泄漏的內存塊的信息：E:/TestMemLeak/TestDlg.cpp(70) : {59} normal block at 0x00881710, 200 bytes long.Data: <abcdefghijklmnop> 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F 70 第一行顯示該內存塊由TestDlg.cpp文件，第70行代碼分配，地址在0x00881710，大小為200字節，{59}是指調用內存分配函數的 Request Order，關于它的詳細信息可以參見MSDN中_CrtSetBreakAlloc()的幫助。第二行顯示該內存塊前16個字節的內容，尖括號內是以 ASCII方式顯示，接著的是以16進制方式顯示。 一般大家都誤以為這些內存泄漏的檢測功能是由MFC提供的，其實不然。MFC只是 封裝和利用了MS C-Runtime Library的Debug Function。非MFC程序也可以利用MS C-Runtime Library的Debug Function加入內存泄漏的檢測功能。MS C-Runtime Library在實現malloc/free，strdup等函數時已經內建了內存泄漏的檢測功能。 注意觀察一下由MFC Application Wizard生成的項目，在每一個cpp文件的頭部都有這樣一段宏定義：#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif |
有了這樣的定義，在編譯DEBUG版時，出現在這個cpp文件中的所有new都被替換成DEBUG_NEW了。那么DEBUG_NEW是什么呢？DEBUG_NEW也是一個宏，以下摘自afx.h，1632行| #define DEBUG_NEW new(THIS_FILE, __LINE__) |
所以如果有這樣一行代碼： 經過宏替換就變成了：| char* p = new( THIS_FILE, __LINE__)char[200]; |
根據C++的標準，對于以上的new的使用方法，編譯器會去找這樣定義的operator new：| void* operator new(size_t, LPCSTR, int) |
我們在afxmem.cpp 63行找到了一個這樣的operator new 的實現void* AFX_CDECL operator new(size_t nSize, LPCSTR lpszFileName, int nLine)
{
return ::operator new(nSize, _NORMAL_BLOCK, lpszFileName, nLine);
}
void* __cdecl operator new(size_t nSize, int nType, LPCSTR lpszFileName, int nLine)
{
…
pResult = _malloc_dbg(nSize, nType, lpszFileName, nLine);
if (pResult != NULL)
return pResult;
…
} |
第二個operator new函數比較長，為了簡單期間，我只摘錄了部分。很顯然最后的內存分配還是通過_malloc_dbg函數實現的，這個函數屬于MS C-Runtime Library 的Debug Function。這個函數不但要求傳入內存的大小，另外還有文件名和行號兩個參數。文件名和行號就是用來記錄此次分配是由哪一段代碼造成的。如果這塊內 存在程序結束之前沒有被釋放，那么這些信息就會輸出到Debug窗口里。 這里順便提一下THIS_FILE，__FILE和 __LINE__。__FILE__和__LINE__都是編譯器定義的宏。當碰到__FILE__時，編譯器會把__FILE__替換成一個字符串，這 個字符串就是當前在編譯的文件的路徑名。當碰到__LINE__時，編譯器會把__LINE__替換成一個數字，這個數字就是當前這行代碼的行號。在 DEBUG_NEW的定義中沒有直接使用__FILE__，而是用了THIS_FILE，其目的是為了減小目標文件的大小。假設在某個cpp文件中有 100處使用了new，如果直接使用__FILE__，那編譯器會產生100個常量字符串，這100個字符串都是飧?/SPAN>cpp文件的路徑 名，顯然十分冗余。如果使用THIS_FILE，編譯器只會產生一個常量字符串，那100處new的調用使用的都是指向常量字符串的指針。 再次觀察一下由MFC Application Wizard生成的項目，我們會發現在cpp文件中只對new做了映射，如果你在程序中直接使用malloc函數分配內存，調用malloc的文件名和行 號是不會被記錄下來的。如果這塊內存發生了泄漏，MS C-Runtime Library仍然能檢測到，但是當輸出這塊內存塊的信息，不會包含分配它的的文件名和行號。 要在非MFC程序中打開內存泄漏的檢測功能非常容易，你只要在程序的入口處加入以下幾行代碼：int tmpFlag = _CrtSetDbgFlag( _CRTDBG_REPORT_FLAG );
tmpFlag |= _CRTDBG_LEAK_CHECK_DF;
_CrtSetDbgFlag( tmpFlag ); |
這樣，在程序結束的時候，也就是winmain，main或dllmain函數返回之后，如果還有內存塊沒有釋放，它們的信息會被打印到Debug窗口里。 如果你試著創建了一個非MFC應用程序，而且在程序的入口處加入了以上代碼，并且故意在程序中不釋放某些內存塊，你會在Debug窗口里看到以下的信息：{47} normal block at 0x00C91C90, 200 bytes long.
Data: < > 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F |
內存泄漏的確檢測到了，但是和上面MFC程序的例子相比，缺少了文件名和行號。對于一個比較大的程序，沒有這些信息，解決問題將變得十分困難。 為了能夠知道泄漏的內存塊是在哪里分配的，你需要實現類似MFC的映射功能，把new，maolloc等函數映射到_malloc_dbg函數上。這里我不再贅述，你可以參考MFC的源代碼。 由于Debug Function實現在MS C-RuntimeLibrary中，所以它只能檢測到堆內存的泄漏，而且只限于malloc，realloc或strdup等分配的內存，而那些系統資 源，比如HANDLE，GDI Object，或是不通過C-Runtime Library分配的內存，比如VARIANT，BSTR的泄漏，它是無法檢測到的，這是這種檢測法的一個重大的局限性。另外，為了能記錄內存塊是在哪里 分配的，源代碼必須相應的配合，這在調試一些老的程序非常麻煩，畢竟修改源代碼不是一件省心的事，這是這種檢測法的另一個局限性。 對 于開發一個大型的程序，MS C-Runtime Library提供的檢測功能是遠遠不夠的。接下來我們就看看外掛式的檢測工具。我用的比較多的是BoundsChecker，一則因為它的功能比較全 面，更重要的是它的穩定性。這類工具如果不穩定，反而會忙里添亂。到底是出自鼎鼎大名的NuMega，我用下來基本上沒有什么大問題。 使用BoundsChecker檢測內存泄漏： BoundsChecker采用一種被稱為 Code Injection的技術，來截獲對分配內存和釋放內存的函數的調用。簡單地說，當你的程序開始運行時，BoundsChecker的DLL被自動載入進 程的地址空間（這可以通過system-level的Hook實現），然后它會修改進程中對內存分配和釋放的函數調用，讓這些調用首先轉入它的代碼，然后 再執行原來的代碼。BoundsChecker在做這些動作的時，無須修改被調試程序的源代碼或工程配置文件，這使得使用它非常的簡便、直接。 這里我們以malloc函數為例，截獲其他的函數方法與此類似。 需要被截獲的函數可能在DLL中，也可能在程序的代碼里。比如，如果靜態連結C-Runtime Library，那么malloc函數的代碼會被連結到程序里。為了截獲住對這類函數的調用，BoundsChecker會動態修改這些函數的指令。 以下兩段匯編代碼，一段沒有BoundsChecker介入，另一段則有BoundsChecker的介入：126: _CRTIMP void * __cdecl malloc (
127: size_t nSize
128: )
129: {
00403C10 push ebp
00403C11 mov ebp,esp
130: return _nh_malloc_dbg(nSize, _newmode, _NORMAL_BLOCK, NULL, 0);
00403C13 push 0
00403C15 push 0
00403C17 push 1
00403C19 mov eax,[__newmode (0042376c)]
00403C1E push eax
00403C1F mov ecx,dword ptr [nSize]
00403C22 push ecx
00403C23 call _nh_malloc_dbg (00403c80)
00403C28 add esp,14h
131: } |
以下這一段代碼有BoundsChecker介入：126: _CRTIMP void * __cdecl malloc (
127: size_t nSize
128: )
129: {
00403C10 jmp 01F41EC8
00403C15 push 0
00403C17 push 1
00403C19 mov eax,[__newmode (0042376c)]
00403C1E push eax
00403C1F mov ecx,dword ptr [nSize]
00403C22 push ecx
00403C23 call _nh_malloc_dbg (00403c80)
00403C28 add esp,14h
131: } |
當BoundsChecker介入后，函數malloc的前三條匯編指令被替換成一條jmp指令，原來的三條指令被搬到地址01F41EC8處了。當程 序進入malloc后先jmp到01F41EC8，執行原來的三條指令，然后就是BoundsChecker的天下了。大致上它會先記錄函數的返回地址 （函數的返回地址在stack上，所以很容易修改），然后把返回地址指向屬于BoundsChecker的代碼，接著跳到malloc函數原來的指令，也 就是在00403c15的地方。當malloc函數結束的時候，由于返回地址被修改，它會返回到BoundsChecker的代碼中，此時 BoundsChecker會記錄由malloc分配的內存的指針，然后再跳轉到到原來的返回地址去。 如果內存分配/釋放函數在DLL中，BoundsChecker則采用另一種方法來截獲對這些函數的調用。BoundsChecker通過修改程序的DLL Import Table讓table中的函數地址指向自己的地址，以達到截獲的目的。 截獲住這些分配和釋放函數，BoundsChecker就能記錄被分配的內存或資源的生命周期。接下來的問題是如何與源代碼相關，也就是說當 BoundsChecker檢測到內存泄漏，它如何報告這塊內存塊是哪段代碼分配的。答案是調試信息（Debug Information）。當我們編譯一個Debug版的程序時，編譯器會把源代碼和二進制代碼之間的對應關系記錄下來，放到一個單獨的文件里 (.pdb)或者直接連結進目標程序，通過直接讀取調試信息就能得到分配某塊內存的源代碼在哪個文件，哪一行上。使用Code Injection和Debug Information，使BoundsChecker不但能記錄呼叫分配函數的源代碼的位置，而且還能記錄分配時的Call Stack，以及Call Stack上的函數的源代碼位置。這在使用像MFC這樣的類庫時非常有用，以下我用一個例子來說明：void ShowXItemMenu()
{
…
CMenu menu;
menu.CreatePopupMenu();
//add menu items.
menu.TrackPropupMenu();
…
}
void ShowYItemMenu( )
{
…
CMenu menu;
menu.CreatePopupMenu();
//add menu items.
menu.TrackPropupMenu();
menu.Detach();//this will cause HMENU leak
…
}
BOOL CMenu::CreatePopupMenu()
{
…
hMenu = CreatePopupMenu();
…
} |
當調用ShowYItemMenu()時，我們故意造成HMENU的泄漏。但是，對于BoundsChecker來說被泄漏的HMENU是在class CMenu::CreatePopupMenu()中分配的。假設的你的程序有許多地方使用了CMenu的CreatePopupMenu()函數，如 CMenu::CreatePopupMenu()造成的，你依然無法確認問題的根結到底在哪里，在ShowXItemMenu()中還是在 ShowYItemMenu()中，或者還有其它的地方也使用了CreatePopupMenu()？有了Call Stack的信息，問題就容易了。BoundsChecker會如下報告泄漏的HMENU的信息：Function
File
Line
CMenu::CreatePopupMenu
E:/8168/vc98/mfc/mfc/include/afxwin1.inl
1009
ShowYItemMenu
E:/testmemleak/mytest.cpp
100 |
這里省略了其他的函數調用 如此，我們很容易找到發生問題的函數是ShowYItemMenu()。當使用MFC之類的類庫編程時，大部分的API調用都被封裝在類庫的class里，有了Call Stack信息，我們就可以非常容易的追蹤到真正發生泄漏的代碼。 記錄Call Stack信息會使程序的運行變得非常慢，因此默認情況下BoundsChecker不會記錄Call Stack信息。可以按照以下的步驟打開記錄Call Stack信息的選項開關： 1. 打開菜單：BoundsChecker|Setting… 2. 在Error Detection頁中，在Error Detection Scheme的List中選擇Custom 3. 在Category的Combox中選擇 Pointer and leak error check 4. 鉤上Report Call Stack復選框 5. 點擊Ok 基于Code Injection，BoundsChecker還提供了API Parameter的校驗功能，memory over run等功能。這些功能對于程序的開發都非常有益。由于這些內容不屬于本文的主題，所以不在此詳述了。 盡管BoundsChecker的功能如此強大，但是面對隱式內存泄漏仍然顯得蒼白無力。所以接下來我們看看如何用Performance Monitor檢測內存泄漏。 使用Performance Monitor檢測內存泄漏 NT的內核在設計過程中已經加入了系統監視功能，比如CPU的使用率，內存的使用情況，I/O操作的頻繁度等都作為一個個Counter，應用程序可以通過讀取這些Counter了解整個系統的或者某個進程的運行狀況。Performance Monitor就是這樣一個應用程序。 為了檢測內存泄漏，我們一般可以監視Process對象的Handle Count，Virutal Bytes 和Working Set三個Counter。Handle Count記錄了進程當前打開的HANDLE的個數，監視這個Counter有助于我們發現程序是否有Handle泄漏；Virtual Bytes記錄了該進程當前在虛地址空間上使用的虛擬內存的大小，NT的內存分配采用了兩步走的方法，首先，在虛地址空間上保留一段空間，這時操作系統并 沒有分配物理內存，只是保留了一段地址。然后，再提交這段空間，這時操作系統才會分配物理內存。所以，Virtual Bytes一般總大于程序的Working Set。監視Virutal Bytes可以幫助我們發現一些系統底層的問題; Working Set記錄了操作系統為進程已提交的內存的總量，這個值和程序申請的內存總量存在密切的關系，如果程序存在內存的泄漏這個值會持續增加，但是 Virtual Bytes卻是跳躍式增加的。 監視這些Counter可以讓我們了解進程使用內存的情況，如果發生了泄漏，即使是隱 式內存泄漏，這些Counter的值也會持續增加。但是，我們知道有問題卻不知道哪里有問題，所以一般使用Performance Monitor來驗證是否有內存泄漏，而使用BoundsChecker來找到和解決。 當Performance Monitor顯示有內存泄漏，而BoundsChecker卻無法檢測到，這時有兩種可能：第一種，發生了偶發性內存泄漏。這時你要確保使用 Performance Monitor和使用BoundsChecker時，程序的運行環境和操作方法是一致的。第二種，發生了隱式的內存泄漏。這時你要重新審查程序的設計，然 后仔細研究Performance Monitor記錄的Counter的值的變化圖，分析其中的變化和程序運行邏輯的關系，找到一些可能的原因。這是一個痛苦的過程，充滿了假設、猜想、驗 證、失敗，但這也是一個積累經驗的絕好機會。 總結 內存泄漏是個大而復雜的問題，即使是Java和.Net這樣有 Gabarge Collection機制的環境，也存在著泄漏的可能，比如隱式內存泄漏。由于篇幅和能力的限制，本文只能對這個主題做一個粗淺的研究。其他的問題，比如 多模塊下的泄漏檢測，如何在程序運行時對內存使用情況進行分析等等，都是可以深入研究的題目。如果您有什么想法，建議或發現了某些錯誤，歡迎和我交流。
第十六章、全排列問題53.字符串的排列。
題目：輸入一個字符串，打印出該字符串中字符的所有排列。
例如輸入字符串abc，則輸出由字符a、b、c 所能排列出來的所有字符串
abc、acb、bac、bca、cab 和cba。 分析：此題最初整理于去年的微軟面試100題中第53題，第二次整理于微軟、Google等公司非常好的面試題及解答[第61-70題] 第67題。無獨有偶，這個問題今年又出現于今年的2011.10.09百度筆試題中。ok，接下來，咱們先好好分析這個問題。
- 一、遞歸實現
從集合中依次選出每一個元素，作為排列的第一個元素，然后對剩余的元素進行全排列，如此遞歸處理，從而得到所有元素的全排列。以對字符串abc進行全排列為例，我們可以這么做：以abc為例
固定a，求后面bc的排列：abc，acb，求好后，a和b交換，得到bac
固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba
固定c，求后面ba的排列：cba，cab。代碼可如下編寫所示：
- template <typename T>
- void CalcAllPermutation_R(T perm[], int first, int num)
- {
- if (num <= 1) {
- return;
- }
-
- for (int i = first; i < first + num; ++i) {
- swap(perm[i], perm[first]);
- CalcAllPermutation_R(perm, first + 1, num - 1);
- swap(perm[i], perm[first]);
- }
- }
或者如此編寫，亦可： - void Permutation(char* pStr, char* pBegin);
-
- void Permutation(char* pStr)
- {
- Permutation(pStr, pStr);
- }
-
- void Permutation(char* pStr, char* pBegin)
- {
- if(!pStr || !pBegin)
- return;
-
- if(*pBegin == '\0')
- {
- printf("%s\n", pStr);
- }
- else
- {
- for(char* pCh = pBegin; *pCh != '\0'; ++ pCh)
- {
-
- char temp = *pCh;
- *pCh = *pBegin;
- *pBegin = temp;
-
- Permutation(pStr, pBegin + 1);
-
- temp = *pCh;
- *pCh = *pBegin;
- *pBegin = temp;
- }
- }
- }
- 二、字典序排列
把升序的排列（當然，也可以實現為降序）作為當前排列開始，然后依次計算當前排列的下一個字典序排列。
對當前排列從后向前掃描，找到一對為升序的相鄰元素，記為i和j（i < j）。如果不存在這樣一對為升序的相鄰元素，則所有排列均已找到，算法結束；否則，重新對當前排列從后向前掃描，找到第一個大于i的元素k，交換i和k，然后對從j開始到結束的子序列反轉，則此時得到的新排列就為下一個字典序排列。這種方式實現得到的所有排列是按字典序有序的，這也是C++ STL算法next_permutation的思想。算法實現如下：
- template <typename T>
- void CalcAllPermutation(T perm[], int num)
- {
- if (num < 1)
- return;
-
- while (true) {
- int i;
- for (i = num - 2; i >= 0; --i) {
- if (perm[i] < perm[i + 1])
- break;
- }
-
- if (i < 0)
- break; // 已經找到所有排列
-
- int k;
- for (k = num - 1; k > i; --k) {
- if (perm[k] > perm[i])
- break;
- }
-
- swap(perm[i], perm[k]);
- reverse(perm + i + 1, perm + num);
-
- }
- }
【引言】在數據結構的課程上，我們學習了不少的排序算法，冒泡，堆，快排，歸并等。但是這些排序方法有著共同的特點，那就是所有的操作都是在內存中完成的，算法過程中不需要IO，這就使得這樣的算法總體上速度比較快，但是也隨之出現了一個問題：當需要排序的數據量異常的大的時候，以上的算法就顯得力不從心了。這時候，你需要一種另外的排序算法，它的名字叫“外排序”。 通常的，設備的內存讀取速度要比外存讀取速度快得多（RAM的訪問速度大約是磁盤的25萬倍），但是內存的容量卻要比外存小很多，當所有的數據不能在內存中完全放下的時候，就需要使用到外排序。這是外排序的一個顯著特征。 【什么是外排序】外排序其實是采用一種分治（Divide and conquer algorithm）的算法設計思想，將一個大問題劃分成相對獨立的若干個小問題，解決小問題，得到小問題的答案，然后合并小問題的答案，最終得到原始大問題的答案。 在這里，我們舉一個外排的典型例子，二路外部歸并排序，假設我們有一個大文件，里面是待排序的數據，一共N個，這些數據在內存中放不下。排序過程如下： - 將該大文件分割成大小為m的文件（m小于可用內存大小）
- 將這些小文件依次讀入內存，在內存中采用任一種排序算法排序并輸出文件F1，F2….Fn。（其實可以和第一步合并，可以省一次IO）
- 分塊快讀取兩個已經排完序的文件Fi和Fi+1，由于兩個文件已經排完序，這里可以用歸并排序，將兩個文件排序完畢，并寫入文件。（這個過程就好比有兩隊人馬將其合并為一對一樣）
- 重復過程3，直到剩余文件數為1。
以上就是二路外部歸并排序的基本思路，毫無疑問，這種排序算法需要讀取外存（IO）次數為log(2,N/m)，這時候算法的性能瓶頸已經不在內存中排序的時間復雜度上，而是內外村交換數據IO的次數了。這里我補充一句，各種操作的性能差別： 讀取網絡 > 磁盤文件IO > 讀取數據庫 > 內存讀取 這個可謂是程序性能的黃金法則，各位在寫對性能要求比較高的程序時一定要考慮。 好，言歸正傳，二路歸并排序這個算法的性能時比較低的。因此就有了多路歸并排序算法，其IO的次數為log(b, N/m)，其中b為幾路歸并。這個可以參考以下地址： http://zh.wikipedia.org/wiki/%E5%A4%96%E6%8E%92%E5%BA%8F 【實戰訓練】淘寶不同用戶的瀏覽log有上千萬or億數據（有重復），統計其中有相同瀏覽愛好的用戶。 轉載請注明出處：http://diducoder.com/mass-data-topic-9-external-sort.html
引言：在信息大爆炸的今天，有了搜索引擎的幫助，使得我們能夠快速，便捷的找到所求。提到搜索引擎，就不得不說VSM模型，說到VSM，就不得不聊倒排索引。可以毫不夸張的講，倒排索引是搜索引擎的基石。 VSM檢索模型VSM全稱是Vector Space Model(向量空間模型)，是IR(Information Retrieval信息檢索)模型中的一種，由于其簡單，直觀，高效，所以被廣泛的應用到搜索引擎的架構中。98年的Google就是憑借這樣的一個模型，開始了它的瘋狂擴張之路。廢話不多說，讓我們來看看到底VSM是一個什么東東。 在開始之前，我默認大家對線性代數里面的向量(Vector)有一定了解的。向量是既有大小又有方向的量，通常用有向線段表示，向量有：加、減、倍數、內積、距離、模、夾角的運算。 文檔(Document)：一個完整的信息單元，對應的搜索引擎系統里，就是指一個個的網頁。 標引項(Term)：文檔的基本構成單位，例如在英文中可以看做是一個單詞，在中文中可以看作一個詞語。 查詢(Query)：一個用戶的輸入，一般由多個Term構成。 那么用一句話概況搜索引擎所做的事情就是：對于用戶輸入的Query，找到最相似的Document返回給用戶。而這正是IR模型所解決的問題： 信息檢索模型是指如何對查詢和文檔進行表示，然后對它們進行相似度計算的框架和方法。
舉個簡單的例子： 現在有兩篇文章(Document)分別是 “春風來了，春天的腳步近了” 和 “春風不度玉門關”。然后輸入的Query是“春風”，從直觀上感覺，前者和輸入的查詢更相關一些，因為它包含有2個春，但這只是我們的直觀感覺，如何量化呢，要知道計算機是門嚴謹的學科^_^。這個時候，我們前面講的Term和VSM模型就派上用場了。 首先我們要確定向量的維數，這時候就需要一個字典庫，字典庫的大小，即是向量的維數。在該例中，字典為{春風,來了,春天, 的,腳步,近了,不度,玉門關} ，文檔向量，查詢向量如下圖：  VSM模型示例 PS:為了簡單起見，這里分詞的粒度很大。 將Query和Document都量化為向量以后，那么就可以計算用戶的查詢和哪個文檔相似性更大了。簡單的計算結果是D1和D2同Query的內積都是1，囧。當然了，如果分詞粒度再細一些，查詢的結果就是另外一個樣子了，因此分詞的粒度也是會對查詢結果（主要是召回率和準確率）造成影響的。 上述的例子是用一個很簡單的例子來說明VSM模型的，計算文檔相似度的時候也是采用最原始的內積的方法，并且只考慮了詞頻(TF)影響因子，而沒有考慮反詞頻(IDF)，而現在比較常用的是cos夾角法，影響因子也非常多，據傳Google的影響因子有100+之多。
大名鼎鼎的Lucene項目就是采用VSM模型構建的，VSM的核心公式如下（由cos夾角法演變，此處省去推導過程）  VSM模型公式 從上面的例子不難看出，如果向量的維度(對漢語來將，這個值一般在30w-45w)變大，而且文檔數量(通常都是海量的)變多，那么計算一次相關性，開銷是非常大的，如何解決這個問題呢？不要忘記了，我們這節的主題就是 倒排索引，主角終于粉墨登場了！！！ 倒排索引倒排索引非常類似我們前面提到的Hash結構。以下內容來自維基百科： 倒排索引（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。 有兩種不同的反向索引形式： - 一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。
- 一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
后者的形式提供了更多的兼容性（比如短語搜索），但是需要更多的時間和空間來創建。
由上面的定義可以知道，一個倒排索引包含一個字典的索引和所有詞的列表。其中字典索引中包含了所有的Term(通俗理解為文檔中的詞)，索引后面跟的列表則保存該詞的信息(出現的文檔號，甚至包含在每個文檔中的位置信息)。下面我們還采用上面的方法舉一個簡單的例子來說明倒排索引。 例如現在我們要對三篇文檔建立索引(實際應用中，文檔的數量是海量的)： 文檔1(D1)：中國移動互聯網發展迅速 文檔2(D2)：移動互聯網未來的潛力巨大 文檔3(D3)：中華民族是個勤勞的民族 那么文檔中的詞典集合為：{中國，移動，互聯網，發展，迅速，未來，的，潛力，巨大，中華，民族，是，個，勤勞} 建好的索引如下圖：  倒排索引 在上面的索引中，存儲了兩個信息，文檔號和出現的次數。建立好索引以后，我們就可以開始查詢了。例如現在有一個Query是”中國移動”。首先分詞得到Term集合{中國，移動}，查倒排索引，分別計算query和d1,d2,d3的距離。有沒有發現，倒排表建立好以后，就不需要在檢索整個文檔庫，而是直接從字典集合中找到“中國”和“移動”，然后遍歷后面的列表直接計算。 對倒排索引結構我們已經有了初步的了解，但在實際應用中還有些需要解決的問題(主要是由海量數據引起的)。筆者列舉一些問題，并給出相應的解決方案，拋磚以引玉，希望大家可以展開討論： 1.左側的索引表如何建立?怎么做才能最高效？ 可能有人不假思索回答：左側的索引當然要采取hash結構啊，這樣可以快速的定位到字典項。但是這樣問題又來了，hash函數如何選取呢？而且hash是有碰撞的，但是倒排表似乎又是不允許碰撞的存在的。事實上，雖然倒排表和hash異常的相思，但是兩者還是有很大區別的，其實在這里我們可以采用前面提到的Bitmap的思想，每個Term(單詞)對應一個位置(當然了，這里不是一個比特位)，而且是一一對應的。如何能夠做到呢，一般在文字處理中，有很多的編碼，漢字中的GBK編碼基本上就可以包含所有用到的漢字，每個漢字的GBK編碼是確定的，因此一個Term的”ID”也就確定了，從而可以做到快速定位。注：得到一個漢字的GBK號是非常快的過程，可以理解為O(1)的時間復雜度。
2.如何快速的添加刪除更新索引？ 有經驗的碼農都知道，一般在系統的“做加法”的代價比“做減法”的代價要低很多，在搜索引擎中中也不例外。因此，在倒排表中，遇到要刪除一個文檔，其實不是真正的刪除，而是將其標記刪除。這樣一個減法操作的代價就比較小了。
3.那么多的海量文檔，如果存儲呢？有么有什么備份策略呢？ 當然了，一臺機器是存儲不下的，分布式存儲是采取的。一般的備份保存3份就足夠了。
好了，倒排索引終于完工了，不足的地方請指正。謝謝 做人要厚道，轉載請注明出處：http://diducoder.com/mass-data-topic-8-inverted-index.html
|