none
遞迴的限制以及多少才會將記憶體用完? RRS feed

  • 問題

  • 各位大大
    小弟因為某個因素
    需要使用到遞迴

    所以大概有去找尋一些資料
    MSDN http://msdn.microsoft.com/zh-tw/library/81tad23s.aspx

    他有提到"您也應該確定不會因過多的遞迴呼叫而將記憶體用完。"

    小弟這裡想知道

    記憶體<==有多大呢?

    小弟要處理的字串為&H0FFFFF 的 Byte
    所以大約估算一下可能的最大遞迴次數 以每次只處理兩個Byte 那次數有524288次
    (我有測試其時處理的速度很快就處理完,並沒有造成記憶體不足。)

    不過小弟這裡還是很想知道
    每一次遞迴會使用多少記憶體
    以及最大可使用到多少記憶體

    麻煩各位大大可以幫小弟解惑一下
    可以的話
    如果有文件可以参考那就更完美了

    PS:順帶一提 奇怪 現在收尋怎麼都出現找不到資料
    2009年2月3日 上午 08:00

解答

  • 從你的程式碼來看,DataArray 會呼叫自己,並且傳入 BufStr 字串,而這個字串的內容從頭到尾都沒有改變(若我說錯了請指正,因為我直接跳過中間一些程式碼了),並且用一個 NowDot 來當作字串索引,指向目前要處理的字元位置。

    若上面所說無誤,你的 NowDot 變數是宣告在此函式之外,那何妨將 BufStr 也宣告在外面?這樣就一樣可以用遞迴(程式碼變動最小),但不用反覆傳遞參數,也就不用太擔心記憶體是否爆掉的問題(當然每次遞迴呼叫還是需要額外配置堆疊的記憶體,只是用量變少了)。

    若剛才的解法行不通,或你不想這麼做,還可以把 BufStr 參數移到函式裡面。用一個迴圈把現有的處理程式碼包起來,效果也是一樣。換言之,這種情況看起來並不需要用到遞迴。

    再提供一個想法,但這個建議會改比較多:捨棄 NowDot 字串指標做法,改用 StringReader。因為,看起來字串中處理過的部分就不需要了,可以丟掉了,這種情況便可以考慮用串流的方式來處理。只是額外想到的,參考看看啦。

    One final note: 其實很多遞迴的場合都可以用迴圈解決,問題只在於哪一種解法比較適當,端看個人的考量了。
    http://huan-lin.blogspot.com/
    • 已標示為解答 動不了 2009年2月4日 上午 05:20
    2009年2月4日 上午 04:48

所有回覆

  • 不知道你在開發甚麼樣的應用程式,不過,與其探究記憶體空間所能容納的最大遞迴數量,建議你先考慮別種作法。例如:切成多個區塊或 buffer 來分段處理、改用迴圈處理等等。
    http://huan-lin.blogspot.com/
    2009年2月3日 下午 12:13
  • TO Michael Tsai大大
        其實我也有想過用區塊來做,
        因為我BUF的格式算是也很固定
        
        FFFF時間日期data1234567890........FFFF時間日期..................FFFF時間日期
        其實我只要找到 "FFFF時間日期"來切割字串
        不過因為前人function已經寫好了,我有點懶的變更
        才想說看看可以遞迴幾次
        謝謝大大了

    2009年2月4日 上午 12:44
  • 從你描述的檔案格式看來,似乎不需要用遞迴耶。我想,一個迴圈也許就能解決了。
    若不嫌麻煩,可將關鍵程式碼貼上來,大家會比較知道怎麼幫你出主意。


    http://huan-lin.blogspot.com/
    2009年2月4日 上午 01:19
  •  Sub DataArray(ByVal BufStr As String) '處理
            Dim rx As Regex = New Regex("^(?:(?:[0-5]\d)){2}(?:(?:[0-1]\d|2[0-3])){1}(?:(?:[0-2]\d|3[0-1])){1}(?:(?:0\d|1[0-2])){1}(?:(?:" & Year1 & "|" & Year2 & ")){1}$")

            Dim i As Int16, iLen As Integer

            Do While Mid(BufStr, NowDot + 20, 4) = "FFFF" And rx.IsMatch(Mid(BufStr, NowDot + 24, 12)) = True
                NowDot += 24
            Loop
            If Mid(BufStr, NowDot + 20, 8) = New String("F", 8) Then Exit Sub

            Date_T = ""
            Date_D = ""
            For i = 1 To 3
                Date_T = Mid(BufStr, NowDot, 2) & Date_T
                NowDot += 2
            Next i
            Date_T = Mid(Date_T, 1, 2) & ":" & Mid(Date_T, 3, 2) & ":" & Mid(Date_T, 5, 2)

            For i = 1 To 3
                Date_D = Mid(BufStr, NowDot, 2) & Date_D
                NowDot += 2
            Next i
            Date_D = Date.Parse(Mid(Date_D, 1, 2) & "/" & Mid(Date_D, 3, 2) & "/" & Mid(Date_D, 5, 2))

            Time_Gap = Val("&H" & Mid(BufStr, NowDot, 4) & "&")
            Call TMS() '計算時間
            NowDot += 4
            Dim temp As String = HEX_To_BIN(Mid(BufStr, NowDot, 4))
            NowDot += 4
            For i = 1 To 16
                If i >= 1 And i <= 8 Then
                    Save_Data(i) = Mid(temp, 9 - i, 1)
                Else
                    Save_Data(i) = Mid(temp, 25 - i, 1)
                End If
            Next

            Dim sb As StringBuilder 
            Do
                Application.DoEvents()

                sb = New StringBuilder

                For i = 1 To 14
                    Select Case i
                        Case 1 To 8
                            iLen = 6
                        Case Else
                            iLen = 4
                    End Select

                    If Save_Data(i) = 1 Then
                        sb.Append(Mid(BufStr, NowDot, iLen))
                        NowDot += iLen
                    Else
                        sb.Append(New String("-", iLen))
                    End If
                Next

                sw.WriteLine(Date_D.PadLeft(10, " ") & Date_T & sb.ToString)

                Call DateTime()
            Loop Until NowDot >= BufStr.Length Or G_Quit = True Or (Mid(BufStr, NowDot, 4) = New String("F", 4) And rx.IsMatch(Mid(BufStr, NowDot + 4, 12)) = True) Or Mid(BufStr, NowDot, 8) = New String("F", 8)

            If Mid(BufStr, NowDot, 4) =New String("F", 4) And Mid(BufStr, NowDot, 8) <> New String("F", 8) And rx.IsMatch(Mid(BufStr, NowDot + 4, 12)) = True Then
                NowDot += 4
                Call DataArray(BufStr)'當 遇到"FFFF"後面又是時間及日期時,後面又不是FFFFFFFFFFF"
            End If

        End Sub

    '=============
     NowDot是我的旗標
    取八個F是因為不可能出現
    如果出現表示後面沒有資料了
    麻煩大大幫我看一下 要如何修正會比較完美

    2009年2月4日 上午 01:48
  • 遞回的空間在 10 kb 內,沒多大。
    線上手冊有寫,自己翻一下。盡量用靜態記憶體、共用記憶體、傳址呼叫來節省記憶體損耗。
    2009年2月4日 上午 03:19
  • 遞迴只是變相地在使用堆疊,而且用的還是受限的 thread stack ...

    那麼 ...
    何不直接用堆疊來寫呢?
    若以 list-based stack 取代遞迴呼叫,那麼你的 process heap 有多大就可以處理多少個 level,就算是數以百萬計的樹狀階層也能夠輕鬆突破的 ...

    至於效能?那從來就不是個問題啦 ...^^
    2009年2月4日 上午 03:51
  • 從你的程式碼來看,DataArray 會呼叫自己,並且傳入 BufStr 字串,而這個字串的內容從頭到尾都沒有改變(若我說錯了請指正,因為我直接跳過中間一些程式碼了),並且用一個 NowDot 來當作字串索引,指向目前要處理的字元位置。

    若上面所說無誤,你的 NowDot 變數是宣告在此函式之外,那何妨將 BufStr 也宣告在外面?這樣就一樣可以用遞迴(程式碼變動最小),但不用反覆傳遞參數,也就不用太擔心記憶體是否爆掉的問題(當然每次遞迴呼叫還是需要額外配置堆疊的記憶體,只是用量變少了)。

    若剛才的解法行不通,或你不想這麼做,還可以把 BufStr 參數移到函式裡面。用一個迴圈把現有的處理程式碼包起來,效果也是一樣。換言之,這種情況看起來並不需要用到遞迴。

    再提供一個想法,但這個建議會改比較多:捨棄 NowDot 字串指標做法,改用 StringReader。因為,看起來字串中處理過的部分就不需要了,可以丟掉了,這種情況便可以考慮用串流的方式來處理。只是額外想到的,參考看看啦。

    One final note: 其實很多遞迴的場合都可以用迴圈解決,問題只在於哪一種解法比較適當,端看個人的考量了。
    http://huan-lin.blogspot.com/
    • 已標示為解答 動不了 2009年2月4日 上午 05:20
    2009年2月4日 上午 04:48
  • 謝謝各位大大了
    經過大大們這些的討論
    小弟我豁然開朗

    前人會這樣做
    有問過他們的說法
    是因為字串很大
    所以不想每次處理好一個段落
    就將處理好的字串刪除
    所以使用的個指標再做OFFSET的動作
    靜量減少記憶體搬動的動作

    沒想到自己卻陷入這個牛角中鑽不出來><"
    Michael Tsai大大說的沒錯字串從頭到尾沒有改變

    所以我目前決定使用FOR迴圈來改寫不要讓程式再做遞迴的動作

    另外大大有提到StringReader的作法,小弟實在愚昧完全想不到要如何做呢?

    也謝謝 dgSpirit 大大
    但是小弟我不了解堆疊的作法 不知道使否有相關資料可以參考呢?

    2009年2月4日 上午 05:20
  • StringReader...簡單解釋一下,其實它就像內部有個 NowDot 字元指標的 buffer,你可以一直呼叫它的 Read 方法取出字元,而無須自行維護指標。
    可以研究一下 MSDN 上面的範例:http://msdn.microsoft.com/en-us/library/system.io.stringreader.aspx,再寫點程式 try 看看,應該就能了解用法了。但最好是先把迴圈的部分改完,如有餘力、時間,再來考慮其他部分的調整。
    http://huan-lin.blogspot.com/
    2009年2月4日 上午 05:37
  • 謝謝大大了
    迴圈的部份我已經修改好了
    剛剛實際測試一下
    都OK了
    StringReader的做法
    小弟目前在練習中
    如有問題就要再麻煩各位大大了
    2009年2月4日 上午 05:54