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

Question

所以我正在编写一个带有嵌套回复的评论系统。我已经完成了存储和检索部分，并以一组评论对象结束，每个评论对象都有一个 replies 属性，它本身就是一组评论对象。

我允许的最大深度是 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
        }
    }
}

Answer 1

首先，你的代码的运行时间不是O(n^3)，而是O(total number of replies)，因为它会迭代仅通过所有回复一次(循环不是从 1 运行到 n，它们是 foreach 循环，它们执行的迭代次数取决于数组的大小).

没有比执行此任务更好的运行时间了，因为您想对每个回复执行某些操作，因此此任务的下限是 O(回复总数)。

不过我会做的是重写代码并使用递归函数，因为你的代码对更改不是很灵活，如果有一天你决定允许 4 级回复，你将不得不重写这个代码，而如果你使用递归，你就不会。

正如我所说，它不会提高性能，而只是一种更好的实践。