入职满月零八天

果然开始工作了就没多少时间了呢。。。

熟悉环境 + 学新知识。 某些东西还是不要丢下的好……

USACO 5.4.4 Betsy’s Tour

好吧好久没写，果然变懒了 = = 简略点好了

N x N 方阵，左上角入，左下角出，只能上下左右相邻移动，每格仅访问一次遍历所有格，求遍历方法数。

暴力 + 剪枝，没想出什么别的方法。最多就位运算优化一下：

   Test 1: TEST OK [0.000 secs, 2900 KB]
   Test 2: TEST OK [0.000 secs, 2900 KB]
   Test 3: TEST OK [0.000 secs, 2900 KB]
   Test 4: TEST OK [0.000 secs, 2900 KB]
   Test 5: TEST OK [0.000 secs, 2900 KB]
   Test 6: TEST OK [0.000 secs, 2900 KB]
   Test 7: TEST OK [0.162 secs, 2900 KB]

All tests OK.

N = 7 的时候在 0.162 秒貌似还不错，嗯。

代码嘛……算了不贴了。在 wordpress 上贴代码各种麻烦。研究一下再说

Hello world!

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!

Upgrade your blog to WordPress.com!

微软终于撑不下去了，在互联网方面真是做啥啥不行。。。
果然还是早点迁走为好吗

至少先把列表保存一下 = =
虽然也好久没更新了

[转]恋爱就像TCP连接

原帖

这个挺搞笑的，TCP三次握手也不顶用

VS2010

VS2010 RTM 了
对 C++ 的支持应该是最近几个版本中改进最大的。

看了下对标准库多了个 <codecvt> 的头文件，终于从 iostream 实现了对 UTF8 UTF16LE UTF16BE 的转码支持，大概前一段我试验的那几个 codecvt_facet 也到时候了吧。不过具体效果如何(性能问题比较难说)还是等拿到再具体判断为好。
右值引用也加入标准库，然后多了个 forward_list 的单链表，几个新的 algorithm 函数，智能指针等

就我感觉类似 <codecvt> 应是 C++ 标准库很需要添加的内容，虽然公司的效率还是比较快，可是等着 C++ 标准委员会整好新标准还不知得等到猴年马月去。每次想到标准库里面的查找函数命名乱得一塌糊涂，就感觉那些个人工作效率真是低的要死。

平面最近点对与最远点对

给定平面上 N 个点的坐标，求其中最近点对与最远点对。看似相似的问题，也都可以在 O(N logN) 时间内解出，却是两种完全不同的思路

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 (0×011101110111ULL),
        maskl(0×011001100110ULL), maskr(0×001100110011ULL){
        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 即可。

今后再处理浮点数的问题时一定要相当小心咯

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 }