Jun 14
回忆一下tx的二面,有一道题是这样的:

假设有1kw个身份证号,以及他们对应的数据。身份证号可能重复,要求找出出现次数最多的身份证号。
一个很显然的做法是,hash之,O(n)搞定。这前提是内存中可以存下。
如果是中国的13亿人口,内存中存不下呢?借用磁盘,多次扫描?磁盘IO的速度慢得能让你疯掉。
这时候你终于感受到,中国人口真TMD多阿。。。

--

然后再看看今天的astar复赛第一题:
Jun 14

map/set的效率 不指定

felix021 @ 2009-6-14 15:28 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(8396) | Via 本站原创
算是续上篇文章吧。

上篇文章最后我有一个不是太好的总结(当然,在上一篇应该成立):
引用
结论:在大多数情况下,我们可以迷信STL之父对效率的迷信。

我们知道vector和数组在基本操作上都是同一数量级的,而且事实上它们的常数也没有多少差别
所以我们可以放心地用vector来替换数组,不仅如此,他们在存储效率上,几乎也没有差别
一个简单的测试程序表明,存储1kw个整数,使用vector,整个程序消耗38.4MB空间,使用array,消耗38.2MB空间。

所以在这里我们可以放纵我们的迷信。

但是迷信也有限度的,就像上帝可以创造万物,但是不能创造自己。

然后进入本篇的主题:map/set的效率。

众所皆知,map/set底层数据结构是RB Tree,虽然不是真正的平衡树

但是其查找效率在统计上是比AVL等平衡树效率更高的,都能达到O(logN)的水平。Excellent。

于是我就迷信了,导致了自己对map的滥用,导致了很挫的结果。

究其原因,我忽略了那个确实很容易被忽略的东西,因为在提及复杂度的时候一般都不讲它。

——它就是传说中的那个常数。(我是不是很挫? =.=)

废话少说,数据说话:

map/set + 1,000,000个int的插入:
real  0m2.153s
user  0m1.812s
sys  0m0.056s

vector + 1,000,000个int的插入 + sort():
real  0m0.581s
user  0m0.436s
sys  0m0.016s
改成堆排sort_heap():
real  0m0.628s
user  0m0.492s
sys  0m0.016s

差别已经很明显了。

-----

然后再看看内存占用:

map: 19.4MB
vector: 4.1MB

so, hash + map用来构建hash table是我至今为止干过的最挫的事情之一了。——还不如用个vector。
Jun 14

关于vector的效率 不指定

felix021 @ 2009-6-14 03:22 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(7528) | Via 本站原创
看过《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之父对效率的迷信。


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

下附测试代码:
Jun 13

semaphore and mutex 不指定

felix021 @ 2009-6-13 01:08 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(4606) | Via 本站原创
花了一点时间测试使用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()
Jun 1

6行代码 X 2 不指定

felix021 @ 2009-6-1 13:56 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(3038) | Via 本站原创
1。
class mystack: public stack<int>{
    public:
        int & operator[](unsigned int i){
            return c[i];
        }
};

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

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

2。
class t: public deque<char>{
public:
    void printBufSize(){
        std::cout << __deque_buf_size(sizeof(char)) << endl;
    }
};

看侯捷大神的《STL源码剖析》以及GCC的STL源码后凑出来的这一段代码。调用 printBufSize() 后输出应该是512。
这个要追溯到一周前和sandy的一个小争论。
记得以前看到过deque的底层实现是分多段连续空间的,以达到高效的首尾增删以及可以接受的随机访问效率
输出的这个512就是SGI STL的默认分段大小。
但是sandy却说,所谓的“分段连续”实际上是分成两段 (听起来就觉得不太对头 -__- )
于是今天特地翻出这本书膜拜一下。当然,不排除其他STL实现使用分两段的可能性,但是这个效率恐怕就不太对劲了。
May 31
东华比赛总结 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题。
May 27
突然想写了,就写了一个。
因为调试需要,自己写了一个stack,继承vector实现(如果是继承自通用stack类的话那就是个类适配器了哦^_^)

代码如下:
May 25

国软比赛总结 不指定

felix021 @ 2009-5-25 01:58 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(4250) | Via 本站原创
很纠结地最后可以参加这个比赛了,但是这个比赛只能两个人参加,于是BFS只能拆散了。
Sandy和Boluor组队,然后我另外去找了Eire组成新队,队名70km  :D

12点左右就到了机房,结果LCY说对外通知是12:30入场>_<|| 郁闷。
然后随便找一台机器测试了一会儿,到大约12点40的时候被安排坐到team30的位置(可是我们是team51=.=)
花了一点时间把vimrc先大致敲了一点进去,和eire讲了一点vim的基本操作,敲了一个model.cpp

1点多一点点开始比赛,8道题目,可是国软这次这么小气,两个人才一份题目,orz。
于是把题目拆开,Felix负责ABCD,Eire负责EFGH。
还好是中文,看完比较快,Eire说后面四道题目貌似没有直接可以写的
然后我看到B是一个简单的BFS,C是一个更简单的模拟水题
于是直接上去敲C,结果很快就WA了,检查了一下,发现一个小错误,Submit,又WA,超郁闷。

打印代码一边检查,然后Eire看H题,我和他讨论了一下,刚开始想到记忆化搜索
但是发现不对,没有高精肯定要溢出,高精效率又太低。
于是列出一个不太严谨的式子:如果把n拆成x份,那么最后的结果是x^(n/x)(忽略小数)
然后大致证明了3是最划算的(我居然忘了怎么求导T_T 还好Eire还记得。。。)
然后又大致觉得如果是4就应该拆成2 * 2
于是顺着这个不严格证明得出的思路写代码。

其间Felix改了一下C题,又WA,检查代码发现多了一个测试的printf T_T,注释,提交,AC@35min
一个简单的C题被我搞出3个WA。。。罪人啊。。。。

很快Eire根据那个"证明"结果写出了代码,提交,1AC@42。振奋。

然后Felix看B题的BFS应该很简单,虽然Eire有点担心,但是还是毅然决然地开题
写完以后测试发现不太对,打印代码一边晾去,由Eire开始写他想得已经差不多的G题
其间Eire又转去细想,而Felix在打印的代码上面发现了几处错误
改正以后样例基本OK了,然后是最后一个不对
自己看了一下样例,发现是样例错了,于是问judge。
结果被告知出题人kid正在地大回途中,waiting。。。

于是Eire继续G题,由于roman 2 arabic的函数写得很好,然后用一个struct+stable_sort,1AC@114min
这个时候开始网络变得非常垃圾,点一个Refresh就能把PC^2卡死,超郁闷。

还好等了不是太久kid回来了,原来是他把6写成5了,不好改题目,于是就把数据改了。
然后提交之,发现TLE了,超囧。
检查了一下,发现在BFS的循环里面有错,队尾指针在某个情况下不会改变(以前没遇到过),于是很囧地进入死循环TLE
修改了以后检查了一遍,又发现一些其他的错误,一并改之,提交,WA@130+min T_T
很郁闷很郁闷地继续检查,大概160min发现原来是存名字的map在每一个case之前没有clear,超囧。
又提交一次,还是WA!郁闷啊郁闷啊郁闷。
纠结了很久,大概30min以后问了maner是不是最后一个case后面不需要再加\n
maner说,大概是。。。于是改之,提交,终于AC@196min...

剩下的四道题目和Eire讨论了一下:
A题是一个枚举+二维DP的问题,Felix能想出这个框架,但是实在是不会写DP,无奈放弃
D题状似计算几何,但是细看其实不然。Felix也想出了应用容斥原理的算法基本框架,就是不会写T_T
E题可见边——Eire很后悔地说没有带上图形学的书。。。
F题奇怪的比赛——完全没有思路,嗯。

此时70km@Rank2,仅次于momo+feli。
但是后面好几个队伍都出了3题甚至4题,估计很快就能超过我们,郁闷
更郁闷的是LCY同志宣布:由于比赛过程中网络状况比较差,比赛延长半个小时
于是我深情地拉着LCY的手说:我恨你T_T

由于最后一个半小时都没有题目可以做,于是Eire在5点多一些就先跑路了
Felix非常无聊地水了一下D题,毫无意外地TLE,于是也不再继续写了。。。。

——

最后非常意外地70km还是留在Rank2的位置。究其原因,主要有这么几点:

首先,因为从地大回来的队伍不仅推迟一个小时才开始做题,而且都太累了——毕竟写了一天的代码啊,此乃侥幸。

其次,做题策略把握得比较好——
  a) 看题,我们把所有的题目都快速扫过去,没有一看到简单的就急于做出来,
      因此在整个比赛的过程中基本上是按照从简单到难的顺序做出来,这个还是比较划算的
  b) 比赛的过程中时间安排得好。一旦觉得自己会陷入僵局的时候就打印代码换人写
      事实上确实是,在纸上看代码很容易找到代码的错误,并且往往一次能找出不止个一并改好
  c) 把自己的想法适当地和队友讨论,这样能让自己明确自己的思路,找到自己可能存在的问题,
      同时如果自己存在问题,也可以借助队友的局外人身份找出(旁观者清啊!)

再次,河蟹的队伍气氛也很重要。整个比赛过程中非常开心,无论是卡题还是AC还是WA还是TLE(其实后两个结果都是Felix的贡献T_T),都可以笑得很happy,一点沉重的气氛都没有,我觉得这对队伍比赛时的状态有非常积极的作用,让我想起的去年暑假集训的Matrix76队,气氛一向都是非常河蟹。

此外,发现自己的基础还有很大一部分不扎实,主要体现在:
1. 简单的DP不会写.....
2. 容斥原理不会写.....
3. 算法流程没有完全想清楚就开始码字.....
4. 一个BFS能写出好几个错误,边写编改.....
5. 居然能挂在初始化上面,无语啊无语啊无语。。。

以上,OVER,特别感谢队友Eire同学,嗯。
分页: 11/22 第一页 上页 6 7 8 9 10 11 12 13 14 15 下页 最后页 [ 显示模式: 摘要 | 列表 ]