2012年6月30日星期六

单链表删除节点的技巧

单链表删除节点的技巧
     -- 注:删除节点非尾节点!
 


在此分享一个小小技巧,在单向链表中删除节点时不必知道其前面节点(若存在前面节点的话),亦可高效地完成删除节点。

===
从一篇别人的博文说起吧,引用自这里,内容很少,仅此如下:

标题:学习数据结构的感想
在链表中删除动作比较多的时候,用双联表比用单链表效率要高,双链表不用从头开始遍历去删除,而是可以直接删除。
用单链表删除的时候,每次知道需要删除元素的前一个指针就好了。不过这个好像很难知道。

我是在无意之间,看到那位朋友的上面问题,先是无意间网上搜到他转载了我的一篇博文《STL稳定排序源码分析》,好奇之下到了他的csdn博客的。
所以我就一时兴致勃勃回复了其问题,与之讨论,内容如下:

===
单向链表删除节点时候,可做到不需要知道(若有的话)上一个节点同样完成删除操作。你可以这么做,描述如下:
原来的链表 ... A -> B[b_ptr] -> C[c_ptr] -> D[d_ptr] ...
现在要删除节点 B,其对于指针为b_ptr注:删除节点非尾节点,重要

首先你可以使用B得到C,D指针,c_ptr和d_ptr,然后你可以用C去覆盖掉B,即*b_ptr = *c_ptr,那么这时你可以删除C即可达到你要的结果即删除节点B。具体操作:
*b_ptr = *c_ptr;
b_ptr->next = d_ptr;
delete c_ptr;

结果的链表 ... A -> C[b_ptr] -> D[d_ptr] ...
按照以上的操作,这样就不需要从头去遍历链表定位上一个节点A了,简单有效吧☺。

===
但是,删除节点不应该为尾节点(链表的最后一个节点),因为B作为尾节点,虽然你可以删除节点B,但无法给节点A的next赋值NULL。若删除的节点为尾节点,那就得老老实实从头遍历链表了,将其前面节点A的next赋NULL。

===
当然你说的“用双(向)链表比用单链表效率要高”,是对的。确切说应该叫实用性高吧,但是其实现的逻辑要复杂不少,可参见STL链表的实现源码。像C++ STL里面的链表(包括单向双向)底层的实现都是以双向链表形式的。可以参考sgi stl源码std::liststd::slist

(完)

2012年6月28日星期四

一种特殊的排序算法 II



一种特殊的排序算法 II
  -- 计数排序(Counting sort)

后续想找时间再写一篇《一种特殊的排序算法 II》,关于计数排序☺。(引自 《一种特殊的排序算法 I》)

所以,继上篇文章《一种特殊的排序算法 I》,在此就(继续)描述,总结另一种特殊的排序算法,计数排序。算法的步骤如下:
  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数,存入数组C的第i
  3. 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
  4. 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1

引用自维基内容,完整介绍可以参见计数排序(维基)

(后面,开始分享我的内容)
关于计数排序(算法),可以划分两种具体的计数法,如下:
 * 比较计数法
 * 分布计数法

===
> 比较计数法
算法 ComparisonCountingSort(A[0 ... n-1])
          // 用比较计数法对数组排序
          // 输入:可排序数组 A[0 ... n-1]
          // 输出:将A中元素按照升序排列的数组 S[0 ... n-1]
          for i : 0 to n-1 do 
               Count[i] = 0;
          for i : 0 to n-2 do
               for j : i+1 to n-1 do
                    if A[i] < A[j]
                         Count[j] += 1;
                    else
                         Count[i] += 1;
          for i : 0 to n-1 do
               S[Count[i]] = A[i];
          return S;

该算法的时间效率如何?答案为O(n^2)。因为该书法执行的键值比较次数和选择排序一样多,并且还占用了线性数量的额外空间,我们几乎不能推荐它来实际的应用。但是计数思想在一种情况下还是卓有成效的,在这种情况下,待排序的元素的值都来自于一个已知的小集合,这就是下面要描述的另一种计数排序算法,分布计算法。

===
> 分布计数法
算法 DistributionCountingSort(A[0 ... n-1, l, u])
          // 用分布计数法对数组排序,对来自于有限范围整数的一个数组进行排序
          // 输入:可排序数组 A[0 ... n-1],数组中的整数位于l和u之间( l <= u)
          // 输出:将A中元素按照升序排列的数组 S[0 ... n-1]

          for i : 0 to u-l do 
               D[i] = 0;                       // 初始化频率数组
          for i : 0 to n-1 do 
               D[A[i] - l] = D[A[i] - l] + 1;  // 计算频率值
          for i : 1 to u-l do 
               D[i] = D[i-1] + D[i];           // 重用于分布值

          for i : n-1 downto 0 do 
               j = A[i] - l;
               S[D[j] - 1] = A[i];             // D[j] - 1]为对应的数组下标
               D[j] -= 1;

 
        return S;

注:频率值,表示元素出现的次数;分布值表示在最后有序数组中,元素最后一次出现的位置。


假设数组值的范围是固定的,这显然是一个线性效率的算法,因为它仅仅对输入数组A从头到尾连续处理两遍,其时间复杂度 O(n)。然而,要重点记忆的是,除了空间换时间之外,分布计数排序这种高效率是因为利用了输入列表独特的自然属性。

===
附:
文章内容乃学习心得(笔记),亦包括引用自《算法设计与分析基础(第2版)》内容(第七章时空权衡,7.1计数排序)。
以上描述的算法,以C\C++完成了简单的实现,示例代码参见 github


(完)

2012年6月27日星期三

一只兔子的深情故事


转:那些你爱过的人,总会在平行时空爱着你.

  -- 一只兔子的深情故事

前几天在同事的日志上,看到一篇转载文章,故事以一只(雌性)小白兔为载体讲述一段不顺利的爱情故事,令人有种触目伤怀,为之惋惜的感情流露,颇为感触。或许你已经看过了该故事,那不免再读一遍吧。好吧,开始转载故事(from here),如下 ……





那些你爱过的人,总会在平行时空爱着你。小兔子故事的另一个版本,有些悲伤……小象版本比较大团圆,可现实总是这么心酸吗?



1.
小白兔有一家糖果铺,小老虎有一个冰淇淋机。兔妈妈告诉小白兔,如果你喜欢一个人呐,就给一颗糖他。小白兔喜欢上了小老虎,那么那么喜欢,忍不住就把整个店子送给了他。回家后兔妈妈问她,那小老虎喜欢你吗。小白兔直点头,妈妈说,那他为什么不给你吃个冰淇淋呢。
2.
小白兔说,他是要给我来着,我说我不爱吃。兔妈妈说,那你真的不爱吃吗,有七种口味呢,巧克力味道的里面还有你最爱吃的杏仁啊。小白兔用脚划拉着地板,喃喃的说,其实我也没吃过,只是就想着把糖给他了。
3.
小老虎有了糖果店,小白兔说不如我帮你把冰淇淋机推到公园去卖吧。夏天可真热啊,冰淇淋每天都卖得光光的,大家都夸小白兔好聪明。小白兔呢,还是一口也舍不得吃。她就想等小老虎亲手送她一个,小白兔自己也没发现,她最爱的口味已经换成了香草,想要的也不再只是冰淇淋了。
4.
时间一天天过去了,小白兔还是没有吃到冰淇淋。倒是隔壁摊子卖饼干的小熊,给了她一盒小兔子造型的曲奇。小白兔留下糖果店和冰淇淋机给了小老虎,跟小熊去了更远的小公园卖饼干。兔妈妈问她,你不是不喜欢吃饼干吗,怎么又收下了呢。小兔子揉着红红的眼睛说,我就是饿了。
5.
后来小兔子听说,小老虎把冰淇淋机送给了小企鹅,和她一起住在了糖果店里。小熊把这些告诉小兔子的时候,她耷拉着耳朵呆了很久。小熊开玩笑的问她,你是不是后悔没有吃个冰淇淋再走呀。小白兔愣愣的转过脸说,就是有点难受,没能留些糖给你。
6.
小兔子卖力的帮着小熊卖饼干,没多久就又攒了一笔积蓄,买了新的糖果铺。这次兔妈妈千叮咛万嘱咐,她说宝宝啊,这糖要慢慢的给,不然后来就不甜了。小兔子 嘴上连连答应,心里却想着小熊收到糖果店该多开心啊。她只知道小熊又加班去了,不知道他小鸭子形状的饼干马上就要烤好了。
7.
小兔子回家看到了偷偷藏起来的小鸭子饼干,什么也没有多问,只是跑回家跟妈妈大哭了一场。她呜咽着和兔妈妈说,小熊最喜欢吃糖了,我终于可以给他糖果屋了,他为什么要离开我呢。兔妈妈笑了,她摸摸小兔子的头说,当他不爱你了,你的糖就不甜了。
8.
小兔子还是想不通,只好带着糖果店搬去了更远的地方。小鸭子可不是什么善茬儿,她不知从哪里打听到了糖果店的事。一天饭后,她揶揄的告诉小熊,哎呀你可不知道吧,你心里最单纯的小白兔,背着你用卖饼干的钱给自己买了好东西呢。不久之后,小兔子就收到了小熊的来信。
9.
信里只有短短几句话,大致是说小兔子走后饼干铺子生意一直不好,钱怎么说也是卖饼干挣来的,希望小兔子能把糖果店还给他。小兔子看完信后眼睛哭成了桃子, 她想起了妈妈的话,把店给了小熊。兔妈妈说小兔子是韭菜馅的脑子勾过芡的心啊,她说妈妈,其实糖还是甜的,只是人生太苦了。
10.
后来小白兔又爱过几个人,都无疾而终了。这缺心眼的小兔子啊,喜欢上一个人,就会使劲对他好,恨不得掏心掏肺给他看。她以为只有这样,才能让爱情活得更久更久一些。可惜那时候的小兔子还不明白,其实任何东西啊只要够深,都是一把刀。
11.
有一天小兔子出门,发现小熊醉倒在她门口。他哭着碎碎念着,说他过的不开心,说糖果店已经被吃完了,小鸭子嫌他没本事拍拍屁股就走了。 他一把抱住小兔子说,如果说着世界上我还有什么值得得回忆的,大概也只有你了。 小兔子被勒的喘不过气来,他心里想着,也许爱上一个旧人,就不会再有新的问题了吧。
12.
很久很久以后,小兔子和别人讲起这段故事,总是感慨万分的说,那些值得回忆的事啊,就该永远放在回忆里。
13.
不知道你又没有玩过一种游戏机,投硬币的那种。有好多小爪子推啊推,硬币们互相推搡着,摇摇欲坠却又固若金汤。拟投入的越多就越难收手,机器里的硬币落得越厚重就越不会有收获,可越是不掉币你就越觉得大奖就要来了。这逻辑很有趣,它只在你输的时候成立。可小兔子就是这么觉得的,她在万丈悬崖边,以为跳下去是学会飞翔的捷径。她默默地想,大奖终于要来了。她被大把硬币即将掉落的景象迷红了眼,以至于忘记了,自己没有翅膀。
14.
既然是童话,总得有点好的不是。小兔子回到了小熊身边,日子没有想象中的糟糕。一起吃饭,逛逛公园,小熊每天都采一朵最漂亮的花回来送给她,小兔子会做一手好菜,小熊总是抢着洗完。小熊以为一切都好了,他甚至点点失望,都说感情是刻骨铭心的,可小兔子似乎没留下任何伤痕。多可笑啊,那些拿刀子去花豆腐的人,永远都不知道疼。
15.
直到有一天晚上,小熊从厨房出来,随手递了一块饼干给小兔子。小兔子摇摇头,说我好久不吃饼干了。然后她抬起头看着小熊,淡淡的说,你给过别人的东西,就不要再给我了。小熊一瞬间明白,这些伤口还是血淋淋的。那年小兔子扑在妈妈怀里哭得那个下午,他就已经弄丢他的小兔子了。一起弄丢的,还有原本可以幸福的可能。
16.
可小熊舍不得小兔子,小兔子自己也没发现自己当初的喜欢,已经只剩下不甘心。日子还在继续,小兔子除了还是不吃饼干,什么都是百依百顺的。在别人眼里,他们俨然成为了恩爱的一对儿。直到有一天,他打开一只旧箱子,里面装满了小熊每天送她的花。花都枯萎了,小兔子想起这些日子,她每天接过小熊的花都是敷衍的笑笑,转身便扔进这个破箱子里。她一下子发现,原来不爱了,是早就不爱了。
17.
和小熊分手后,小兔子断断续续的又开过几个糖果店,卖的卖送的送,也所剩无几了。可她还是学不会开口,说她饿,说她想要吃个带杏仁儿的冰淇淋。她把给糖果当成了一种惯性和礼节,看起来和从前没什么差别。她还给它们报了亮晶晶的糖纸,但小兔子心里明白,它们早就没有味道了。
18.
后来小兔子结婚了,是和其貌不扬的小猪,再后来还有了两个孩子。小猪是隔壁村子来旅行的,据他后来说,是来小兔子店里买糖的时候,一眼就喜欢上了这个小机灵。小猪一连来了好几次,每次都是买完糖,付了钱,又悄悄把糖留下。兔妈妈说,这样的孩子品行好,可以嫁了。小猪果然也没让兔妈妈失望,结婚后包揽了所有家务,他家都夸小兔子好福气。小兔子也总是笑眯眯的,她常常摸着两个孩子的头说,如果你们喜欢上一个人啊,就找他要一颗糖。
19.
故事就要结束了。没人知道,当年小猪留下的糖,是小兔子准备吃下的毒药。小兔子明明知道是有毒的,却也懒得阻拦就卖给了小猪。她想,这些贪图甜腻的人啊,总该受到些惩罚。当她刚准备重新拿出毒药服下的时候,发现了小猪买走的糖,居然安安静静的放在罐子中。
20.
第天小猪又来了,第三天也是。小兔子还是给他有毒的糖,她甚至不明白自己为什么要这样残忍,他总想着只要小猪收下一次,一切就都结束了。可小猪每次都巧妙的放回了罐子里,然后趁小兔子还来不及发现就走了。小兔子在和自己较劲中,似乎又看到了春天。他幸免的不只是那些有毒的糖果,而是小兔子这些年对这个世界巨大的失望。终于他们相爱了,后面的故事也水到渠成了。
21.
可她忘记了兔妈妈说的,你拿谎言去考验爱情,就永远遇不到真心的爱人。
22.
有一次小猪喝多了,朋友们起哄问到他当时怎么想到不收下糖果。小猪被灌了太多酒,回答的稀里糊涂,颠三倒四。但当那些字组合在一起,传到小兔子耳朵里时。在场的谁也没听懂,只有她在一瞬间放声大哭。
23.
小猪说,那天啊,那天我只是路过来着,小熊硬塞的钱,小老虎说如果我能把糖放回去,冰淇淋机就是我的了。
24.
嗯,故事说完了。
别哭,这世界是守恒的。你付出的每一颗糖都去了该去的地方。
那些你爱过的人,总会在平行时空,爱着你。

(完)

2012年6月26日星期二

一种特殊的排序算法 I


一种特殊的排序算法 I
     -- 位排序 OR 桶排序


绝大部分经典的排序算法,都是以元素间的比较为基础,如冒泡,选择,插入,快速,归并,堆排序等,虽然这些排序算法的时间和空间复杂度存在不同,但其算法平均时间复杂度均不超过O(n logn) (基数排序也比较特殊可做到O(k*n),详细对比情况可以参见维基排序算法
===

而下面内容描述的排序算法比较特殊,并非以元素间比较为基础的,其算法时间复杂度达到了O(n)。先来看看一道简单的示例题目吧(引用自:Google groups TopLanguage
   
特殊排序算法题目,如下:
     姓名集合names,名次集合ranks,按照名次顺序输出她们的名字,要求O(N)的时间复杂度。

解法如下: 
     解法一,不改变原来集合顺序,O(N)时间, O(N)空间。
     描述: 数组下标相当于姓名索引,新空间以名次顺序依次记录着姓名索引。

     解法二,在位重新排序,改变原来集合顺序,O(N)时间, O(1)空间。
     描述:每一次swap确定一元素的位置,最多总共N次swap能全部定位。


具体的程序设计(C/C++)代码在这里
===

有一种特殊的排序算法,在《编程珠玑I II》有讲述到的位排序(bitsort),也称桶排序
其实,上面的排序题目正是位排序的一种变种的应用,不知你是否已经发现了否?

位排序算法的整体思想,可以描述如下:
     1. 每字节有8bit(位),那么它就可标记8个连续的数,分别对应每bit位,若数值存在则对应bit位置为1。
     2. 把N个数分为1+N/8组(相当于有这么多个桶),每组标记连续的8个数。
     3. 申请(1+N/8)字节数组均初始化为0,遍历要排序的集合,存在的元素在对应的bit位标记1。
     标记规则: array[i/8] = (array[i/8] | (1<<(i%8)))
注:算法描述的字节亦可替换为整型类型,对应的比特位数字变为32。


===
关于位排序,同样可以瞄瞄其他网友描述,这里
后续想找时间再写一篇《一种特殊的排序算法 II》(20120629更新链接),关于计数排序☺。

(完)



2012年6月21日星期四

资源的拥有权


资源的拥有权
     -- C++程序申请与释放资源小结

开篇先引用一下,《Effective C++》的条款16:成对使用new和delete时要采取相同形式。简单的示例就是下面这样的,如下:

  example 1.
     type* ptr = new type;
     ...
     delete ptr;


  example 2.   
     type* ptr = new[10] type;
     ...
     delete[] ptr;

 
  还有C语言的版本,如下:
example 3.
     type* ptr = (type*) malloc(sizeof(type));
     ...
     free(ptr);   
      
一条编程实践的经验条款,经如上的简单示例显得很简单,浅显易懂。类似地,我想在此延伸到另一点:在哪里申请资源,最后就在哪里释放资源吧。
PS. 这里提到的“哪里”,其实理解了模块更好一些。若缩小了(作用域)范围如函数显然不妥,做不到在函数A申请资源,又在函数A释放资源,毕竟资源是要提供给对外使用的。若“哪里”理解成类型,好像还可以如某工厂类,其负责对象的创建和析构。

比如说,在模块A申请资源R,资源R属于多模块B,C,D等共享的,那么最后应该同样在模块A释放资源R。
虽然,一般情况下你在其它模块最后使用完资源R之后即完成释放,不会出现什么问题,但是这样的逻辑看着也令人觉得也不合理乎。“某女人生的孩子,日子过着过着,结果孩子长大成人了,却客死他乡了。”多么令人遗憾,心生不妥啊。(额,我承认举得例子太言重,恐怖了)

某些情况下,这种做法(在其它模块是否资源R)明显会出现程序异常情况,如释放资源导致程序崩溃。

什么情况下呢?
答:当其它模块如B,C,D模块编译链接时候所使用的运行时库与模块A的不同,如VC++编译器的不同运行时库包括如下:
多线程 (/MT)
多线程调试 (/MTd)
多线程 DLL (/MD)
单线程 (/ML)
单线程调试 (/MLd)



还有另一种情况,更可能导致程序异常,模块A与其他模块使用着不同的内存分配器

所以,你应该(或必须)做到在同一模块申请和释放内存资源。如模块A存在这样成对接口:
resource* allocate_resourse(...);
void release_resourse(resource* res);

这样,不管模块A,或其他模块B,C,D若需要新的resource,即通过模块A接口allocate_resourse申请;若最后用完了resource,即通过模块A接口release_resourse完成释放。逻辑也足够简单。


忌讳、痛恨那种在模块A申请资源,却在其他模块做释放资源的。很可能,最后你(程序)怎么死的都不知道。
好吧,最后总结一句,资源的拥有权始终保持唯一性。

(完)

2012-06-18/ Junkun Huang.



2012年6月16日星期六

被入室盗窃的事记


被入室盗窃的事记
     -- 生活故事之2012-06 被入室盗窃


2012-06-01,由于那件令人费心费神的房屋租赁纠纷的事情,而且其过程还甚是漫长(去年10份开始算起),吾与同学共三人一同到法院去与那位‘无敌极品’房东继续对簿公堂。额,这件事情足以长篇大论一番,在此就不多详述了(已整理一大部分),待日后事情了结再完成吧。
诶,2012年六月份第一天,主要新闻如上,貌似挺友好的。还亏当天是六一儿童节啊!


可惜,没过几天后面的故事更加令人‘瞠目结舌’,生活常常会有一些事情出现让你措手不及啊,而且是那种你不喜欢碰到的不愿面对的……说到这点上,不禁让我想起以前的听过有意思的那么一句话,“生活总是有趣的,又很好玩的,而且常常喜欢玩(弄)我。”。好吧,转发我的两条微博,开始我的一段生活故事,如下:

晚上下班回家,发现家里遭贼了啊,丢失笔记本一台,一部G1手机,义雄和我是受害者!。报警能有用吗?报了。

报完警,被警察接到派出所备完案,然后再回家拍照取证等,折腾完都半夜十二点多快一点了,'惨不忍睹' 洗洗睡觉睡觉。困- - !

--------- 分割线 --------- 分割线 --------- 分割线 --------- 分割线 --------- 分割线 ---------

至此,什么样的故事应该大致清楚了吧,够杯具乎,不,餐具也!家里被入室盗窃了,主要损失即一台Thinkpad笔记本,一部智能手机。

零零碎碎地整理着描述一下吧,如下:
诶,这几天事情多费心费神的,各种折腾各种坎坷啊。
还有什么比家里遭贼了,被入室盗窃的,更坑爹的吗。


同学三人白天都上班,晚上下班,那天九点多到家我最早了,一会儿雄也回家了,然后才发现家里遭贼了。他的thinkpad笔记本连带电池,鼠标一套不见了(尼玛的,不这么谈心会死啊),然后我才发现我的那部落在家里的手机也不见了,被入室盗窃了……
奇怪的是,我的电脑竟然幸免了。唯一可以接受的原因就是,该小偷不敢或是不便一下子偷了带走两台笔记本,害怕容易暴露被发现、怀疑。可以继续推测,该小偷不是专业小偷,只是一个生活无赖的小偷。但他懂得同学的thinkpad比起我的acer高级,就选择了thinkpad,诶!

当天晚上果断出去找师傅换锁了。犹豫了会儿后还是报了警察(虽然心知此举在该国度效果不明显但还是报了吧算是寻求一点点心里慰藉),接着,跟同学又去了趟附近派出所录了笔供,再接着,与两位民警一同回家拍了照取了证。

种种迹象看来,那小偷有钥匙开门进来,入室盗窃的。门锁没有发现没撬动痕迹。
而且,那天早上我是最后一个出门上班的,清清楚楚记得自己反锁了两扇大门……刚好那天要带着垃圾出去丢了,出门时先放下垃圾袋在大门一旁然后锁门锁门……晚上回家时候,奇怪的发现两扇大门都没有发现,当时我没有在意以为同学先回家了吧。直到(上面描述情况)……发现情况不妙。

……

之前租房时候,雄问房东门锁是否安全,房东说已更换过了,当时他就这样算过去了。
(我也是事发之后,问起门锁安全吗,才听雄这么说起的 - -!唉。)
然后我们就匆匆忙忙地搬进来入住,当时没心思留意更换门锁这点,后来也忘了……直到被入室盗窃那天,都住了两个多月。

这次的租房,我当时各种忙碌没时间所以都让雄去操心租房的事情了,现在想想觉得我有点后悔与愧疚,当时我应该分担一些,多考虑些安全问题。

第二天早上,我询问隔壁的大妈,他们一大家子都住在隔壁一般都有人在家,问问道些情况,或许可以了解到线索。不料大妈说到情况,“昨天下午三点多我们家里灯亮着,外门关着,内门留着小缝隙而开着。”,“好像是09年还是10年时候,以前也是你们这件间屋子503遭贼被盗过笔记本和手机 …… ”

我当时听着有些恐怖毛骨悚然的感觉,照情况看来这小偷十成八九有着钥匙的,真的为之前两个月的日子捏了把冷汗啊,完全没安全感了!即使现在换好锁了安全感也大打折扣啊。


有朋友提醒,会不会你们房东自己安排干着的这趟事啊。不会,应该不会吧,但愿不会吧,否则我等完全败了!

虽然门锁已更换好了,但自身的安全感被严重打击受损了,所以这几天上班都开始背着本子一块上下班的,还好并不怎么重。估计还要持续背包上下班一段时间吧,至少把自己放心下来,安稳些日子吧。

这等糟糕的事情既然发生了,也报了警(中间虽然犹豫了会儿,知道后面也需要麻烦配合警方工作)。发了条微博说“……报警有用吗?报了。” 好多朋友纷纷回复,都质疑了报警的有效性。
少数的几个朋友表示理解,报了警可以为自己受损的心理图个小小的慰藉,或曰小小的希望吧。

其实,我就是这么个想法才报了警,暂且图个心理慰藉吧。Good luck!

20120606 / Junkun Huang.



(201206016 更新)

刚好这周六不必上班,所以跟附近警务室管理监控录像的工作人员预约了时间上午10点,到时我过去查看录像。唉,可惜的是盯着监控屏幕看到中午12点半,仍然未果,那些已有的监控录像实在是没法令人看出个啥毛线(锁)啊。虽然楼下安装了三个摄像头,但是那些都是楼房负责人私人安装的,警察那边问了负责人,话说录像没有保持了。擦,难道那几个摄像头是假的,忽悠人的吗!

上周六,同学雄已看了那些监控录像内容,未果。听着监控录像的工作人员说,请示警察去获取其他更有线索的监控录像资料,俺们就抱有希望警务人员能够联系到楼房负责人,获取到楼下最近摄像头的监控录像。额,这两天竟然说那三摄像头的监控录像都没保存。鸟啊!

而警察安装的那几个摄像头,倒是均有监控录像保持下来,可供查看。但是但是最最狗血的是,最靠近我们楼房的那个摄像头那天正好被某大妈晾的衣服给挡住了,我勒了个去啊,监控录像画面大部分被一件白色T恤挡住了,唉。所以,只能对着其他摄像头的监控录像查看了,而且只有一个靠谱一点,另外的真是相隔太远了。

至今天,之前心里对于警察办案抱有那一丝希望也抹灭去了。
洗洗去了啊,早点睡觉!

“生活总是有趣的,又很好玩的,而且常常喜欢玩(弄)我。” 

20120616 / Junkun Huang.

(完)


删接口,哥以后惹不起了。


# 删接口,哥以后惹不起了。 
     -- 越是稳定的产品项目,其接口越不予改动。

# 背景

今天遇到一件比较尴尬的工作上事情,虽然有些后悔,但也没有啥不好意思的。所以就想在此描述聊聊,吐吐内心里的小小“憋屈”。
其实,只是涉及一个小小的程序改动,不过故事倒是不短。那开始讲起……

最近工作上都挺忙的,事情多需要经常多线程切换操作,这边事情那边事情的:
负责日常项目管理事务(项目计划安排,组织开会讨论等),负责版本控制安排(版本统一编译,提测,配合打包等),负责项目开发工作,负责配合测试的工作(撰写需求、设计文档,梳理、解释、讨论设计逻辑等),负责解决问题(包括测试发现的问题,关注崩溃系统问题,用户反馈诡异问题等)。
(故事背景,当是讲故事前奏预热吧☺)

# 故事

前一阵子,某项目涉及一个接口的修改,而该接口为异步返回结果,描述如下:
原来,调用者不需要关心其返回结果。一个简单接口可以满足,
int set_xxx_func ( ... );

现在,新的需求决定调用者要关心其返回结果,调用之后调用者需要以轮循的方式查询结果。此时需要两个接口得以满足:
int submit_set_xxx_func ( ... );
int query_set_xxx_func ( ... );

PS. 至于这里为啥是轮循方式查询?在这里不是重点不需关心☺,具体的系统设计决定了这样的形式吧,不过当然是callback机制的效率高于一筹了!不再多说了,否则离题了。

说到这里还没有说到重点呢,改接口。后来因这样的新需求决定如上描述修改了该接口。记得在过(讨论)详细设计方案时候,开发测试四人(包括YJ,JL,SY还有我)都提到了是否保留原来接口set_xxx_func的问题,讨论中确认了已经没有其他产品,其他模块在使用该接口了,而且差不多已一年的时间没有使用到了吧,最后大家均同意了去掉该接口吧,直接上新的接口吧。因为该接口的模块一直都是跟着另一接口层模块DK一起发布的(该点是问题的所在),只要保证到时DK模块一块更新新的接口就万事大吉了。

好吧,那就果断去掉吧,我当然乐意了。作为开发人员,我已经难受很久那些“无用久已”的接口了,看着就觉得接口资源浪费在那儿,一个dll导出了四百多接口不少了吧,而且也碍着程序猿们查看代码啊。注意,这里带着当初一时比较重的个人感情色彩。汗。。

修改过程,与DK模块一并更新了新的接口设计,后面也完成了开发与测试,提测顺利完毕了。没出啥接口方面的问题,就不再关心了,以为没事就放心了。

差不多过了三周的时间吧。突然在今天下午,兄弟部门某同事突然报了一个问题到了欧爷(My TL)那边,转给了我。查了原因,他竟然使用了旧版的DK模块,Check不到老接口set_xxx_func了,囧,然后程序刻意做就地崩溃下来了。

这时,欧爷大怒了(可能夸张了点,其实情况还好吧)。痛批,“ Too simple,too stupid!,你们怎能去掉老接口呢,甚低级错误也“。

虽然某同事使用接口不当,但崩溃这种不良情况确实发生了,我有点愣住了,必须无条件承认自己过错了。奇怪,当初我们四人咋都同意了如此做法了呢。即使留着旧接口吧,也不崩溃。回想揣摩一下,”该接口的模块一直都是跟着另一接口层模块DK一起发布的“ 其实,这只是一条”一直以来都这样“的常识判断,而不是某确定的发布方案。

# 结果

情况还好,产品版本未发布,还在测试改错阶段。尽快恢复老接口,修补该问题即可。
越是稳定的产品项目,其接口越不予改动。

……
好吧,故事就讲到此吧。
所以,删接口,哥以后惹不起了。谨记!

晚安好梦。

(完)

20120615 / Junkun Huang.


2012年6月14日星期四

代码风格杂谈

代码风格杂谈


在此,想随便说说几句关于C++程序代码风格的话题。

以前,我所在的项目大组(下载库)的程序代码,基本都是C++代码,一直沿袭的代码风格大致情况描述,如下:

1,内部逻辑
Linux风格,统一小写字符配合下划线。该风格规范为内部使用的代码命名风格。

2,对外接口
驼峰风格,大小写字符配合,单词首字符大写。该风格规范为对外接口使用的代码命名风格。详细参考驼峰式大小写(维基)

大驼峰式命名法(upper camel case):
每一个单字的首字母都采用大写字母,例如:FirstName、LastName、CamelCase,也被称为Pascal命名法。


其实,我一直赞成,推崇这样的代码风格规范。关键一点,其做到了内部逻辑与对外接口之间的明显区分。

--------- 在此分割吧 ---------

现在(其实是去年九月份就开始制定了规则),我们所有涉及的新项目有关于C++代码,其风格均采用统一的“驼峰风格”。

不管内部逻辑与对外接口,函数命名规则均采用大驼峰式命名法
变量命名规则统一为,匈牙利命名法。


相比“以前”和“现在”,个人感觉“现在”不好的地方在于:
(程序的函数)不能从代码命名规则层次上,快速地区分出代码逻辑属于内部处理或对外暴露的。

话说回来了,既然当时讨论会议上,多数同事支持了“现在”的风格,规则已定下,那就安分遵循吧。

其实嘛,只要你在命名规则上做些善意的“手脚”,还是可帮助你较快地区分出其所属的内外逻辑,如:

void InnerFunc1();
void OutterFunc2();

如下示例只是简单说明情况,具体安排设计依具体情况而定。

     / 2012-06-10/ Junkun Huang.
--

最后,推荐良好的代码风格可参考,列表如下:








2012年6月11日星期一

盖茨将被历史铭记,乔布斯会被忘却?

盖茨将被历史铭记,乔布斯会被忘却?


文章最后总结的那一点,如下:
“他们并非有道德的领导者。如果他们是有道德的领导者,那么就不会成为伟大的商人。因此,当一名商人同时也是伟大的有道德的领导者时,那是因为他们保持着独立于公司业务以外的道德心。”
原来,慈善威武的地方正是如此,最终还是盖茨明智啊!

(转载如下)

纽约客:盖茨将被历史铭记 乔布斯会被忘却?


腾讯科技讯(童云)北京时间6月8日消息,《纽约客》杂志专职作家、曾是《华盛顿邮报》商务科学专栏作家的马尔科姆·格拉德威尔(Malcolm Gladwell)最近参加了在多伦多公共图书馆召开的苹果沙龙,他对美国文化中的企业家精神有一些有趣的深刻见解。
“在我们的文化中,我们尊敬企业家。”格拉德威尔说道。“他们是我们新的先知。让我们一个字一个字的来说吧:我们尊敬他们。如果你正在读有关伟大企业家的文学作品,那么可能会把它们当做‘肖像学’或是‘圣徒言行录’来读吧。”
那么,这些企业家是否值得这种高度的尊敬呢?格拉德威尔并不这样以为。
到最后,企业家受人尊敬的原因是他们如何帮助人类,而并非其大量赚钱的能力。他对传奇企业家比尔·盖茨(Bill Gates)和史蒂夫·乔布斯(Steve Jobs)进行了对比,以此作为一个例子:
“盖茨是最无情的资本家,然后有一天他起床后对自己说:‘够了。’然后他辞职,拿走了属于他的钱。”
“我鉴定地相信,在从现在算起的五十年以后,盖茨将因他在慈善事业方面所做的工作而被人铭记,而那时甚至没人会记得微软是什么。”
“而作为这一时代中的伟大企业家,乔布斯则将被人们忘却。谁是乔布斯?而盖茨的雕像则遍及整个第三世界。”
那么,象乔布斯这样的企业家为何不值得被偶像化呢?格拉德威尔指出,所有伟大的企业家都有一件事情是共通的。
“最伟大的企业家都是不分是非的。这并不是说他们是不道德的,而是说他们超越了是非。”他解释道。在2011年为《纽约客》撰写的一篇有关欧莱雅与纳粹德国之间交易的文章中,他曾说过这个问题。
“他们都是彻头彻尾的单细胞,着魔般的集中致力于他们企业的健康性。”格拉德威尔说道。“那让他们擅长建设企业,但也正因如此,他们才不值得受到这种程度的尊崇。”
“因此,当我们崇拜企业家时,我们需要搞清楚我们崇拜的是什么。”格拉德威尔说道。“他们并非有道德的领导者。如果他们是有道德的领导者,那么就不会成为伟大的商人。因此,当一名商人同时也是伟大的有道德的领导者时,那是因为他们保持着独立于公司业务以外的道德心。”

转载自这里

下载与上传速度计算的总结


下载与上传速度计算的总结
     -- 从良好的用户体验出发,速度计算乃一门艺术活儿。


# 背景说明

首先,背景说明一下,这里要探讨的速度涉及到两部分,一个下载速度,一个上传速度。

前段时间从事的一个项目开发,正好涉及到计算速度,要求在界面提供有速度的显示。刚开始认为要显示速度应该很简单的逻辑,计算公式如下:
download_speed = download_bytes / tick_time_count;
upload_speed = upload_bytes / tick_time_count;


照此,若要计算每秒的即时速度,只需获取每秒的流量差值结果即可,足够简单吧☺。
# 情况描述

但是,我们上面涉及的问题很单纯,忽略了产品设计细节上的很多东西,复杂的元素。
有必要先说明清楚我们产品的在统计速度方面,大致流程是怎么设计的,如下:
--
为了方便描述逻辑,在此先定义我们产品的两进程p1和p2,说明,p1负责具体的下载逻辑,p2负责下载展示与用户交互。
-- 1,p1进程实时更新流量统计值download_bytes,upload_bytes 。
     在系统应用层,毕竟下载与上传逻辑都是在p1进程直接处理,足以做到实时更新,提供准确信息。
  
2,p2与p1的通信均为异步-轮循机制。所以p2投递异步请求获取流量统计值,然后轮循尝试获取结果。
     两进程通信是单方面,只有p2向p1投递请求,而p2获取请求结果需要以定时轮循方式得以获取。
  
3,p2获到统计值download_bytes,upload_bytes ,与上次获取的流量统计值download_bytes’,upload_bytes ‘相比得到差值
 diff_download_bytes,diff_upload_bytes 。

4,p2同时取得p1返回流量时的时间戳tick_time_count,与上次的时间戳tick_time_count‘,相比得到差值diff_tick_time_count。

5, 差值与时间代入以上速度计算公式,最后得到速度值。
     download_speed = diff_download_bytes / diff_tick_time_count;
     upload_speed = diff_upload_bytes / diff_tick_time_count;

6,界面显示的速度值为6秒的平均速度,作为平滑效果的处理。
# 问题剖析

那么,产品上面具体的复杂细节在哪里?个人的总结可能不太全面,描述如下:

1,统计流量的地方与显示速度地方不在同一进程。
     p1负责流量统计而不涉及具体的速度计算,该点主要从逻辑分层方面考虑,一个属于功能逻辑,一个属于具体的业务逻辑。
     p2可以周期从p1获取流量统计值,根据具体场合计算所需的速度。

2,两进程通信为异步交互,存在堵塞导致延迟。
     由于下载与上传涉及逻辑诸多,p1进程需要处理的请求可能很多很多,导致p2获取流量的请求等到一段时间才得以处理返回,出现延迟现象。这样,请求时刻与计算速度的时刻出现较大的时差。
     其实,第二点是由第一点而引起的。

    

# 歇后语

像以上的情况,要想进程间的尽量同步(准确)显示速度,的确是一件考验的事情啊。

如同事振振所说的,”公司单独安排一同事负责这方面工作的研究,设计好速度显示的用户体验,也不为过。”

所以,从良好的用户体验出发,速度计算乃一门艺术活儿。



2012年6月7日星期四

生活玩你的故事(微博)

生活玩你的故事(微博)
 -- 201206 转自我的微博

故事零零散散碎碎,心情凄凄惨惨戚戚,围观如下:



报完警,被警察接到派出所备完案,然后再回家拍照取证等,折腾完都半夜十二点多快一点了,'惨不忍睹' 洗洗睡觉睡觉。困- - !

[图片]

-- 分割线 --
晚上下班回家,发现家里遭贼了啊,丢失笔记本一台,一部G1手机,义雄和我是受害者!。报警能有用吗?报了。
-- 分割线 --
Today,某故事又暂时告一段落,诶。不断“修身”淡然加明智,克制冲动与愤慨,在深圳与一’无敌极品‘房东的漫长而艰辛的故事。 #深圳中级法院#

Bless me,good luck!

(完)