存档在 2012年9月

海量数据处理的 Top K算法(问题) 小顶堆实现

2012年9月25日

问题描述:有N(N>>10000)个整数,求出其中的前K个最大的数。(称作Top k或者Top 10)

问题分析:由于(1)输入的大量数据;(2)只要前K个,对整个输入数据的保存和排序是相当的不可取的。

可以利用数据结构的最小堆来处理该问题。

最小堆如图所示,对于每个非叶子节点的数值,一定不大于孩子节点的数值。这样可用含有K个节点的最小堆来保存K个目前的最大值(当然根节点是其中的最小数值)。

每次有数据输入的时候可以先与根节点比较。若不大于根节点,则舍弃;否则用新数值替换根节点数值。并进行最小堆的调整。

20173247-86b11c08bf4145c284b263b28215feef

#include<stdio.h>
int n;  ///数字个数,n很大(n>10000)
int dui[10];
#define K 10    ///Top K,K的取值

void create_dui();  ///建堆
void UpToDown(int);  ///从上到下调整
int main()
{
    int i;
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=K;i++) ///先输入K个
            scanf("%d",&dui[i]);
        create_dui();  ///建小顶堆
        for(i=K+1;i<=n;i++)
        {
            scanf("%d",&tmp);
            if(tmp>dui[1])  ///只有大于根节点才处理
            {
                dui[1]=tmp;
                UpToDown(1);    ///向下调整堆
            }
        }
    }
    return 1;
}

void create_dui()
{
    int i;
    int pos=K/2;      ///从末尾数,第一个非叶节点的位置K/2
    for(i=pos;i>=1;i--)
        UpToDown(i);
}

void UpToDown(int i)
{
    int t1,t2,tmp,pos;
    t1=2*i; ///左孩子(存在的话)
    t2=t1+1;    ///右孩子(存在的话)
    if(t1>K)    ///无孩子节点
        return;
    else
    {
        if(t2>K)  ///只有左孩子
            pos=t1;
        else
            pos=dui[t1]>dui[t2]? t2:t1;

        if(dui[i]>dui[pos]) ///pos保存在子孩子中,数值较小者的位置
        {
            tmp=dui[i];dui[i]=dui[pos];dui[pos]=tmp;
            UpToDown(pos);
        }
    }
}

面试题集锦

2012年9月25日

1、实现一个函数,对一个正整数n,算得到1需要的最少操作次数。

操作规则为:如果n为偶数,将其除以2;如果n为奇数,可以加1或减1;一直处理下去。
例子:
func(7) = 4,可以证明最少需要4次运算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1
要求:实现函数(实现尽可能高效) int func(unsign int n);n为输入,返回最小的运算次数。给出思路(文字描述),完成代码,并分析你算法的时间复杂度。
答:

· int func(unsigned int n)
· {
· if(n == 1)
· return 0;
· if(n % 2 == 0)
· return 1 + func(n/2);
· int x = func(n + 1);
· int y = func(n – 1);
· if(x > y)
· return y+1;
· else
· return x+1;
· }

假设n表示成二进制有x bit,可以看出计算复杂度为O(2^x),也就是O(n)。
将n转换到二进制空间来看(比如7为111,6为110):
– 如果最后一位是0,则对应于偶数,直接进行除2操作。
– 如果最后一位是1,情况则有些复杂。
– 如果最后几位是???01,则有可能为???001,???1111101。在第一种情况下,显然应该-1;在第二种情况下-1和+1最终需要的步数相同。所以在???01的情况下,应该选择-1操作。
**如果最后几位是???011,则有可能为???0011,???11111011。在第一种情况下,+1和-1最终需要的步数相同;在第二种情况下+1步数更少些。所以在???011的情况下,应该选择+1操作。
**如果最后有更多的连续1,也应该选择+1操作。
如果最后剩下的各位都是1,则有11时应该选择-1;111时+1和-1相同;1111时应选择+1;大于四个1时也应该选择+1;
· int func(unsigned int n)
· {
· if(n == 1)
· return 0;
· if(n % 2 == 0)
· return 1 + func(n/2);
· if(n == 3)
· return 2;
· if(n&2)
· return 1 + func(n+1);
· else
· return 1 + func(n-1);
· }

2、找到满足条件的数组
给定函数d(n)=n+n的各位之和,n为正整数,如d(78)=78+7+8=93。这样这个函数可以看成一个生成器,如93可以看成由78生成。
定义数A:数A找不到一个数B可以由d(B)=A,即A不能由其他数生成。现在要写程序,找出1至10000里的所有符合数A定义的数。
回答:
申请一个长度为10000的bool数组,每个元素代表对应的值是否可以有其它数生成。开始时将数组中的值都初始化为false。
由于大于10000的数的生成数必定大于10000,所以我们只需遍历1到10000中的数,计算生成数,并将bool数组中对应的值设置为true,表示这个数可以有其它数生成。
最后bool数组中值为false的位置对应的整数就是不能由其它数生成的。

3、一个大的含有50M个URL的记录,一个小的含有500个URL的记录,找出两个记录里相同的URL。
回答:
首先使用包含500个url的文件创建一个hash_set。
然后遍历50M的url记录,如果url在hash_set中,则输出此url并从hash_set中删除这个url。
所有输出的url就是两个记录里相同的url。

4、海量日志数据,提取出某日访问百度次数最多的那个IP。
回答:
IP地址最多有2^32=4G种取值可能,所以不能完全加载到内存中。
可以考虑分而治之的策略,按照IP地址的hash(IP)24值,将海量日志存储到1024个小文件中。每个小文件最多包含4M个IP地址。
对于每个小文件,可以构建一个IP作为key,出现次数作为value的hash_map,并记录当前出现次数最多的1个IP地址。
有了1024个小文件中的出现次数最多的IP,我们就可以轻松得到总体上出现次数最多的IP。

5、有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。如何按照query的频度排序?
回答:
1)读取10个文件,按照hash(query)的结果将query写到对应的文件中。这样我们就有了10个大小约为1G的文件。任意一个query只会出现在某个文件中。
2)对于1)中获得的10个文件,分别进行如下操作
-利用hash_map(query,query_count)来统计每个query出现的次数。
-利用堆排序算法对query按照出现次数进行排序。
-将排序好的query输出的文件中。
这样我们就获得了10个文件,每个文件中都是按频率排序好的query。
3)对2)中获得的10个文件进行归并排序,并将最终结果输出到文件中。

6、蚂蚁爬杆问题
有一根27厘米长的细木杆,在第3厘米,7厘米,11厘米,17厘米,23厘米这五个位置上各有一只蚂蚁,木杆很细,不能同时通过两只蚂蚁,开始时,蚂蚁的头朝向左还是右是任意的,他们只会朝前走或掉头,但不会后退,当两只蚂蚁相遇后,蚂蚁会同时掉头朝反方向走,假设蚂蚁们每秒钟可以走1厘米的距离。求所有蚂蚁都离开木杆的最小时间和最大时间。
答案:
两只蚂蚁相遇后,各自掉头朝相反方向走。如果我们不考虑每个蚂蚁的具体身份,这和两只蚂蚁相遇后,打个招呼继续向前走没有什么区别。
所有蚂蚁都离开木杆的最小时间为
max(min(3,27-3),min(7,27-7), min(11,27-11), min(17,27-17),min(23,27-23))=11
所有蚂蚁都离开木杆的最大时间为
max(max(3,27-3),max(7,27-7), max(11,27-11), max(17,27-17),max(23,27-23))=24

7、当在浏览器中输入一个url后回车,后台发生了什么?比如输入url后,你看到了百度的首页,那么这一切是如何发生的呢?
回答:
简单来说有以下步骤:
1、查找域名对应的IP地址。这一步会依次查找浏览器缓存,系统缓存,路由器缓存,ISPDNS缓存,根域名服务器。
2、向IP对应的服务器发送请求。
3、服务器响应请求,发回网页内容。
4、浏览器解析网页内容。
当然,由于网页可能有重定向,或者嵌入了图片,AJAX,其它子网页等等,这4个步骤可能反复进行多次才能将最终页面展示给用户。

8、判断两棵树是否相等,请实现两棵树是否相等的比较,相等返回1,否则返回其他值,并说明算法复杂度。
数据结构为:
typedef struct TreeNode
{
char c;
TreeNode *leftchild;
TreeNode *rightchild;
}TreeNode;
函数接口为:int CompTree(TreeNode* tree1,TreeNode* tree2);
注:A、B两棵树相等当且仅当RootA->c==RootB–>c,而且A和B的左右子树相等或者左右互换相等。
递归方法:
bool CompTree(TreeNode *tree1, TreeNode *tree2)
{
if(tree1 == NULL && tree2 == NULL)
return true;
if(tree1 == NULL || tree2 == NULL)
return false;
if(tree1->c != tree2->c)
return false;
if( (CompTree(tree1->leftchild, tree2->leftchild) && CompTree(tree1->rightchild, tree2->rightchild)) || CompTree(tree1->leftchild, tree2->rightchild) && CompTree(tree1->rightchild, tree2->leftchild))
return true;
}

时间复杂度:
在树的第0层,有1个节点,我们会进行1次函数调用;
在树的第1层,有2个节点,我们可能会进行4次函数调用;
在树的第2层,有4个节点,我们可能会进行16次函数调用;
….
在树的第x层,有2^x个节点,我们可能会进行(2^x)^2次函数调用;
所以假设总节点数为n,则算法的复杂度为O(n^2)。

9、三个警察和三个囚徒的过河问题
三个警察和三个囚徒共同旅行。一条河挡住了去路,河边有一条船,但是每次只能载2人。存在如下的危险:无论在河的哪边,当囚徒人数多于警察的人数时,将有警察被囚徒杀死。问题:请问如何确定渡河方案,才能保证6人安全无损的过河。
回答:

警察囚徒过去,警察回来
囚徒囚徒过去,囚徒回来
警察警察过去,警察囚徒回来
警察警察过去,囚徒回来
囚徒囚徒过去,囚徒回来
囚徒囚徒过去

10、从300万字符串中找到最热门的10条
搜索的输入信息是一个字符串,统计300万输入信息中的最热门的前10条,我们每次输入的一个字符串为不超过255byte,内存使用只有1G。请描述思想,写出算法(c语言),空间和时间复杂度。
答案:
300万个字符串最多(假设没有重复,都是最大长度)占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理。
可以使用key为字符串(事实上是字符串的hash值),值为字符串出现次数的hash来统计每个每个字符串出现的次数。并用一个长度为10的数组/链表来存储目前出现次数最多的10个字符串。
这样空间和时间的复杂度都是O(n)。

11、如何找出字典中的兄弟单词。给定一个单词a,如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的兄弟单词。现在给定一个字典,用户输入一个单词,如何根据字典找出这个单词有多少个兄弟单词?
答案:
使用hash_map和链表。
首先定义一个key,使得兄弟单词有相同的key,不是兄弟的单词有不同的key。例如,将单词按字母从小到大重新排序后作为其key,比如bad的key为abd,good的key为dgoo。
使用链表将所有兄弟单词串在一起,hash_map的key为单词的key,value为链表的起始地址。
开始时,先遍历字典,将每个单词都按照key加入到对应的链表当中。当需要找兄弟单词时,只需求取这个单词的key,然后到hash_map中找到对应的链表即可。
这样创建hash_map时时间复杂度为O(n),查找兄弟单词时时间复杂度是O(1)。

12、找出数组中出现次数超过一半的数,现在有一个数组,已知一个数出现的次数超过了一半,请用O(n)的复杂度的算法找出这个数。
答案1:
创建一个hash_map,key为数组中的数,value为此数出现的次数。遍历一遍数组,用hash_map统计每个数出现的次数,并用两个值存储目前出现次数最多的数和对应出现的次数。
这样可以做到O(n)的时间复杂度和O(n)的空间复杂度,满足题目的要求。
但是没有利用“一个数出现的次数超过了一半”这个特点。也许算法还有提高的空间。
答案2:
使用两个变量A和B,其中A存储某个数组中的数,B用来计数。开始时将B初始化为0。
遍历数组,如果B=0,则令A等于当前数,令B等于1;如果当前数与A相同,则B=B+1;如果当前数与A不同,则令B=B-1。遍历结束时,A中的数就是要找的数。
这个算法的时间复杂度是O(n),空间复杂度为O(1)。

13、找出被修改过的数字
n个空间(其中n<1M),存放a到a+n-1的数,位置随机且数字不重复,a为正且未知。现在第一个空间的数被误设置为-1。已经知道被修改的数不是最小的。请找出被修改的数字是多少。
例如:n=6,a=2,原始的串为5,3,7,6,2,4。现在被别人修改为-1,3,7,6,2,4。现在希望找到5。
回答:
由于修改的数不是最小的,所以遍历第二个空间到最后一个空间可以得到a的值。
a到a+n-1这n个数的和是total=na+(n-1)n/2。
将第二个至最后一个空间的数累加获得sub_total。
那么被修改的数就是total-sub_total。

14、设计DNS服务器中cache的数据结构
要求设计一个DNS的Cache结构,要求能够满足每秒5000以上的查询,满足IP数据的快速插入,查询的速度要快。(题目还给出了一系列的数据,比如:站点数总共为5000万,IP地址有1000万,等等)
回答:
DNS服务器实现域名到IP地址的转换。
每个域名的平均长度为25个字节(估计值),每个IP为4个字节,所以Cache的每个条目需要大概30个字节。
总共50M个条目,所以需要1.5G个字节的空间。可以放置在内存中。(考虑到每秒5000次操作的限制,也只能放在内存中。)
可以考虑的数据结构包括hash_map,字典树,红黑树等等。

15、找出给定字符串对应的序号。
序列Seq=[a,b,…z,aa,ab…az,ba,bb,…bz,…,za,zb,…zz,aaa,…]类似与excel的排列,任意给出一个字符串s=[a-z]+(由a-z字符组成的任意长度字符串),请问s是序列Seq的第几个。
回答:
注意到每满26个就会向前进一位,类似一个26进制的问题。
比如ab,则位置为26*1+2;
比如za,则位置为26*26+1;
比如abc,则位置为26*26*1+26*2+3;

16、找出第k大的数字所在的位置。

写一段程序,找出数组中第k大小的数,输出数所在的位置。例如{2,4,3,4,7}中,第一大的数是7,位置在4。第二大、第三大的数都是4,位置在1、3随便输出哪一个均可。
答案:
先找到第k大的数字,然后再遍历一遍数组找到它的位置。所以题目的难点在于如何最高效的找到第k大的数。
我们可以通过快速排序,堆排序等高效的排序算法对数组进行排序,然后找到第k大的数字。这样总体复杂度为O(NlogN)。
我们还可以通过二分的思想,找到第k大的数字,而不必对整个数组排序。从数组中随机选一个数t,通过让这个数和其它数比较,我们可以将整个数组分成了两部分并且满足,{x,xx,…,t}<{y,yy,…}。
在将数组分成两个数组的过程中,我们还可以记录每个子数组的大小。这样我们就可以确定第k大的数字在哪个子数组中。
然后我们继续对包含第k大数字的子数组进行同样的划分,直到找到第k大的数字为止。
平均来说,由于每次划分都会使子数组缩小到原来1/2,所以整个过程的复杂度为O(N)。

17、给40亿个不重复的unsigned int的整数,没排过序的,然后再给几个数,如何快速判断这几个数是否在那40亿个数当中?
答案:
unsigned int的取值范围是0到2^32-1。我们可以申请连续的2^32/8=512M的内存,用每一个bit对应一个unsigned int数字。首先将512M内存都初始化为0,然后每处理一个数字就将其对应的bit设置为1。当需要查询时,直接找到对应bit,看其值是0还是1即可。

18、在一个文件中有10G个整数,乱序排列,要求找出中位数。内存限制为2G。
回答:
不妨假设10G个整数是64bit的。
2G内存可以存放256M个64bit整数。
我们可以将64bit的整数空间平均分成256M个取值范围,用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后,我们便知道中数在那个范围内出现,以及这个范围内总共出现了多少个整数。
如果中数所在范围出现的整数比较少,我们就可以对这个范围内的整数进行排序,找到中数。如果这个范围内出现的整数比较多,我们还可以采用同样的方法将此范围再次分成多个更小的范围(256M=2^28,所以最多需要3次就可以将此范围缩小到1,也就找到了中数)。

Top K问题

2012年9月25日

问题描述:(百度面试题)搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为0-255字节。假设目前有1000万个记录,除去重复后,不超过300万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门,请你统计最热门的10个查询串,要求内存不能超过1G。

问题解析:

【分析】:要统计最热门查询,首先就是要统计每个query出现的次数,然后根据统计结果,找出Top 10。所以我们可以根据该思路分两步来设计该算法。

第一步:Query统计

(算法一)直接排序法

首先我们能想到的就是排序,首先对这个日志里面的所有Query进行排序,然后再遍历排好序的Query,统计每个Query出现的次数。但是题目中有明确要求,就是内存不超过1G,一千万条记录,每条记录是255字节,很显然要占据2.5G内存,这个条件就不满足要求了。

让我们回忆下数据结构课程上的内容,当数据量较大而且内存无法装下的时候,我们可以采用外排序的方法来进行排序,这里我采用归并排序,因为归并排序有一个较好的时间复杂度O(nlogn)。

排完序后,我们再对已有的Query文件进行遍历,统计每个Query出现的次数,再次写入文件中。
综合分析一下,排序的时间复杂度是O(NlogN),而遍历的时间复杂度是O(N),因此该算法的总体时间复杂度是O(NlogN)。

(算法二)Hash Table法
题目说明了,虽然有1000万个Query,但是由于重复度比较高,因此事实上只有300万个Query,每个Query占255个字节,因此我们可以考虑把它们全部都放进内存去,Hash Table绝对是我们的优先选择,因为Hash Table的查询速度快,时间复杂度几乎是O(1)。

那么我们的算法就有了:维护一个Key为Query的字串,Value为该Query出现次数的HashTable,每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设置为 1;如果该字串在Table中,那么将该字串的计数加1即可,最终我们在O(N)的时间复杂度完成了对该海量数据的处理。

第一步:找出Top 10
(算法一)排序
排除的时间复杂度是O(NlogN),在本题目中,三百万条记录,用1G内存是可以存下的。

(算法二)部分排序
题目要求的是求出Top 10,因此我们没有必要对所有的Query进行排序,我们只需要维护一个10个大小的数组,初始化放入10个Query,按照每个Query的统计次数由大到小排序,然后遍历这300万条记录,没读一条记录就与数组的最后一个Query进行对比,如果小于这个Query,则继续遍历,否则将数据的最后一条记录淘汰,加入当前的Query。最后当所以的数据都遍历完毕之后,那么这个数组中的10个Query便是我们要找的Top 10了。
不难分析出,这样的算法的时间复杂度是N*K,K是top多少的值。

(算法三)堆排序
在算法二中,每次比较完成之后,需要操作的复杂度都是K,因为要把元素插入到一个线性表之中,而且采用的是顺序比较。这里我们注意下,该数组是有序的,因此我们每次查找的时候可以采用二分的方法查找,这样操作的复杂度就降低到了LogK,可是随之而来的就是数据移动,因此移动数据的次数增多了。借助堆结构,我们可以在Log量级的时间内查找和调整/移动。因此,我们的算法可以改进为这样,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行比对,那么时间复杂度就降低到了 NlogK。

进程与线程的区别

2012年9月25日

一 程序是存放在磁盘上的一系列代码和数据的看执行映像,是一个静止的实体,

  二 进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,是系统进行资源分配和调度的一个独立单位, 是一个执行中的程序,它是动态的实体;

  三 线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),一个线程可以创建和撤销另一个线程;

  一 进程与线程区别与联系

  (1) 划分尺度:线程更小,所以多线程程序并发性更高;

  (2) 资源分配:进程是资源分配的基本单位,同一进程内多个线程共享其资源;

  (3) 地址空间:进程拥有独立的地址空间,同一进程内多个线程共享其资源;

  (4) 处理器调度:线程是处理器调度的基本单位;

  (5) 执行:每个线程都有一个程序运行的入口,顺序执行序列和程序的出口,但线程不能单独执行,必须组成进程,一个进程至少有一个主线程。简而言之,一个程序至少有一个进程,一个进程至少有一个线程。
 二 进程和程序区别和联系

  (1)程序只是一组指令的有序集合,它本身没有任何运行的含义,它只是一个静态的实体。而进程则不同,它是程序在某个数据集上的执行。进程是一个动态的实体,它有自己的生命周期。反映了一个程序在一定的数据集上运行的全部动态过程。

  (2)进程和程序并不是一一对应的,一个程序执行在不同的数据集上就成为不同的进程,可以用进程控制块来唯一地标识每个进程。而这一点正是程序无法做到的,由于程序没有和数据产生直接的联系,既使是执行不同的数据的程序,他们的指令的集合依然是一样的,所以无法唯一地标识出这些运行于不同数据集上的程序。一般来说,一个进程肯定有一个与之对应的程序,而且只有一个。而一个程序有可能没有与之对应的进程(因为它没有执行),也有可能有多个进程与之对应(运行在几个不同的数据集上)。

  (3)进程还具有并发性和交往性,这也与程序的封闭性不同。

  进程和程序区别和联系表现在以下方面:

  1)程序只是一组指令的有序集合,它本身没有任何运行的含义,它只是一个静态的实体。而进程则不同,它是程序在某个数据集上的执行。

  进程是一个动态的实体,它有自己的生命周期。它因创建而产生,因调度而运行,因等待资源或事件而被处于等待状态,因完成任务而被撤消。反映了一个程序在一定的数据集上运行的全部动态过程。

  2)进程和程序并不是一一对应的,一个程序执行在不同的数据集上就成为不同的进程,可以用进程控制块来唯一地标识每个进程。而这一点正是程序无法做到的,由于程序没有和数据产生直接的联系,既使是执行不同的数据的程序,他们的指令的集合依然是一样的,所以无法唯一地标识出这些运行于不同数据集上的程序。一般来说,一个进程肯定有一个与之对应的程序,而且只有一个。而一个程序有可能没有与之对应的进程(因为它没有执行),也有可能有多个进程与之对应(运行在几个不同的数据集上)。

  3)进程还具有并发性和交往性,这也与程序的封闭性不同。进程和线程都是由操作系统所体会的程序运行的基本单元,系统利用该基本单元实现系统对应用的并发性。进程和线程的区别在于:

  简而言之,一个程序至少有一个进程,一个进程至少有一个线程.

  线程的划分尺度小于进程,使得多线程程序的并发性高。

  另外,进程在执行过程中拥有独立的内存单元,而多个线程共享内存,从而极大地提高了程序的运行效率。

  线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行,必须依存在应用程序中,由应用程序提供多个线程执行控制。

  从逻辑角度来看,多线程的意义在于一个应用程序中,有多个执行部分可以同时执行。但操作系统并没有将多个线程看做多个独立的应用,来实现进程的调度和管理以及资源分配。这就是进程和线程的重要区别。

  进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位.

  线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源.

  一个线程可以创建和撤销另一个线程;同一个进程中的多个线程之间可以并发执行

线程安全和线程可重入

2012年9月24日

线程安全:概念比较直观。一般说来,一个函数被称为线程安全的,当且仅当被多个并发线程反复调用时,它会一直产生正确的结果。

可重入:概念基本没有比较正式的完整解释,但是它比线程安全要求更严格。根据经验,所谓“重入”,常见的情况是,程序执行到某个函数foo()时,收到信号,于是暂停目前正在执行的函数,转到信号处理函数,而这个信号处理函数的执行过程中,又恰恰也会进入到刚刚执行的函数foo(),这样便发生了所谓的重入。此时如果foo()能够正确的运行,而且处理完成后,之前暂停的foo()也能够正确运行,则说明它是可重入的。

线程安全的条件:

要确保函数线程安全,主要需要考虑的是线程之间的共享变量。属于同一进程的不同线程会共享进程内存空间中的全局区和堆,而私有的线程空间则主要包括栈和寄存器。因此,对于同一进程的不同线程来说,每个线程的局部变量都是私有的,而全局变量、局部静态变量、分配于堆的变量都是共享的。在对这些共享变量进行访问时,如果要保证线程安全,则必须通过加锁的方式。

可重入的判断条件:

要确保函数可重入,需满足一下几个条件:

1、不在函数内部使用静态或全局数据
2、不返回静态或全局数据,所有数据都由函数的调用者提供。
3、使用本地数据,或者通过制作全局数据的本地拷贝来保护全局数据。
4、不调用不可重入函数。

经典智力问题收集

2012年9月24日

第一部分题目开始:
1、有两根不均匀分布的香,香烧完的时间是一个小时,你能用什么方法来确定一段15分钟的时间?

2、一个经理有三个女儿,三个女儿的年龄加起来等于13,三个女儿的年龄乘起来等于经理自己的年龄,有一个下属已知道经理的年龄,但仍不能确定经理三个女儿的年龄,这时经理说只有一个女儿的头发是黑的,然后这个下属就知道了经理三个女儿的年龄。请问三个女儿的年龄分别是多少?为什么?

3、有三个人去住旅馆,住三间房,每一间房$10元,于是他们一共付给老板$30,第二天,老板觉得三间房只需要$25元就够了于是叫小弟退回$5给三位客人,谁知小弟贪心,只退回每人$1,自己偷偷拿了$2,这样一来便等于那三位客人每人各花了九元,于是三个人一共花了$27,再加上小弟独吞了$2,总共是$29。可是当初他们三个人一共付出$30那么还有$1呢?

4、有两位盲人,他们都各自买了两对黑袜和两对白袜,八对袜了的布质、大小完全相同,而每对袜了都有一张商标纸连着。两位盲人不小心将八对袜了混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?

5、有一辆火车以每小时15公里的速度离开洛杉矶直奔纽约,另一辆火车以每小时20公里的速度从纽约开往洛杉矶。如果有一只鸟,以30公里每小时的速度和两辆火车同时启动,从洛杉矶出发,碰到另一辆车后返回,依次在两辆火车来回飞行,直到两辆火车相遇,请问,这只小鸟飞行了多长距离?

6、你有两个罐子,50个红色弹球,50个蓝色弹球,随机选出一个罐子,随机选取出一个弹球放入罐子,怎么给红色弹球最大的选中机会?在你的计划中,得到红球的准确几率是多少?

7、你有四个装药丸的罐子,每个药丸都有一定的重量,被污染的药丸是没被污染的重量+1.只称量一次,如何判断哪个罐子的药被污染了?

8、你有一桶果冻,其中有黄色,绿色,红色三种,闭上眼睛,抓取两个同种颜色的果冻。抓取多少个就可以确定你肯定有两个同一颜色的果冻?

9、对一批编号为1~100,全部开关朝上(开)的灯进行以下操作:凡是1的倍数反方向拨一次开关;2的倍数反方向又拨一次开关;3的倍数反方向又拨一次开关……问:最后为关熄状态的灯的编号。

10、想象你在镜子前,请问,为什么镜子中的影像可以颠倒左右,却不能颠倒上下?

11、一群人开舞会,每人头上都戴着一顶帽子。帽子只有黑白两种,黑的至少有一顶。每个人都能看到其它人帽子的颜色,却看不到自己的。主持人先让大家看看别人头上戴的是什幺帽子,然后关灯,如果有人认为自己戴的是黑帽子,就打自己一个耳光。第一次关灯,没有声音。于是再开灯,大家再看一遍,关灯时仍然鸦雀无声。一直到第三次关灯,才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子?

12、两个圆环,半径分别是1和2,小圆在大圆内部绕大圆圆周一周,问小圆自身转了几周?如果在大圆的外部,小圆自身转几周呢?

13、假如每3个空啤酒瓶可以换一瓶啤酒,某人买了10瓶啤酒,那么他最多可以喝到多少瓶啤酒?

答案:
1、香a点燃一头,香b点燃两头。等香b烧完时,时间过去了30分钟。再把香a剩下的另一头也点燃。从这时起到a烧完的时间就是15分钟。

2、三女的年龄应该是2、2、9。因为只有一个 孩子黑头发,即只有她长大了,其他两个还是幼年时期即小于3岁,头发为淡色。再结合经理的年龄应该至少大于25。

3、典型的偷换概念。事实上3人只付出了27元,老板得了25元,小弟拿了2元。

4、将每对袜子拆开一人一只。

5、设洛杉矶到纽约的铁路长为A公里。则两辆火车到相遇用了A/(15+20)小时,也就是小鸟飞行的时间。所以小鸟飞行的距离就是速度×时间=30×A/35=6/7的洛杉矶到纽约的铁路长。

6、1/2的几率。先选出球在选罐子。这样罐子其实对球的颜色无影响。

7、1号罐取1丸,2号罐取2丸,3号罐取3丸,4号罐取4丸,称量该10个药丸,比正常重量重几就是几号罐的药有问题。

8、4个。数量>颜色种类。颜色必重复。

9、有10盏灯为灭,分别为1、4、9、16、25、36、49、64、81、100号。因为:每个质数能被1和自身整除,所以质数的灯是亮的。设一个合数能被N个数整除,N必然是个偶数。对于非某数平方的合数来说,将被开关N次也就是偶数次,灯保留为亮;对于上面列出的平方数,则只被开关N-1次,所以灯是灭的。

10、镜像对称的轴是人的中轴

11、有三个人戴黑帽。假设有N个人戴黑,当N=1时,戴黑人看见别人都为白则能肯定自己为黑。于是第一次关灯就应该有声。可以断定N>1。对于每个戴黑的人来说,他能看见N-1顶黑帽,并由此假定自己为白。但等待N-1次还没有人打自己以后,每个戴黑人都能知道自己也是黑的了。所以第N次关灯就有N个人打自己。

12、无论内外,小圆转两圈。

13、喝完10瓶后用9个空瓶换来3瓶啤酒(喝完后有4个空瓶)喝完这三瓶又可以换到1瓶啤酒(喝完后有2个空瓶)
  这时他有2个空酒瓶,如果他能向老板先借一个空酒瓶,就凑够了3个空瓶可以换到一瓶啤酒,把这瓶喝完后将空瓶还给老板就可以了。
  所以他最多可以喝10+3+1+1=15瓶

信号量与互斥锁的区别

2012年9月24日

信号量用在多线程多任务同步的,一个线程完成了某一个动作就通过信号量告诉别的线程,别的线程再进行某些动作(大家都在sem_wait的时候,就阻塞在那里)。而互斥锁是用在多线程多任务互斥的,一个线程占用了某一个资源,那么别的线程就无法访问,直到这个线程unlock,其他的线程才开始可以利用这个资源。比如对全局变量的访问,有时要加锁,操作完了,在解锁。有的时候锁和信号量会同时使用的.
也就是说,信号量不一定是锁定某一个资源,而是流程上的概念,比如:有A,B两个线程,B线程要等A线程完成某一任务以后再进行自己下面的步骤,这个任务并不一定是锁定某一资源,还可以是进行一些计算或者数据处理之类。而线程互斥量则是“锁住某一资源”的概念,在锁定期间内,其他线程无法对被保护的数据进行操作。在有些情况下两者可以互换。

两者之间的区别:
作用域

信号量: 进程间或线程
互斥锁: 线程间

上锁时

信号量: 只要信号量的value大于0,其他线程就可以sem_wait成功,成功后信号量的value减一。若value值不大于0,则sem_wait阻塞,直到sem_post释放后value值加一。一句话
信号量的value>=0。

互斥锁: 只要被锁住,其他任何线程都不可以访问被保护的资源。如果没有锁,获得资源成功,否则进行阻塞等待资源可用。一句话,线程互斥锁的vlaue可以为负数。

信号量和线程互斥锁的实现机制:

在Linux下,信号量和线程互斥锁的实现都是通过futex系统调用。

futex(快速用户区互斥的简称)是一个在Linux上实现锁定和构建高级抽象锁如信号量和POSIX互斥的基本工具。它们第一次出现在内核开发的2.5.7版;其语义在2.5.40固定下来,然后在2.6.x系列稳定版内核中出现。

Futex 是fast userspace mutex的缩写,意思是快速用户空间互斥体。Linux内核把它们作为快速的用户空间的锁和信号量的预制构件提供给开发者。Futex非常基础,借助其自身的优异性能,构建更高级别的锁的抽象,如POSIX互斥体。大多数程序员并不需要直接使用Futex,它一般用来实现像NPTL这样的系统库。

Futex 由一块能够被多个进程共享的内存空间(一个对齐后的整型变量)组成;这个整型变量的值能够通过汇编语言调用CPU提供的原子操作指令来增加或减少,并且一个进程可以等待直到那个值变成正数。Futex 的操作几乎全部在应用程序空间完成;只有当操作结果不一致从而需要仲裁时,才需要进入操作系统内核空间执行。这种机制允许使用 futex 的锁定原语有非常高的执行效率:由于绝大多数的操作并不需要在多个进程之间进行仲裁,所以绝大多数操作都可以在应用程序空间执行,而不需要使用(相对高代价的)内核系统调用。

TCP连接的建立与断开

2012年9月24日

1.为什么建立连接协议是三次握手,而关闭连接却是四次握手呢?

这是因为服务端的LISTEN状态下的SOCKET当收到SYN报文的建连请求后,它可以把ACK和SYN(ACK起应答作用,而SYN起同步作用)放在一个报文里来发送。但关闭连接时,当收到对方的FIN报文通知时,它仅仅表示对方没有数据发送给你了;但未必你所有的数据都全部发送给对方了,所以你可以未必会马上会关闭SOCKET,也即你可能还需要发送一些数据给对方之后,再发送FIN报文给对方来表示你同意现在可以关闭连接了,所以它这里的ACK报文和FIN报文多数情况下都是分开发送的.

2.为什么TIME_WAIT状态还需要等2MSL后才能返回到CLOSED状态?

这是因为虽然双方都同意关闭连接了,而且握手的4个报文也都协调和发送完毕,按理可以直接回到CLOSED状态(就好比从SYN_SEND状态到ESTABLISH状态那样);但是因为我们必须要假想网络是不可靠的,你无法保证你最后发送的ACK报文会一定被对方收到,因此对方处于LAST_ACK状态下的SOCKET可能会因为超时未收到ACK报文,而重发FIN报文,所以这个TIME_WAIT状态的作用就是用来重发可能丢失的ACK报文。