跟大家分享一個悲劇

看板C_and_CPP (C/C++)作者yoco315 (眠月)時間18年前 (2006/03/23 01:54)推噓7(7推 0噓 12→)

留言19則, 7人參與討論串1/2 (看更多)

事情是這樣的，我實作了一個 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

推

drkkimo

03/23 02:06, , 1^F

03/23 02:06, 1^F

推

drkkimo

03/23 02:09, , 2^F

03/23 02:09, 2^F

推

PsMonkey

03/23 02:28, , 3^F

03/23 02:28, 3^F