Monthly Archives: February 2012

1 post

巧用未初始化的数组

问题: 我们在写程序的时候, 经常会碰到重置一大块连续数组空间的问题, 我们把问题简单化, 比如有 “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了. 让我们来反思一下这个问题, […]