Felix021

因为需要测试算法的效率，所以专门找了一下在Linux下C/C++如何取得精确的时间来进行判断。
有两个办法，
1. 调用系统命令data +%s.%N，可以取得当前的Unix时间戳，格式为 秒数.毫秒数
FILE *pipe = popen("data +%s.%N", "r");
fscanf(pipe, "%d.%d", &s, &ns);
这样就取得了精确的时间。
2. 使用gettimeofday()函数
struct timeval { long tv_sec, tv_usec; }; //这个结构体保存秒数和毫秒数(0~1000000)
int gettimeofday(struct timeval *tv,struct timezone *tz); //调用时tz一般用NULL代替

下面对第二种方法给出样例程序：Linux下测试程序运行时间的一个类

摘自boost库的文档：
Currently   the   library   contains   only   naive   implementation   of   find   algorithms   with   complexity   O(n   *   m)   where   n   is   the   size   of   the   input   sequence   and   m   is   the   size   of   the   search   sequence.   There   are   algorithms   with   complexity   O(n),   but   for   smaller   sequence   a   constant   overhead   is   rather   big.   For   small   m   < <   n   (m   by   magnitude   smaller   than   n)   the   current   implementation   provides   acceptable   efficiency.   Even   the   C++   standard   defines   the   required   complexity   for   search   algorithm   as   O(n   *   m).   It   is   possible   that   a   future   version   of   library   will   also   contain   algorithms   with   linear   complexity   as   an   option。

也就是说string::find()提供的是O(m*n)的效率，不是KMP的O(n)，很汗。。。

    在C++里，STL中string和vector的空间是可以自动增长的，但是有一个问题是，当你将它们中的元素删除(甚至是使用clear函数)时，多余的空间不会被释放，这时候可以用一个交换技巧(详见Effective STL)来清空多余的元素：

这些天花了不少时间看STL，当然也少不了看《Effective STL》这本书。
这本书讲了很多内容，我只记下了对于初学者比较容易理解和需要记住的一些重要条款：

条款4：用empty()来代替检查size()是否为0
因为size()可能需要O(n)的时间，但是empty()只需要O(1)

条款5：尽量使用区间成员函数代替它们的单元素兄弟
对于插入已知数量或已知区间的元素，使用区间版的成员函数效率高。
比如vt.insert(a, a+100000)效率将显然高于for(i=0;i<100000;i++)vt.insert(a[i]);
因为后者需要反复调用insert()并可能多次重新分配空间

今天做比赛的时候Cplus用STL的list写一个3000个vertex的图的邻接表MLE了，所以产生了测试STL容器内存占用的念头。
没下什么软件，也没用系统什么命令，就是写个程序插入500,000个元素到这些容器中，然后分别提交到WOJ 1035进行测试。
因为1035的内存限制是64M，时间限制是1000ms，所以没有用更大的数据进行测试，但是测试结果确实能说明一些问题了：

实测环境:WOJ 1035 BG
数据量: 500,000个int(map使用的是<int,int>)
结果:
容器    内存占用    时间
array  3060K      4ms
deque  3200K      15ms
queue  3204K      19ms
stack  3204K      19ms
vector 5168K      14ms
priority_queue 5172K  650ms
list   16768K     132ms
set    24584K     922ms
map<int,int> 24584K   913ms

不知道为什么list会占用那么大的空间，看来以后对list的使用要谨慎再谨慎了。

VC6_基于对话框MFC程序最基础教程示例～

by Sandy_zc_1  

（说实话我觉得发这帖子很不像我的风格，倒是Felix经常给别人写示例。不过最近有学弟学妹们学习MFC啊，就借个地方把之前自己写的这些东西放上来给他们参考吧）

前段时间为了教几个学弟学妹们写的几个最基本的MFC简单例子，

只适合刚学过C，完全没有接触过VC6，想MFC入门的同志，稍微有点基础的就不要看了～～

共5个例子，每个中都有说明文件，按顺序看完跟着做完，自己再练一下基本就可以掌握了。

因为Vista挂掉的原因使得我Wubi安装的Ubuntu 8.04 Hardy启动后只能引导到一个叫做什么Busybox的sh shell界面，没有读取root.disk，上网搜了一下，有一个解决办法是，打开grub的menu.lst，或者直接在grub界面按e进入修改模式，找到这一行：
kernel    /boot/vmlinuz-2.6.24-21-generic root=UUID=2874D2DE74D2AE36 loop=/ubuntu/disks/root.disk ro quiet splash
删掉quiet splash, 换成irqpoll  回车，按下b键(boot)然后等两三分钟，终于进入了可爱的Ubuntu...

地址：
http://developer.berlios.de/project/showfiles.php?group_id=8724&release_id=14679