Final Blog

SUMMARY I think about this for a long time, and I have read lots of programs, which contain single thread or multiple threads. In my  opinion, some of them are not very good, that is why I write this blog. SINGLE THREAD Single thread program is simple for us, there is no lock to care, … Read more

Ok, a long time did not write a new blog since last wrote, there were so many things what I have to deal with. Sorry about that. So, the new blog I’ll introduce that Why we need to use Git instead of SVN. I have introduced many people to use it, and I also have … Read more

问题: 我们在写程序的时候, 经常会碰到重置一大块连续数组空间的问题, 我们把问题简单化, 比如有 “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 … Read more