Latest Entries »
http://dantvt.is-programmer.com/posts/11949.html
很多时候较大数据量的文件 IO 总是成为瓶颈，为了提高效率，有时想要先将文件大块大块的读入再行处理。下面分析两种惯常的处理手法。
1. 将文件一次性读入 string 中。
貌似 std::getline 、 istream::getline 或是 operator<< operator>> 等都不提供一次读到文件结尾的机制，只有 istreambuf_iterator 可以做到：
string instr((istreambuf_iterator<char>(in)), istreambuf_iterator<char>());
string 的构造函数前一个参数要多加一层 () 以免编译器误认为是函数声明 = = …
这样读入 string 会随着内容动态增长，空间不足时会触发额外的 realloc 及 copy 操作，为提高效率有必要预分配足够的空间：
in.seekg(0, ios::end);
streampos len = in.tellg();
in.seekg(0, ios::beg);
string instr;
instr.reserve(len);
instr.assign(istreambuf_iterator<char>(in), istreambuf_iterator<char>());
2. 将文件一次性读入 stringstream 中。
filebuf 和 stringbuf 无法直接通过 rdbuf() 重定向，因此从 filebuf 到 stringbuf 需要一次 copy 操作。最简单的方法是直接复制整个 streambuf ：
stringstream ss;
ss<<in.rdbuf();
与 string 的情况相同，这里同样也有一个空间 realloc 及 copy 的问题。但 streambuf 的缓冲区不是那么方便操作的，解决方法是我们给他手动指定一个空间：
in.seekg(0, ios::end);
streampos len = in.tellg();
in.seekg(0, ios::beg);
vector<char> buffer(len);
in.read(&buffer[0], len);
stringstream ss;
ss.rdbuf()->pubsetbuf(&buffer[0], len);
最后再顺便 BS 一下 VC 的 STL = =…
虽然 VC 的编译器效率没的说，但被 STL 拖后腿的话不就白搭了嘛。在文件 IO 方面 (fstream) 比起 MinGW (GCC 4.4.0) 带的要慢好几倍。GCC 的 fstream 格式化读写效率与 C 的比已经不分伯仲，以后应该还会有进一步的提升空间 (编译时格式控制 vs 执行时)
另外上面最后一段程序在 VS2008 (VC9.0) 下应该无法得到预想的结果，跟踪进去看了一下，VC 标准库里的 pubsetbuf 函数体居然是空的！内容如下(中间还有一层函数调用)：
{ // offer buffer to external agent (do nothing)
return (this);
}
看来是等着我们来继承了啊 = = 。而在 MinGW (GCC 4.4.0) 中可以得到预期的结果。
(2) configure –with-boost=/lib/boost_1_36_0
# 设置 boost 路径时中间不要有空格，不然后面会很难办
(3) cd build/lib
(4) mingw32-make -f gcc.mak all
# 要用 mingw 带的那个 make，不要用 MSYS 的那个
# 编译好后把 .a 和 .dll 文件分别复制到 stlport/lib 和 stlport/bin
# all 选项默认 build 所有动态库，要编译静态库须如下步指定：
(5) mingw32-make -f gcc.mak release-static dbg-static stldbg-static
# 编译三种静态库。同样把 .a 文件复制到 stlport/lib
(6) 设置 MinGW 的 include:
这个貌似只能在编译时指定参数 -I 和 -L
(7) 使用时的参数
–动态链接：
g++ xxx.cpp -mthreads -I /lib/STLport5.2.1/stlport -L /lib/STLport5.2.1/lib/mingw -lstlport.5.2
–静态链接：
在源文件开头添加：#define _STLP_USE_STATIC_LIB
g++ xxx.cpp -mthreads -I /lib/STLport5.2.1/stlport -L /lib/STLport5.2.1/lib/mingw -lstlport
# 与动态链接版相比最后的库名不带版本号
# 要链接 debug 版只需把最后的库名改为相应名称即可，如 -lstlportg
http://dantvt.is-programmer.com/posts/8313 两边同步吧…
很奇怪的，或者说是一个不应成为问题的问题…
std::list 的 size() 方法时间复杂度是多少？第一感觉应该是 O(1) 没错吧，多一个变量用于储存链表长度应该是很轻易的事情。于是有了下面这段代码：
#include<list>
#include<ctime>
using namespace std;
int main(){
time_t start, finish;
int num = 0;
list<int> coll;
start = clock();
for(int i=0;i<10000;++i){
coll.push_back(i);
num += coll.size();
}
finish = clock();
cout<<finish – start<<" num:"<<num<<endl;
coll.clear();
start = clock();
for(int i=0;i<10000;++i){
coll.push_back(i);
}
finish = clock();
cout<<finish – start<<endl;
return 0;
}
对两个循环分别计时比较。前一个循环只比后一个多了一句 num += coll.size(); 为了使编译器确实生成 list::size() 的代码。
在 MinGW 5.1.4 中 (GCC 3.4.5) 编译结果运行如下：
10
可以看到，前一个循环居然比后一个多花了几乎 45 倍的时间…当我把循环次数从 10000 加到 100000 时程序半天没出结果…
由此有理由猜测 std::list 的 size() 方法难道是 O(N) 的？果然，在头文件中发现了这一段：
size() const
{ return std::distance(begin(), end()); }
直接调用 <algorithm> 算法库函数 distance() 计算元素个数……怪不得这么慢。然后又用 VS2008 (VC9.0)编译，结果如下：
60
奇怪的是前一个循环居然比后一个还快…不过至少知道 VS2008 (VC9.0)里的 size() 应该是 O(1) 的。同样查看了一下代码，如下：
{ // return length of sequence
return (_Mysize);
}
_Mysize 是一个 size_type 类型的变量。疑问解决。不过又有了新问题：
————— 咱 – 是 – 分 – 隔 – 线 ——————
为什么 GCC 里要把 list::size() 的复杂度搞成 O(N)？
一通搜索后终于看到有这样的讨论：关于 list::splice() 函数。
list 是链表结构，它的优势就在于可以 O(1) 的时间复杂度任意插入删除甚至拼接 list 片段(删除时可能不是，因为要释放内存)，list::splice() 是一个很强大的功能，它可在任意位置拼接两个 list，这正是 list 的优势。如果我们在类内部以一个变量储存 list 的长度，那么 splice() 之后新 list 的长度该如何确定？这是一个很严峻的问题，如果要在拼接操作时计算拼接部分的长度，那么将把 O(1) 的时间变成 O(N)，这么一来 list 相对 vector 的优势就消失殆尽。
面对这个问题，GCC 和 VC 的 STL 库作者们做了不同的选择。GCC 选择舍弃在 list 内部保存元素数量，而在 size() 时直接从头数到尾，这便出现了开头看到的 O(N) 时间才算出 size()；相反，VC 中有了变量 _Mysize ，无论在 insert() erase() splice() 或是 push() pop() 时都需要对其做相应修改。在上面的两个试验中已经看出同样是 10000 个 push_back() 操作，VC 花的时间比较长，不过也仅仅是一个 inc 指令，差别很小就是了。上面几种会改变 list 内容的操作中，大部分对元素数量的影响只是 +1 或 -1，只有 splice() 需要计算拼接部分元素个数，这个差别就大了，咱还是继续用实验证明吧：
#include<list>
#include<ctime>
using namespace std;
int main(){
time_t start,finish;
list<int> col;
col.push_back(1);
col.push_back(10000);
list<int> col2;
start = clock();
for(int i=2;i<10000;++i)
col2.push_back(i);
finish = clock();
cout<<finish – start<<endl;
int num = 0;
start = clock();
for(int i=0;i<10000;++i){
col.splice(++col.begin(),col2,++col2.begin(),–col2.end());
num += *(++col.begin());
col2.splice(++col2.begin(),col,++col.begin(),–col.end());
num += *(++col2.begin());
}
finish = clock();
cout<<finish – start<<" num:"<<num<<endl;
return 0;
}
首先是 MinGW (GCC 3.4.5) 的结果：
0 num:60000
可以看到 10000 次 push 是 10，相对的 20000 次 splice() 几乎没花时间 = =
然后是 VS2008 (VC9.0)：
2714 num:60000
差别非常明显，花了2秒多才完成。当我把循环次数改成 100000 后 GCC 仍是眨眼间的事，VC 却长时间运行无结果……
怎么说呢，GCC 显然是追求效率至上，尽量体现出 list 的优势所在，不过我觉得这么一来倒不如干脆不提供 list 的 size() 方法，有需求的程序员可以自己维护一个变量记录长度，以免误认为 size() 是 O(1) 的而犯下严重错误。相对的 VC 强调功能性和整体效率，可能在实际中需要对链表一段内容做 splice() 操作的机会远远小于求 size() 的操作，所以舍弃前者而保留后者，不过要维护 _Mysize 其他相关函数中也增加了开销。一个见仁见智的问题，我觉得还是 GCC 的选择比较好，list 的优势应该保留，但能在 size() 函数处给个 warning 什么的就好了。
我想还有一个选择是这样：在 list 内部用一个 bool 变量指示当前内部 size 值是有效还是无效。在通常操作时 bool 保持 true，这样在 size() 时直接返回原值即可；在 splice() 后将此 bool 值置为 false 并不计算长度，直到最后又有需要 size() 时发现 bool 是 false 则从头再来一遍 distance() 并再将 bool 置为 true。暂时只想出这么一个算是折中的方法，基本上都能保持两边 O(1) 的效率，但相应其他各关于元素数量的函数内部都要多一个判断当前 size 值是有效还是无效并选择是否改变其值。反正总是不能非常完美
嘛…本来只是发现 size() 的效率问题，没想到却扯出这么一桩事出来…也算长知识了吧
