Appropriate algorithm to replace three nested loops - nested comments

So I'm in the process of writing a commenting system with nested replies. I've got the storage and retrieval part down, and am ending up with an array of comment objects that each have a replies property, which is itself an array of comment objects.

The maximum depth I'm allowing is 3 - or a reply to a reply.

I'm looking for an appropriately efficient replacement for three nested loops to display the comments, or looping through the top layer, then looping through their replies, then looping through THEIR replies as this is not scalable.

Ok, so I've been asked for some code:

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

So a comment object contains an array of replies, which are themselves comment objects. This goes three layers deep so I have an array of top level comments, which each contain an array of replies, which each contain an array of replies.

I want to find a solution that's superior to this, as it comes out to O(n^3) i believe:

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
        }
    }
}

Answers


First of all, the running time for the your code is not O(n^3), but O(total number of replies), as it will iterate through all the replies exactly once (the loops are not running from 1 to n, they're foreach loops and the numbers of iterations they perform depend on the size of the array).

There's no better running time for performing this task, as you want to do something with each reply, so the lower bound of this task is O(total number of replies).

What I would do though, is rewrite the code and use a recursion function, because your code is not very flexible to changes, if one day you'll decide you allow 4 levels of replies, you'll have to rewrite this code, while if you use recursion, you wouldn't.

Like I said, it is not expected to enhance the performance, but merely a better practice.


Need Your Help

convert month from name to number

php time

Is there an easy way to change $month = "July"; so that $nmonth = 7 (07 would be fine too).