几点说明：
1 作者不懂Python，本文也不讨论它。之所以用这个题目，缘于一篇旧文一个Python程序引发的讨论。如果不了解来龙去脉，还请预先读之，前篇已有的内容，本篇不会再重复。
2 本文主要讨论一些C++的优化技巧，提高程序效率是主要目的。本文仅讨论优化要点，不会详细分析所有代码。
3 部分通用算法可以在很多开源里找到，因此本文不含通用代码，也无法编译。通用算法可以有以下参考：二叉树，参考stlport的rb_tree；快速内存非配，参考本文前篇。
第一部分 算法简介
1 用文件映射读取数据。实际上使用小缓存方式读入数据，效率也不差。不过文件映射代码简单，就先用着了。
2 使用二叉树进行字符串唯一性判断。在前篇中，最后作者使用hash算法结合二叉树来进行字符串唯一性判定。这一次优化了二叉树算法，hash就不必要了。
3 使用小缓存分批写入数据。
第二部分 二叉树优化
标准库里的rb_tree(map/set)实在太好用了，好得让人忘记了它的底层机制。其实，我们完全可以实现一个类型无关的封装，只包含一些最基本的操作，如：插入节点，删除节点等。推荐研读一下stlport的代码，那里面就有最经典的底层操作封装。
最简单的multimap插入节点算法，应该是下面这个样子：
rb_node* y = &m_node;
rb_node* x = m_node.m_parent;
bool comp = true;
while (x != 0)
{
y = x;
comp = compare(v, x);
x = comp ? x->m_left : x->m_right;
}
do_insert(y, v, comp);
那个do_insert就可以实现成类型无关的通用算法。我们的优化主要是针对do_insert之前那个小循环。注意，multimap算法不能直接用，实际上，我们需要的是map算法，这个容器不能有重复元素。
优化步骤1：比较子返回值
标准库的容器都要求提供一个比较子，返回true或者false。不过字符串的比较还是返回三个结果比较划算，因此算法可以修改成
int comp = -1;
while (x != 0)
{
y = x;
comp = compare_str(v, x);
if(comp == 0) return false;
x = comp < 0 ? x->m_left : x->m_right;
}
这个算法在小循环里判断了是否相等，这样就可以把multimap的插入算法转变成了map的插入算法。multimap和map的插入算法有何区别，还是推荐看stlport。这样的做法一来可以在找到元素后直接返回，二来可以免去循环结束时的节点递减和再度比较等操作。
优化步骤2：按长度分组
内存比较总是要先进行一次长度比较，这不划算。别小看这个长度比较，在这个大循环里，还是有些消耗的。而且给每个字符串保留一个长度也浪费内存的。写前篇的时候也用过strcmp，不过后来感觉还是memcmp快一些。
按照字符串长度分组，每种长度的字符串插入到指定的map里。比较时就可以不管长度了。
实际上，步骤1和步骤2是相辅相成的，单独进行任何一步都意义不大。进行了这两部优化以后，效率基本上与前篇的hash算法相当了。
优化步骤3：数据改为整数
既然变成简单的数据比较了，那么是不是字符串就无所谓了。因此可以把字符串修改成整数数据。这个改动能使整体效率提高30%。
第三部分 效果讨论
写前篇的时候，CPU是AMD2600+。现在的电脑，CPU是赛扬3.06G。
运行前篇的那个hash算法实现，最短时间为546ms。
执行现在的这个算法，最短时间为391ms。
还实现了一个多线程版的，在双核（Core2Duo7500）笔记本上试验了一下，最短时间是220ms。笔记本上单线程执行时间为280ms。多线程带来的好处不是很明显，可能是因为IO的瓶颈。由于效果一般，就不提供多线程版的代码了。
第四部分 代码
这个代码不包含通用算法，如果都贴出来，太多了。因此不要尝试编译它，就是读个思路。
struct rb_item : rb_node
{
uint_t m_data[1];
};
struct rb_item_s : rb_node
{
size_t m_size;
uint_t m_data[1];
};
struct string_mgr
{
alg::grow_heap* m_heap;
rb_data m_rb_data[rb_count];
string_mgr(alg::grow_heap* heap);
bool insert(uint_t* p, size_t c);
bool insert(const char* p, size_t c);
};
string_mgr::string_mgr(alg::grow_heap* heap)
{
m_heap = heap;
for(size_t i = 0; i < rb_count; ++ i)
{
m_rb_data[i].fn_reset();
}
}
bool string_mgr::insert(uint_t* v, size_t c)
{
if(c < rb_count)
{
if(c == 0) return false;
rb_data* rb = m_rb_data+c;
rb_node* y = &rb->m_node;
rb_node* x = y->m_parent;
int comp = -1;
while(x)
{
y = x;
uint_t* d = static_cast<rb_item*>(x)->m_data;
size_t i = 0;
while(v[i] == d[i])
{
if(++i == c) return false;
}
if(v[i] < d[i])
{
comp = -1;
x = x->m_left;
}
else
{
comp = 1;
x = x->m_right;
}
}
// allocate item
rb_item* z = (rb_item*)m_heap->allocate(sizeof(rb_item)+sizeof(uint_t)*(c-1));
memcpy(z->m_data, v, sizeof(uint_t)*c);
// insert to rb_tree
rb->fn_insert(y, z, comp < 0);
return true;
}
rb_data* rb = m_rb_data;
rb_node* y = &rb->m_node;
rb_node* x = y->m_parent;
int comp = -1;
while(x)
{
y = x;
size_t xc = static_cast<rb_item_s*>(x)->m_size;
if(xc == c)
{
comp = memcmp(v, static_cast<rb_item_s*>(x)->m_data, sizeof(uint_t)*c);
if(comp == 0)
{
return false;
}
}
else
{
comp = c < xc ? -1 : 1;
}
x = comp < 0 ? x->m_left : x->m_right;
}
// allocate item
rb_item_s* z = (rb_item_s*)m_heap->allocate(sizeof(rb_item_s)+sizeof(uint_t)*(c-1));
memcpy(z->m_data, v, sizeof(uint_t)*c);
z->m_size = c;
// insert to rb_tree
rb->fn_insert(y, z, comp < 0);
return true;
}
bool string_mgr::insert(const char* v, size_t c)
{
if(c <= rb_count*sizeof(uint_t))
{
if(c == 0) return false;
uint_t s[rb_count];
size_t i = (c+3) >> 2;
s[i-1] = 0;
memcpy(s, v, c);
return insert(s, i);
}
else
{
size_t i = (c+3) >> 2;
uint_t* s = new uint_t[i];
s[i-1] = 0;
memcpy(s, v, c);
bool r = insert(s, i);
delete [] s;
return r;
}
}
// line_reader
struct line_reader
{
io::fmapping m_file;
const char* m_pos;
const char* m_end;
const char* m_data;
size_t m_size;
size_t m_hash;
line_reader(const wstring& path);
void set(const char* p);
bool get();
};
line_reader::line_reader(const wstring& path)
{
m_pos = 0;
m_end = 0;
m_data = 0;
m_size = 0;
m_file.create(path.c_str());
m_pos = (char*)m_file.m_data;
m_end = m_pos+m_file.m_size;
}
void line_reader::set(const char* p)
{
m_data = m_pos;
m_size = p-m_pos;
}
bool line_reader::get()
{
const char* p = m_pos;
for(; p < m_end; ++ p)
{
switch(*p)
{
case '/r':
set(p);
++ p;
if(p < m_end && *p == '/n')
{
++ p;
}
m_pos = p;
return true;
case '/n':
set(p);
++ p;
m_pos = p;
return true;
}
}
if(m_pos == p) return false;
set(p);
m_pos = p;
return true;
}
// line_writer
struct line_writer
{
io::fstream m_stream;
char* m_pos;
char* m_end;
char* m_data;
size_t m_size;
line_writer(const wstring& path);
~line_writer();
void add(const char* p, size_t c);
void flush();
void allocate();
};
line_writer::line_writer(const wstring& path)
{
m_pos = 0;
m_end = 0;
m_data = 0;
m_size = 0;
m_stream.open(path, io::access_t::write, io::share_t::read, io::open_t::create);
}
line_writer::~line_writer()
{
flush();
if(m_data)
{
::free(m_data);
}
}
void line_writer::add(const char* p, size_t c)
{
for(;;)
{
size_t r = m_end-m_pos;
if(r >= c+2)
{
::memcpy(m_pos, p, c);
m_pos += c;
*m_pos++ = '/r';
*m_pos++ = '/n';
return;
}
switch(c+2-r)
{
case 1:
::memcpy(m_pos, p, c);
m_pos += c;
*m_pos++ = '/r';
flush();
*m_pos++ = '/n';
return;
case 2:
::memcpy(m_pos, p, c);
m_pos += c;
flush();
*m_pos++ = '/r';
*m_pos++ = '/n';
return;
default:
::memcpy(m_pos, p, r);
m_pos += r;
flush();
p += r;
c -= r;
break;
}
}
}
void line_writer::flush()
{
if(m_data && m_data < m_pos)
{
size_t w;
m_stream.write(m_data, m_pos-m_data, w);
}
allocate();
m_pos = m_data;
m_end = m_data+m_size;
}
void line_writer::allocate()
{
if(m_data) return;
m_size = 32*1024;
m_data = (char*)::malloc(m_size);
}
void main()
{
wstring data_dir = io::fsys::extract_dir(io::fsys::app_dir())+L"//data//";
wstring path_in = data_dir+L"email.txt";
wstring path_out = data_dir+L"email_new.txt";
for(int i = 0; i < 10; ++ i)
{
clock_t tm = clock();
{
line_reader reader(path_in);
line_writer writer(path_out);
alg::grow_heap heap;
heap.m_page_size = 64000;
string_mgr mgr(&heap);
while(reader.get())
{
if(mgr.insert(reader.m_data, reader.m_size))
{
writer.add(reader.m_data, reader.m_size);
}
}
}
tm = clock()-tm;
printf("time : %.2f (ms)/n", float(tm)*1000.0f/(float)CLOCKS_PER_SEC);
}
wprintf(L"press any key to continue.");
getchar();
}