經過昨天學長找到一個case來進行實驗,
發現了我們用的方法將會產生loop.

而我今天在慢慢的觀察下,找出為什麼會發生的原因,
主要是因為DP的觀念下,因為只和neighbor要資訊,

所以傳遞太慢了,以致於先被不好的deploy_map所取代,
然後我又把我們之前的grid的爛方法加進來,來解決這個問題,

一開始試小case時還好,還以為如願解決了,
一試大一點的又產生loop了,只是讓產生的次數少了一些,

當然除了這個之外,我一直再想,為什麼我們的程式會跑這麼的慢,
跑25x25的地圖竟要跑兩三天,之前是記憶體吃緊的關係,
我判斷兩個node是否為neighbor還是每次都去算是不是,

現在想想是不是該用空間來換取時間,想了約半小時到一個小時的架構後,
就決定要動工做這件事了,在程式一開始時,就存好每個點的neighbor_table,

開始進行只有執行速度提升,結果只會一樣的工作,
晚餐時我和學長提了我要做這件事,花了一段時間說服後,
並保證不會花費太多的時間,至少不會超過兩天,

寫快一點,我應該一個晚上就能夠搞定了,
他也半信半疑的覺得要不要做這工作,

只是我還是慢慢的說服他說要做就是了,
並且說老師不會關心這個事的,而且做的話以後也能用到,

後來晚上吃完晚飯,經過我前面的構思,就能夠馬上動工,
而差不多在十點左右,花了不到三小時就搞定了,

而一測之下....10x10的map.....原本的 2分40秒左右....
改過後的.....16秒....記憶體 多用了和整個程式比較來..少很多,

ㄟ...會不會快太多了啊...10倍耶...那我之前在做什麼啊...
囧rz......一開始就應該這樣做的...自己耍笨,

只因為當被那樣子比較好寫,就先寫......

其實目前解np-complete問題用的heuristic,
比起研究跑出來的結果變的接不接近optimal,

反而我會比較傾向於用同樣的想法,
研究時間複雜度降到更低,

這...可能以前大學acm寫多了...結果只有一個,
但程式跑的快不快才是重點害的 XD

而老師也不重視時間複雜度的問題...唉..做理論的都這樣,
所以才做np-c的問題.....

印象最深的就是 當初修影像處理時,
寫 傅麗葉轉換 的程式,

將一張圖片 用傅麗葉轉換 去高低頻,
再還原的方式,

特地去找寫成FFT的程式,
因為只有FT的話....只能做32x32的圖片...
好小一張啊....>Q< 和msn圖示差不多,可能還更小....
而且要跑個30秒一分鐘的

寫完FFT ....用512x512的都能在10秒內解決
這樣的程式作業 交出去才有爽度嘛 >Q<

我承認我瘋了,因為上課沒教FFT......
自己去看數學的定義,以及原理...然後再轉成程式.....

arrow
arrow
    全站熱搜

    Jzx0614 發表在 痞客邦 留言(0) 人氣()