作者yoco315 (眠月)
看板C_and_CPP
标题跟大家分享一个悲剧
时间Thu Mar 23 02:02:25 2006
事情是这样的，
我实作了一个 O(n) 的 suffix tree 建构函数，
大家都知道 suffix tree 酷的就是那个 O(n)，
所以写好了当然要测试一下速度。
测试分成两阶段，
第一阶段是正确性验证，
我先给他一些比较短的字串让他建 suffix tree，
最长大概就是人工可以验证的长度，
我去网路上蒐了另外一个 java applet，
然後比对 suffix tree 来验证正确性，
事後证明是无误
（吧！）。
第二阶段是效率测试，
（悲剧）
听说这个 suffix tree 如过没写错的话，
长度 1,ooo,ooo 的字串也可以在
几秒钟建完，
当然我没这麽多力气慢慢打 1,ooo,ooo 个字去让他跑，
懒惰是程式设计师无上的美德，
所以我给他两个变数 n,k，
让他根据乱数产生器产生长度 n，字元集大小 k 的随机字串，
然後丢给函式去跑 suffix tree。
快乐的事情来了，
我发现当我的字元集是 2, 4, 8, 16.. 等数字的时候，
这个 suffix tree 就跑不完，整个程式就 hang 在那边，
跑的很慢很慢，但是还是有动，只是真的很慢，
但是不是这些数字的时候，则是一瞬间就建完 suffix tree。
我怀疑我的程式有很难抓的 bug，
有一类 bug 很度烂，就是要大量测试资料或是大量计算以後才会
偶而浮现，
例如你写了一个 multi-layer perceptron 神经网路，
却发现他在 XOR 问题一直无法收敛，
这时候你很难确定你的程式是不是有 bug，
因为他也可能是回馈系数太大导致震荡学习。
更可怕的是这种时候你的 input 是
随机的，
这表示你没办法复制他，或是即使可以复制你也很难分析，
在测试了多次以後，我拼了！
我决定先找出大概的点之後用人工慢慢 trace，
我花了很多功夫不断的去逼出程式到底是从什麽时候开始变慢，
我发现当 k=2 的时候，程式会在建立第 131,073 个 suffix 的时候比对到字串尾部，
因为比对完 1,ooo,ooo 个字元要很多时间，所以整个程式就是慢在这边，
通常都是比对几个字元以後就 branch， 所以很快就完成动作。
k = 4 的时候，则是会停在 262,145，
k = 8 的时候，停在 524,289，
k = 16 的时候，停在 1028577。
这真是神奇！杰克！
比对到字串尾部代表这个字串有超过几十万的部分是完全一样的重复才有可能！
但是我是用
乱数产生字串，最好是有可能连续数十万个字完都完全 match！
我觉得我的程式有错，但是我不可能真的去 trace 131073 次回圈来抓这只虫，
所以我决定检视我的程式码，看看能不能用肉眼看出来，
但是我看了很久很久，都看不出任何问题，
我感到很绝望，我感觉可能我永远抓不到这个 bug。
只有当 k 是 2 的幂次的时候这个 bug 才会发生也一直很困惑我，
奇怪，当 k 是 3, 5, 6, 7, 9, 10, 11, 12.. 的时候程式都是一瞬间就结束，
为什麽当 k=2 的时候会在 131073 字串就开始完全重复？
131073.. 131072.. 2 的 17 次方.. 2 的 16 次方..
可能有人早就想到原因了，不过我是在这刹那才想到.......
.................乱数产生器循环了.......................
所以每 2 的 17 次方整个字串就会重复一次，
所以才有办法连续 match 好几十万个字元一直到一百万！
虽然一直都知道乱数产生器会有循环，
但是被整到还真的是第一次，
实在很难相信这麽衰的事情会发生，
绝大多数的状况下即使乱数循环也无所谓，
在 suffix tree 的随机字串很碰巧有所谓，
而且还害我
以为我那没有 bug 的程式有 bug，
白白忙了一整个晚上，是个悲剧。
恩，还好最终还是被我想到了，
跟大家分享一下 T______T
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.129.180
1F：推 drkkimo:对suffix tree不太熟 改天了解看看.. 03/23 02:06
2F：推 drkkimo:是说ｃ的乱数产生器循环吗？ 不知道它的周期是多少？ 03/23 02:09
3F：推 PsMonkey:虽然看不太懂，不过还是推一下... >///< 03/23 02:28
4F：→ PsMonkey:光看标题还以为是张爸文 [逃] 03/23 02:28
5F：推 hiroshiyui:看标题还以为是张爸文 [溜] 03/23 02:30
6F：推 ckclark:所以还是改个标题吧..... 03/23 02:33
7F：→ yoco315:．．．．．．．跟大家分享一个悲剧．．．．．．． 03/23 02:46
8F：→ yoco315:张爸标题前後有点点点点 XD 03/23 02:47
9F：推 cplusplus:哈哈 辛苦你了~! 没想到会这样呀... 03/23 02:49
10F：→ cplusplus:不过这样是否也显示suffix tree对重复性很高的pattern 03/23 02:50
11F：→ cplusplus:效率会很差呢~? 我只对suffix tree有初步研究而已 03/23 02:50
12F：→ cplusplus:可能有其他改进的方式吧 对了 最近有一个演算法 是为了 03/23 02:51
13F：→ cplusplus:cpu cache特别设计的 据说比ukkonen快上好几倍 你可try 03/23 02:51
14F：→ cplusplus:前面说错 是tree construction 不是tree本身效率不佳 03/23 02:53
15F：→ yoco315:但是重复性刚刚好在某个程度的时候建构效率则最差 03/23 03:36
16F：→ yoco315:仔细分析的话，重复性很低／高，ST的建构都可以很快 03/23 03:37
17F：→ yoco315:(以上两句推反XD)完全循环则是一个特例.. 03/23 03:37
18F：→ yoco315:我对 suffix tree 只会基本基本基本...|| 03/23 07:06
19F：推 uqljnro:刚试了一下，我的c++乱数产生器循环是2^30 03/23 21:21