樹建築功能超過最大執行時間

我正在採取約15,000個節點，並試圖從它們建立一個層次結構。節點不能以任何方式排序，並且每個節點可以有無限數量的孩子 - 但是父母總是會在他們的孩子面前被饋送到該功能。我的代碼適用於N的小值，但最終超過N> 2,000時服務器上的最大執行時間。我不知道是否有更好的方式來做到這一點，但這裏是我有：樹建築功能超過最大執行時間

function insertNode(&$treeNode, $insertNode) { 
    if($insertNode['DEPTH'] <= $treeNode['DEPTH']) return false; 
    if($treeNode['ID'] == $insertNode['PARENT_ID']) { 
     $treeNode['CHILDREN'][] = $insertNode; 
     $treeNode['CHILD_COUNT']++; 
     return true; 
    } 
    else { 
     foreach($treeNode['CHILDREN'] as $key=>$value) { 
      $found = insertNode($treeNode['CHILDREN'][$key], $insertNode); 
      if($found) { 
       $treeNode['CHILD_COUNT']++; 
       return true; 
      } 
     } 
    } 
}

的解決方案，現在是限制我的遞歸建築只有幾千節點值得深入我的最好的想法，然後在Javascript中調用每個底層節點的腳本，直到樹真正完成。不過，我寧願能夠一勞永逸。

來源

2013-08-01 user2000008

...野生遞歸出現了！ – MightyPork

我想出了自己。關鍵是：

父母總是會被直接送入功能子女

我使用（在Oracle CONNECT BY）的SQL查詢打印出每一個孩子（和他們的孩子的）前在他們的直系祖先之後。例如，數據集：

|id|parent_id| 
|A-|---------| 
|B-|-----A---| 
|Bb|-----B---| 
|C-|-----A---|

我是通過查詢的每一行循環，從而，然後調用每個遞歸插入功能：

|id|parent_id| 
|A-|---------| 
|C-|-----A---| 
|Bb|-----B---| 
|B-|-----A---|

將由查詢作爲交付行。在每一個函數調用，我使用的是foreach循環進行遞歸調用在樹，直到該行的母公司當前節點的每個孩子都被發現了，在這裏：

foreach($treeNode['CHILDREN'] as $key=>$value) { 
    $found = insertNode($treeNode['CHILDREN'][$key], $insertNode); 
    if($found) { 
     $treeNode['CHILD_COUNT']++; 
     return true; 
    } 
}

但是，由於每個孩子的家長總是最新插入的深度項目（因爲它是我深入其中的最後一行），父項保證是樹中最右側分支中最右邊的子項。不僅循環不必要，它實際上是最糟糕的事情我本來可以做的 - 它是從左到右循環通過孩子，但父母總是最右邊的分支的最右邊的孩子，功能的最後一個項目會循環遍歷。（那是什麼，O(N^2)？）難怪它是超時。

我剪了foreach，而是用end()調用代替它。

$lastChild = $treeNode['CHILDREN']; 
end($lastChild); 
$key = key($lastChild); 
$found = insertNode($treeNode['CHILDREN'][$key], $insertNode); 
if($found) { 
    $treeNode['CHILD_COUNT']++; 
    return true; 
}

這大大縮短了執行時間，因爲它成倍削減了多少次的函數遞歸調用本身，每行。它現在在約6秒內工作N = 15,000（在30秒之前達到N = 2,000的最低值之前）。不需要節點號碼上限或通過JS進行延遲加載。

來源

2013-08-01 18:13:02 user2000008

樹建築功能超過最大執行時間

回答

相關問題