Сложный алгоритм упорядочения для списка Python?

Question

Мне нужно заказать list комментариев, чтобы они отображались в порядке их потоков.

Каждый комментарий имеет:

• Верхний родительский комментарий (для запросов)
• Родительский комментарий
• Уровень отступа

Если я получаю комментарии как list, какой будет самый эффективный способ сортировки, чтобы каждый комментарий был ниже своего родителя ?

Это должно оставаться в виде одномерного списка. Я просто хочу переставить предметы. Я пытаюсь это, но это не работает, поскольку список видоизменяется во время перечисления, ломая счетчик:

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;

Answer 1

Итак ... у вас есть что-то вроде этого?

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?

Это просто обход дерева предварительных заказов в глубину.

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])

Как предполагает Харипион, хранение детей является более эффективным способом просмотра этой проблемы, чем сохранение родителей и их вычисление.

РЕДАКТИРОВАТЬ:

Я не думаю, что хранение детей возможно с MySQL.

Хорошо ... это в базе данных , и вы (вероятно) хотите немногоSQL, который дает желаемый результат?

У вас есть таблица, похожая на эту?ни табличных выражений, ни connect by), поэтому эта самоссылочная схема, хотя и проста и элегантна, бесполезна, если вы хотите выполнить всю задачу в одном запросе с произвольной глубиной и всеми необходимыми метаданными.Есть два решения.Во-первых, вы можете эмулировать рекурсивный запрос, выполняя эквивалент общего запроса таблицы в Python или в MySQL, используя временные таблицы, причем каждый из вложенных элементов выбирается как отдельный фактический запрос.Недостатком является то, что это не элегантно (много запросов sql) и не расточительно (дополнительные данные передаются по соединению или хранятся на диске).

Другой вариант - принять, что транзитивное замыкание дерева комментариев просто не вычислимо, но вы все равно можете обойтись компромиссом.Скорее всего, вы не хотите (или не хотите) показывать более ста комментариев одновременно, и вам также не нужно показывать глубину, превышающую, скажем, 5 уровней вложенности.Чтобы получить больше информации, вы просто запустите тот же запрос с другим корневым комментарием.Таким образом, вы получите запрос типа

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 = ?

, который даст вам хороший пакет комментариев, до 5 уровней.

Answer 2

Я предлагаю вам изменить / создать класс Comment, содержащий информацию о комментариях и список его дочерних элементов. Затем переберите свой список и создайте словарь комментариев как Comment объектов. Повторяем цикл, на этот раз добавляем каждый комментарий к родительскому объекту. Наконец, переберите словарь и выберите комментарии без родителей, это ваши комментарии высшего уровня. Эти Comment объекты содержат ссылки на все остальные комментарии!

Вот некоторый код, который иллюстрирует, что я имею в виду, и помещает объекты окончательного комментария в одномерный список:

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]