2016-05-15 83 views
3

更新:請注意,現在這個問題沒有多大意義,因爲callstack將獨立於類型T而增長。callstack完全取決於正在處理的列表中的節點數 - 這些數據包含在節點對調用堆棧的大小沒有影響。遞歸使用多少堆棧(從列表中刪除節點)?


比方說,我有一個遞歸java實現了「刪除節點 - 從列表」的方法看起來是這樣的:

// head 
public void remove(T data) { 
    if (data == null) 
     throw new IllegalArgumentException(); 
    head = remove(head, data); 
} 

// other nodes of list 
private ListNode remove(ListNode current, T data) { 
    if (current == null) 
     return null; 
    if (current.data.compareTo(data) == 0) 
     return current.next; 
    current.next = remove(current.next, data); 
    return current; 
} 

讓我們進一步假設該類型Tint

我的問題是:與我正在處理的列表大小相比,調用堆棧會得到多少(在最壞的情況下)?

什麼我至今認爲: 從我所看到的Java 8不優化遞歸(?右我的整個分析假設這是真的)。因此,我們將有一個與列表大小成線性增長的調用堆棧。

更確切地說:這個方法remove(ListNode current, T data)將基本上在我的列表中的每個節點的調用堆棧上放置一個節點引用(32位位置上的32位)和一個int(也是32位)。

現在,由於列表中的一個節點也由一個引用和一個節點構成,因此節點實際上與其中一個遞歸調用的大小几乎相同。實際上,其中一個調用甚至可能會佔用更多空間(返回地址也必須被推入堆棧,對嗎?或者可以通過某種方式進行優化?)。

所以,如果我是正確的,那麼在最壞情況下(當要移除的元素是列表中的最後一個時),callstack基本上會像列表本身一樣大!這是真的嗎?如果我是正確的,那麼就處理int列表所需的堆棧而言,這意味着1或甚至更大的因子!因此,當處理大型列表時(實際上並不那麼大),比如說1M人將獲得一個stackoverflow,如果用stacksize(0.5M)的默認設置運行的話,我會得到一個stackoverflow。我知道這樣一個事實,對於更大的數據類型來說,這個因子會更少,但是我仍然堅信在任何情況下基本上都是這樣的:如果沒有進行優化,那麼callstack將隨着列表大小線性增長 - 因此一個應該更喜歡遞歸過程的迭代。

一般來說,我會說,這個callstack將會以一個因子(size_of_all_arguments_in_call + size_of_return_address)/size_of_a_single_listelement粗略線性增長,在int列表的情況下,它幾乎是一樣的,對吧?請不要誤解我的size_of_all_arguments:我知道我們只傳遞對這些調用中對象的引用的值,而不是整個對象本身。因此,對於大型物體來說,這個因素可能不會那麼戲劇化,但我仍然認爲不應該接受不必要的線性空間開銷。但是,對於int的列表,該因子將是約。 1.

這個分析是否正確,或者我錯過了什麼?

背景:我與討論這樣做的人,試圖說服我,在Java調用堆棧不會那麼顯着增長,並指出我缺少明顯的東西(很遺憾沒能告訴我什麼,對我來說真的不是很明顯的話) - 因爲我不知道它是什麼,我很想念我渴望學習;)

相關:

在我相關的問題,缺少的主要事情是多少空間將調用堆棧實際使用從

+0

我不知道如果JVM帳戶的東西,但你可以看到這篇文章和鏈接的重複http://stackoverflow.com/questions/17250883/is-it-possible-to-determine-how-much -space-is-on-the-stack –

+0

找到了Java問題http://stackoverflow.com/questions/20030120/java-default-stack-size –

+0

我認爲你還需要考慮這個框架的大小: http://www.herongyang.com/JVM/Stack-Overflow-and-JVM-Stack-Frame.html – Lee

回答

0

的堆棧如何做一個遞歸使用(刪除節點列表)?

這是一個難以回答的問題,無需分析代碼或在特定的JVM上具體細節。這是因爲Java Virtual Machine Specification (JVMS)留下了許多細節的實現者。

JVMS Chapter 2:實現細節不屬於 Java虛擬機的規範的一部分會不必要地限制 創造力實現者。例如,運行時間 數據區的內存佈局,垃圾收集算法中使用,並在Java虛擬機指令的任何內部 優化(例如, 其翻譯成機器代碼)都留給的自由裁量權 實現者。的那些細節

部分是堆棧和堆棧幀實現。而且因爲它似乎你實際上問由遞歸刪除和列表中的算法處理創建堆棧之間的關係,我們要考慮的是,堆棧幀甚至可能不是大堆棧上,你認爲(或在你的問題中提出)。

JVMS (§2.5.2):因爲Java虛擬機堆是從未 直接操作除了push和pop幀,幀可能是 堆分配。

這意味着每個堆棧幀可能只有一個引用放入堆棧。如果是這樣,這將使棧和它的處理爲您提供真正例子微不足道的列表之間的關係。讓我們看一下一些數字:

根據Algorithms (Sedgewick, Wayne)

  • Integer爲24個字節
    開銷+實例變量(int)+填充
    = 16 + 4 + 4 = 24個字節

  • 一個非靜態遞歸定義的Node類嵌套在關聯的 List是40個字節 開銷+引用+額外的開銷(參照List類)
    = 16 + 8 + 8 + 8 = 40字節

因此,我們可以看到有每個條目爲64字節列表。所以,如果有一個框架堆分配的實現,堆棧和你正在處理的列表之間的關係將是8/64 = 1/8 bytes

當在堆棧上分配堆棧幀時,確定堆棧的大小更加困難。事實上,我們需要進一步的實施細節來確定它。

JVMS (§2.6. Frames): 局部變量陣列和操作數堆棧的尺寸被確定 在編譯時和與代碼沿着 被提供與所述框架(§4.7.3)相關聯的方法。因此,幀數據結構的大小僅取決於Java虛擬機的實現,並且這些結構的存儲器可以在方法調用時同時分配爲 。

即便如此,我想說,就你的例子而言,堆棧相對於列表(在此討論內存總大小)與1:1不可能成比例或接近1:1。當然,你可以提出一個具體的問題來驗證你的論點,但這可能是微不足道的,可能不是你提供的例子。