n-самых больших элементов в последовательности (необходимо сохранить дубликаты)

Question

Мне нужно найти n самых больших элементов в списке кортежей. Вот пример для 3 верхних элементов.

# I have a list of tuples of the form (category-1, category-2, value)
# For each category-1, ***values are already sorted descending by default***
# The list can potentially be approximately a million elements long.
lot = [('a', 'x1', 10), ('a', 'x2', 9), ('a', 'x3', 9), 
       ('a', 'x4',  8), ('a', 'x5', 8), ('a', 'x6', 7),
       ('b', 'x1', 10), ('b', 'x2', 9), ('b', 'x3', 8), 
       ('b', 'x4',  7), ('b', 'x5', 6), ('b', 'x6', 5)]

# This is what I need. 
# A list of tuple with top-3 largest values for each category-1
ans = [('a', 'x1', 10), ('a', 'x2', 9), ('a', 'x3', 9), 
       ('a', 'x4', 8), ('a', 'x5', 8),
       ('b', 'x1', 10), ('b', 'x2', 9), ('b', 'x3', 8)]

Я пытался использовать heapq.nlargest. Однако он возвращает только первые 3 самых больших элемента и не возвращает дубликаты. Например,

heapq.nlargest(3, [10, 10, 10, 9, 8, 8, 7, 6])
# returns
[10, 10, 10]
# I need
[10, 10, 10, 9, 8, 8]

Я могу думать только о приближении грубой силы. Это то, что у меня есть, и это работает.

res, prev_t, count = [lot[0]], lot[0], 1
for t in lot[1:]:
    if t[0] == prev_t[0]:
        count = count + 1 if t[2] != prev_t[2] else count
        if count <= 3:
            res.append(t)   
    else:
        count = 1
        res.append(t)
    prev_t = t

print res

Любые другие идеи о том, как я могу это реализовать? Спасибо!

РЕДАКТИРОВАТЬ: timeit результаты для списка из 1 миллиона элементов показывают, что решение mhyfritz работает в 1/3 времени грубой силы. Не хотел делать вопрос слишком длинным. Так что добавили больше подробностей в мой ответ .

Answer 1

Из вашего фрагмента кода я понимаю, что lot сгруппировано по category-1 .Следующее должно работать тогда:

from itertools import groupby, islice
from operator import itemgetter

ans = []
for x, g1 in groupby(lot, itemgetter(0)):
    for y, g2 in islice(groupby(g1, itemgetter(2)), 0, 3):
        ans.extend(list(g2))

print ans
# [('a', 'x1', 10), ('a', 'x2', 9), ('a', 'x3', 9), ('a', 'x4', 8), ('a', 'x5', 8),
#  ('b', 'x1', 10), ('b', 'x2', 9), ('b', 'x3', 8)]

Answer 2

Если у вас уже есть входные данные, отсортированные таким образом, то вполне вероятно, что ваше решение немного лучше, чем решение на основе heapq.

Ваш алгоритм имеет сложность O (n), в то время как основанный на heapq концептуально O (n * log (3)), и ему, вероятно, потребуется больше проходов по данным, чтобы правильно его упорядочить.

Answer 3

Некоторые дополнительные детали ... Я рассчитал как отличное решение mhyfritz , которое использует itertools, так и мой код (перебор).

Вот результаты timeit для n = 10 и для списка с 1 миллионом элементов.

# Here's how I built the sample list of 1 million entries.
lot = []
for i in range(1001):
    for j in reversed(range(333)):
        for k in range(3):
            lot.append((i, 'x', j))

# timeit Results for n = 10
brute_force = 6.55s
itertools = 2.07s
# clearly the itertools solution provided by mhyfritz is much faster.

Если кому-то интересно, вот след из того, как работает его код.

+ Outer loop - x, g1
| a [('a', 'x1', 10), ('a', 'x2', 9), ('a', 'x3', 9), ('a', 'x4', 8), ('a', 'x5', 8), ('a', 'x6', 7)]
+-- Inner loop - y, g2
  |- 10 [('a', 'x1', 10)]
  |- 9 [('a', 'x2', 9), ('a', 'x3', 9)]
  |- 8 [('a', 'x4', 8), ('a', 'x5', 8)]
+ Outer loop - x, g1
| b [('b', 'x1', 10), ('b', 'x2', 9), ('b', 'x3', 8), ('b', 'x4', 7), ('b', 'x5', 6), ('b', 'x6', 5)]
+-- Inner loop - y, g2
  |- 10 [('b', 'x1', 10)]
  |- 9 [('b', 'x2', 9)]
  |- 8 [('b', 'x3', 8)]

Answer 4

from collections import *

categories = defaultdict(lambda: defaultdict(lambda: set()))
for t in myTuples:
    cat1,cat2,val = t
    categories[cat1][val].add(t)

def onlyTopThreeKeys(d):
    keys = sorted(d.keys())[-3:]
    return {k:d[k] for k in keys}

print( {cat1:onlyTopThreeKeys(sets) for cat1,sets in categories.items()} )

Результат:

{'a': {8: {('a', 'x5', 8), ('a', 'x4', 8)},
       9: {('a', 'x3', 9), ('a', 'x2', 9)},
       10: {('a', 'x1', 10)}},
 'b': {8: {('b', 'x3', 8)}, 
       9: {('b', 'x2', 9)}, 
       10: {('b', 'x1', 10)}}}

---

плоский список : я выполнил описанный выше метод, потому что он дает вам больше информации.Чтобы получить простой список, используйте замыкания для выдачи результатов с onlyTopThreeKeys:

from collections import *

def topTiedThreeInEachCategory(tuples):
    categories = defaultdict(lambda: defaultdict(lambda: set()))
    for t in myTuples:
        cat1,cat2,val = t
        categories[cat1][val].add(t)

    reap = set()

    def sowTopThreeKeys(d):
        keys = sorted(d.keys())[-3:]
        for k in keys:
            for x in d[k]:
                reap.add(x)
    for sets in categories.values():
        sowTopThreeKeys(sets)

    return reap

Результат:

>>> topTiedThreeInEachCategory(myTuples)
{('b', 'x2', 9), ('a', 'x1', 10), ('b', 'x3', 8), ('a', 'x2', 9), ('a', 'x4', 8), ('a', 'x3', 9), ('a', 'x5', 8), ('b', 'x1', 10)}

---

Вы также можете использовать itertools.groupby, если ваш вводгарантированно будет отсортировано, как в вашем примере ввода, но это приведет к сбою вашего кода, если сортировка когда-либо изменится.

Answer 5

Как насчет этого?Он не точно возвращает желаемый результат, так как он выполняет обратную сортировку по y.

# split lot by first element of values
lots = defaultdict(list)
for x, y, z in lot:
    lots[x].append((y, z))

ans = []
for x, l in lots.iteritems():
    # find top-3 unique values
    top = nlargest(3, set(z for (y, z) in l))
    ans += [(x, y, z) for (z, y) in sorted([(z, y) for (y, z) in l
                                                   if z in top],
                                           reverse=True)]

print ans

Answer 6

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

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

Быстрый, некрасивый код:

>>> sum(
        map(lambda x: x[1],
            sorted(dict([(x[2], filter(lambda y: y[2] == x[2], lot))
                for x in lot]).items(),
                reverse=True)[:3]),
    [])

7: [('a', 'x1', 10),
 ('b', 'x1', 10),
 ('a', 'x2', 9),
 ('a', 'x3', 9),
 ('b', 'x2', 9),
 ('a', 'x4', 8),
 ('a', 'x5', 8),
 ('b', 'x3', 8)]

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