适当的算法来替换三个嵌套循环 - 嵌套注释

所以我正在写一个嵌套回复的评论系统的过程。我已经完成了存储和检索部分，并且最终得到了一系列评论对象，每个评论对象都有一个回复属性，它本身就是一个评论对象数组。适当的算法来替换三个嵌套循环 - 嵌套注释

我允许的最大深度是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 - 无限的任何数字（理论上） –

适当的算法来替换三个嵌套循环 - 嵌套注释

回答

相关问题