Как получить наиболее представленный объект из массива

Question

У меня есть массив с некоторыми объектами, и есть несколько похожих объектов.Например: фрукты = [яблоко, апельсин, яблоко, банан, банан, апельсин, яблоко, яблоко]

Какой самый эффективный способ получить наиболее представленный объект из этого массива?В этом случае это будет «яблоко», но как бы вы вышли и посчитали это эффективным способом?

Answer 1

Не изобретай велосипед. В Python 2.7+ вы можете использовать Счетчик класса :

import collections
fruit=['apple', 'orange', 'apple', 'banana', 'banana', 'orange', 'apple', 'apple']
c=collections.Counter(fruit)
print(c.most_common(1))
# [('apple', 4)]

Если вы используете более старую версию Python, вы можете скачать Counter здесь .

Хотя полезно знать, как реализовать нечто подобное самостоятельно, также неплохо бы привыкнуть к использованию Counter, поскольку он является (или будет) частью стандартной библиотеки.

Answer 2

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

results = {}
for item in somelist:
  if item not in results:
    results[item] = 1
  else
    results[item] += 1

print max(results.iteritems(), key=operator.itemgetter(1))

Answer 3

Ведите словарь о том, как часто появляется каждый объект.

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

Этот код не проверен.

from collections import defaultdict

def mode(objects):
    h = defaultdict(int)
    max_f = 0
    max_obj = None
    for o in objects:
        f = h[o] = h[o] + 1
        if f > max_f:
            max_f = f
            max_obj = o
    return max_obj

Если объекты не могут быть хешируемыми, вы можете вместо этого хэшировать некоторые их уникальные свойства, такие как id(o).

Answer 4

Вы хотите эффективный метод. Очевидно, что это возможно за время O (n), поэтому любой метод, требующий сортировки списка, будет отсутствовать, поскольку это будет O (n log (n)). Невозможно сделать это быстрее, чем O (n), потому что даже если вы проверите первые элементы n / 2-1, и все они являются «яблочными», вы не знаете, что остальные элементы не будут бананами .

Итак, учитывая, что мы ищем O (n), вы должны выполнить итерацию по списку и вести подсчет количества предметов каждого типа, которые вы видели.

Дефолт по умолчанию был бы простым способом реализовать это на практике.

>>> from collections import defaultdict
>>> d = defaultdict(int)
>>> for i in ['apple', 'banana', 'apple']:
...    d[i] += 1
...
>>> d
defaultdict(<type 'int'>, {'apple': 2, 'banana': 1})

Answer 5

Лучшее время, которое вы можете надеяться достичь здесь, это O (n) - вам всегда нужно будет обходить весь массив хотя бы один раз. Самый простой способ , безусловно, состоит в построении гистограммы. Если ваша словарная структура (какая-то карта) предлагает O (1), вставьте и получите, то это так же просто, как (псевдокод groovy-ish):

def histogram = new HashMap()
def maxObj = null
def maxObjCount = 0
objectList.each {
    if(histogram.contains(it)) histogram.put(it, histogram.get(it)+1)
    else histogram.put(it, 1)

    if(histogram.get(it) > maxObjCount) {
        maxObj = it
        maxObjCount = histogram.get(it)
    }
}

Answer 6

Как говорит ~ unutbu: используйте коллекции. Счетчик В противном случае, время вашего кода. Вот мой (вероятно, неэффективный) подход:

python -m timeit -s "fruit = ['apple']*4 + ['banana'] + ['orange']*2" \
"kL = set(fruit);  L = [fruit.count(f) for f in kL];  D = dict(zip(kL,L)); \
sorted(D,key = lambda k: D[k],reverse=True)" 
100000 loops, best of 3: 10.1 usec per loop

Answer 7

Это не O (n), а O (n ^ 2), поэтому он может не соответствовать вашему счету как «наиболее эффективный способ», но он компактен и позволяет избежать циклов for, которые в Python довольно медленные. Это будет быстрее, чем опция O (n), до 11 уникальных предметов.

def most_common(items):
    s = set(items)
    return max([(items.count(i), i) for i in s])[1]

Answer 8

Вот другой подход, который по сути сортирует список, а затем обрабатывает его в отсортированном порядке.

fruits = ['apple', 'orange', 'apple', 'banana', 'banana', 'orange', 'apple', 'apple']

max_fruit_count = 0
max_fruit = ''
current_fruit_count = 0
current_fruit = ''
for fruit in sorted(fruits) :
    if fruit != current_fruit :
        if current_fruit != max_fruit :
            if current_fruit_count > max_fruit_count :
                max_fruit = current_fruit
                max_fruit_count = current_fruit_count
        current_fruit = fruit
        current_fruit_count = 1
    else :
        current_fruit_count += 1

if current_fruit_count > max_fruit_count :
    max_fruit = current_fruit
    max_fruit_count = current_fruit_count

print max_fruit, max_fruit_count

Answer 9

def count_reps(item, agg):
  k = hash(item)
  try:
    agg[k] += 1
  except KeyError:
    agg[k] = 1
  return agg

item_dict = reduce(your_array, {})

item_dict будет содержать количество, тогда вы можете оценить популярность каждого объекта.