A complex ordering algorithm for a Python list?

Question

I need to order a list of comments so they appear in their threaded order.

Each comment has a:

Top parent comment (for queries)
Parent comment
Indentation level

If I'm fetching the comments as a list, what would be the most efficient way of sorting it so each comment is below its parent?

It has to remain as a 1-dimensional list. I just want to rearrange the items. I'm trying this but it doesn't work as the list is mutated during enumaration, breaking the counter:

i = 0;
for child in childList:
    ii = 0;
    for ch in childList:
        if (ch.reply == child.id):
            childList.insert(i+1, childList.pop(ii))

    ii += 1;
    i += 1;

Kindall, he wants to order the comments in their threaded order. — Håvard
– Håvard, Commented Aug 19, 2011 at 17:19
What if i put them in a graph, where G = (V, E); v, element of V, is a comment; e, element of E, is a directed edge from parent comment to child comment. And i do a topology sort on it. — Vikas
– Vikas, Commented Aug 19, 2011 at 17:22
Or starting from top parent as root, if i do a DFS then encountered comments will be in the order you want. — Vikas
– Vikas, Commented Aug 19, 2011 at 17:25

SingleNegationElimination · Accepted Answer · 2011-08-19 19:34:05Z

So... you've got something like this?

class Comment(object):
    all_comments = []

    def __init__(self, message, parent):
        self.message = message
        self.parent = parent
        self.all_comments.append(self)

    def __iter__(self):
        """
        Yields tuples of (indentation level, comments), with this comment first
        and child comments later.
        """
        # what goes here?

This just a depth-first pre-order tree traversal.

import itertools

class Comment(object):
    def __iter__(self):
        return _iter_helper(self, 0)

    def _iter_helper(self, depth):
        item = {'indent_level': depth, 'comment': self}
        return itertools.chain([item], 
                               *[comment._iter_helper(depth+1)
                                 for comment 
                                 in self.all_comments
                                 if comment.parent == self])

As Harypyon suggests, storing the children is a more efficient way of viewing this problem than storing the parent and then computing the children.

EDIT:

I don't think storing children is possible with MySQL.

Ok.. this is in a database and you (probably) want some SQL that produces the desired result?

You've got a table like something like this?

CREATE TABLE comments (
    id INTEGER PRIMARY KEY,
    parent INTEGER,
    comment TEXT        
);

Unfortunately, MySQL doesn't support recursive query syntac (neither the with recursive common table expressions nor connect by), so this self referential schema, though simple and elegant, is not useful if you want to do the whole thing in a single query with arbitrary depth and all of the needed metadata.

There are two solutions. First, you can emulate the recursive query by doing the equivalent of a common table query in python, or in MySQL using temporary tables, with each of the sub-selects as a separate actual query. The downside is that this is neither elegant (many sql queries) and wasteful, (extra data transmitted over the connection or stored on disk).

Another option is to is accept that the transitive closure of the tree of comments is simply not computable, but that you can still make do with a compromise. You most likely don't want (or need) to show more than a hundred comments at a time, and you similarly don't need to show a depth of more than, say, 5 levels of nesting. To get more information, you would Just run the same query with a different root comment. Thus, you end up with a query something like

SELECT c1.*, c2.*, c3.*, c4.*, c5.*
FROM comments c1
LEFT JOIN comments c2 ON c1.id = c2.parent
LEFT JOIN comments c3 ON c2.id = c3.parent
LEFT JOIN comments c4 ON c3.id = c4.parent
LEFT JOIN comments c5 ON c4.id = c5.parent
WHERE c1.parent = ?

Which will give you a good "batch" of comments, up to 5 levels deep.

I can't change the Comment class implementation. How can I reorder it without changing the class?

Håvard · Accepted Answer · 2011-08-19 17:43:05Z

I suggest you change/create a Comment class that holds comment information plus a list of its children. Then loop through your list and create a dictionary of the comments as Comment objects. Loop again, this time add each comment to the parent object. Lastly, loop over the dictionary and pick the comments without parents, those are your top-level comments. These Comment objects contain references to all the other comments!

Here's some code that illustrates what I mean, and puts the final comment objects in a 1-dimensional list:

class Comment:
    def __init__(self, _id, parent):
        self.id, self.parent = _id, parent
        self.children = []

comments = [
    [1, None], # id, parent
    [2, 1],
    [3, None],
    [4, 2],
    [5, 3],
]

# store comments by their ID, as Comment objects
comments_dict = {}
for comment in comments:
    comments_dict[comment[0]] = Comment(*comment)

# store top level comments, and add child comments to their parent objects
top_comments = []
for _id, comment in comments_dict.items():
    if comment.parent != None:
        comments_dict[comment.parent].children.append(comment)
    else:
        top_comments.append(comment)

# final list of comments
comments = []
def add_comment(comment):
    """Recursively add comments to final list"""
    global comments
    comments.append(comment)
    if comment.children:
        for child in comment.children:
            add_comment(child)

for comment in top_comments:
    add_comment(comment)

print [comment.id for comment in comments]

Collectives™ on Stack Overflow

A complex ordering algorithm for a Python list?

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related