Latest Entries »

万恶的 xxx

于是连 python 也成了关键词
哪天你把 c, java, php, 或者干脆 linux windows 都封了算了。。。
 
Advertisements

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) 中可以得到预期的结果。

国庆愉快

Oh…换一篇,上一篇太不和谐啦
好像几天没连上
不知是不是被 GFW 了,这一段貌似封的挺紧
过了十一再看看
 
果然是被墙了.>>最近 fg U tor puff 全部失效 … TMd gcd
目前已发现 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 搞反的,还有很多印刷错误就不一一列举了。当然书的内容还是很好的,只是看的时候得小心点。。。

海猫 EP4 汉化补丁发布

庆贺!
可惜日语还是没学好,哎~

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。同时用两套系统还是挺麻烦的,同一套库也得准备两遍 – –

http://dantvt.is-programmer.com/posts/8313 两边同步吧…

很奇怪的,或者说是一个不应成为问题的问题…
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() 的效率问题,没想到却扯出这么一桩事出来…也算长知识了吧

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 很无敌…

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的数组,第一遍求所有质数(顺便将不是质数的值存为下标方便遍历),然后筛选数字和满足条件的数,同样使下标形成链表方便遍历。同时选出各位数字满足条件的组合预先存起来,剩下只用循环便是。排序嘛,就每位挨个判断了,也没几个数。