Неправильный вывод с помощью itertools.groupby - PullRequest
Новая
       17

Неправильный вывод с помощью itertools.groupby

0 голосов
/ 24 апреля 2019

Я получил этот домашний вопрос, после прохождения курса по Udemy, я до сих пор не могу понять, как получить правильный результат, такой как Solution.

Более того: как я могу сделать это более эффективным. Как я могу сделать это без использования явных циклов, но вместо этого использовать списочные / словарные выражения.

Вот что я делаю: 

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

1 Ответ

1 голос
/ 24 апреля 2019

Функция клавиши для 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, но они все еще подвержены обычным алгоритмическим сложностям времени.

...