Felix021

看过《STL之父访谈录》，了解了STL之父对效率的极度迷信，因而我对STL容器的效率也是很迷信的。

但是某一次和feli聊到vector的效率问题，他说，有时候在比赛的时候用vector会TLE，换成自己写的单链表就AC了。

可惜当时是在永和门口争论的，无法验证，后来某天想到这个问题，于是验证之：

1. vector和数组的效率对比：

对一个含有100,000,000个元素的int数组进行循环10遍的写入，测试结果(使用linux下的time命令统计)为：

Array:
real  0m3.801s
user  0m3.136s
sys  0m0.568s

Vector:
real  0m4.210s
user  0m3.548s
sys  0m0.520s

可以看出，vector和Array相比，至少在acm程序中，效率损失几乎是可以忽略的。
还需要声明一点，这里的vector是在运行时动态申请的空间，而array则是预分配的。

测试程序后附。


2. 单链表的效率和STL的list效率对比：

添加10,000,000个元素，测试结果为：

单链表:
real  0m0.836s
user  0m0.620s
sys  0m0.204s

list<int>:
real  0m1.202s
user  0m1.024s
sys  0m0.168s

可以看出来，完全没必要和vector对比的，接近两个数量级的差距阿。

单链表比STL的list快并不是因为STL效率损失，而是因为STL的list是一个双向链表，可能还有更多的底层细节（具体我就不了解了）。


---------------------

所以很显然的，vector比手写的单链表快。快很多。非常多。至于原因，我觉得主要有2：

1。链表是基于指针访问的，不仅需要更多的访存，而且cache命中率会比较低。
而vector的存储空间是连续的，在连续访问的情况下，命中率会高很多。

2。链表的内存是动态申请的，每一次都使用new/malloc从系统维护的堆中进行申请，效率很低。
当然，STL的list使用了优秀的allocator，但是效率仍然和vector无法比拟，所以说明第一条才是关键。

结论：在大多数情况下，我们可以迷信STL之父对效率的迷信。


--------------------

下附测试代码：

也许你听过所谓"标准"答案：因为圆形的井盖不会掉下去。

但是也许不需要考虑这么深这么复杂，从适配器模式的角度考虑，你只要这么回答就可以了：

其实很简单，因为井口是圆的，它提供了一个圆形的接口，所以它期望一个圆形的盖子，由此你不得不设计一个圆形的井盖。

方形的盖子也许容易掉下去，但是那不是主要问题，现在的问题是，方形的盖子不适合盖圆形的井口。

--

虽然今天要早起，但是还是一不小心看了太多东西，比如上面这个回答就是在"云风的Blog"的这篇文章的评论里面看到的：

http://blog.codingnow.com/2008/06/object_oriented.html

很有收获。

另外google了一下这个回答，看到另一个搞笑的(或者很有深度的?)，顺便帖出来：

花了一点时间测试使用semaphore和pthread_mutex这两个东西，很赞。

#include<semaphore.h>
sem_init()
sem_wait()
sem_post()

#include<pthread.h>
pthread_mutex_init()
pthread_mutex_lock()
pthread_mutex_unlock()

@ 2009-06-14 0:00 p.s.
居然还有 pthread_spinlock_t .... Orz了。
pthread_spin_init()
pthread_spin_lock()
pthread_spin_unlock()

写了一点代码来判断astar公开的代码中任意两段代码的相似性。
最关键的是求字符串的编辑距离，O(N^2)，很慢。
于是跑了6个小时，还是2台机器、多个进程同时运行。
但是那个囧到我的astarAnticheat则很快就cha到了我的代码。
问了他怎么回事，然后发现自己做了很挫很挫的事情（详见聊天记录，后附）。

附上用来判相似的代码：


聊天记录如下：

1. c函数调用约定
http://blog.csdn.net/andylin02/archive/2009/04/30/4139410.aspx

对一个函数 int func(int a, int b); 当执行 func(1, 2) 的时候，它的栈结构是怎样的？
这是tx一面的时候的一个问题，我答错了。
正确的答案是:
  push 2      第二个参数入栈
  push 1      第一个参数入栈
  call function  调用参数，注意此时自动把cs:eip入栈; 如果是近程调用，那么CS是不需要入栈的。
此外，对于函数的返回是如何约定的，printf() 的不定参数列表的实现是基于什么方式。。。
详细看看这篇文章，很有收获。


2. 如果你是编程新手,你确信对系统栈结构有所了解吗？
http://blog.csdn.net/andylin02/archive/2009/04/30/4139409.aspx

和上一篇文章内容接近，或者解释更清晰一些 :)

之前写了一篇 myftp: 一个linux下简单的ftp客户端实现
里面详细介绍了ftp协议的基本工作过程。

为了明天晚上的Windows下的程序，于是把它移植到了Win32下面。
然后异常庆幸我当时做了多么明智的封装啊，只要稍稍改几行就可以在windows下面编译了 :D

这个压缩包在Windows和Linux下面都可以直接make编译了哈^_^
不过这次的修改只是增加跨平台编译，没有修正myftp的BUG，仅供参考 :D

1。

很happy，哈哈。
刚刚看 /usr/include/c++/4.3/bits/stl_stack.h
发现原来stack和queue使用的底层容器默认是deque，名字是c, 而且是protected

@ 2009-06-29 p.s.
其实这是件很挫的事情，STL容器的析构函数不是虚函数，继承自他们的子类的析构函数不会被调用，有可能导致内存泄露。

2。

看侯捷大神的《STL源码剖析》以及GCC的STL源码后凑出来的这一段代码。调用 printBufSize() 后输出应该是512。
这个要追溯到一周前和sandy的一个小争论。
记得以前看到过deque的底层实现是分多段连续空间的，以达到高效的首尾增删以及可以接受的随机访问效率
输出的这个512就是SGI STL的默认分段大小。
但是sandy却说，所谓的“分段连续”实际上是分成两段 （听起来就觉得不太对头 -__- )
于是今天特地翻出这本书膜拜一下。当然，不排除其他STL实现使用分两段的可能性，但是这个效率恐怕就不太对劲了。

东华比赛总结 By Felix021 @ 70km??

首先批一下主办方。。。整个比赛过程都好挫，包括比赛的衣服、证书、没有队牌、不发餐券、让参赛选手站在赛场外面等、打印很麻烦、工作人员不太负责、发的点心是很挫的饼干而且还是比赛快结束了才发下来（以及水）、比赛结束后就散了，证书也不知道怎么着、题目非常囧。。。。。。（400米的报名费阿，相当相当地不值得）

然后批一下自己吧。。。整个比赛过程也好挫，纠结在一道最后才有一只队伍出的数学题目上，WA了5次最后还是没过。。。严重失误，嗯。

正式过程是这样的，首先是练习赛，A+B不说了，接下来一道很麻烦的模拟题，写了100多行的代码调了半天还没调对头就结束了- -|| 不过新版本的PC^2做的很不错阿，可以直接compile & run & test，题目也直接显示在侧边，用起来很方便。

12点开始正式比赛，10道题目，我看ABCD，jieyu看EFG，yihong看HIJ。A题是求生成树的数量，yihong和jieyu都看过那篇论文，但是忘了具体怎么做。B是一个SB题，看到有队伍AC了，马上写，提交，AC。C题是一个计算几何，给出一个圆的半径和三角形的三条边，求二者可能交叉的最大面积，这题只有6提交，0AC。D题是一个概率论的题目，数学盲飘过。。E题也很囧，给你一个n，要求用加减乘除最后能组合出多少种不同的算式，0提交。F题就是我们一直纠结的那道数学题了，因式分解(x^n-1)，我和yihong想得非常深了，已经几乎完全确定没有问题了，但是最后还是WA了，非常无语。G题是一个简单的模拟，暴力一下就行了，jieyu写的，WA了一次很郁闷，我看了下他的代码，发现是边界条件写错了，改了两个地方，AC。H题比较像是线段树的题目，但是在具体实现上感觉又很困难，我写了一点写不下去了（其实根本就不该写，另一个失误），最后的rank显示这题是84提交0AC。I题是另一个数学题，要求[a,b]之间所有数字化成最小底数后的幂的和，数据量太大，没有想法。最后J题，算是计算几何吧：求钟表指针的重心从time1到time2经过的路程；这描述一看就觉得太TM复杂了，这是怎样一个弧线，算个毛阿。于是就一直没去想，但是3个小时左右的时候收到一个说明，每一秒内的运动按直线算----其实这样的话这提就比较简单了，最后AC率超过50%，不过当时一直在想F，所以没有去看那题，又一个大失误。

于是最后只出2题，Rank35，按照10%,20%,30%的比例，108支队伍，我们应该就是铜牌开始的那几个了，sigh。

总的来说这次比赛结果不太好，有两个原因：
1。偏题：题目都靠近计算几何、数学题，看不到经典的DP和图论，于是我们三个都挂了。
2。决策失误，以上详细说明了，很遗憾，否则我们至少应该能出3题。