Kaguya Houraisan's gloriette

好长时间没做题了，拿这个来练练手...

 

时限居然有 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 了...

 

 

 

 

 

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();
}

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 即可。

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

其实关于这个问题的讨论似乎总会以类似语言信仰问题而告终，再加 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 做基准

 

首先用 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++ 的格式是通过多个连续函数调用控制的，可以在编译时即进行优化。但实践往往存在各种变数 = =

 

 

STLport 的 C 库函数完全是照搬 VC 的标准运行库，而只是重新实现了整个 C++ 库，所以 C 函数的效率与上一例是相同的，可直接横向比较。
面对这样的结果，我只能说 STLport 太赞了！！再考虑到其他的种种特性，赶紧扔掉 VC STL 全部换用 STLport 吧
不过转码看来确实是一个平台相关的特性，仍然无法比过 WinAPI 的效率

 

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 }

于是连 python 也成了关键词

哪天你把 c, java, php, 或者干脆 linux windows 都封了算了。。。

 

http://dantvt.is-programmer.com/posts/11949.html

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

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

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

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

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

2. 将文件一次性读入 stringstream 中。

filebuf 和 stringbuf 无法直接通过 rdbuf() 重定向，因此从 filebuf 到 stringbuf 需要一次 copy 操作。最简单的方法是直接复制整个 streambuf ：

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

最后再顺便 BS 一下 VC 的 STL = =...

虽然 VC 的编译器效率没的说，但被 STL 拖后腿的话不就白搭了嘛。在文件 IO 方面 (fstream) 比起 MinGW (GCC 4.4.0) 带的要慢好几倍。GCC 的 fstream 格式化读写效率与 C 的比已经不分伯仲，以后应该还会有进一步的提升空间 (编译时格式控制 vs 执行时)

另外上面最后一段程序在 VS2008 (VC9.0) 下应该无法得到预想的结果，跟踪进去看了一下，VC 标准库里的 pubsetbuf 函数体居然是空的！内容如下(中间还有一层函数调用)：

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