Re: [問題] 遞迴與堆疊-Connected Component label

[yauhh (喲)]

※ 引述《MaconChou (得罪了方丈還想走)》之銘言：
: 程式說明：
: 此function為要在圖片上找尋是否有255的光點如有的話
: ，進行connected component label由1～n，圖片大小目前為640*480。


: 4.是否有撰寫遞迴時須注意的小地方！？
: 5.或許除了使用遞迴之外是否有比較理想的方式！？

你的程式使用漣漪式的搜尋,有很多重覆的檢查,並且可能因為遞迴使Stack overflow.

既然目的是要找connected component,程式可以分二個階段,第一個階段是掃描圖檔
找出全部的光點,傳回光點位置的陣列. 第二階段是在位置陣列中將鄰接項目整理成
同一個component.

資料順序一定是先碰到component左上角,於是,可對每一筆資料,在後續陣列中尋找
右/下/左下/右下相鄰的光點位置,都可以列為同一個component.

----------------------------
遞迴方面:
起碼朝左/左上/上/右上的檢查可以刪掉,那些在之前都已經做過了.
左下/右下也可以刪掉,因為往下走一行的時候,遲早會檢查現在左下和右下的項目.

或者是,目前你用ConnectedComponent和FindPixels二個函數共用,有迴圈也有遞迴,
其實這樣重覆掃了同一個格子好幾次. 你可以改設計成全遞迴搜尋,則block狀態要
怎麼改,則要運用一下智慧.
------------------

另外,你的工作需求是不管多大的component都必須能找完. 而衝突的因素是,在遞迴
搜尋中,遇到格點太多的component就會Stack overflow. 那麼,解決辦法可以是設定
一個遞迴的中斷點,是一個遞迴總數的計數器,這是個跨遞迴instances的狀態變數.

因你的問題叫做connected component,在遞迴次數在可容許的數目之前,結束這次
遞迴,必須要將接下來要做卻沒做的工作接續下去. 也就是你要從這次遞迴中,傳回
一些資訊告知主控端ConnectedComponent,要開另外一些遞迴呼叫,從這次遞迴的
結束點開始繼續做. 這個意思就是要把目前發生遞迴中斷的位置放在某個變數中,
可能是指定為函數的傳回值,或者是在遞迴函數的參數列多加幾個狀態變數(然而
這樣的動作會增加遞迴的Stack負擔). 主控端收到遞迴要繼續的信號,就可以從
遞迴中斷位置再開啟一個新的遞迴呼叫. 這樣環環相扣可以保持你的程式不會意外
中斷.


--
補充: 至於推文說遞迴多可怕多濫用的... 資訊領域不欠這一類廢話.
      一個東西你想用就用,不用就不要用. 能用的時候自己知道善用就好了.
      不要盲目說"那個東西會怎樣"於是就永遠不用.
      不要用一種很瞎的方式,不經討論就徹底說它壞.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.225.35
※ 編輯: yauhh           來自: 59.112.225.35        (09/02 07:10)
推 ledia:這就是遞迴的濫用, 容易寫出很難 scale up 的程式
→ yauhh:so what?
→ yauhh:那你可以告訴我,他每個遞迴呼叫使用了多少Stack空間嗎?
→ yauhh:若真的要討論,請巨細彌遺的討論.不要囫圇吞棗地放話.
→ yauhh:那我提個問題好了,以原程式來看,640x480的數字,如何產生使
→ yauhh:Stack overflow的遞迴量? 請說說看,平均一個遞迴呼叫,以這樣
→ yauhh:的資料量,最多有多少個遞迴單位佔用Stack空間?
※ 編輯: yauhh           來自: 211.21.94.199        (09/02 12:00)
推 ledia:他寫圖片大小目前為 640 x 480, 可以請問這位先生妳拍的照片
→ ledia:的大小都是多少 ?
→ ledia:你要不要算一算 640 x 480 的 function call 跟用迴圈比起來
→ ledia:速度差多少?
→ ledia:不應該用遞迴的地方用遞迴本來就是濫用, 不會因為你特別擁
→ ledia:護遞回, 就會變得天下無敵了
→ yoco315:ledia 你跟他認真你就輸了, 這個人程式寫的之爛
→ yoco315:補充: 可能不是真的很爛, 只是跟我比起來很爛
→ yoco315:當然, 也比 ledia 還要爛...
推 nowar100:版友討論請保持心情和緩，小心違反板規，鎖文處理
→ nowar100:解鎖