輝夜 的个人资料Kaguya Houraisan's glori...照片日志列表更多  |  工具 帮助 |
|
2009年11月 USACO 5.2.3 Wisconsin Squares好长时间没做题了，拿这个来练练手...
时限居然有 5s ，看来得做好极限优化的准备。
开始想的是用一个 int [4][4][5] 数组记录每格周围有同种羊的格数，然后 dfs 时每放一格就改变周围 8 格的数字。运行下貌似很慢，在我的机器上都 10s 多。 于是想到以前写过五子棋的位运算优化，这题一共 16 格，每格数字最多不大于 4，因此可用一个 64位 unsigned int 放下，每格数字只用 4 bit 表示即可。位运算的优点是可同时操作 64 位，这样只用一句便可同时改变周围 8 格的数据。 可惜在我的机器上依然跑到了 6s，考虑到还开着耗 CPU 的 APE 在听，正常应该能跑进 5s 吧。结果提交一看在评测机上只用了 2.1s 。。。哦 ... 咱的机器看来该淘汰了 = = 按 6:2 来算不加位运算优化的估计也能进 5s 了... TASK: wissqu
LANG: C++ Compiling...
Compile: OK Executing...
Test 1: TEST OK [2.117 secs, 2940 KB] All tests OK.
C++语言: USACO 5.2.3 wissqu
#include<cstdlib> #include<fstream> #include<iterator> #include<algorithm> using namespace std; class farm{ int cnt, cowat[16], cowleft[5]; bool nochange[16]; unsigned long long ajtcnt[5]; const unsigned long long mask, maskl, maskr; pair<int, int> putorder[16]; int dfscow[16], dfspos[16]; void addcow(int cowidx, int posidx){ switch(posidx){ /* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 */ case 0: case 4: ajtcnt[cowidx] += maskl >> (5 - posidx) * 4; break; case 3: ajtcnt[cowidx] += maskr >> (5 - posidx) * 4; break; case 1: case 2: ajtcnt[cowidx] += mask >> (5 - posidx) * 4; break; case 5: case 6: case 9: case 10: case 13: case 14: ajtcnt[cowidx] += mask << (posidx - 5) * 4; break; case 8: case 12: ajtcnt[cowidx] += maskl << (posidx - 5) * 4; break; case 7: case 11: case 15: ajtcnt[cowidx] += maskr << (posidx - 5) * 4; break; } cowat[posidx] = cowidx; } int replace(int newcow, int posidx){ int oldcow = cowat[posidx]; unsigned long long m; switch(posidx){ case 0: case 4: m = maskl >> (5 - posidx) * 4; ajtcnt[newcow] += m; ajtcnt[oldcow] -= m; break; case 3: m = maskr >> (5 - posidx) * 4; ajtcnt[newcow] += m; ajtcnt[oldcow] -= m; break; case 1: case 2: m = mask >> (5 - posidx) * 4; ajtcnt[newcow] += m; ajtcnt[oldcow] -= m; break; case 5: case 6: case 9: case 10: case 13: case 14: m = mask << (posidx - 5) * 4; ajtcnt[newcow] += m; ajtcnt[oldcow] -= m; break; case 8: case 12: m = maskl << (posidx - 5) * 4; ajtcnt[newcow] += m; ajtcnt[oldcow] -= m; break; case 7: case 11: case 15: m = maskr << (posidx - 5) * 4; ajtcnt[newcow] += m; ajtcnt[oldcow] -= m; break; } cowat[posidx] = newcow; return oldcow; } bool putable(int cowidx, int posidx) const { return !((ajtcnt[cowidx] >> posidx*4) & 0xF); } void dfs(int idx){ int oldcow; if(idx == 16){ if(!(cnt++)){ for(int i = 0; i < 16; ++i) putorder[i] = make_pair(dfscow[i], dfspos[i]); } return; } int &cow(dfscow[idx]), &pos(dfspos[idx]); for(cow = 0; cow < 5; ++cow)if(cowleft[cow]){ --cowleft[cow]; for(pos = 0; pos < 16; ++pos)if(nochange[pos] && putable(cow, pos)){ nochange[pos] = false; oldcow = replace(cow, pos); dfs(idx + 1); replace(oldcow, pos); nochange[pos] = true; } ++cowleft[cow]; } } public: template<class Iter> farm(Iter beg, Iter end): cnt(0), mask (0x011101110111ULL), maskl(0x011001100110ULL), maskr(0x001100110011ULL){ fill_n(ajtcnt, 5, 0); fill_n(cowleft, 5, 3); fill_n(nochange, 16, true); for(int i=0; beg != end; ++beg, ++i) addcow(*beg - 'A', i); } void calput(void){ int oldcow, &pos(dfspos[0]); dfscow[0] = 3; for(pos = 0; pos < 16; ++pos)if(putable(3, pos)){ nochange[pos] = false; oldcow = replace(3, pos); dfs(1); replace(oldcow, pos); nochange[pos] = true; } } ostream& output(ostream& os){ for(int i=0; i<16; ++i){ div_t pos = div(putorder[i].second, 4); os << char(putorder[i].first + 'A') << ' ' << pos.quot + 1 << ' ' << pos.rem + 1 << '\n'; } os << cnt << '\n'; return os; } }; int main(){ ifstream fin("wissqu.in"); farm wissqu((istream_iterator<char>(fin)), istream_iterator<char>()); fin.close(); ofstream fout("wissqu.out"); wissqu.calput(); wissqu.output(fout); fout.close(); } 2009年11月 又一次吃了浮点数的亏 = =C++:
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 即可。
今后再处理浮点数的问题时一定要相当小心咯 2009年10月 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 support other locale...
mingw libstdc++ doesnot support 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 的情况...
最后按惯例是程序代码：
C++语言:
001 // test the performance of C I/O & C++ streams & C++ codecvt facet 002 #include<cstdio> 003 #include<iostream> 004 #include<fstream> 005 #include<locale> 006 #include<cstdlib> 007 #include<ctime> 008 #include<windows.h> 009 using namespace std; 010 011 const int testsize = 50000; 012 013 int main(){ 014 char cstr[] = "这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串"; 015 wchar_t wstr[] = L"这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串这是实验字符串"; 016 char buffer[200]; 017 int cstrlen = strlen(cstr); 018 locale defloc(""); 019 020 clock_t start; 021 FILE *cfile; 022 ofstream fout; 023 wofstream wfout; 024 025 // pure text ........................... 026 start = clock(); 027 cfile = fopen("text_out_C_fputs.txt", "w"); 028 for(int i = 0; i < testsize; ++i){ 029 fputs(cstr, cfile); 030 fputc('\n', cfile); 031 } 032 fclose(cfile); 033 printf("Text out C fputs: %d\n", clock()-start); 034 035 start = clock(); 036 cfile = fopen("test_out_C_fprintf.txt", "w"); 037 for(int i = 0; i < testsize; ++i){ 038 fprintf(cfile, "%s\n", cstr); 039 } 040 fclose(cfile); 041 printf("Text out C fprintf: %d\n", clock()-start); 042 043 fout.clear(); 044 start = clock(); 045 fout.open("text_out_Cpp_ofstream.txt"); 046 for(int i = 0; i < testsize; ++i){ 047 fout << cstr << '\n'; 048 } 049 fout.close(); 050 printf("Text out Cpp ofstream: %d\n", clock()-start); 051 052 fout.clear(); 053 start = clock(); 054 fout.open("text_out_Cpp_rdbuf.txt"); 055 for(int i = 0; i < testsize; ++i){ 056 fout.rdbuf()->sputn(cstr, cstrlen); 057 fout.rdbuf()->sputc('\n'); 058 } 059 fout.close(); 060 printf("Text out Cpp rdbuf: %d\n", clock()-start); 061 062 // wchar_t text ............................... 063 wfout.clear(); 064 start = clock(); 065 wfout.open("wtext_out_Cpp_wofs_defloc.txt"); 066 wfout.imbue(defloc); 067 for(int i = 0; i < testsize; ++i){ 068 wfout << wstr << L'\n'; 069 } 070 wfout.close(); 071 printf("wText out Cpp wofs with default locale: %d\n", 072 clock()-start); 073 074 fout.clear(); 075 start = clock(); 076 char *next; 077 const wchar_t *wnext; 078 mbstate_t st; 079 fout.open("wtext_out_Cpp_codecvt_facet.txt"); 080 for(int i = 0; i < testsize; ++i){ 081 use_facet<codecvt<wchar_t, char, mbstate_t> >(defloc).out( 082 st, wstr, wstr+sizeof(wstr)/2-1, wnext, 083 buffer, buffer+sizeof(buffer)-1, next); 084 fout.rdbuf()->sputn(buffer, next-buffer); 085 fout.rdbuf()->sputc('\n'); 086 } 087 fout.close(); 088 printf("wText out Cpp ofs with codecvt facet: %d\n", 089 clock()-start); 090 091 fout.clear(); 092 start = clock(); 093 fout.open("wtext_out_Cpp_ofs_WinAPI.txt"); 094 for(int i = 0; i < testsize; ++i){ 095 WideCharToMultiByte(CP_ACP, 0, wstr, -1, buffer, 200, 096 NULL, NULL); 097 fout << buffer << '\n'; 098 } 099 fout.close(); 100 printf("wText out Cpp ofs with WideCharToMultiByte API: %d\n", 101 clock()-start); 102 103 // Format out ........................................... 104 srand((unsigned)time(NULL)); 105 106 char datastr[] = "TestDataString实验格式化字符串"; 107 start = clock(); 108 cfile = fopen("format_data_out_C_fprintf.txt", "w"); 109 for(int i = 0; i < testsize; ++i){ 110 fprintf(cfile, "%d %lf %s\n", rand(), 111 double(rand())/RAND_MAX, datastr); 112 } 113 fclose(cfile); 114 printf("Format data out C fprintf: %d\n", clock()-start); 115 116 fout.clear(); 117 start = clock(); 118 fout.open("format_data_out_Cpp_ofstream.txt"); 119 for(int i = 0; i < testsize; ++i){ 120 fout << rand() << ' ' << double(rand())/RAND_MAX << ' ' 121 << datastr << '\n'; 122 } 123 fout.close(); 124 printf("Format data out Cpp ofstream: %d\n", clock()-start); 125 126 fout.clear(); 127 start = clock(); 128 fout.open("format_data_out_Cpp_ofs_facet.txt"); 129 for(int i = 0; i < testsize; ++i){ 130 use_facet<num_put<char> >(locale::classic()).put( 131 ostreambuf_iterator<char>(fout), fout, ' ', (long)rand()); 132 fout.rdbuf()->sputc(' '); 133 use_facet<num_put<char> >(locale::classic()).put( 134 ostreambuf_iterator<char>(fout), fout, ' ', 135 double(rand())/RAND_MAX); 136 fout.rdbuf()->sputc(' '); 137 fout.rdbuf()->sputn(datastr, sizeof(datastr) - 1); 138 fout.rdbuf()->sputc('\n'); 139 } 140 fout.close(); 141 printf("Format data out Cpp ofs with facet: %d\n", clock()-start); 142 143 system("pause"); 144 } 2009年10月 万恶的 xxx2009年10月 fstream 文件 IO 点滴http://dantvt.is-programmer.com/posts/11949.html 很多时候较大数据量的文件 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) 中可以得到预期的结果。 2009年9月 fileden 貌似挂了？好像几天没连上
不知是不是被 GFW 了，这一段貌似封的挺紧
过了十一再看看
果然是被墙了.>>最近 fg U tor puff 全部失效 ... TMd gcd 2009年7月 用 MSVC 9.0 和 MinGW (GCC 3.4.5) 编译 STLport 5.2.1目前已发现 VC 9.0 所带 STL 的几处缺陷，为了保证在任何 C++ 编译器中使用 STL 时能够表现一致，决定将标准库都统一为 STLport 。
MinGW 下则是为了使用 wstream 的宽字符流。
大致记录下编译过程，以后也能做个参考。
编译版本 STLport-5.2.1
一、VS2008 (MSVC 9.0) 下
(1) 将压缩包解到某文件夹，如 D:\STLport (路径中无空格)
(2) 启动 VS2008 的命令行模式。(注意不是 Run... 中的 cmd)
cd D:\STLport
(3) configure msvc9 -x --with-static-rtl --use-boost D:\lib\boost_1_36_0
msvc9 指明编译器
-x 参数指明是 cross-compile ，在 lib 文件夹下会生成一个 vc9 文件夹。加不加无所谓。
--with-static-rtl 指明编译静态库，编译器参数选择 /MT 时会使用此库。
若是需要动态库则改为 --with-dynamic-rtl
经试验好像没法同时编译动态和静态库。一次一种也无所谓。
但是选择编译静态库时也会生成动态库的文件，不过那些是不可用的，文件名中也有 x 字母表示无效文件
--use-boost 指明 boost 库的路径。仅使用一下 boost 的几个头文件，所以无需事先编译 boost。路径中不要有空格，不然很麻烦
(4) cd build\lib
切换到 build\lib 子目录
(5) nmake /fmsvc.mak install
开始编译。需要待一会儿。完成后会在 STLport\lib 和 STLport\bin (动态库时) 下生成 LIB 和 DLL 文件。
(6) 启动 VS2008 设定 include 目录。注意把 STLport\stlport 的位置放在 VC 自带的 STL 库的前面。完毕～
----------------------------
2009.11.1 补充：
最近根据需要又重新编译了一遍 STLport，发现以前写的这篇文章有几个问题。
先是关于 --use-boost 的选项。STLport 在 5.2.1 版上已经停留好久了，而这期间，boost 的版本从 1.36.0 变动到 1.40.0 ，所以 STLport 中 --use-boost 的选项貌似和新版 boost 已经不能很好的协作了。所以不要再指定这个选项即可，本来这个对 Win32 VC 来说就不是很有必要。
其次关于 --with-static-rtl 和 --with-dynamic-rtl ，以前理解是有误的。
--with-static-rtl 这个指明编译时静态链接到 VC 的 C runtime library (即 libcmt.lib)，这样编译出来的库，我们以后在 build 自己的程序时选择 /MT 选项会用到。如果没有其他改动的话，默认也是静态链接到 stlport 库的，如果想要静态链接到 C runtime library 的同时，动态链接到 stlportxx.dll ，那么在自己的项目属性中添加 _STLP_USE_DYNAMIC_LIB 的预定义宏即可。此时会用到带有字母 x 的生成文件(在上面说带 x 的是无效文件，是因为当时不会用，呵呵。)
--with-dynamic-rtl 这个指明编译时动态链接到 VC 的 C runtime library (即 MSVCxxx.lib MSVCP90.dll)，这样编译出来的库，我们以后在 build 自己程序时选择 /MD 选项会用到。如果没有其他改动的话，默认也是动态链接到 stlport 库(依赖 stlport.5.2.dll)，如果想动态链接到 C runtime library 的同时，静态链接到 stlportxx.lib ，那么在项目属性中添加 _STLP_USE_STATIC_LIB 的预定义宏即可。(此时也会用到带 x 字母的另一些文件。)
现在编译的话，直接这么做：
(1) configure msvc9 -x --with-dynamic-rtl
(2) 切换到 build/lib 目录，nmake /fmsvc.mak install clean
(3) configure msvc9 -x --with-static-rtl
(4) 切换到 build/lib 目录，nmake /fmsvc.mak install clean
完毕~ 生成文件在 /lib/vc9 和 /bin/vc9 目录下。
STLport 用起来真的很爽，效率比 VC9 自带的 STL 库高不少，特别对于 C++ 的 stream IO 操作优化很好，基本上都可以超过 C 库函数的效率。
----------------------------------------
不过在 VC 中使用 STLport 也发现点小问题，主要是和 VC 的调试器配合不好，因为 STLport 中一些标准容器的结构变得比较复杂，好像没法在单步调试时方便的观察数据变化。
二、MinGW (GCC 3.4.5) 下
(1) start MSYS & cd /lib/STLport-5.2.1
(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 本来一个月前就写好的。。。结果拜某节日所赐那几天 Space live 被封。。。然后居然拖了这么久 = = 还是懒啊~
然后再发点牢骚。看中文书一般总说里面错误成堆措辞不准确什么的，说计算机书都去看原版质量多高，结果这本按说也是 STL 标准学习手册的《C++ Stardand Library : A Tutorial and Reference》里也是错误频频，什么样的都有。。。函数名写错、算法写错、时间复杂度写错、函数返回值true false 搞反的，还有很多印刷错误就不一一列举了。当然书的内容还是很好的，只是看的时候得小心点。。。 2009年5月 Win32 + GCC 的一点尝试前一段试用了 MinGW 5.1.4 (GCC-3.4.5) 感觉还好，但是有两点不满意：
(1) GCC 自带的 libstdc++-v3 不支持宽字符流 (wcin/wcout/wstream...)，似乎是与 Win32 平台的 locale 不兼容所致，但仅用 wstring 的话还是可以的。
(2) GCC 版本有点点久远。毕竟 4.x 版都出来几年了。
(3) MSYS 对中文的支持够呛。这个我也认了，反正只用它来编译，文件名都保持鸟文的就没什么问题。
反正免费平台几乎都这样，那帮老外写的系统总是把国际化支持弄得很差，时不时就得担心来个乱码啥的，毕竟人家也不用管那么多，单就那26个字母的话啥时候也不会出问题。
当然也有优点
(1) 全套组件免费。不用总为版权问题心存愧疚
当然 VC 也有免费 Express 版，但好用的工具 Visual Assist、模拟 Vi 编辑器的 ViEmu 等都不是免费的。
(2) 体积小方便携带。一套 MinGW + MSYS 也就 100MB 出头；VC 随便一整就上 GB...
(3) 运行时库默认链接到 MSVCRT.dll，不像 VC 出个新版就整一套新的 MSVCRxx.dll MSVCRPxx.dll 很乱。
不过我惊异的是 GCC 动态链接出来的文件体积比 VC 静态链接的还大...写小程序的时候对这个还是有点在意的，毕竟完成同样功能的话一个只要几十KB，另一个要几百KB甚至几MB，差别还是有点大。
基于以上考虑，决定对 MinGW 系统尝试做点小升级。
对于宽字符流的支持问题，可以换用其他STL库如 STLport。不过不换而直接使用 API 搞定字符转换也麻烦不到哪去。新的 GCC 可以自己编译着试试。
为了编译 GCC 得先编译安装 GMP 和 MPFR 库，比较简单
cd gmp-x.x.x/
mkdir build & cd build
../configure --prefix=/mingw --disable-shared
make
make check (可选)
make install
编译时间还真长，可以看集动画片了。
然后 MPFR 库类似。make 好后只要通过 check 应该就没什么问题了。
麻烦的在编译 GCC ，参数真叫一个多，看半天了 documentation 。这个不敢马虎，毕竟设错的话再来一遍要好久...
GCC 的编译正常来要3遍：第1遍用原GCC编译，第2遍用刚生成的 GCC 自己编译自己，第3遍用第2遍生成的继续编译。如果第2遍和第3遍生成的二进制代码一致则编译成功。
可惜试了三次都没完成。几乎都死在 第2遍编译 上了，似乎环境设置哪里还有问题。然后上 MinGW 官网发现已经有发布预编译过的 4.3.0 版了，晕早发现就不去自己编译了，不然后面还有 libstdc++ ，任务量依然很大。
然后咱就偷懒只下了 gcc-part-core-4.3.0-mingw32-bin 和 gcc-part-g++-4.3.0-mingw32-bin 两个包，看说明只用覆盖即可。结果编译一个带 iostream 的程序就出问题，一堆头文件说找不到。不得已继续搜，发现去年都已经有人问了，回答是那两个包里文件选择有bug ，得去下最大的包自己把缺的文件挑出来 = =。我X 这问题都出现快一年了你那俩包也不说修复一下。。。然后又下了最大那个包，把 lib/gcc/ming32/4.3.0/include/c++/ext 这个文件夹覆盖一下问题解决。
历尽艰险终于用上 GCC 4.3.0 了。。。先别忙着庆祝，稍微编个小程序，结果发现与 3.4.5 版相比生成的文件体积又大了几乎一倍 = =，执行速度嘛就上次那个计算量很大的 ditch 试了一下，确实快了不少 -O3 参数与 VC 编译的相比差距只在 20% 以内，不过这体积嘛 52KB vs. 9KB ...
又试了下 wcout 似乎可以用，至少编译顺利通过，locale 好像也能使用，只可惜一运行仍然不正常，说程序运行时不正常关闭 - -。看来还得找 STLport ...
总之感觉 MinGW 上 4.3.0 版还是不够成熟，看官方文档似乎打算把 GCC 4.3.1 版作为新的 official release 在半年后发布，希望到那时能解决些问题吧。不过 wchar stream 咱就不奢望了。
算了，有空再试 STLport + Boost。以前用 VC 编译过一遍 boost。同时用两套系统还是挺麻烦的，同一套库也得准备两遍 - - 2009年5月 从 std::list 中 size() 的时间复杂度引出的讨论...http://dantvt.is-programmer.com/posts/8313 两边同步吧... 很奇怪的，或者说是一个不应成为问题的问题... #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() 的代码。 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() 的效率问题，没想到却扯出这么一桩事出来...也算长知识了吧 2009年5月 VC 在 Win32 平台还是强啊小试一下 MinGW，最简单装的 5.1.4 版。看了下附带 GCC 是 3.4.5，只是06年的版本，应该是考虑稳定性的问题。现在 GCC 已经 4.4.0 了吧。
试着编译一个 iostream 输入输出的小程序居然有 400+ KB... strip 后还有 270+...
然后把前面做题目的程序试了下，只用 cstdio 的 fscanf fprintf 倒是体积小了很多只有 20KB+，虽然用了 -O3 但是效率比起 VS2008 编译的还是有挺大差距。拿 VS2008 与前两年的 GCC 比是挺不厚道，不过咱也只是随便试试而已。
果然在 Win 平台下 VC 很无敌... 2009年4月 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的数组，第一遍求所有质数(顺便将不是质数的值存为下标方便遍历)，然后筛选数字和满足条件的数，同样使下标形成链表方便遍历。同时选出各位数字满足条件的组合预先存起来，剩下只用循环便是。排序嘛，就每位挨个判断了，也没几个数。 2009年4月 VC 中的 STL string 实现今天小实验一下发现 VC9 的 STL string 实现中没有使用 引用计数和写时拷贝
在 VC6.0 时默认还是有这两个特性的，从 VC7.0 开始貌似就取消了，大概是考虑到线程安全问题
如果我不用多线程，这两个特性应该还是可以一定程度上提高效率的吧
不然在返回一个 string 时是否也要考虑用 auto_ptr 了呢...
看来有必要自己实现一个 string ，或者偶尔考虑用一下其他库的...
不过从一致性考虑，感觉还是显式使用智能指针实现以上功能比较好，不然其他各种自定类型是不是也有必要封装一个 share_ptr 类似特性呢。 2009年4月 USACO 4.2.1 Ditch 网络最大流问题算法小结http://dantvt.is-programmer.com/posts/7974.html 通过 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 的非递归版本代码，网络采用邻接表 + 反向弧指针：
2009年3月 Sound Horizon - Elysion ～楽園幻想物語組曲～译文转自Popgo
对歌词的说明： 演出： ========================================= 01. EL的乐园 [→ Side：E →] ========================================= 02. Ark ========================================= 03. EL的画册 【魔女与Lafrenze】 ========================================= 04. Baroque ========================================= 05. EL的肖像 ========================================= 06. Yield ========================================= 07. EL的天秤 ========================================= 08. Sacrifice ========================================= 09. EL的画册 【吹笛人与游行队】 ========================================= 10. StarDust ========================================= 11. EL的乐园 [→ Side：A →] ========================================= 44. Ending =========================================== 2009年3月 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++ 的风格吧 2009年3月 C++ STL IO流 与 Unicode (UTF-16 UTF-8) 的协同工作凡用到文件读写，输入输出，就得和编码、Unicode 打交道。这系列实验来测试一下 C++ STL 的 IO流 对 ANSI 编码、Unicode 编码的支持特性，看能否找到一个自动识别编码，自动转码的解决方案。从基础开始，一步一步来：
平台 Win32 XP sp3 + VS2008. (+ Boost 1.36.0)
实验 01:
#include<string>
#include<iostream> #include<locale> using namespace std;
locale prevloc;
locale loc("chs"); string str1("string class");
string str2("汉字与字符"); wstring wstr1(L"wstring class"); //去掉L前缀则编译错误 wstring wstr2(L"汉字与字符"); prevloc = cout.imbue(locale(""));
cout<<"Default Locale: "<<prevloc.name()<<endl; cout<<"System Locale: "<<locale("").name()<<endl; cout<<"C风格字符串\n"<<L"w-string\n"<<str1<<'\n'<<str2<<'\n'<<endl; prevloc = wcout.imbue(loc); //若去掉此句，则wstr2无法正常输出
wcout<<"Default Locale: "<<prevloc.name().c_str()<<endl; //若不加 .c_str() 则编译错误 wcout<<"chs Locale Name: "<<loc.name().c_str()<<endl; wcout<<"C-string\n"<<"C风格字符串\n"<<L"宽字符串\n"<<wstr1<<'\n'<<wstr2<<'\n'<<endl; 结论：
1.cout 与 string 配合使用，wcout 与 wstring 配合使用，交错则编译错误(类型问题)
2.wstring 初始化时需用 L"xxx" 的宽字符形式，同样 string 初始化时不能加 L 前缀 3.默认locale ("C")下 cout 可以正常输出 C风格字符串与std::string类型，包括汉字也能正常显示 但对 L"xxx" 宽字符串无能为力 默认locale ("C")下 wcout 不能输出中文，包括C风格字符串、宽字符串与std::wstring 设定系统 locale ("chs")后，正常输出宽字符串与std::wstring，但 C风格字符串 中的汉字无法显示 总之，string cout "C-style 字符串" 自成体系
wstring wcout L"宽字符串" 自成体系，但 wcout 要选择 locale 后才能正常输出中文。
实验 02:
cout.imbue(locale(""));
wcout.imbue(locale("")); string str3 ( "abc汉字");
wstring wstr3(L"abc汉字"); cout<<"str1 length: "<<str1.length()<<'\n'; // 12
cout<<"str2 length: "<<str2.length()<<'\n'; // 10 cout<<"str3 length: "<<str3.length()<<'\n'; // 7 cout<<str2[0]<<' '<<str2[1]<<'\n'; // 输出：? cout<<endl; wcout<<L"wstr1 length: "<<wstr1.length()<<'\n'; // 13
wcout<<L"wstr2 length: "<<wstr2.length()<<'\n'; // 5 wcout<<L"wstr3 length: "<<wstr3.length()<<'\n'; // 5 wcout<<wstr2[0]<<' '<<wstr2[1]<<'\n'; // 输出：汉 字 结论：
4.std::string 内部以 char 类型储存字符，当有汉字时以双字节存储，此时 length() 给出
字符串所占字节数而不是字符数 std::wstring 内部以 wchar_t 类型存储字符，字母汉字统一都是双字节，此时 length() 给出是正确的字符数。 5.当std::string中有汉字存在时，通过下标访问不能得到正确的字符。这是显而易见的， 一方面字符宽度不统一无法随机访问，另一方面 std::string[] 返回 char 类型。std::wstring 不存在此问题。
实验 03:
// test.txt 为 ANSI 编码(GB2312)，内容为以上 str1 ~ str3 的3行。
#include<fstream>
string str;
wstring wstr; ifstream fin("test.txt");
//fin.imbue(locale("")); while(fin>>str) cout<<str<<'\n'; fin.close(); wifstream wfin("test.txt");
//wfin.imbue(locale("")); //wfin.imbue(locale(".936"));
while(wfin>>wstr) wcout<<wstr<<'\n'; wfin.close(); 结论：
6.std::ifstream 读取 ANSI 编码正常，std::wifstream 读取 ANSI 编码错误...默认 locale("C") 不能识别中文字符
std::wifstream 设置 imbue(locale("")) 或 locale(".936") 后正常读取。936 为 GB2312 的代码页。 实验 04:
test.txt 为 Shift-JIS 编码，内容为 うみねこのなく頃に 程序代码同实验3 ifstream 输出为
偆傒偹偙偺側偔崰偵 wifstream 设定 imbue(locale("")) 后输出相同 结论：
7.显而易见的，其他地区的编码无法正确识别。这也是很多日本游戏和文本文件运行
或读取时产生乱码的原因。 实验 05:
test.txt 为 Shift-JIS 编码，内容同上 ifstream 与 wifstream 都添加 imbue(locale("jpn")) 或 locale(".932") 932 为 Shift-JIS 的代码页
输出为： 偆傒偹偙偺側偔崰偵
うみねこのなく頃に 结论：
8.这里可以看出一个显著性差异。wifstream 在读取时按照 Shift-JIS 编码将其转换为
Unicode 储存，在 wcout 输出时又按照 ANSI (GB2312) 转换，其结果是 —— 正确显示 了其他地区编码的字符。而 ifstream 与 cout 则缺少那两步转换，结果与上例相同
以后的实验将不再考虑 ifstream 而只实验 wifstream。
实验 06:
test.txt 存为 UTF-16 编码(Win32 默认的 little endian)，内容同上。 wifstream 设定为 imbue(locale(".1200")) 1200 为 UTF-16 的 code page 结果，运行出错...发现是 imbue(locale(".1200")); 这句的问题
试着将 ".1200" 改为 ".936" 则运行正常，输出乱码。(936是 GB2312 的代码页) 翻 MSDN 时在 Code Page 那页1200 UTF-16 后面发现一行小字： "available only to managed applications"...郁闷 看来用 locale 转Unicode的想法到此结束了？记得 STL 书中貌似说过，locale 的名 字在各平台上是不统一的，因为关系到各平台的支持问题。这样的话，要么自己写 代码，要么就只好用 API 显式转换了：MultiByteToWideChar 另外，在 setlocale 函数说明中也写到，UTF-8 和 UTF-7 等每字符有可能大于2字节
的编码不被支持，所以 UTF-8 也只能用 MultiByteToWideChar 转咯... 目前大概只能得出结论 C++ STL locale 在 Win32 平台上支持不完善吧 实验 07: 用 API 重写读文件部分代码
#include<windows.h>
HANDLE hFile; if(INVALID_HANDLE_VALUE != (hFile = CreateFileW(L"test.txt", GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, 0, NULL))){ int iFileLength, iUniTest, i; iFileLength = GetFileSize(hFile,NULL); char *pBuffer, *pText; pBuffer = new char[iFileLength+2]; DWORD dwBytesRead; ReadFile(hFile,pBuffer,iFileLength,&dwBytesRead,NULL); CloseHandle(hFile); pBuffer[iFileLength] = '\0'; pBuffer[iFileLength + 1] = '\0'; iUniTest = IS_TEXT_UNICODE_SIGNATURE | IS_TEXT_UNICODE_REVERSE_SIGNATURE;
if(IsTextUnicode(pBuffer,iFileLength,&iUniTest)){ pText = pBuffer + 2; iFileLength -= 2; if(iUniTest & IS_TEXT_UNICODE_REVERSE_SIGNATURE){ for(i = 0;i < iFileLength; i+=2) swap(pText[i],pText[i+1]); } wstr = (wchar_t*)(pBuffer+2); } delete [] pBuffer; wcout<<wstr<<'\n';
} 输出正确。以上程序段自动识别 Unicode 编码文件开头的 0xFFFE 标记判断是 Little Endian 还是
Big Endian 并做相应转换。但是代码量较大，且与 C++ 的 IO流 很不搭调...
结论：
9.可以看到，只是把输入内容去掉UTF-16开头的0xFFFE，直接把内存指针改为
wchar_t* 后 std::wstring 即可正确识别，说明程序中的宽字符存储格式实际上用的就是 UTF-16 little endian 实验 08:
不死心又去翻了 boost 库，发现 codecvt_null 这个好东西，看下实现是把文件存储内容 按照 wchar_t 为单位直接读入内存不做任何转换。这其实不正好是 UTF-16 需要做的么 以下把 test.txt 存为 UTF-16 little endian 再次实验 #include<boost/archive/codecvt_null.hpp>
wifstream wfin(L"test.txt"); locale utf16(loc, new boost::archive::codecvt_null<wchar_t>); wfin.imbue(utf16); while(wfin>>wstr){ wcout<<wstr<<endl; }
wfin.close(); 输出正确。
结论：
10. 看来可以把 codecvt_null 作为 UTF-16 的 codecvt_facet 读入 locale
来使用，避免使用类似上面 API 那么多代码。 实验 09:
将 test.txt 存为 UTF-16 Big Endian ,内容不变。程序不变 无法输出任何内容。
结论：
11. wcout 不认识 big endian 的 wchar_t ...
看来想读取 UTF-16 Big Endian，仅靠 codecvt_null 还不够。稍微翻了一下
《C++ 输入输出流与本地化》这本书，现在可以考虑写一个自己的 codecvt_facet
了。有了 codecvt_null 的代码，稍作改动即可用于 UTF-16 big endian。虽说有了
现在的知识自己写个 utf-16 的codecvt_facet 也可以，但效率大概比不上 boost 里的。
代码准备：用类似的方法写出了自己的 codecvt_utf16 和 codecvt_utf16_reverse 两个
codecvt_facet...然后继续实验。自己写的内容放入咱自己的头文件吧：codecvt_utf.h，
内容加入自己的 namespace : tvt
实验 10: 用 codecvt_utf.h 代替 codecvt_null.hpp。用 codecvt_utf16 和
codecvt_utf16_reverse 实现 little endian 与 big endian 的输入。 wifstream wfin(L"test.txt"); locale utf16(loc,new tvt::codecvt_utf16<wchar_t>); wfin.imbue(utf16); while(wfin>>wstr){ wcout<<wstr<<endl; }
wfin.close(); ///////////////////////////////////////
wifstream wfin(L"test.txt");
locale utf16(loc,new tvt::codecvt_utf16_reverse<wchar_t>); wfin.imbue(utf16); while(wfin>>wstr){ wcout<<wstr<<endl; }
wfin.close(); 第一段程序读取 UTF-16 little endian 编码的 text.txt 正确输出
第二段程序读取 UTF-16 big endian 编码的 text.txt 正确输出
UTF-16 的转码顺利完成。下面考虑 UTF-8 ，写法类似。在 boost 库中继续寻找，发现
这个东东 boost/detail/utf8_codecvt_facet.hpp 。看下说明，不支持直接使用此文件，这文件
是专门提供其他 boost 组件使用的。仅 include 它的话编译出问题。再寻找到同名的 cpp 文件
后即可看到 do_in do_out 这两个转码关键的虚函数。有了上面 UTF-16 的基础，我们类似可写
出 UTF-8 的转码 codecvt_facet。我给他起名为 codecvt_utf8, 依然加入 codecvt_utf.h 文件。
现在此文件有一两百行了。经试验可正确输入 UTF-8 编码。
对应编码有了处理方法后，下一个问题是编码识别。
实验 11:
wchar_t wc;
wchar_t buf[2]; wifstream wfin(L"text.txt");
wfin.read(&wc,1);
wfin.read(&buf[0],2);
将 wc 和 buf 的内容按2进制或16进制输出。
结论：
12. wistream.read(buffer,count) 操作每次读入 count 个字节，但将每个字节存入一个
wchar_t 类型的 buffer[i] 中。其实 buffer 中每个 wchar_t 的高位都字节是 0 ... 实验 12:
加入判断条件，在 wfin 中自动加入合适的 utf16 facet，使得自动识别并读取 little endian 和 big endian 编码的文件： wchar_t buf[2]; wifstream wfin(L"test.txt"); wfin.read(buf,2); if(buf[0] == wchar_t(0xFF) && buf[1] == wchar_t(0xFE)){ cout<<"little endian"<<endl; wfin.imbue(locale(loc,new tvt::codecvt_utf16<wchar_t>)); } else if(buf[0] == wchar_t(0xFE) && buf[1] == wchar_t(0xFF)){ cout<<"big endian"<<endl; wfin.imbue(locale(loc,new tvt::codecvt_utf16_reverse<wchar_t>)); } while(wfin>>wstr){ wcout<<wstr<<endl; } 对于两种编码的 text.txt 都实现了自动识别并正确读取。输出正确！
结论：
13.UFT-16在传输时几乎都会加上 0xFFFE 等传输标志很容易判断，即使没有， Win32 下
也有 IsTextUnicode 这 API 用专门方法判断。UTF-8 就很麻烦了，开头不一定都有 BOM 标 记，与各地区字符集一样都可以用一个或多字节表示一个字符，编码长度不固定，如果是
很长一段 ASCII 字符，那么用 UTF-8 和 GB2312 编码出来结果一样，就很难分辨
代码准备：经过一段时间思考，打算用这种算法。先读取前3字节，若是 BOM 头标记最好。若
不是则排除 UTF-16 ，下面集中力量分辨 UTF-8 与 ANSI 。从头开始寻找第一个 >127 的字节
若此字节内容 < 0xC0 或 >0xEF 则可判断不是 UTF-8 。否则，根据 UTF-8 的规则，在后面1 或
2 字节中看开头两位是不是 10 。若不是则断定不是 UTF-8 ，否则就算得到一个 UTF-8 字符。
如果能够找到 10个 满足条件的 UTF-8 字符就判断为 UTF-8 编码。若未到 10 个即遇到文件结
尾，那么找到 UTF-8 字符数大于 1 即断定为 UTF-8 否则断定为 ANSI ...
用这种方式选择对应转码 facet:
wistrm.imbue(std::locale(wistrm.getloc(), new codecvt_utf8));
按以上想法写成函数 int IsStreamUnicode(std::wistream &wistrm); UTF-16 LE 返回1，BE 返回2，
UTF-8 返回3，否则返回 0 (判断为ANSI)
实验 13:
std::wifstream wfin(L"test.txt");
if(!tvt::IsStreamUnicode(wfin)) wfin.imbue(loc); while(wfin>>wstr) wcout<<wstr<<endl; 在我试验的各种情况下，均能自动识别 UTF-16 LE UTF-16 BE UTF-8 与 ANSI 编码
并正确设定转码 locale . -------------------------------------------------------------------------------------
8小时后，关于后续实验的补充：
使用中发现某些情况下 UTF-16 的读写出现问题，特别是有换行符或某字节中编码刚好
等于控制符时。经过反复测试认定是 读写mode 问题。在读写 Unicode 文件时，
wifstream 与 wofstream 都设定为 ios_base::binary 模式即可。后来又补充了一个添加
BOM 头的小东西。为了使用简便把 utf_16 的 template 也去掉了。最终情形使用起来
像这个样子：
#include<iostream>
#include<fstream>
#include<codecvt_utf.h>
using namespace std;
wstring wstr;
wcout.imbue(locale(""));
// Open the Input and Output Files:
std::wifstream wfin(L"test.txt", ios_base::binary);
std::wofstream wfout(L"testout.txt", ios_base::binary); // Set Output Format and Write BOM tag:
wfout.imbue(locale(locale(""), new tvt::codecvt_utf16)); wfout<<tvt::utf_bom;
// Detect the Format of the Input File
if(!tvt::IsStreamUnicode(wfin))
wfin.imbue(locale("")); // Read and Write
//while(wfin>>wstr){
// wcout<<wstr<<endl; // wfout<<wstr<<endl; //} // Another way:
while(getline(wfin,wstr)){
wcout<<wstr<<endl; wfout<<wstr<<endl; } // Close Files:
wfin.close();
wfout.close(); 读写测试全部通过！
感谢 记事本、EditPlus 和 HxDen 的大力支持...
至此，关于 Unicode 编码和 C++ STL IO流 的协作算是大功告成了吧，呵呵。以后有需要再 在实践中改进
花了整整一天时间 + 8 小时 = = 还算有价值吧，因为在网上看到很多人都在问且没有结果 ===========分隔线============
再加一点关于 locale 的使用总结
另附：现在来看用 c++ 的 IO stream locale 系列实现转码并不是一个经济的选择，如果用 STLport 的话还好些，用 VC STL 则存在较严重的效率问题：
2009年3月 Python os.walk() 函数中的陷阱用 VC 写程序多了会留下很多中间文件和辅助文件，浪费不少空间，一个个去清理项目又费时费力，写个脚本吧，以后也好用。
然后想当然的写下了这样的语句：
for root, dirs, files in os.walk(path):
for name in files: if splitext(name)[1] == '.sln': print "Cleaning",join(root,splitext(name)[0]),"..." dirs = [] CleanSolution(root,splitext(name)[0]) 在某文件夹下发现 '.sln' 项目文件则不需再往下层文件夹寻找。根据 os.walk() 函数的解释，在循环中修改 dirs 变量即可控制下层递归访问的文件夹，语句 dirs = [] 把 dirs 置空，则递归访问应到此结束。但是在跟踪执行中发现，虽然 dirs 确实被置空了，os.walk() 的递归访问却并没有终止，仍然依次访问了下层的所有文件夹...为什么呢？
尝试着把 dirs = [] 改为 for dir in dirs: dirs.remove(dir) 后运行得到了理想的结果
但为何 remove() 函数可以，赋值却不行？猛然间想到以前实验的一个例子：
例一：
>>> a = [1,2,3]
>>> b = a >>> b.remove(2) >>> a [1, 3] 此例很能说明问题，虽然在 b 上执行了 remove(2) 操作，但 a 中的元素也被改动了，说明 b = a 实际上并没有复制 list 中的元素，而只是相当于把一个指针传给了 b，a、b实际都指向同一个 list
例二：
>>> a = [1,2,3]
>>> b = a >>> b = [] >>> a [1, 2, 3] 有了上例的基础再看这个应当很好理解了，b = [] 只相当于把一个空 list 的指针给了 b，a 中的元素自然不受影响
例三：
>>> a = [1,2,3]
>>> b = a >>> b[:] = [] >>> a [] 只是把 b 变成了 b[:]，这次 a 中的元素被全部清空
最后再次回到一开始的 os.walk() 上，递归中 dirs 实际上是以类似 b = 内部 list 的形式得到了所有子文件夹列表，dirs = [] 就不会有任何结果了。把程序改为
dirs[:] = [] 或
del dirs[:]
即可正确实现。
看来还是实践比较有锻炼效果，以前专门注意过 list 的赋值动作，结果这次藏在 os.walk() 函数中依然没有发现，造成了潜在错误…
PS. 脚本挺好用，居然腾出了 1GB 多空间 2009年2月 最小环 与 FloydFloyd 的 改进写法可以解决最小环问题，时间复杂度依然是 O(n^3)，储存结构也是邻接矩阵
int mincircle = infinity;
Dist = Graph;
for(int k=0;k<nVertex;++k){ //新增部分:
for(int i=0;i<k;++i) for(int j=0;j<i;++j) mincircle = min(mincircle,Dist[i][j]+Graph[j][k]+Graph[k][i]); //通常的 floyd 部分:
for(int i=0;i<nVertex;++i)
for(int j=0;j<i;++j){ int temp = Dist[i][k] + Disk[k][j];
if(temp < Dist[i][j])
Dist[i][j] = Dist[j][i] = temp;
}
} 上面是对无向图的情况。
Floyd 算法保证了最外层循环到 k 时所有顶点间已求得以 0…k-1 为中间点的最短路径。一个环至少有3个顶点，设某环编号最大的顶点为 L ，在环中直接与之相连的两个顶点编号分别为 M 和 N (M,N < L)，则最大编号为 L 的最小环长度即为 Graph(M,L) + Graph(N,L) + Dist(M,N) ，其中 Dist(M,N) 表示以 0…L-1 号顶点为中间点时的最短路径，刚好符合 Floyd 算法最外层循环到 k=L 时的情况，则此时对 M 和 N 循环所有编号小于 L 的顶点组合即可找到最大编号为 L 的最小环。再经过最外层 k 的循环，即可找到整个图的最小环。
若是有向图，只需稍作改动。注意考虑有向图中2顶点即可组成环的情况。 |
|
|
