|
|
与在前面:++(--)有太多让人困惑的地方,(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
|