適當的算法來替換三個嵌套循環 - 嵌套註釋

所以我正在寫一個嵌套回覆的評論系統的過程。我已經完成了存儲和檢索部分，並且最終得到了一系列評論對象，每個評論對象都有一個回覆屬性，它本身就是一個評論對象數組。適當的算法來替換三個嵌套循環 - 嵌套註釋

我允許的最大深度是3 - 或回覆答覆。

我正在尋找一個適當高效的三個嵌套循環顯示評論，或循環通過頂層，然後循環通過他們的答覆，然後循環通過他們的回覆，因爲這是不可擴展的替代。

好了，我一直在問了一些代碼：

class Comment{ 
    public $replies = array(); 
    public $content; 
}

所以評論對象包含回覆的數組，這本身就是評論的對象。這會深入三層，因此我有一系列頂級註釋，每個註釋都包含一組響應，每個響應都包含一組響應。

我想找到一個解決方案，它優於這一點，因爲它出來到爲O（n^3）我相信：

foreach($comments as $c){ 
    //do some stuff to display the comment here 
    foreach($c->replies as $r){ 
     //do some stuff to display the replies here 
     foreach($r->replies as $rr){ 
      //do some stuff to display replies to replies here 
     } 
    } 
}

來源

2014-03-13 Rhodesian Hunter

爲了獲得合格答案的遠程機會，我認爲你必須發佈一些代碼 - 就像這些「_three嵌套loops_」的例子.. :) – davidkonrad

@davidkonrad - 修復，請參閱附加代碼。 –

你的'評論'和'答覆'和答覆'保存在mysql表中的答覆？如果是的話，我可以建議使用JOIN查詢。 – Jhn

首先，運行時間爲你的代碼是不是O(n^3)但是O(total number of replies)，因爲它只會遍歷所有回覆一次（循環未從1運行到n，它們是foreach循環，它們執行的迭代次數取決於數組大小）。

執行此任務時沒有更好的運行時間，因爲您想對每個回覆執行一些操作，所以此任務的下限爲O(total number of replies)。

但是我會做的是重寫代碼並使用遞歸函數，因爲您的代碼不易變更，如果有一天您決定允許4級回覆，您必須重寫這個代碼，而如果你使用遞歸，你不會。

就像我說的那樣，它不會提高性能，而只是一種更好的做法。

來源

2014-03-13 15:30:52

由於理論上可以添加無限數量的評論，它確實是O（n^3）。 N被使用是因爲我們不知道評論的總數，事實上我們不會直到我們將它們從數據庫中提取出來。 –

@RhodesianHunter這種情況下'n'是什麼？每個評論的答覆數量是否相同？不必要。 'n'應該代表輸入的大小，在這種情況下，它是回覆的總數，不管在哪個級別上，並且算法在該輸入的大小上以線性時間運行。 –

想象disqus這樣的評論系統 - 可以有無限次數的回覆0-2級別的任何評論 - 我們在這種情況下使用n，因爲n可以是0 - 無限的任何數字（理論上） –

適當的算法來替換三個嵌套循環 - 嵌套註釋

回答

相關問題