Jun
14
nth element, 也就是要找出一个数列中排名第n的那个数。
很直观地，把所有的数排序以后，就可以得出这nth element了。
快排测试：4.5s，1千万个int。
仔细想一下，这似乎有点浪费：其实只要找出最大的n个就行了。
如果n比较小，我们可以直接用选择排序。
这个程序太简单了，懒得测试。
然后再仔细想一下，发现还是有点浪费，其实前n个数不需要排序。
于是可以用最小堆来实现。
测试结果：3.02s，1千万个int，n = 500。
然后你可能会发现，STL里面有个函数，叫做nth_element，就是用来做这个的
测试一下：3.4s，1千万个int, n = 500。
如果想要深入了解，那么实际上这个nth_element使用的算法是快速划分。
它其实就是不完全的快速排序，只要递归地排序需要排序的部分就可以了。
自写代码测试：3.4s，1千万个int, n = 500。
------
从上面可以看出，在k=500（N = 10,000,000)时，最小堆是最快的，其次是快速划分，快排当然最慢。
最小堆的时间复杂度是 O( N * log(k) )
快速划分虽然平均时间复杂度是O(C*N)（但是C比较大），但是最坏时间复杂度是O(N^2)（所以随机化很重要！可以避免RPWT！）
快排就不用说了，撑死 O(N * log(N) )，最坏时间复杂度也可能是O(N^2)。
似乎最小堆是最快的，快速划分慢些，但是它们各有自己的适用范围：
当 k 接近 N / 2时，最小堆的时间复杂度其实就相当于一个堆排，事实上还不如快排。
所以最小堆的适用范围是k << N时的情况，或者当k 很接近N， 可以转化成 N-k << N的情况。
而快速划分的算法本身决定了其复杂度和 k 的大小无关，所以当 k 接近 N/2 时，快速划分显然更优。
可是还有另一种情况，也是大公司面试的时候很可能会问到的题目：
给你200亿个整数，找出TOP500000。
第一次遇到这个问题，估计大多数人直接口突白沫了吧。
200亿，对一般PC而言，内存显然存不下，需要保存在辅存中，而辅存的IO速度。。。
所以你应该尽可能少地扫描。
于是这时候最小堆就是最优解决方案：只扫描一遍，就可以得出结果。
------
代码如下：
很直观地，把所有的数排序以后，就可以得出这nth element了。
快排测试：4.5s，1千万个int。
仔细想一下，这似乎有点浪费：其实只要找出最大的n个就行了。
如果n比较小，我们可以直接用选择排序。
这个程序太简单了，懒得测试。
然后再仔细想一下，发现还是有点浪费，其实前n个数不需要排序。
于是可以用最小堆来实现。
测试结果：3.02s，1千万个int，n = 500。
然后你可能会发现，STL里面有个函数，叫做nth_element，就是用来做这个的
测试一下：3.4s，1千万个int, n = 500。
如果想要深入了解，那么实际上这个nth_element使用的算法是快速划分。
它其实就是不完全的快速排序，只要递归地排序需要排序的部分就可以了。
自写代码测试：3.4s，1千万个int, n = 500。
------
从上面可以看出，在k=500（N = 10,000,000)时，最小堆是最快的，其次是快速划分，快排当然最慢。
最小堆的时间复杂度是 O( N * log(k) )
快速划分虽然平均时间复杂度是O(C*N)（但是C比较大），但是最坏时间复杂度是O(N^2)（所以随机化很重要！可以避免RPWT！）
快排就不用说了，撑死 O(N * log(N) )，最坏时间复杂度也可能是O(N^2)。
似乎最小堆是最快的，快速划分慢些，但是它们各有自己的适用范围：
当 k 接近 N / 2时，最小堆的时间复杂度其实就相当于一个堆排，事实上还不如快排。
所以最小堆的适用范围是k << N时的情况，或者当k 很接近N， 可以转化成 N-k << N的情况。
而快速划分的算法本身决定了其复杂度和 k 的大小无关，所以当 k 接近 N/2 时，快速划分显然更优。
可是还有另一种情况，也是大公司面试的时候很可能会问到的题目：
给你200亿个整数，找出TOP500000。
第一次遇到这个问题，估计大多数人直接口突白沫了吧。
200亿，对一般PC而言，内存显然存不下，需要保存在辅存中，而辅存的IO速度。。。
所以你应该尽可能少地扫描。
于是这时候最小堆就是最优解决方案：只扫描一遍，就可以得出结果。
------
代码如下：
Jun
14
回忆一下tx的二面，有一道题是这样的：
假设有1kw个身份证号，以及他们对应的数据。身份证号可能重复，要求找出出现次数最多的身份证号。
一个很显然的做法是，hash之，O(n)搞定。这前提是内存中可以存下。
如果是中国的13亿人口，内存中存不下呢？借用磁盘，多次扫描？磁盘IO的速度慢得能让你疯掉。
这时候你终于感受到，中国人口真TMD多阿。。。
--
然后再看看今天的astar复赛第一题：
假设有1kw个身份证号，以及他们对应的数据。身份证号可能重复，要求找出出现次数最多的身份证号。
一个很显然的做法是，hash之，O(n)搞定。这前提是内存中可以存下。
如果是中国的13亿人口，内存中存不下呢？借用磁盘，多次扫描？磁盘IO的速度慢得能让你疯掉。
这时候你终于感受到，中国人口真TMD多阿。。。
--
然后再看看今天的astar复赛第一题：
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到了我的代码。
问了他怎么回事，然后发现自己做了很挫很挫的事情（详见聊天记录，后附）。
附上用来判相似的代码：
下载文件 (已下载 次)聊天记录如下：
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
和上一篇文章内容接近，或者解释更清晰一些 :)
