又一次吃了浮点数的亏 = =

while(step > 0.02){
    for(;;){
        if(x+step <= 100.0 &&
            (ttlen = ttl(x+step, y)) < minlength){
            minlength = ttlen;
            x += step;
        } else if(x-step >=0.0 &&
            (ttlen = ttl(x-step, y)) < minlength){
            minlength = ttlen;
            x -= step;
        } else if(y+step <= 100.0 &&
            (ttlen = ttl(x, y+step)) < minlength){
            minlength = ttlen;
            y += step;
        } else if(y-step >= 0.0 &&
            (ttlen = ttl(x, y-step)) < minlength){
            minlength = ttlen;
            y -= step;
        } else break;
    }
    step /= 2.0;
}
在 x-y 平面上寻找一个对 ttl 函数的极值点。先用 step 为步长寻找，然后步长减半再找，直到满足一定精度为止。
逻辑上过程上都很简单才对，可惜以上代码在 VC2008 运行正确，用 Gcc 却陷入死循环。
 
调试下发现居然出现了这种情况：在 A 点时发现 B 比 A 小，然后在 B点 发现 C 比 B 小，而在 C点 又发现 A 更小……于是就在这几个点上跳不出来了。
其实以前也看过不少强调处理浮点数比较时要特别注意的地方，但每个地方都特别写一下又很麻烦，而且觉得 double 的精度够高应该不用担心，没想到还是出了问题。VC 里大概对浮点数的比较运算做了特殊处理才没出错，感觉在这种很细节的地方 VC 非常强调安全性，但可能有时候也会觉得多此一举或是担心性能上的影响吧。
总之发现问题所在就好解决了，(ttlen = ttl(x, y+step)) < minlength 改为 (ttlen = ttl(x, y+step)) < minlength - 1e-4 即可。
今后再处理浮点数的问题时一定要相当小心咯

C/C++ VC gcc double Comments(0) 2009年11月12日 04:41

File I/O 效率 C vs C++ (一)

继续关注文件读写...这次测试写的效率

其实关于这个问题的讨论似乎总会以类似语言信仰问题而告终，再加 C++ IO 库的复杂性，很多半调子 C++ 程序员总会出现各种误用，反过来却作为攻击 C++ IO 效率低的凭证。
比如经常有人边在输出时大量使用类似
    fout<<...<<endl;
的语句边嚷嚷着写文件速度超慢的，只能说这些人根本不知道自己写的句子都做了什么...
 
所以说在评价任何东西之前先要做到最起码的了解
咱也算是大致研究过 C++ IO stream 各方面的内容，虽然不能说完全掌握仍在学习中，但自认为还是可以写点东西的。
 
总之还是用数据说话。
平台 XPsp3 + VC2008 Express Edition SP1 + STLport / MinGW(GCC4.4.0)
 
实验内容：
共做了三种类型写入的比较，每种类型采用几种不同方法实现：
1. 纯字节流写入
     (1) C fputs()
     (2) C fprintf()
     (3) C++ ofstream<<
     (4) C++ ofstream.rdbuf()->sputn()
2. 宽字符流通过转码写入
     (1) C++ locale + wofstream<<
     (2) C++ codecvt<> facet + ofstream.rdbuf()->sputn()
     (3) WinAPI WideCharToMultiByte() + ofstream<<
3. 格式化写入 (一个 int 一个 double + 一个字符串)
     (1) C fprintf()
     (2) C++ ofstream<<
     (3) C++ ostream.rdbuf()->sputn() sputc() + num_put<> facet
 
前两类比较时写入的内容是完全一致的，也可以横向做下参照。
 
结果：(由于和硬盘寻道时间等也有关系，尽量多次测试取受影响最小的值)
以 C Runtime library 的 fputs 函数所用时间为 1.0 做基准

VC2008EE + VC STL:
text out C fputs()                      1.0
text out C fprintf()                    2.0
text out C++ ofstream <<                1.2
text out C++ ofstream rdbuf()->sputn()  0.8
wText out C++ wofstream deflocale      25.0
wText out C++ locale codecvt            7.5
wText out C++ ofstream + WinAPI         1.5
Format data out C fprintf()             2.0
Format data out C++ ofstream  <<        4.0
Format data out C++ ofs num_put facet   3.0
 
首先用 VC 自带的标准库，可以看到直接用 C++ fstream 的 << 效率与 C 库函数相比还是略低一些，但差距并没有到不可忍受的地步，考虑到 C++ IO stream 的各种特性，这些还是可以接受的。
而直接调用下层 rdbuf()->sputn() 函数却比 fputs() 效率更高，让我对 C++ IO 库的进一步优化仍有希望。
在 Unicode 大行其道的今天，宽字符的读写已成为必需，但使用 locale 配合 wstream 来做的话效率确实无法接受，从上面看居然比调用 WinAPI 的方法慢几十倍。我还是严重怀疑 VC STL 的实现有问题，只是换做直接调用 codecvt<> facet 就能提高好几倍效率。
格式化读写一向是 C++ IO stream 被重点诟病的地方，与 fprintf() 函数整相差一倍，即使直接调用 num_put (去掉了构造 ios_base::sentry 对象产生的流同步、空白跳过等操作)，仍然有 50% 的差距。
其实从理论上来说，C++ 的格式化读写应当是比 C 的 fprintf() 函数要快的，因为 fprintf() 总要有一个解析格式字符串的过程，这个只能放在运行时，而 C++ 的格式是通过多个连续函数调用控制的，可以在编译时即进行优化。但实践往往存在各种变数 = =
 
VC2008EE + STLport5.2.1:
text out C fputs()                      1.0
text out C fprintf()                    2.0
text out C++ ofstream <<                0.7
text out C++ ofstream rdbuf()->sputn()  0.6
wText out C++ wofstream deflocale       7.5
wText out C++ locale codecvt            7.0
wText out C++ ofstream + WinAPI         1.0
Format data out C fprintf()             2.0
Format data out C++ ofstream  <<        2.0
Format data out C++ ofs num_put facet   1.7
 
STLport 的 C 库函数完全是照搬 VC 的标准运行库，而只是重新实现了整个 C++ 库，所以 C 函数的效率与上一例是相同的，可直接横向比较。
面对这样的结果，我只能说 STLport 太赞了！！再考虑到其他的种种特性，赶紧扔掉 VC STL 全部换用 STLport 吧
不过转码看来确实是一个平台相关的特性，仍然无法比过 WinAPI 的效率

MinGW GCC4.4.0 + libstdc++:
text out C fputs()                      1.5
text out C fprintf()                    2.7
text out C++ ofstream <<                6.0
text out C++ ofstream rdbuf()->sputn()  2.7
mingw libstdc++ doesnot surpport other locale...
mingw libstdc++ doesnot surpport other locale...
wText out C++ ofstream + WinAPI         2.1
Format data out C fprintf()             3.0
Format data out C++ ofstream  <<        6.6
Format data out C++ ofs num_put facet   5.8
 
MinGW 貌似比较慢，是因为 MinGW 默认输出按 UTF-8 编码，对中文来说，字节数是 ANSI 的 1.5 倍。只有调用 API 的那个例子保持了 ANSI 编码。
除以 1.5 的话可以看到 C 库函数的效率与 VC 差不多，但 C++ 的效率比 VC 略低，与 STLport 比就差更远了。毕竟 GCC + libstdc++ 在 Win 平台不是原生支持，只作为跨平台的特性这样也足够了。
没有用 MinGW + STLport 做实验，不知能不能达到 VC 的效率。
 
-------------------------------------------------------------
以前使用 C++ 的 IO stream 做输入输出时总担心效率问题，现在有了 STLport 做支持就可以放心大胆的用了。
但可以看到 C++ 的流式 IO 非常依赖于库实现，在各平台上的表现大概不如 C 库函数来得稳定。
而且使用除 "C" 之外的 locale 时效率确实还是有问题，转码的话还是直接调用平台 API 省时省力又高效。MinGW 考虑不引入 locale 部分也是有道理的啊...
 
这次全是 O，下次再比较 I 的情况...
 
最后按惯例是程序代码：
  1. // test the performance of C I/O & C++ streams & C++ codecvt facet
  2. #include<cstdio>
  3. #include<iostream>
  4. #include<fstream>
  5. #include<locale>
  6. #include<cstdlib>
  7. #include<ctime>
  8. #include<windows.h>
  9. using namespace std;
  10.  
  11. const int testsize = 50000;
  12.  
  13. int main(){
  14.     char cstr[] = "这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串";
  15.     wchar_t wstr[] = L"这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串";
  16.     char buffer[200];
  17.     int cstrlen = strlen(cstr);
  18.     locale defloc("");
  19.  
  20.     clock_t start;
  21.     FILE *cfile;
  22.     ofstream fout;
  23.     wofstream wfout;
  24.  
  25.     // pure text ...........................
  26.     start = clock();
  27.     cfile = fopen("text_out_C_fputs.txt", "w");
  28.     for(int i = 0; i < testsize; ++i){
  29.         fputs(cstr, cfile);
  30.         fputc('\n', cfile);
  31.     }
  32.     fclose(cfile);
  33.     printf("Text out C fputs: %d\n", clock()-start);
  34.  
  35.     start = clock();
  36.     cfile = fopen("test_out_C_fprintf.txt", "w");
  37.     for(int i = 0; i < testsize; ++i){
  38.         fprintf(cfile, "%s\n", cstr);
  39.     }
  40.     fclose(cfile);
  41.     printf("Text out C fprintf: %d\n", clock()-start);
  42.  
  43.     fout.clear();
  44.     start = clock();
  45.     fout.open("text_out_Cpp_ofstream.txt");
  46.     for(int i = 0; i < testsize; ++i){
  47.         fout << cstr << '\n';
  48.     }
  49.     fout.close();
  50.     printf("Text out Cpp ofstream: %d\n", clock()-start);
  51.  
  52.     fout.clear();
  53.     start = clock();
  54.     fout.open("text_out_Cpp_rdbuf.txt");
  55.     for(int i = 0; i < testsize; ++i){
  56.         fout.rdbuf()->sputn(cstr, cstrlen);
  57.         fout.rdbuf()->sputc('\n');
  58.     }
  59.     fout.close();
  60.     printf("Text out Cpp rdbuf: %d\n", clock()-start);
  61.  
  62.     // wchar_t text ...............................
  63.     wfout.clear();
  64.     start = clock();
  65.     wfout.open("wtext_out_Cpp_wofs_defloc.txt");
  66.     wfout.imbue(defloc);
  67.     for(int i = 0; i < testsize; ++i){
  68.         wfout << wstr << L'\n';
  69.     }
  70.     wfout.close();
  71.     printf("wText out Cpp wofs with default locale: %d\n", clock()-start);
  72.  
  73.     fout.clear();
  74.     start = clock();
  75.     char *next;
  76.     const wchar_t *wnext;
  77.     mbstate_t st;
  78.     fout.open("wtext_out_Cpp_codecvt_facet.txt");
  79.     for(int i = 0; i < testsize; ++i){
  80.         use_facet<codecvt<wchar_t, char, mbstate_t> >(defloc).out(
  81.             st, wstr, wstr+sizeof(wstr)/2-1, wnext,
  82.             buffer, buffer+sizeof(buffer)-1, next);
  83.         fout.rdbuf()->sputn(buffer, next-buffer);
  84.         fout.rdbuf()->sputc('\n');
  85.     }
  86.     fout.close();
  87.     printf("wText out Cpp ofs with codecvt facet: %d\n", clock()-start);
  88.  
  89.     fout.clear();
  90.     start = clock();
  91.     fout.open("wtext_out_Cpp_ofs_WinAPI.txt");
  92.     for(int i = 0; i < testsize; ++i){
  93.         WideCharToMultiByte(CP_ACP, 0, wstr, -1, buffer, 200, NULL, NULL);
  94.         fout << buffer << '\n';
  95.     }
  96.     fout.close();
  97.     printf("wText out Cpp ofs with WideCharToMultiByte API: %d\n",
  98.         clock()-start);
  99.  
  100.     // Format out ...........................................
  101.     srand((unsigned)time(NULL));
  102.  
  103.     char datastr[] = "TestDataString实验格式化字符串";
  104.     start = clock();
  105.     cfile = fopen("format_data_out_C_fprintf.txt", "w");
  106.     for(int i = 0; i < testsize; ++i){
  107.         fprintf(cfile, "%d %lf %s\n",
  108.             rand(), double(rand())/RAND_MAX, datastr);
  109.     }
  110.     fclose(cfile);
  111.     printf("Format data out C fprintf: %d\n", clock()-start);
  112.  
  113.     fout.clear();
  114.     start = clock();
  115.     fout.open("format_data_out_Cpp_ofstream.txt");
  116.     for(int i = 0; i < testsize; ++i){
  117.         fout << rand() << ' ' << double(rand())/RAND_MAX << ' '
  118.             << datastr << '\n';
  119.     }
  120.     fout.close();
  121.     printf("Format data out Cpp ofstream: %d\n", clock()-start);
  122.  
  123.     fout.clear();
  124.     start = clock();
  125.     fout.open("format_data_out_Cpp_ofs_facet.txt");
  126.     for(int i = 0; i < testsize; ++i){
  127.         use_facet<num_put<char> >(locale::classic()).put(
  128.             ostreambuf_iterator<char>(fout), fout, ' ', (long)rand());
  129.         fout.rdbuf()->sputc(' ');
  130.         use_facet<num_put<char> >(locale::classic()).put(
  131.             ostreambuf_iterator<char>(fout), fout, ' ',
  132.             double(rand())/RAND_MAX);
  133.         fout.rdbuf()->sputc(' ');
  134.         fout.rdbuf()->sputn(datastr, sizeof(datastr) - 1);
  135.         fout.rdbuf()->sputc('\n');
  136.     }
  137.     fout.close();
  138.     printf("Format data out Cpp ofs with facet: %d\n", clock()-start);
  139.  
  140.     system("pause");
  141. }

C/C++ performance locale fstream c++ VC STL Comments(0) 2009年10月31日 16:22

fstream 文件 IO 点滴

很多时候较大数据量的文件 IO 总是成为瓶颈，为了提高效率，有时想要先将文件大块大块的读入再行处理。下面分析两种惯常的处理手法。

1. 将文件一次性读入 string 中。

貌似 std::getline 、 istream::getline 或是 operator<< operator>> 等都不提供一次读到文件结尾的机制，只有 istreambuf_iterator 可以做到：

ifstream in("input.txt");
string instr((istreambuf_iterator<char>(in)), istreambuf_iterator<char>());

string 的构造函数前一个参数要多加一层 () 以免编译器误认为是函数声明 = = ...

这样读入 string 会随着内容动态增长，空间不足时会触发额外的 realloc 及 copy 操作，为提高效率有必要预分配足够的空间：

ifstream in("input.txt");
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 ：

ifstream in("input.txt");
stringstream ss;
ss<<in.rdbuf();

与 string 的情况相同，这里同样也有一个空间 realloc 及 copy 的问题。但 streambuf 的缓冲区不是那么方便操作的，解决方法是我们给他手动指定一个空间：

ifstream in("input.txt");
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 函数体居然是空的！内容如下(中间还有一层函数调用)：

virtual _Myt *__CLR_OR_THIS_CALL setbuf(_Elem *, streamsize)
        {       // offer buffer to external agent (do nothing)
        return (this);
        }

看来是等着我们来继承了啊 = = 。而在 MinGW (GCC 4.4.0) 中可以得到预期的结果。

C/C++ VC STL c++ gcc string fstream Comments(0) 2009年10月06日 18:24

从 std::list 中 size() 的时间复杂度引出的讨论...

很奇怪的，或者说是一个不应成为问题的问题...
std::list 的 size() 方法时间复杂度是多少？第一感觉应该是 O(1) 没错吧，多一个变量用于储存链表长度应该是很轻易的事情。于是有了下面这段代码：

#include<iostream>
#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) 编译结果运行如下：

450   num:50005000
10

可以看到，前一个循环居然比后一个多花了几乎 45 倍的时间...当我把循环次数从 10000 加到 100000 时程序半天没出结果...

由此有理由猜测 std::list 的 size() 方法难道是 O(N) 的？果然，在头文件中发现了这一段：

size_type
size() const
{ return std::distance(begin(), end()); }

 

直接调用 <algorithm> 算法库函数 distance() 计算元素个数……怪不得这么慢。然后又用 VS2008 (VC9.0)编译，结果如下：

30   num:50005000
60

奇怪的是前一个循环居然比后一个还快...不过至少知道 VS2008 (VC9.0)里的 size() 应该是 O(1) 的。同样查看了一下代码，如下：

size_type size() const
    {   // 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<iostream>
#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) 的结果：

10
0   num:60000

可以看到 10000 次 push 是 10，相对的 20000 次 splice() 几乎没花时间 = =

然后是 VS2008 (VC9.0)：

20
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() 的效率问题，没想到却扯出这么一桩事出来...也算长知识了吧

C/C++ STL gcc list VC c++ Comments(0) 2009年5月10日 05:49

STL locale 使用小结

locale 是多种 facet 的容器，每种 facet 管理与 locale 相关的一种功能。
facet 除了按名称区别外，更常用的是按 category 来分类。分类情况如下：
 
locale::ctype 类别，包括以下 facet 模板
ctype         // 字符分类和转换
codecvt     // 字符编码转换
locale::collate 类别，包括以下 facet 模板
collate         // 字符串校对
locale::message 类别，包括以下 facet 模板
messages // 从信息目录中获得本地化信息
locale::numeric 类别，包括以下 facet 模板
numpunct   // 有关数字和布尔运算表达式中标点符号及格式信息
num_get     // 代表数字或布尔值的字符串的解析
num_put     // 代表数字或布尔值的格式化字符串的生成
locale::monetary 类别，包括以下 facet 模板
moneypunct // 货币表达式中的标点符号及格式
money_get   // 代表货币值的字符串的解析
money_put   // 代表货币值的格式化字符串的生成
locale::time 类别，包括以下 facet 模板
time_get        // 代表日期和时间的字符串的解析
time_put        // 代表日期和时间的格式化字符串的生成
 
使用方法：
locale 对象是不可变的，即在它们的生命周期中，它们的内容不可改变。所包含的 facet 不能进行修改或替换，同时 facet 不能增加或删除。
鉴于以上特性，在使用 locale 时一般都是根据需要生成新的 locale 对象，然后选入IO流中。因此 locale 的构造函数就变得十分多样，方便我们以各种形式构造所需要的locale 对象。
例如，需要 std::wostream 输出中文，我们就需要 locale("chs") 中编码转换相关的功能，但若直接选择 locale("chs")，输出数字时也会进行转换处理，例如将 1234 输出为 "1,234"。为了避免这一转换，就需要保留原 locale("C") 中除了字符相关的其他facet。如下处理即可
locale loc("chs", locale::ctype);
此函数以 global 对应的 locale （一般是 locale("C") ） 初始化 loc 并选择 locale("chs") 的字符相关 facet ，这样我们就可以用 loc 正确输出中文，并保持输出数字时不进行其他处理
其他可参阅 MSDN 中关于 locale 的构造函数说明，解释很详细，用法很简单。
此外，locale 对象还可使用 combine 成员函数 选取其他 locale 中指定 facet 进行组合。总之接口多样，不过也一定程度上增加了对 locale 学习的复杂性。
 
最后，还有更简便的解决方案，即全局 locale 对象。
如果你建立了一个流对象，并且没有规定流使用的 locale 对象，那么流使用全局 locale 对象。如果我们在程序开始处改变全局 locale 对象为我们需要的形式，以后就不需再反复设定每个流的 locale 了。如
locale::global(locale("",locale::ctype));
除了将字符处理部分改为当前系统默认的编码方式外其他不变，这样一般就满足需求了。
再加一条，当流建立后再改变全局locale，则对已建立的流无影响。还有改变 C++ 的全局 locale 对象可能会影响 C 的全局 locale 设定，请不要混用。既然用 locale 对象，就全部采用 C++ 的风格吧

C/C++ STL locale Comments(0) 2009年4月25日 07:41

关于 VC 中的 STL string 实现

今天小实验一下发现 VC9 的 STL string 实现中没有使用 引用计数和写时拷贝
在 VC6.0 时默认还是有这两个特性的，从 VC7.0 开始貌似就取消了，大概是考虑到线程安全问题
如果我不用多线程，这两个特性应该还是可以一定程度上提高效率的吧
不然在返回一个 string 时是否也要考虑用 auto_ptr 了呢...
看来有必要自己实现一个 string ，或者偶尔考虑用一下其他库的...
 
不过从一致性考虑，感觉还是显式使用智能指针实现以上功能比较好，不然其他各种自定类型是不是也有必要封装一个 share_ptr 类似特性呢。

 

C/C++ VC STL string Comments(0) 2009年4月25日 07:35

USACO 4.3.2 The Primes

够BT的一道题，改了几遍才过 - -
一开始没想费太多内存觉得稍微预存几种结果应该就差不多了，结果完全低估了数据规模。
只好把所有可能用到的模式全预算出来再循环。结果弄了快300行ORZ...
还有一次犯傻没排序就跑去提交了
 
TASK: prime3
LANG: C++
 
Compiling...
Compile: OK
 
Executing...
   Test 1: TEST OK [0.065 secs, 2984 KB]
   Test 2: TEST OK [0.054 secs, 2988 KB]
   Test 3: TEST OK [0.065 secs, 2984 KB]
   Test 4: TEST OK [0.065 secs, 2988 KB]
   Test 5: TEST OK [0.076 secs, 2984 KB]
   Test 6: TEST OK [0.140 secs, 2984 KB]
   Test 7: TEST OK [0.119 secs, 2988 KB]
   Test 8: TEST OK [0.130 secs, 2988 KB]
   Test 9: TEST OK [0.205 secs, 2988 KB]
   Test 10: TEST OK [0.259 secs, 2988 KB]
 
All tests OK.
Your program ('prime3') produced all correct answers!  This is your
submission #5 for this problem.  Congratulations!
 
要速度，貌似只能模拟填表的过程，并且每步选限制尽可能多的行或列来填。
第1行和第1列限制最多，开头第1位已定，且各位都不能出现0，先把他们填了。
然后选辅对角线(左下到右上)，因为开头结尾两位都已定。
再填主对角线，第1位和第3位已定。
下面是第二行、第二列、第四行、第四列，这四种情况都是 1、2、4 位已定
然后第三行和第三列都只剩下最后一位空缺了。最后检查一下第五行和第五列即可。
 
从上面过程看出要预先计算的是：
(1) 所有5位质数且各位数字和满足条件的数
(2) 第1位已知且满足(1)，各位都不为0的组合
(3) 1、5位已知且满足(1)的组合
(4) 1、3位已知且满足(1)的组合
(5) 1、2、3、4位已知且满足(1)的组合
 
其他好像有提出先填第5行和第5列的，因为这两行除了满足质数与数字和外 各位只能是 1、3、7、9 四选一。不过我觉得这没有用，例如只要第一列填了质数，则第5行第一位自然就只会是 1、3、7、9 之一了，先填第5行对第1列来说也并没有其他额外限制作用。但仅是猜测，也没试验过。
 
预先开个100000的数组，第一遍求所有质数(顺便将不是质数的值存为下标方便遍历)，然后筛选数字和满足条件的数，同样使下标形成链表方便遍历。同时选出各位数字满足条件的组合预先存起来，剩下只用循环便是。排序嘛，就每位挨个判断了，也没几个数。

USACO usaco Comments(0) 2009年4月25日 07:29

USACO 4.2.1 Ditch 网络最大流问题算法小结

通过 USACO 4.2.1 Ditch 学习一下最大流算法 。可惜它给的测试数据几乎没有任何杀伤力，后面测试时我们采用 DD_engi 写的程序生成的加强版数据。

总体上来说，最大流算法分为两大类：增广路 (Augmenting Path) 和预流推进重标号 (Push Relabel) 。也有算法同时借鉴了两者的长处，如 Improved SAP 。本篇主要介绍增广路类算法，思想、复杂度及实际运行效率比较，并试图从中选择一种兼顾代码复杂度和运行效率的较好方案。以下我们将会看到，有时理论分析的时间复杂度并不能很好的反映一种算法的实际效率。

1. Ford - Fulkerson 方法

所有增广路算法的基础都是 Ford - Fulkerson 方法。称之为方法而不是算法是因为 Ford - Fulkerson 只提供了一类思想，在此之上的具体操作可有不同的实现方案。

给定一个有向网络 G(V,E) 以及源点 s 终点 t ，FF 方法描述如下：

Ford-Fulkerson 方法 (G,s,t)
1 将各边上流量 f 初始化为 0
2 while 存在一条增广路径 p
3     do 沿路径 p 增广流量 f
4 return f

假设有向网络 G 中边 (i,j) 的容量为 c(i,j) ，当前流量为 f(i,j) ，则此边的剩余流量即为 r(i,j) = c(i,j) - f(i,j) ，其反向边的剩余流量为 r(j,i) = f(i,j) 。有向网中所有剩余流量 r(i,j) > 0 的边构成残量网络 Gf ，增广路径p即是残量网络中从源点 s 到终点 t 的路径。

沿路径 p 增广流量 f 的操作基本都是相同的，各算法的区别就在于寻找增广路径 p 的方法不同。例如可以寻找从 s 到 t 的最短路径，或者流量最大的路径。

2. Edmonds - Karp 算法

Shortest Augmenting Path (SAP) 是每次寻找最短增广路的一类算法，Edmonds - Karp 算法以及后来著名的 Dinic 算法都属于此。SAP 类算法可统一描述如下：

Shortest Augmenting Path
1 x <-- 0
2 while 在残量网络 Gx 中存在增广路 s ~> t
3     do 找一条最短的增广路径 P
4        delta <-- min{rij:(i,j) 属于 P}
5        沿 P 增广 delta 大小的流量
6        更新残量网络 Gx
7 return x

在无权边的有向图中寻找最短路，最简单的方法就是广度优先搜索 (BFS)，E-K 算法就直接来源于此。每次用一遍 BFS 寻找从源点 s 到终点 t 的最短路作为增广路径，然后增广流量 f 并修改残量网络，直到不存在新的增广路径。

E-K 算法的时间复杂度为 O(VE2)，由于 BFS 要搜索全部小于最短距离的分支路径之后才能找到终点，因此可以想象频繁的 BFS 效率是比较低的。实践中此算法使用的机会较少。

3. Dinic 算法

BFS 寻找终点太慢，而 DFS 又不能保证找到最短路径。1970年 Dinic 提出一种思想，结合了 BFS 与 DFS 的优势，采用构造分层网络的方法可以较快找到最短增广路，此算法又称为阻塞流算法 (Blocking Flow Algorithm)。

首先定义分层网络 AN(f)。在残量网络中从源点 s 起始进行 BFS，这样每个顶点在 BFS 树中会得到一个距源点 s 的距离 d，如 d(s) = 0，直接从 s 出发可到达的点距离为 1，下一层距离为2 ... 。称所有具有相同距离的顶点位于同一层，在分层网络中，只保留满足条件 d(i) + 1 = d(j) 的边，这样在分层网络中的任意路径就成为到达此顶点的最短路径。

Dinic 算法每次用一遍 BFS 构建分层网络 AN(f)，然后在 AN(f) 中一遍 DFS 找到所有到终点 t 的路径增广；之后重新构造 AN(f)，若终点 t 不在 AN(f) 中则算法结束。DFS 部分算法可描述如下：

 1 p <-- s
 2 while s 的出度 > 0 do
 3     u <-- p.top
 4     if u != t then
 5         if u 的出度 > 0 then
 6             设 (u,v) 为 AN(f) 中一条边
 7             p <-- p, v
 8         else
 9             从 p 和 AN(f) 中删除点 u 以及和 u 连接的所有边
10     else
11         沿 p 增广
12         令 p.top 为从 s 沿 p 可到达的最后顶点
13 end while

 实际代码中不必真的用一个图来存储分层网络，只需保存每个顶点的距离标号并在 DFS 时判断 dist[i] + 1 = dist[j] 即可。Dinic 的时间复杂度为 O(V2E)。由于较少的代码量和不错的运行效率，Dinic 在实践中比较常用。具体代码可参考 DD_engi 网络流算法评测包中的标程，这几天 dinic 算法的实现一共看过和比较过将近 10 个版本了，DD 写的那个在效率上是数一数二的，逻辑上也比较清晰。

 4. Improved SAP 算法

 本次介绍的重头戏。通常的 SAP 类算法在寻找增广路时总要先进行 BFS，BFS 的最坏情况下复杂度为 O(E)，这样使得普通 SAP 类算法最坏情况下时间复杂度达到了 O(VE2)。为了避免这种情况，Ahuja 和 Orlin 在1987年提出了Improved SAP 算法，它充分利用了距离标号的作用，每次发现顶点无出弧时不是像 Dinic 算法那样到最后进行 BFS，而是就地对顶点距离重标号，这样相当于在遍历的同时顺便构建了新的分层网络，每轮寻找之间不必再插入全图的 BFS 操作，极大提高了运行效率。国内一般把这个算法称为 SAP...显然这是不准确的，毕竟从字面意思上来看 E-K 和 Dinic 都属于 SAP，我还是习惯称为 ISAP 或改进的 SAP 算法。

 与 Dinic 算法不同，ISAP 中的距离标号是每个顶点到达终点 t 的距离。同样也不需显式构造分层网络，只要保存每个顶点的距离标号即可。程序开始时用一个反向 BFS 初始化所有顶点的距离标号，之后从源点开始，进行如下三种操作：(1)当前顶点 i 为终点时增广 (2) 当前顶点有满足 dist[i] = dist[j] + 1 的出弧时前进 (3) 当前顶点无满足条件的出弧时重标号并回退一步。整个循环当源点 s 的距离标号 dist[s] >= n 时结束。对 i 点的重标号操作可概括为 dist[i] = 1 + min{dist[j] : (i,j)属于残量网络Gf}。具体算法描述如下：

algorithm Improved-Shortest-Augmenting-Path
 1 f <-- 0
 2 从终点 t 开始进行一遍反向 BFS 求得所有顶点的起始距离标号 d(i)
 3 i <-- s
 4 while d(s) < n do
 5     if i = t then    // 找到增广路
 6         Augment
 7         i <-- s      // 从源点 s 开始下次寻找
 8     if Gf 包含从 i 出发的一条允许弧 (i,j)
 9         then Advance(i)
10         else Retreat(i)    // 没有从 i 出发的允许弧则回退
11 return f

procedure Advance(i)
1 设 (i,j) 为从 i 出发的一条允许弧
2 pi(j) <-- i    // 保存一条反向路径，为回退时准备
3 i <-- j        // 前进一步，使 j 成为当前结点

procedure Retreat(i)
1 d(i) <-- 1 + min{d(j):(i,j)属于残量网络Gf}    // 称为重标号的操作
2 if i != s
3     then i <-- pi(i)    // 回退一步

procedure Augment
1 pi 中记录为当前找到的增广路 P
2 delta <-- min{rij:(i,j)属于P}
3 沿路径 P 增广 delta 的流量
4 更新残量网络 Gf

 算法中的允许弧是指在残量网络中满足 dist[i] = dist[j] + 1 的弧。Retreat 过程中若从 i 出发没有弧属于残量网络 Gf 则把顶点距离重标号为 n 。

 虽然 ISAP 算法时间复杂度与 Dinic 相同都是 O(V2E)，但在实际表现中要好得多。要提的一点是关于 ISAP 的一个所谓 GAP 优化。由于从 s 到 t 的一条最短路径的顶点距离标号单调递减，且相邻顶点标号差严格等于1，因此可以预见如果在当前网络中距离标号为 k (0 <= k < n) 的顶点数为 0，那么可以知道一定不存在一条从 s 到 t 的增广路径，此时可直接跳出主循环。在我的实测中，这个优化是绝对不能少的，一方面可以提高速度，另外可增强 ISAP 算法时间上的稳定性，不然某些情况下 ISAP 会出奇的费时，而且大大慢于 Dinic 算法。相对的，初始的一遍 BFS 却是可有可无，因为 ISAP 可在循环中自动建立起分层网络。实测加不加 BFS 运行时间差只有 5% 左右，代码量可节省 15~20 行。

 5. 最大容量路径算法 (Maximum Capacity Path Algorithm)

 1972年还是那个 E-K 组合提出的另一种最大流算法。每次寻找增广路径时不找最短路径，而找容量最大的。可以预见，此方法与 SAP 类算法相比可更快逼近最大流，从而降低增广操作的次数。实际算法也很简单，只用把前面 E-K 算法的 BFS 部分替换为一个类 Dijkstra 算法即可。USACO 4.2 节的说明详细介绍了此算法，这里就不详述了。

 时间复杂度方面。BFS 是 O(E)，简单 Dijkstra 是 O(V2)，因此效果可想而知。但提到 Dijkstra 就不能不提那个 Heap 优化，虽然 USACO 的算法例子中没有用 Heap ，我自己还是实现了一个加 Heap 的版本，毕竟 STL 的优先队列太好用了不加白不加啊。效果也是非常明显的，但比起 Dinic 或 ISAP 仍然存在海量差距，这里就不再详细介绍了。

 6. Capacity Scaling Algorithm

 不知道怎么翻比较好，索性就这么放着吧。叫什么的都有，容量缩放算法、容量变尺度算法等，反正就那个意思。类似于二分查找的思想，寻找增广路时不必非要局限于寻找最大容量，而是找到一个可接受的较大值即可，一方面有效降低寻找增广路时的复杂度，另一方面增广操作次数也不会增加太多。时间复杂度 O(E2logU) 实际效率嘛大约稍好于最前面 BFS 的 E-K 算法，稀疏图时表现较优，但仍然不敌 Dinic 与 ISAP。

 7. 算法效率实测！

 重头戏之二，虽然引用比较多，哎~

 首先引用此篇强文 《Maximum Flow: Augmenting Path Algorithms Comparison》

 对以上算法在稀疏图、中等稠密图及稠密图上分别进行了对比测试。直接看结果吧：

稀疏图：

ISAP 轻松拿下第一的位置，图中最左边的 SAP 应该指的是 E-K 算法，这里没有比较 Dinic 算法是个小遗憾吧，他把 Dinic 与 SAP 归为一类了。最大流量路径的简单 Dijkstra 实现实在是太失败了 - -，好在 Heap 优化后还比较能接受……可以看到 Scaling 算法也有不错的表现。

 中等稠密图：

 

 ISAP 依然领先。最大流量算法依然不太好过……几个 Scaling 类算法仍然可接受。

 稠密图：

 

 ISAP……你无敌了！这次可以看出 BFS 的 Scaling 比 DFS 实现好得多，而且几乎与 Improved Scaling 不相上下，代码量却差不少。看来除 ISAP 外 BFS Scaling 也是个不错的选择。

 最后补个我自己实测的图，比较算法有很多是 DD 网络流算法评测包里的标程，评测系统用的 Cena，评测数据为 DD ditch 数据生成程序生成的加强版数据：

 

 我一共写了 7 个版本的 ISAP ，Dinic 算法也写了几个递归版的但效率都不高，只放上来一个算了。从上图来看似乎 ISAP 全面超越了号称最大流最快速算法的 HLPP，但在另外一台机器上测试结果与此却不大相同，有时 ISAP 与 HLPP 基本持平，有时又稍稍慢一些。在这种差距非常小的情况下似乎编译器的效果也比较明显。那个 HLPP 是用 PASCAL 写的，我不知在 Win32 平台下编译代码效率如何，至少我的几个 ISAP 用 VC2008 + SP1 编译比用 g++ 要强不少，也可能是参数设置的问题。

不过这些都是小事，关键是见证了 ISAP 的实际效率。从上面可以看出不加 GAP 优化的 ISAP 有几个测试点干脆无法通过，而不加 BFS 却无甚大影响，递归与非递归相差在 7% 左右的样子。综合以上表现，推荐采用 ISAP 不加 BFS，非递归 + GAP 优化的写法，Ditch 这道题一共也才 80 行左右代码。要提的一点是 GAP 优化用递归来表现的话不如 while 循环来得直接。另外，看起来 HLPP 表现确实很优秀，有机会也好好研究一下吧，预流推进重标号算法也是一大类呢……

最后附上一个 ISAP + GAP + BFS 的非递归版本代码，网络采用邻接表 + 反向弧指针：

  1. #include<cstdio>
  2. #include<memory>
  3. using namespace std;
  4.  
  5. const int maxnode = 1024;
  6. const int infinity = 2100000000;
  7.  
  8. struct edge{
  9.     int ver;    // vertex
  10.     int cap;    // capacity
  11.     int flow;   // current flow in this arc
  12.     edge *next; // next arc
  13.     edge *rev;  // reverse arc
  14.     edge(){}
  15.     edge(int Vertex, int Capacity, edge *Next)
  16.         :ver(Vertex), cap(Capacity), flow(0), next(Next), rev((edge*)NULL){}
  17.     void* operator new(size_t, void *p){
  18.         return p;
  19.     }
  20. }*Net[maxnode];
  21. int dist[maxnode]= {0}, numbs[maxnode] = {0}, src, des, n;
  22.  
  23. void rev_BFS(){
  24.     int Q[maxnode], head = 0, tail = 0;
  25.     for(int i=1; i<=n; ++i){
  26.         dist[i] = maxnode;
  27.         numbs[i] = 0;
  28.     }
  29.  
  30.     Q[tail++] = des;
  31.     dist[des] = 0;
  32.     numbs[0] = 1;
  33.     while(head != tail){
  34.         int v = Q[head++];
  35.         for(edge *e = Net[v]; e; e = e->next){
  36.             if(e->rev->cap == 0 || dist[e->ver] < maxnode)continue;
  37.             dist[e->ver] = dist[v] + 1;
  38.             ++numbs[dist[e->ver]];
  39.             Q[tail++] = e->ver;
  40.         }
  41.     }
  42. }
  43.  
  44. int maxflow(){
  45.     int u, totalflow = 0;
  46.     edge *CurEdge[maxnode], *revpath[maxnode];
  47.     for(int i=1; i<=n; ++i)CurEdge[i] = Net[i];
  48.     u = src;
  49.     while(dist[src] < n){
  50.         if(u == des){    // find an augmenting path
  51.             int augflow = infinity;
  52.             for(int i = src; i != des; i = CurEdge[i]->ver)
  53.                 augflow = min(augflow, CurEdge[i]->cap);
  54.             for(int i = src; i != des; i = CurEdge[i]->ver){
  55.                 CurEdge[i]->cap -= augflow;
  56.                 CurEdge[i]->rev->cap += augflow;
  57.                 CurEdge[i]->flow += augflow;
  58.                 CurEdge[i]->rev->flow -= augflow;
  59.             }
  60.             totalflow += augflow;
  61.             u = src;
  62.         }
  63.  
  64.         edge *e;
  65.         for(e = CurEdge[u]; e; e = e->next)
  66.             if(e->cap > 0 && dist[u] == dist[e->ver] + 1)break;
  67.         if(e){    // find an admissible arc, then Advance
  68.             CurEdge[u] = e;
  69.             revpath[e->ver] = e->rev;
  70.             u = e->ver;
  71.         } else {    // no admissible arc, then relabel this vertex
  72.             if(0 == (--numbs[dist[u]]))break;    // GAP cut, Important!
  73.             CurEdge[u] = Net[u];
  74.             int mindist = n;
  75.             for(edge *te = Net[u]; te; te = te->next)
  76.                 if(te->cap > 0)mindist = min(mindist, dist[te->ver]);
  77.             dist[u] = mindist + 1;
  78.             ++numbs[dist[u]];
  79.             if(u != src)
  80.                 u = revpath[u]->ver;    // Backtrack
  81.         }
  82.     }
  83.     return totalflow;
  84. }
  85.  
  86. int main(){
  87.     int m, u, v, w;
  88.     freopen("ditch.in", "r", stdin);
  89.     freopen("ditch.out", "w", stdout);
  90.     while(scanf("%d%d", &m, &n) != EOF){    // POJ 1273 need this while loop
  91.         edge *buffer = new edge[2*m];
  92.         edge *data = buffer;
  93.         src = 1; des = n;
  94.         while(m--){
  95.             scanf("%d%d%d", &u, &v, &w);
  96.             Net[u] = new((void*) data++) edge(v, w, Net[u]);
  97.             Net[v] = new((void*) data++) edge(u, 0, Net[v]);
  98.             Net[u]->rev = Net[v];
  99.             Net[v]->rev = Net[u];
  100.         }
  101.         rev_BFS();
  102.         printf("%d\n", maxflow());
  103.         delete [] buffer;
  104.     }
  105.     return 0;
  106. }

 

 

 

算法研究 最大流 Dinic SAP usaco 算法 Comments(22) 2009年4月06日 22:58




 

Host by is-Programmer.com | Power by Chito 1.2.6 beta
Designed by : Rambling Soul