巧用未初始化的数组

Table of Contents

问题:

我们在写程序的时候, 经常会碰到重置一大块连续数组空间的问题, 我们把问题简单化, 比如有 “int array[N]” 这样的数组作为hash映射表, N是个非常大的数字, 当插入元素M的时候我们就令array[M] =1 ( 0 <= M < N ), 在使用了一段时间后需要对其全部重置为0, 要求时间尽可能的快, 并且假定我们的内存是充足的.

对于上面的命题, 往往会有几种常见的解决方案:
1. memset
2. 用额外的链表记录有哪些位置是修改过的, 最后根据这个链表的记录去重置指定位置的值

OK, 现在我们来看一下以上这两种方案的优缺点:
方案1: 实现起来最简单, 只需要一行代码 memset(array, 0, N)即可. 不过随着N的增大, 我们在时间上的损耗也是巨大的, 而这个array有可能仅仅有少数几个位置的值发生了改变, 我们不必要去遍历以便把所有的值都重置一次, 显然这不是我们需要的方案.
方案2: 根据这个链表我们可以解决方案1中不必要的遍历过程, 我们准确的重置仅被改变的位置即可. 不过问题也随之而来, 链表的特点让构造其自身节点的成本上升, 而更悲剧的是如果修改过的节点数目过多, 甚至接近原array的大小, 那反倒不如memset了.

让我们来反思一下这个问题, 这两个方案都陷入同一个思维误区–要清除(重置)已经被修改过的数值. 然而我们其实并不需要那样也可以做到”重置”. :)

解决方案:

无意间看到Russ Cox的一篇文章: http://research.swtch.com/sparse , 这篇文章可以说是完整的描述了该问题的解决方案, 我在这里仅仅说几条特别重要的, 着重阐述一下利用这个方案解决的实际问题.

√ 首先我们需要明确几个先决条件:

1. 内存是廉价的

2. 时间是昂贵的

3. 数组是稀疏的

√ 该方案的思路是: 准备2个等长数组, 一个稀疏作为hash, 一个稠密作为记录元素值. 最关键的一点是稀疏数组的值是用于关联稠密数组而使用, 其记录的是稠密数组真实元素值的下标, 附其原图:

所以, 检测元素是否在其中也非常简单:

is-member(i):     return sparse[i] < n && dense[sparse[i]] == i

而我们关心的问题, 重置数组则变得十分简单:

clear-set():     n = 0

其时间复杂度仅为O(1), 我们不必去重置每一个改变过的值, 重置n=0, 即表达了当前稀疏数组中没有数据发生改变, 此时稀疏数组中残留的数据我们也大可不用关心了, 因为is-member function会保证这一点. :D, OK, 这样看起来我们的两个数组都是未初始化的, 却能正确的完成功能, 是不是很cool.

由于篇幅有限, 我就不在此多费笔墨阐述其原理, 如果对其原理还有不解, 可以参看其原文. 下面说下利用此方法具体解决的问题.

应用:

在编写linux网络库的时候, 我们常会遇到这样一个循环:

 memset(firelist, 0, n);
 int num = epoll_wait(...);
 for(int i=0; i<num; i++) {
     if( firelist[fd] ) continue;
     process(...);
 }

这里, firelist的作用就是标记在一次wait loop中被remove掉的event, 这样我们就放弃处理它. 很显然, 这里通过memset重置firelist显得过于低效, 尤其是当n非常大, 且firelist很稀疏的情况. 然而这里我们正好可以利用上面的思路去改进它, 保留firelist并将其作为稠密数组, 增加一个稀疏数组作为hash映射.我们添加3个接口:

void add_firelist(int fd)
{
    firelist[n] = fd;
    sparse[fd] = n;
    n++;
}

int is_fired(int fd)
{
    return sparse[fd] < n &&
        firelist[ sparse[fd] ] == fd;
}

void clear_firelist()
{
    n = 0;
}

这样, 我们回过头在修改下源程序:

 clear_firelist();
 int num = epoll_wait(...);
 for(int i=0; i<num; i++) {
     if( is_fired(fd) ) continue;
     process(...);
 }

至此, 我们就非常简单的完成了其的优化工作, 是不是很简单有很高效 :D

详细的源程序请见: https://github.com/finaldie/final_libs/blob/master/fev/fev_epoll.c

have fun :) , btw, 本文中出现的图引用自Russ Cox的文章. thanks.

问题:

解决方案:

应用:

Related