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

Question

def maxVote(nLabels):
    count = {}
    maxList = []
    maxCount = 0
    for nLabel in nLabels:
        if nLabel in count:
            count[nLabel] += 1
        else:
            count[nLabel] = 1
    #Check if the count is max
        if count[nLabel] > maxCount:
            maxCount = count[nLabel]
            maxList = [nLabel,]
        elif count[nLabel]==maxCount:
            maxList.append(nLabel)
    return random.choice(maxList) 

nLabels содержит список целых чисел.

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

например. maxVote([1,3,4,5,5,5,3,12,11]) равно 5

Answer 1

import random
import collections

def maxvote(nlabels):
  cnt = collections.defaultdict(int)
  for i in nlabels:
    cnt[i] += 1
  maxv = max(cnt.itervalues())
  return random.choice([k for k,v in cnt.iteritems() if v == maxv])

print maxvote([1,3,4,5,5,5,3,3,11])

Answer 2

В Python 3.1 или в будущем 2.7 вы сможете использовать Counter:

>>> from collections import Counter
>>> Counter([1,3,4,5,5,5,3,12,11]).most_common(1)
[(5, 3)]

Если у вас нет доступа к этим версиям Python, вы можете сделать:

>>> from collections import defaultdict
>>> d = defaultdict(int)
>>> for i in nLabels:
    d[i] += 1


>>> max(d, key=lambda x: d[x])
5

Answer 3

Кажется, он запускается за O (n) время. Однако может быть узкое место в проверке if nLabel in count, так как эта операция также может потенциально выполнить O (n) время, в результате чего общая эффективность O (n ^ 2).

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

Answer 4

Я не уверен, что именно вы хотите оптимизировать, но это должно работать:

from collections import defaultdict

def maxVote(nLabels):
   count = defaultdict(int)
   for nLabel in nLabels:
      count[nLabel] += 1
   maxCount = max(count.itervalues())
   maxList = [k for k in count if count[k] == maxCount]
   return random.choice(maxList)

Answer 5

Полный пример:

#!/usr/bin/env python

def max_vote(l):
    """
    Return the element with the (or a) maximum frequency in ``l``.
    """
    unsorted = [(a, l.count(a)) for a in set(l)]
    return sorted(unsorted, key=lambda x: x[1]).pop()[0]

if __name__ == '__main__':
    votes = [1, 3, 4, 5, 5, 5, 3, 12, 11]
    print max_vote(votes)
    # => 5

---

Тесты:

#!/usr/bin/env python

import random
import collections

def max_vote_2(l):
    """
    Return the element with the (or a) maximum frequency in ``l``.
    """
    unsorted = [(a, l.count(a)) for a in set(l)]
    return sorted(unsorted, key=lambda x: x[1]).pop()[0]

def max_vote_1(nlabels):
    cnt = collections.defaultdict(int)
    for i in nlabels:
        cnt[i] += 1
        maxv = max(cnt.itervalues())
    return random.choice([k for k,v in cnt.iteritems() if v == maxv])

if __name__ == '__main__':
    from timeit import Timer
    votes = [1, 3, 4, 5, 5, 5, 3, 12, 11]
    print max_vote_1(votes)
    print max_vote_2(votes)

    t = Timer("votes = [1, 3, 4, 5, 5, 5, 3, 12, 11]; max_vote_2(votes)", \
        "from __main__ import max_vote_2")
    print 'max_vote_2', t.timeit(number=100000)

    t = Timer("votes = [1, 3, 4, 5, 5, 5, 3, 12, 11]; max_vote_1(votes)", \
        "from __main__ import max_vote_1")
    print 'max_vote_1', t.timeit(number=100000)

Урожайность:

5
5
max_vote_2 1.79455208778
max_vote_1 2.31705093384

Answer 6

Идея 1

Действительно ли возврат должен быть случайным, или вы можете просто вернуть максимум a ? Если вам просто необходимо недетерминистически вернуть максимальную частоту, вы можете просто сохранить одну метку и удалить логику списка, включая

 elif count[nLabel]==maxCount:
        maxList.append(nLabel)

Идея 2

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