% ключ и первое значение в списке - qacode.ru" />

Группировка словарь списки, основанные на % ключ и первое значение в списке


Как можно оптимизировать этот код ?

Описание Проблемы:

Вход(counts) массив \ФП\$ целых чисел, где каждое counts[i], (\$0\ЛЭ я< Н\$) указывает общее число элементов в определенной группе, что элемент I принадлежит. Например, если counts = [3, 3, 3, 3, 3, 1, 3]тогда есть три группы; элементы 0, 1, 2, 3, 4, и 6 находятся в одном из двух 3-элементом группы, А элемент 5 в 1-элемент группы.

Группа является допустимым, если все элементы группы имеют минимальный идентификационные номера. Другими словами, Группа размер \$К\$ должен содержать \$к\$ маленький идентификационные номера, принадлежащие к группе, что размер относительно маленький элемент ID в группе. Например, если counts = [3, 3, 3, 3, 3, 1, 3]тогда группировка [0, 1, 2], [3, 4, 6]и [5] действует, однако, группировка [0, 1, 4], [2, 3, 6]и [5] не действует, потому что группа [0, 1, 4] не содержит три маленьких идентификаторов элементов для набора идентификаторов элементов, принадлежащих к 3-элемент группы (т. е., \${0,1,2,3,4,6}\$).

Гарантируется, что действует группировка всегда существует для данного входного массива.

ДЕЙСТВИТЕЛЬНЫЙ ГРУППИРОВКУ:

0 1 2
3 4 6
5

НЕВЕРНЫЙ ГРУППИРОВКА:

0 1 4
2 3 6
5

Образец Ввод (1):

counts = [2,1,1,2,1]

Пример Вывода (1):

0 3 
1 
2 
4

Образец Входного (2):

counts = [4,2,4,5,5,4,4,5,5,2,5,7,1,7,1,7,1,7,1,7,1,7,1,7,5,5,5,5,5]

Пример Вывода (2):

0 2 5 6
1 9
3 4 7 8 10 
11 13 15 17 19 21 23
12
14
16
18
20
22
24 25 26 27 28

Код:

from collections import OrderedDict

def groupCount(counts):
    group_dict = OrderedDict()
    for i in range(len(counts)):
        if counts[i] in group_dict.keys():
            group_dict[counts[i]].append(i)
        else:
            group_dict[counts[i]] = [i]
    op_list = []
    for key in group_dict:
        prnt_count = 0
        temp_list = []
        while len(group_dict[key])!=0:
            prnt_count += 1
            temp_list.append(group_dict[key].pop(0))
            if prnt_count % key == 0:
                op_list.append(temp_list)
                temp_list = []
    op_list.sort(key=lambda x: x[0])
    for value in op_list:
        print(*value, sep=' ')


Комментарии
1 ответ

1. Комментарий


  1. Нет строкой документации. Что groupCount делать? Текст в посте очень понятно все объясняет, так что это будет хорошее начало.

  2. groupCount имеет две функции: (I) он собирает входных данных на группы, и (II) он печатает с разбором результатов. Проблемы с совмещением обязанностей, как это, что это делает его трудно, чтобы повторно использовать код. Если нужно использовать группы в другой код, как вы получаете их? Если вы хотите написать автоматические тесты, как вы это делаете? Было бы лучше разбить группировку и печати кода на отдельные функции. (Это и есть "принцип единой ответственности".)

  3. Этот код перебирает индексы в последовательности counts а потом смотрит на предмет с помощью counts[i].

    for i in range(len(counts)):
    # code using i and counts[i]

    Python предоставляет функцию enumerate для одновременного перебора элементов и их индексов:

    for i, count in enumerate(counts):
    # code using i and count

  4. Для систематизации элементов на основе их ключей, удобно использовать collections.defaultdictвот так:

    groups = defaultdict(list)
    for i, count in enumerate(counts):
    groups[count].append(i)

  5. Разделить последовательность на группы длины \ФП\$, есть известный трюк, который описан в документации zip, где он говорит:


    Это делает возможным идиома для кластеризации данных серии в n-длина группы, используя zip(*[iter(s)]*n). Это повторяется тот же итератор n раз так, что каждый выход Кортеж был результат n призывы к итератору. Это имеет эффект деления ввода в n-длина кусками.

  6. Нет необходимости, чтобы пройти основную функцию sort. Последовательности сравниваются лексикографически по их элементам, и потому что мы знаем, что все элементы различны, то сравнение никогда не будет обращать внимания на первый пункт.

2. Пересмотренный кодекс

from collections import defaultdict

def group_by_count(counts):
"""Given a sequence of group sizes for each item, return a list of
groups, each group being a tuple of indexes of items.

>>> group_by_count([3, 3, 3, 3, 3, 1, 3])
[(0, 1, 2), (3, 4, 6), (5,)]

"""
groups = defaultdict(list)
for i, count in enumerate(counts):
groups[count].append(i)
result = []
for count, group in groups.items():
result.extend(zip(*[iter(group)] * count))
return sorted(result)

(Обратите внимание на пример в строкой документации: это может быть автоматически установлен с помощью doctest модуль.)

3
ответ дан 28 февраля 2018 в 12:02 Источник Поделиться