2

好的。这可能很困难，但我一直在努力奋斗，但没有很大的进步，所以我想知道你们的想法。

假设我有以下对象列表：

objects = [
        {'id': '1', 'w': 0.20}, 
        {'id': '1.1', 'w': 0.80}, 
        {'id': '1.2', 'w': 0.20},
        {'id': '1.3', 'w': 0.30},
        {'id': '1.1.1', 'w': 0.60},
        {'id': '1.1.2', 'w': 0.70},
        {'id': '1.1.3', 'w': 0.40},
        {'id': '1.2.1', 'w': 0.30},
    ]

我想按“id”（例如'1', '1.1', '1.1.1', '1.1.2', '1.1.3', '1.2', '1.2.1', '1.3'）对该列表进行排序，但是具有相同父级的所有元素都需要按“w”排序（相反）。我所说的“同父异母”是什么意思？那么，“1”是“1.1”、“1.2”和“1.3”的父级。同样，“1.1”是“1.1.1”、“1.1.2”、“1.1.3”的父级，“1.2”是“1.2.1”的父级。为了更好地说明这一点，假设这是一个带有嵌套评论的线程的表示（'1' 是原始帖子，'1.1' 是它的答案，等等）。

目前，我已经能够达到以下形式：

[ [ {'w': 0.2, 'id': '1'} ], [ {'w': 0.8, 'id': '1.1'}, {'w': 0.3, 'id': '1.3'}, 
{'w': 0.2, 'id': '1.2'} ], [ {'w': 0.7, 'id': '1.1.2'}, {'w': 0.6, 'id': '1.1.1'},
{'w': 0.4, 'id': '1.1.3'} ], [ {'w': 0.3, 'id': '1.2.1'} ] ]

如您所见，每个嵌套列表都包含其他元素的子元素。例如，第二个嵌套列表[ {'w': 0.8, 'id': '1.1'}, {'w': 0.3, 'id': '1.3'}, {'w': 0.2, 'id': '1.2'} ]包含 element 的所有子项[ {'w': 0.2, 'id': '1'} ]。此外，每个嵌套列表都按“w”排序。

最终结果应该是这样的（假设链接所有内部列表 - list(itertools.chain(*b))）：

{'id': '1', 'w': 0.20}, {'id': '1.1', 'w': 0.80}, {'id': '1.1.2', 'w': 0.70}, 
{'id': '1.1.1', 'w': 0.60}, {'id': '1.1.3', 'w': 0.40}, {'id': '1.3', 'w': 0.30}, 
{'id': '1.2', 'w': 0.20},   {'id': '1.2.1', 'w': 0.30}

基本上，首先是父母，然后是它的孩子（按'w'排序），这同样适用于每个元素（如果它有孩子，当然 - 这里{'id': '1.3', 'w': 0.30}没有孩子，所以我们不需要做任何事情它）。

我已经尝试了一些事情（太复杂以至于不值得解释）。我最终得到了很多条件和一个丑陋的代码。

我怎样才能完成这种排序？

提前致谢。

4

2 回答 2

4

简单的排序不会解决您的问题，因为不可能比较任何两个元素并立即知道何时出现在另一个之前（父母的权重可能会改变排序）。

您需要将列表处理成树形结构，然后按顺序提取：

tree = {}

for d in objects:
    ids = d['id'].split('.')
    w = d['w']
    # walk into the tree, creating nodes as necessary
    subtree = [0,tree]
    for n in ids:
        if n not in subtree[1]:
            subtree[1][n] = [0,{}] # w, list of nodes
        subtree = subtree[1][n] # recurse
    # subtree is now the relevant node, set w
    subtree[0] = w

## now we have a tree:
## >>> pprint.pprint(tree, width=10)
## {'1': [0.2,
##       {'1': [0.8,
##              {'1': [0.6,
##                     {}],
##               '2': [0.7,
##                     {}],
##               '3': [0.4,
##                     {}]}],
##        '2': [0.2,
##              {'1': [0.3,
##                     {}]}],
##        '3': [0.3,
##              {}]}]}

# now walk the tree and extract the nodes:
result = []
def walk_subtree(subtree, path=[]):
    keyweights = [(subtree[key][0], key) for key in subtree]
    # walk through nodes at this level, outputting.
    for weight, key in sorted(keyweights, reverse=True):
        result.append(('.'.join(path + [key]), weight))
        walk_subtree(subtree[key][1], path=path+[key])

walk_subtree(tree)

##>>> pprint.pprint(result)
##[('1', 0.2),
## ('1.1', 0.8),
## ('1.1.2', 0.7),
## ('1.1.1', 0.6),
## ('1.1.3', 0.4),
## ('1.3', 0.3),
## ('1.2', 0.2),
## ('1.2.1', 0.3)]
于 2012-05-29T06:14:11.117 回答
0

用比较器排序。也就是说，你写了一个看起来像的方法

def comparator(x, y):
    ## some code that sets value to -1 if x is "less than" y
    ## or 1 if x is "greater than or equal to" y.
    return value

然后打电话objects.sort(comparator)，你应该被设置。

这样，您一次只需要比较两个项目。只要你保持一致，这应该不是问题。

于 2012-05-29T06:06:51.683 回答