2008年7月6日 星期日

理論與現實

這篇只是描述剛遇到的小例子,不是要探討什麼大道理。

這段話說得太有道理了,先引用一下:

In theory, there is no difference between theory and practice. But, in practice, there is.

By Jan L. A. van de Snepscheut 

剛才很快樂地實作別人的方法來補我的碩論實驗,結果遇到一個作者沒考慮到的情況,於是程式就噴了。理論上這是不會發生的,但實務上因為浮點數的誤差,造成這個 bug。看來得用強硬的方式解掉。

舉個類似的例子說明我的情況,用 Quadtree 存地理性資料時,當一個 region 內的資料數量超過上限時(比方每個 region 不要超過五個點),會把該 region 切成四個 sub-region,理論上可以無限地切下去直到所有 region 的數量都小於給定值。

事實上,當一部份點很散(造成起始 region 空間很大),而大部份點極為密集時,切到後來會因為 region 空間過小,浮點數不精確,而使得某些點「不屬於」任何 sub-region。比方說 region 左上角的 x 變成 296.999999999988,寬度則切為 1.82751591637498e-11,結果四個 sub-region 拼不回原來的 region。

幸好我有加 assertion 檢查是不是所有點都在切開的 sub-region 內(如同廢話般的檢查),不然寫到後面 debug 時就慘了。隨手養成的好習慣,總會在無形之中救了自己。

沒有留言:

張貼留言