Jun
14
算是续上篇文章吧。
上篇文章最后我有一个不是太好的总结(当然,在上一篇应该成立):
我们知道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。
上篇文章最后我有一个不是太好的总结(当然,在上一篇应该成立):
引用
结论:在大多数情况下,我们可以迷信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
看过《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之父对效率的迷信。
--------------------
下附测试代码:
但是某一次和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
14
也许你听过所谓"标准"答案:因为圆形的井盖不会掉下去。
但是也许不需要考虑这么深这么复杂,从适配器模式的角度考虑,你只要这么回答就可以了:
其实很简单,因为井口是圆的,它提供了一个圆形的接口,所以它期望一个圆形的盖子,由此你不得不设计一个圆形的井盖。
方形的盖子也许容易掉下去,但是那不是主要问题,现在的问题是,方形的盖子不适合盖圆形的井口。
--
虽然今天要早起,但是还是一不小心看了太多东西,比如上面这个回答就是在"云风的Blog"的这篇文章的评论里面看到的:
http://blog.codingnow.com/2008/06/object_oriented.html
很有收获。
另外google了一下这个回答,看到另一个搞笑的(或者很有深度的?),顺便帖出来:
但是也许不需要考虑这么深这么复杂,从适配器模式的角度考虑,你只要这么回答就可以了:
其实很简单,因为井口是圆的,它提供了一个圆形的接口,所以它期望一个圆形的盖子,由此你不得不设计一个圆形的井盖。
方形的盖子也许容易掉下去,但是那不是主要问题,现在的问题是,方形的盖子不适合盖圆形的井口。
--
虽然今天要早起,但是还是一不小心看了太多东西,比如上面这个回答就是在"云风的Blog"的这篇文章的评论里面看到的:
http://blog.codingnow.com/2008/06/object_oriented.html
很有收获。
另外google了一下这个回答,看到另一个搞笑的(或者很有深度的?),顺便帖出来:
Jun
13
花了一点时间测试使用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()
#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
7
写了一点代码来判断astar公开的代码中任意两段代码的相似性。
最关键的是求字符串的编辑距离,O(N^2),很慢。
于是跑了6个小时,还是2台机器、多个进程同时运行。
但是那个囧到我的astarAnticheat则很快就cha到了我的代码。
问了他怎么回事,然后发现自己做了很挫很挫的事情(详见聊天记录,后附)。
附上用来判相似的代码:
聊天记录如下:
最关键的是求字符串的编辑距离,O(N^2),很慢。
于是跑了6个小时,还是2台机器、多个进程同时运行。
但是那个囧到我的astarAnticheat则很快就cha到了我的代码。
问了他怎么回事,然后发现自己做了很挫很挫的事情(详见聊天记录,后附)。
附上用来判相似的代码:
下载文件 (已下载 1480 次)
聊天记录如下:
Jun
6
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
和上一篇文章内容接近,或者解释更清晰一些 :)
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
和上一篇文章内容接近,或者解释更清晰一些 :)
Jun
2
之前写了一篇 myftp: 一个linux下简单的ftp客户端实现
里面详细介绍了ftp协议的基本工作过程。
为了明天晚上的Windows下的程序,于是把它移植到了Win32下面。
然后异常庆幸我当时做了多么明智的封装啊,只要稍稍改几行就可以在windows下面编译了 :D
这个压缩包在Windows和Linux下面都可以直接make编译了哈^_^
不过这次的修改只是增加跨平台编译,没有修正myftp的BUG,仅供参考 :D
里面详细介绍了ftp协议的基本工作过程。
为了明天晚上的Windows下的程序,于是把它移植到了Win32下面。
然后异常庆幸我当时做了多么明智的封装啊,只要稍稍改几行就可以在windows下面编译了 :D
这个压缩包在Windows和Linux下面都可以直接make编译了哈^_^
不过这次的修改只是增加跨平台编译,没有修正myftp的BUG,仅供参考 :D
下载文件 (已下载 1480 次)
Jun
1
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实现使用分两段的可能性,但是这个效率恐怕就不太对劲了。
class mystack: public stack<int>{
public:
int & operator[](unsigned int i){
return c[i];
}
};
public:
int & operator[](unsigned int i){
return c[i];
}
};
很happy,哈哈。
刚刚看 /usr/include/c++/4.3/bits/stl_stack.h
发现原来stack和queue使用的底层容器默认是deque,名字是c, 而且是protected
@ 2009-06-29 p.s.
其实这是件很挫的事情,STL容器的析构函数不是虚函数,继承自他们的子类的析构函数不会被调用,有可能导致内存泄露。
2。
class t: public deque<char>{
public:
void printBufSize(){
std::cout << __deque_buf_size(sizeof(char)) << endl;
}
};
public:
void printBufSize(){
std::cout << __deque_buf_size(sizeof(char)) << endl;
}
};
看侯捷大神的《STL源码剖析》以及GCC的STL源码后凑出来的这一段代码。调用 printBufSize() 后输出应该是512。
这个要追溯到一周前和sandy的一个小争论。
记得以前看到过deque的底层实现是分多段连续空间的,以达到高效的首尾增删以及可以接受的随机访问效率
输出的这个512就是SGI STL的默认分段大小。
但是sandy却说,所谓的“分段连续”实际上是分成两段 (听起来就觉得不太对头 -__- )
于是今天特地翻出这本书膜拜一下。当然,不排除其他STL实现使用分两段的可能性,但是这个效率恐怕就不太对劲了。