手机分配短讯id的面试题目(分析解答篇)

看过上回《厘清需求篇》&＃xff0c;读者想到多少个解呢&＃xff1f;本篇首先谈及一些基本分析&＃xff0c;之后会按两种API设计(纯函数API和含状态的API)&＃xff0c;分别描述多个解。虽然面试时或许不能进行实际测试&＃xff0c;但本文还是给出PC上的效能测试结果。最后分析比较各解之优劣作为总结。

问题分析

原来的问题是要从一个无序ids数组里分配一个id。我们可以用数学方式去更清楚地说明这个问题。

设m &＃61; 256 为所有id的个数&＃xff0c;集合U &＃61; \left\{ 0, 1, ..., m-1 \right\}为所有id的集合。那么&＃xff0c;给定一个已分配id的集合A\subset U&＃xff0c;A &＃61; \left\{ a_0, a_1, ..., a_{n-1} \right\}(即参数ids)&＃xff0c;本题目可表示为&＃xff0c;求一个x(即传回的id)&＃xff0c;符合条件:

减号是补集的意思&＃xff0c;即x属于U但不属于A。上回的对答已确定U - A\ne \oslash &＃xff0c;即x必然存在。此外&＃xff0c;这个条件又可以写成:

以上两种表达式可说明此问题的两种解法&＃xff0c;一种编程方向是查找U集里有没有不属于A的id&＃xff0c;而另种是计算A的补集再取出其中一个id。

纯函数API的解

实现程序之前&＃xff0c;如果可以&＃xff0c;应先写测试函数。笔者认为&＃xff0c;若面试者在情况容许下&＃xff0c;也可在解答题目之前&＃xff0c;写下测试程序。如果有多个面试者能同样解题&＃xff0c;或许同时写下测试程序的面试者能脱颖而出。

测试函数

为了简单起见&＃xff0c;笔者使用了assert()来检测正确性&＃xff0c;只于Debug版本有效。而Release版本则用来测试效能。

由于U集合的子集合很多&＃xff0c;\left| P(U) \right| &＃61; 2^m&＃61;2^{256}\approx 10^{76} &＃xff0c;不可能穷举所有可能集合。所以&＃xff0c;只能够举出随机的集合以作测试。

以下是一些常数(宏)及类型声明&＃xff0c;TEST_COUNT是测试次数&＃xff0c;而TEST_REPEATCOUNT是为了测试效能时&＃xff0c;重覆测试的次数(即Release版本会调用测试函数一百万次):

#define M 256 // ID的数目&＃xff0c;且所有ID在[0, M)的区间内
#define TEST_COUNT 10000
#ifdef NDEBUG
#define TEST_REPEATCOUNT 100
#else
#define TEST_REPEATCOUNT 1
#endif
typedef unsigned char byte;
typedef unsigned long dword;
typedef byte (*idalloc_func)(byte*, size_t);


首先&＃xff0c;写一个帮助函数测试某id是否在ids集合之内(不熟C&＃43;&＃43;的读者可参考C版本):

// 检测ids里是否含id (C&＃43;&＃43; 版本)
inline bool contain(byte* ids, size_t n, byte id) {
assert(ids !&＃61; NULL);
return find(ids, ids &＃43; n, id) !&＃61; ids &＃43; n;
}



// 检测ids里是否含id (C 版本)
inline bool contain(byte* ids, size_t n, byte id) {
assert(ids !&＃61; NULL);
for (size_t i &＃61; 0; i if (ids[i] &＃61;&＃61; id)
return true;
return false;
}


笔者首先写了一个测试平均情况的测试平台函数:

// 测试平均情况
void test_average(idalloc_func idalloc) {
assert(idalloc !&＃61; NULL);
byte ids[M];
for (size_t i &＃61; 0 ; i ids[i] &＃61; (byte)i;
srand(0); // 使每次测试的伪随机数相同
size_t n &＃61; 0;
for (int test &＃61; 0; test random_shuffle(ids, ids &＃43; M); // 把整个数组洗牌
for (int repeat &＃61; 0; repeat byte id &＃61; idalloc(ids, n);
(void)id;
assert(!contain(ids, n, id));
// 测试是否最小的id
for (size_t i &＃61; 0; i assert(contain(ids, n, (byte)i));
}
n &＃61; (n &＃43; 1) % M;
}
}


简单解释。首先&＃xff0c;把ids数组填入所有id值。利用random_shuffle()把把整个ids数组洗牌&＃xff0c;而n则是在[0, M)区间里循环递增。

由于笔者给出的解&＃xff0c;都能传回最小的id&＃xff0c;所以也会测试这条件。而最坏情况&＃xff0c;就是ids含无序的{0, 1, ... M - 2}&＃xff0c;分配到的id为M-1&＃xff0c;笔者也为此编了一个最坏情况的效能测试函数。

// 测试最坏情况(ids为无序的[0, M - 2], 结果必然是id &＃61; M - 1)
void test_worst(idalloc_func idalloc) {
assert(idalloc !&＃61; NULL);
const size_t n &＃61; M - 1;
byte ids[n];
srand(0); // 使每次测试的伪随机数相同
for (size_t i &＃61; 0 ; i ids[i] &＃61; (byte)i;
for (int test &＃61; 0; test random_shuffle(ids, ids &＃43; n);
for (int repeat &＃61; 0; repeat byte id &＃61; idalloc(ids, n);
(void)id;
assert(id &＃61;&＃61; M - 1);
}
}
}


线性查找

最简单的想法&＃xff0c;可能是遍历所整个U集合(即0至M-1)&＃xff0c;并使用contain()函数检测该id是否不包含在ids数组里。

// 线性查找 (总是传回最小id)
// 时间复杂度: O(n^2)
// 临时内存大小: 0 字节
// 注: 因为n byte linear_search(byte* ids, size_t n) {
assert(ids !&＃61; NULL);
assert(n // 逐个id检查是否存在于[ids, ids &＃43; n)
for (byte id &＃61; 0; ; id&＃43;&＃43;)
if (!contain(ids, n, id))
return id;
}


二分查找

网友Doyle在TL里提出了用二分查找的主意。笔者实现了两种形式&＃xff0c;以下这个是不需额外内存。原理是把U集合分割为两个各占一半的区间&＃xff0c;分别数算两个区间内的已分配元素数目&＃xff0c;若元素数目少于区间大小&＃xff0c;即代表该区间内有未分配的id。再继续分割该区间&＃xff0c;直至区间内都是可分配的id(即找到的元素是零)。

// 数ids内有多少个id在[min, max)的区间内
inline size_t count_interval(byte* ids, size_t n, size_t min, size_t max) {
size_t count &＃61; 0;
for (size_t i &＃61; 0; i if (ids[i] >&＃61; min && ids[i] count&＃43;&＃43;;
return count;
}
// 二分查找 (总是传回最小id)
// 时间复杂度: O(n lg n)
// 临时内存大小: 0 字节
byte binary_search(byte* ids, size_t n) {
assert(ids !&＃61; NULL);
assert(n size_t l &＃61; 0, r &＃61; M;
for(;;) {
size_t c &＃61; (l &＃43; r) / 2; // 把id范围从[l, r)分割为[l, c), [c, r)两个区间
size_t count;
// 以下的条件测试次序保证了传回最小id
if ((count &＃61; count_interval(ids, n, l, c)) if (count &＃61;&＃61; 0)
return (byte)l;
r &＃61; c;
}
else if ((count &＃61; count_interval(ids, n, c, r)) if (count &＃61;&＃61; 0)
return (byte)c;
l &＃61; c;
}
else
assert(false); // 因为n }
}

这算法在最坏情况比线性查找快&＃xff0c;但平均情况下却不一定。

排序

以上两个解&＃xff0c;都是查找的方式&＃xff0c;毋需改动数据。相反&＃xff0c;另一类解用的算法需改动ids数组内的元素&＃xff0c;或是把ids复制到另一个临时数组里进行更改型的算法。

最简单的算法&＃xff0c;是把无序的ids排序。之后就可以从头开始扫描未分配的id。

// 排序 (总是传回最小id)
// 时间复杂度: O(n lg n)
// 临时内存大小: M 字节(如果可改变ids则是0)
byte sort_stl(byte* ids, size_t n) {
assert(ids !&＃61; NULL);
assert(n byte buffer[M];
memcpy(buffer, ids, n);
sort(buffer, buffer &＃43; n); // 平均 O(n lg n)
for (size_t i &＃61; 0; i if (buffer[i] !&＃61; i)
return (byte)i;
return (byte)n;
}

但读者可能会想到&＃xff0c;把整个数组排序可能会做了很多无用工。而且&＃xff0c;快速排序(quicksort)的最坏时间复杂度是O(n^2)。因此&＃xff0c;就有了下一个解。

堆

笔者想到的另一个解是使用堆(heap)数据结构。堆可保证第一个元素是最小的元素(通常是最大的&＃xff0c;但这题目里我们希望取得最小的)&＃xff0c;而每次弹出这个元素&＃xff0c;取出第二小的元素只需要O(lg n)的时间。 sort_stl()需要完整排序&＃xff0c;而使用堆则是逐步进行的&＃xff0c;中途找到没用到的id就可以停下来&＃xff0c;所以平均来说会省下很多时间。

// 堆 (总是传回最小id)
// 时间复杂度: O(n lg n)
// 临时内存大小: M 字节(如果可改变ids则是0)
byte heap_stl(byte* ids, size_t n) {
assert(ids !&＃61; NULL);
assert(n byte buffer[M];
memcpy(buffer, ids, n);
byte* end &＃61; buffer &＃43; n;
make_heap(buffer, end, greater()); // O(n)
for (byte id &＃61; 0; buffer !&＃61; end; id&＃43;&＃43;, end--) {
if (buffer[0] !&＃61; id)
return id;
pop_heap(buffer, end, greater()); // O(lg n)
}
return (byte)n;
}

最坏的情况&＃xff0c;是要把最小的M-1个元素最弹出&＃xff0c;才能求得id&＃61;M-1。这情况其实等价于堆排序(heapsort)。

剖分

另一个方法和二分查找相似&＃xff0c;就是把数组剖分(partition)为两部分&＃xff0c;这应该是Doyle提出的原意。原理是&＃xff0c;设一个中间c&＃61;M/2&＃xff0c;用它把无序ids集合剖分为两个无序集合&＃xff0c;前一个集合的元素小于c&＃xff0c;后一个的元素大于或等于c。那么&＃xff0c;应该有一个集合的元素数量少于id区间的大小&＃xff0c;再把该集合继续剖分&＃xff0c;直至变成空集。

// 剖分 (总是传回最小id)
// 时间复杂度: O(n)
// 临时内存大小: M 字节(如果可改变ids则是0)
byte partition_stl(byte* ids, size_t n) {
assert(ids !&＃61; NULL);
assert(n byte buffer[M];
memcpy(buffer, ids, n);
byte *first &＃61; buffer, *last &＃61; buffer &＃43; n;
size_t l &＃61; 0, r &＃61; M;
for (;;) {
size_t c &＃61; (l &＃43; r) / 2;
byte* middle &＃61; partition(first, last, bind2nd(less(), c)); // O(n)
// 后置条件: l <&＃61; [first, middle)内元素 // 以下的条件测试次序保证了传回最小id
if (first &＃61;&＃61; middle)
return (byte)l;
else if ((size_t)distance(first, middle) last &＃61; middle;
r &＃61; c;
}
else if (middle &＃61;&＃61; last)
return (byte)c;
else if ((size_t)distance(middle, last) first &＃61; middle;
l &＃61; c;
}
else
assert(false);
}
}

此算法的妙处在于&＃xff0c;时间复杂度仅为O(n)&＃xff01;为什么呢&＃xff1f;因为partition()的时间复杂度是O(n)&＃xff0c;而此算法中每个迭代需处理的元素是n, n/2, n/4, ...&＃xff0c;把这个几何数列求和&＃xff0c;得出2n&＃xff0c;所以此算法为线性时间。

布尔集合

也许&＃xff0c;最多网友都想到的解&＃xff0c;就是把ids无序数组变换为另一个集合表示方式&＃xff0c;能更快地测试A是否不含某id。这种表达方式是使用一个布尔数组(boolean array)&＃xff0c;储存某id是否在ids无序数组里。用数学方式&＃xff0c;可以称这个数组为一个函数f:U\rightarrow \{0,1\}:

建立这个数组之后&＃xff0c;再扫描一次&＃xff0c;找出没使用到的id。

// 布尔集合 (总是传回最小id)
// 时间复杂度: O(n)
// 临时内存大小: M 字节
byte boolset(byte* ids, size_t n) {
assert(ids !&＃61; NULL);
assert(n bool id_used[M] &＃61; { false };
// 填充 id_used
for (size_t i &＃61; 0; i assert(!id_used[ids[i]]); // 此处断言失败代表ids有重复元素
id_used[ids[i]] &＃61; true;
}
// 扫描id_used去找出最小未用id
for (size_t i &＃61; 0; i if (!id_used[i])
return (byte)i;
assert(false);
return 0;
}

这类解法在纯函数API中是最快的&＃xff0c;但必须使用额外内存。

位集合

上述的解&＃xff0c;每个数组元素由于只需储存1个位(bit)&＃xff0c;可以把8个布尔值置于字节里&＃xff0c;减少额外内存。这种集合称为位集合(bit set)或位图(bitmap)。此外&＃xff0c;在32位CPU上&＃xff0c;可一次检查32位是否全0或全1&＃xff0c;这可是一个优化。这次&＃xff0c;我们直接储存补集A&＃xff0c;即是那些分配了的id会把位设为0&＃xff0c;那么在扫描时就不需做一个not位元运算。

// 位集合 (总是传回最小id)
// 时间复杂度: O(n)
// 临时内存大小: floor((M &＃43; 31) / 32) * 4 字节
byte bitset_standard(byte* ids, size_t n) {
assert(ids !&＃61; NULL);
assert(n const size_t dword_count &＃61; (M &＃43; 31) / 32;
dword id_unused_bits[dword_count];
// 开始时设全部id为未用(即设位为1)
memset(id_unused_bits, ~0, sizeof(id_unused_bits));
// 填充id_unused_bits (ids内的位清为0)
for (size_t i &＃61; 0; i size_t index &＃61; ids[i] / 32;
dword bitIndex &＃61; ids[i] % 32;
assert(id_unused_bits[index] & (1 <id_unused_bits[index] ^&＃61; (1 <}
// 扫描id_unused_bits&＃xff0c;找出最小未用id
for (size_t index &＃61; 0; index if (dword bits &＃61; id_unused_bits[index]) {
for (dword bitIndex &＃61; 0; bitIndex <32; bitIndex&＃43;&＃43;)
if (bits & (1 <dword id &＃61; index * 32 &＃43; bitIndex;
assert(id return (byte)id;
}
}
}
assert(false);
return 0;
}

在某些CPU上&＃xff0c;还会支持一个汇编指令bsf(bit scan forward)&＃xff0c;可扫描一个32位值里&＃xff0c;第一个为1的位索引(从LSB至MSB)。这正正是我们想要的。以下使用了Visual C&＃43;&＃43;的内部函数(intrinsic)去使用此指令。

// 位集合(使用内部函数(intrinsic))
byte bitset_intrinsic(byte* ids, size_t n) {
assert(ids !&＃61; NULL);
assert(n const size_t dword_count &＃61; (M &＃43; 31) / 32;
dword id_unused_bits[dword_count];
// 开始时设全部id为未用(即设位为1)
memset(id_unused_bits, ~0, sizeof(id_unused_bits));
// 填充id_unused_bits (ids内的位清为0)
for (size_t i &＃61; 0; i size_t index &＃61; ids[i] / 32;
dword bitIndex &＃61; ids[i] % 32;
assert(id_unused_bits[index] & (1 <id_unused_bits[index] ^&＃61; (1 <}
// 扫描id_unused_bits&＃xff0c;找出最小未用id
for (size_t index &＃61; 0; index dword bitIndex;
if (_BitScanForward(&bitIndex, id_unused_bits[index])) {
dword id &＃61; index * 32 &＃43; bitIndex;
assert(id return (byte)id;
}
}
assert(false);
return 0;
}

由于建立位集合所需的操作较布尔集合多&＃xff0c;扫描的优化未必能弥补&＃xff0c;所以位集合的主要好处是减低了临时内存的大小&＃xff0c;为布尔集合的八分之一。

含状态API的解

笔者对此题目提出另一种API的设计&＃xff0c;就是保存一些状态:

struct manager {
// 这里有一些状态变量(暂未决定)
byte alloc();
void dealloc(byte id);
};

而在工程上&＃xff0c;我们都可以估计到&＃xff0c;传给纯函数API的ids数组&＃xff0c;其内容实际上是以某方式储存在系统内的。若能改善它们储存的方式&＃xff0c;就能加速id的分配过程。

测试函数

同样&＃xff0c;笔者为此API设计编写了测试函数。纯函数API的测试函数每次都是独立调用&＃xff0c;但本测试的对象是有状态的。因此&＃xff0c;此函数设计为随机分配为释放id(各概率约为50%)。

template
void test_manager() {
T manager;
bool id_allocated[M] &＃61; { false };
byte allocated_ids[M]; // allocated_ids[0]至allocated_ids[id_used_count - 1]储存无序的已分配id
size_t allocated_id_count &＃61; 0;
srand(0); // 使每次测试的伪随机数相同
for (int test &＃61; 0; test // id集为空时必须进行分配&＃xff0c;否则若id集未满时&＃xff0c;有一半概率进行分配
if (allocated_id_count &＃61;&＃61; 0 || (rand() > RAND_MAX / 2 && allocated_id_count byte id &＃61; manager.alloc();
assert(!id_allocated[id]);
id_allocated[id] &＃61; true;
allocated_ids[allocated_id_count&＃43;&＃43;] &＃61; id;
}
else {
// 其他情况&＃xff0c;随机抽一个已分配id进行释放
assert(allocated_id_count > 0);
size_t index &＃61; rand() % allocated_id_count;
byte id &＃61; allocated_ids[index];
assert(id_allocated[id]);
manager.dealloc(id);
id_allocated[id] &＃61; false;
allocated_ids[index] &＃61; allocated_ids[--allocated_id_count]; // 用列表末的id取代已释放的id
}
}
}

此外&＃xff0c;这个测试函数不使用O(n)的contain()&＃xff0c;所有操作都是O(1)的&＃xff0c;测试的开销比较少。

布尔集合(含状态)

首先的解是把之前的布尔集合储存为状态&＃xff0c;那么就不用每次重新建立该集合。

// 布尔集合 (总是传回最小id)
// 分配的时间复杂度: O(n)
// 释放的时间复杂度: O(1)
// 状态所需内存: M 字节
struct boolset_manager {
bool id_used[M];
boolset_manager() {
for (size_t i &＃61; 0; i id_used[i] &＃61; false;
}
byte alloc() {
for (size_t i &＃61; 0; i if (!id_used[i]) {
id_used[i] &＃61; true;
return (byte)i;
}
}
assert(0);
return false;
}
void dealloc(byte id) {
assert(id_used[id]);
id_used[id] &＃61; false;
}
};

当然&＃xff0c;亦可以用位集合减少内存。此处就不再详述了。

这个解可以传回最小id&＃xff0c;但若是没此需要&＃xff0c;则有更快的解。

栈

笔者认为&＃xff0c;以下这个采用栈(stack)的解可能是本文最简单的一个解&＃xff0c;同时&＃xff0c;它的分配和释放时间复杂度皆是O(1)&＃xff0c;而且系数应为最低&＃xff0c;所以是本文最高效的解。

其原理很简单&＃xff0c;把整个U集合压入栈&＃xff0c;分配的时候弹出一个id&＃xff0c;释放的时候压回去。

// 栈
// 分配的时间复杂度: O(1)
// 释放的时间复杂度: O(1)
// 状态所需内存: M &＃43; 4 字节(使用short top会是M &＃43; 2 字节)
struct stack_manager {
byte ids[M];
size_t top;
stack_manager() : top(M) {
for (size_t i &＃61; 0; i ids[i] &＃61; (byte)i;
}
byte alloc() {
assert(top > 0);
return ids[--top]; // 弹出
}
void dealloc(byte id) {
assert(top ids[top&＃43;&＃43;] &＃61; id; // 压入
}
};

数组链表

而另一个接近高效的解是Qiaojie提出的&＃xff0c;把数组当作链表。这个解的分配和释放时间复杂度亦是O(1)。

// 数组链表 (来自qiaojie)
// 分配的时间复杂度: O(1)
// 释放的时间复杂度: O(1)
// 状态所需内存: M &＃43; 1 字节(若以freelist形式储存&＃xff0c;则所需额外内存只是1字节)
struct arraylinkedlist_manager {
byte next[M];
byte head;
arraylinkedlist_manager() : head(0) {
// 填入完整的环
for(int i &＃61; 0; i next[i] &＃61; (byte)(i &＃43; 1);
}
byte alloc() {
byte id &＃61; head;
head &＃61; next[head];
// next[id]在这里已经不需要&＃xff0c;可以用来放短讯或其他数据&＃xff0c;这里放置0作为测试。实际上这步是可有可无的。
next[id] &＃61; 0;
return id;
}
void dealloc(byte id) {
next[id] &＃61; head;
head &＃61; id;
}
};

这个解其实可称为free list&＃xff0c;其优点是&＃xff0c;next数组的元素若被分配&＃xff0c;则本身可以储存其他数据。所以实际上会占用的额外内存只是1个字节&＃xff01;例如&＃xff0c;可以把短讯的结构定义为:

// 用于数组链表的freelist的结构例子
union sms {
byte next;
char message[160];
};

此数据结构其实最适合做对象池(object pool)。

效能测试

以下是在i7 920、Windows 7、Visual C&＃43;&＃43; 2008 x86模式下的结果(单位为秒):

0.068476 test_average(dummy)
0.545491 test_average(linear_search)
3.030943 test_average(binary_search)
4.209131 test_average(sort_stl)
0.966749 test_average(heap_stl)
0.424917 test_average(partition_stl)
0.208690 test_average(boolset)
0.272523 test_average(bitset_standard)
0.271665 test_average(bitset_intrinsic)
0.068385 test_worst(dummy)
27.025864 test_worst(linear_search)
11.407150 test_worst(binary_search)
10.122118 test_worst(sort_stl)
13.912083 test_worst(heap_stl)
0.887030 test_worst(partition_stl)
0.498429 test_worst(boolset)
0.570213 test_worst(bitset_standard)
0.458865 test_worst(bitset_intrinsic)
0.042507 test_manager()
0.073745 test_manager()
0.042462 test_manager()
0.042526 test_manager()

当中&＃xff0c;dummy/dummy_manager为没有实际计算的测试对象&＃xff0c;用以量度测试本身的开销。读者比较时可把测试的时间减去相对的开销。

讨论

以下的表简单总括各个解的特性:

原题目中的需求中谈及「……我要求你的程序尽量快&＃xff0c;并少用内存。」但时间和空间是两个互相竞争的需求&＃xff0c;通常难以同时满足。而在上文中&＃xff0c;也把问题的API需求细分为:

1. 纯函数API
2. 可改动ids的函数API
3. 含状态API

本文列出的解并没有各方面都完美的解。例如&＃xff0c;在无需额外内存的纯函数解里&＃xff0c;二分查找在最坏情况下比线性查找的性能好&＃xff0c;但平均来说却是相反。

在变动数组(或复制数组)的纯函数解里&＃xff0c;剖分在平均和最坏情况下&＃xff0c;性能都比排序和堆好。剖分的优点是可以不占内存(当能改动ids时)&＃xff0c;性能又比查找好。

布尔集合和位集合的性能在纯函数解里是最好的&＃xff0c;但必须占一些内存(虽然当m&＃61;256&＃xff0c;位集合只需32字节)。

含状态的解中&＃xff0c;若需要传回最小id&＃xff0c;可使用布尔集合和位集合。不然&＃xff0c;可采用栈和数组链表。若在数组链表中以free list使用&＃xff0c;当然是最理想&＃xff0c;因为这只占1字节。但栈的性能会好一点点。

结语

个人认为&＃xff0c;本题是一个不错的面试题目&＃xff0c;因为它并没有一个各方面都完美的解。这样&＃xff0c;更可以考验应试者对算法的基础知识和编程能力。当然&＃xff0c;笔者在编写这些程序也花了多个小时&＃xff0c;在有限的面试时间中不太可能写这么多。但也可以用简单文字描述&＃xff0c;或在交流中讲解一些思考方向。个人认为&＃xff0c;理想的工程人员不但能解决问题&＃xff0c;还会知道有其他解的存在&＃xff0c;并去实验、分析、选择最适合某场合的解。

如果读者也想到其他的解&＃xff0c;或对上述解的改善&＃xff0c;希望不吝告之&＃xff0c;本人也会尽量整理于此。

下载源文件