Получить максимальное количество кортежей в списке

Question

У меня есть список кортежей, которые можно понимать как пары ключ-значение, где ключ может появляться несколько раз, возможно, с разными значениями, например

[(2,8),(5,10),(2,5),(3,4),(5,50)]

Теперь я хочу получить список кортежей с наибольшим значением для каждого ключа, т.е.

[(2,8),(3,4),(5,50)]

Порядок ключей не имеет значения.

Как мне сделать это эффективно?

Answer 1

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

Группировка может быть легко выполнена с помощью defaultdict. Подробное объяснение группировки с defaultdicts можно найти в моем ответе здесь . В вашем случае мы группируем кортежи по их первому элементу, а затем используем функцию max, чтобы найти кортеж с наибольшим номером.

import collections

tuples = [(2,8),(5,10),(2,5),(3,4),(5,50)]

groupdict = collections.defaultdict(list)
for tup in tuples:
    group = tup[0]
    groupdict[group].append(tup)

result = [max(group) for group in groupdict.values()]
# result: [(2, 8), (5, 50), (3, 4)]

В вашем конкретном случае мы можем немного оптимизировать код, сохранив только максимальный 2-й элемент в dict, вместо того, чтобы хранить список всех кортежей и найти максимум в конце:

tuples = [(2,8),(5,10),(2,5),(3,4),(5,50)]

groupdict = {}
for tup in tuples:
    group, value = tup

    if group in groupdict:
        groupdict[group] = max(groupdict[group], value)
    else:
        groupdict[group] = value

result = [(group, value) for group, value in groupdict.items()]

Это сводит к минимуму объем памяти, но работает только для кортежей с ровно 2 элементами.

---

Это имеет ряд преимуществ перед Решением Netwave :

• Это более читабельно. Любой, кто видит, как создается экземпляр defaultdict, знает, что он будет использоваться для группировки данных, а использование функции max позволяет легко понять, какие кортежи хранятся. Однострочное использование Netwave является умным, но умные решения редко легко читаются.
• Поскольку данные не нужно сортировать, они выполняются за линейное O (n) время вместо O (n log n).

Answer 2

Сортируйте их, затем приведите к словарю и снова возьмите из него предметы:

l = [(2,8),(5,10),(2,5),(3,4),(5,50)]
list(dict(sorted(l)).items()) #python3, if python2 list cast is not needed
[(2, 8), (3, 4), (5, 50)]

Идея состоит в том, что пары ключ-значение будут обновляться в порядке возрастания при преобразовании в словарь, отфильтровывающий самые низкие значения для каждого ключа, тогда вам просто нужно принять его как кортежи.