使用itertools.groupby输出不正确

Question

我得到了这个家庭作业的问题，在Udemy学习了一门课程后，我仍然无法弄清楚如何获得像解决方案一样的正确输出。

此外：我怎样才能提高效率。如何在不使用显式循环的情况下执行此操作，而是使用list / dictionary comprehensions。

这就是我做的：

def group_permutation_values(permutations_list): 

    dic = {}
    f = lambda x: x[1]
    for key, group in itertools.groupby(sorted(permutations_list, key=f), f):
        dic[key] = list(group)

    return dic

    pass

results = [
    ((1, 2, 3), -4),
    ((1, 3, 2), -4),
    ((2, 1, 3), -2),
    ((2, 3, 1), -2),
    ((3, 1, 2), 0), 
    ((3, 2, 1), 0)
]
print(group_permutation_values(results))

这就是我得到的：

{
    -4: [((1, 2, 3), -4), ((1, 3, 2), -4)],
    -2: [((2, 1, 3), -2), ((2, 3, 1), -2)],
     0: [((3, 1, 2), 0), ((3, 2, 1), 0)]
}

并期望输出：

{
    -4: [(1, 2, 3), (1, 3, 2)],
    -2: [(2, 1, 3), (2, 3, 1)],
     0: [(3, 1, 2), (3, 2, 1)]
}

Answer 1

groupby的关键功能只决定了值的分组方式;该函数不用于更改组元素本身。仅仅因为你被element[1]分组，并不意味着这些组只会包含element[0]，你得到整个元组。

您需要做的就是在创建列表值时从组的每个元素中提取第一个嵌套元组：

dic[key] = [t[0] for t in group]

所以list(group)返回[((1, 2, 3), -4), ((1, 3, 2), -4)]，上面的列表理解反而产生[(1, 2, 3), (1, 3, 2)]。

您可以用for结果替换构建字典的外部groupby循环，并使用字典理解：

def group_permutation_values(permutations_list): 
    f = lambda x: x[1]
    sorted_list = sorted(permutations_list, key=f)
    return {k: [t[0] for t in g] for k, g in itertools.groupby(sorted_list, f)}

但是，使用groupby()是错误的工具。 groupby()要求您先对输入进行排序，这会使您的性能降低。排序是一个O（N log N）操作，但是将元组分解为字典可以在O（N）线性时间内完成，只需循环输入列表并附加到每个条目的列表：

def group_permutation_values(permutations_list):
    grouped = {}
    for a, b in permutations_list:
        grouped.setdefault(b, []).append(a)
    return grouped

这不能变成字典理解，但更有效率。理解不是魔术子弹，它们只是通过处理迭代中的每个元素来创建容器（列表，字典，集合）的语法。是的，它们比等效的for-loop-with-add-to-container-operation更有效，但它们仍然受制于通常的算法时间复杂性。