JAVA學習筆記：續DFS (深度優先搜尋) 改良方式~

之前有因為論文需要做有向網路的計算
所以最後採用的是DFS演算法去看兩點之間 2~6步距離路徑總數

JAVA學習筆記：以DFS (深度優先搜尋) 尋找兩節點間所有路徑

但其實後來遇到的問題相當多~以下列舉一下

1. 演算法時間複雜度相當可怕：
    當時在網站 stackoverflow上抓到的程式雖然精簡，但因為我後來修改的時候都只使用小型網路
    edge約22條、node 10個，所以在試驗的時候計算都非常快，根本就是秒殺!!!
    結果最後真正輸入我的資料的時候，挖喔~時間就爆炸了ㄝ~~>.^
    事實上，當時我最大的網路edge有數十萬條，node也是上萬個....
    可想而知，如果等他算完，我大概是兩年後畢業吧(轉圈)

     當時解決方式：增加過濾條件，把不必要的資料移除
     結果：我們選了一個過濾完資料量最小的類別來做實驗~因為資料量變很小很小很小~
     所以計算速度就飛快了XDDDD

2. 網站上的程式，node存取的資料型態是String：
     我到了今天才知道，原來資料型態是真的真的真的影響程式速度很重要的主因XDDDDD
     應該說我終於認命了....

      好在有學長幫我看了程式，他指出我整個DFS的Graph形成、node比對等等的都是使用String
      這個也是造成時間複雜度爆炸的原因之一~~>.^
      因此學長建議我把String改成Integer~ 所以再做一個HashMap來對應原本User (node)跟index
      而且學長還建議做一個雙向的HashMap~~這樣不論用String還是Integer都可以馬上查到對應的UserID或是Index!!!!!


恩~~於是我回來之後~~在剛剛終於改好了~~

真的變快了ㄝ!!!!  雖然用的資料量是不夠大的XDDD
但我覺得比之前快多了....

送啦!!!


PS  雖然很開心~~但這些跟論文結果好壞都沒有直接關係>.^