Определить, совпадает ли список Python на 95%?

Question

Этот вопрос спрашивает, как определить, одинаковы ли все элементы в списке.Как мне определить, являются ли 95% элементов в списке одинаково эффективным способом?Например:

>>> ninety_five_same([1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1])
True
>>> ninety_five_same([1,1,1,1,1,1,2,1]) # only 80% the same
False

Это должно быть несколько эффективным, поскольку списки могут быть очень большими.

Answer 1

>>> from collections import Counter
>>> lst = [1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
>>> _, freq = Counter(lst).most_common(1)[0]
>>> len(lst)*.95 <= freq
True

Answer 2

На самом деле, существует простое линейное решение для аналогичной проблемы, только с ограничением 50% вместо 95%. Проверьте этот вопрос , это всего лишь несколько строк кода.

Это будет работать и для вас, только в конце вы убедитесь, что выбранный элемент соответствует порогу 95%, а не 50%. (Хотя, как отмечает Thilo , это не обязательно, если currentCount >= n*0.95 уже.)

Я также выложу код Python из ответа st0le , чтобы показать всем, насколько это сложно.

currentCount = 0
currentValue = lst[0]
for val in lst:
   if val == currentValue:
      currentCount += 1
   else:
      currentCount -= 1

   if currentCount == 0:
      currentValue = val
      currentCount = 1

Если вы ищете объяснение, я думаю, Набб получил лучший .

Answer 3

def ninety_five_same(lst):
    freq = collections.defaultdict(int)
    for x in lst:
        freq[x] += 1
    freqsort = sorted(freq.itervalues())
    return freqsort[-1] >= .95 * sum(freqsort)

При условии идеальной производительности хеш-таблицы и хорошего алгоритма сортировки, это работает в O ( n + m lg m ), где m - количество отдельных предметов. O ( n lg n ) наихудший случай.

Редактировать : вот O ( n + m ), однопроходная версия (при условии m << <em>п ):

def ninety_five_same(lst):
    freq = collections.defaultdict(int)
    for x in lst:
        freq[x] += 1
    freq = freq.values()
    return max(freq) >= .95 * sum(freq)

Память используется O ( m ). max и sum могут быть заменены одним циклом.

Answer 4

Это даже менее эффективно, чем проверка того, что все элементы одинаковы.

Алгоритм примерно одинаков, просмотрите все элементы в списке и подсчитайте те, которые не соответствуют ожидаемому (с помощьюдополнительная трудность определения того, какой из них является ожидаемым).Однако на этот раз вы не можете просто вернуть false, когда встретите первое несоответствие, вы должны продолжать, пока у вас не будет достаточно несоответствий, чтобы составить 5% ошибок.

Если подумать,Элемент является «правильным», один, вероятно, не так прост и включает в себя подсчет каждого значения до того момента, когда вы можете быть уверены, что 5% неуместны.42:

  (1,2,3,4,5,6,7,8,9,10, ... , 100, 42,42, 42, 42 .... 42)

Так что я думаю, вам нужно было бы начать строить таблицу частот хотя бы для первых 5% таблицы.

Answer 5

def ninety_five_same(l):
  return max([l.count(i) for i in set(l)])*20 >= 19*len(l)

Также устраняется проблема с точностью деления поплавка.

Answer 6

Сортировка

как общее решение, вероятно, является тяжелой, но рассмотрим исключительно хорошо сбалансированную природу сортировки tim в Python, которая использует существующий порядок списка.Я бы предложил отсортировать список (или скопировать его с сортировкой, но эта копия ухудшит производительность).Сканируйте с конца и спереди, чтобы найти тот же элемент или достигните длины сканирования> 5%, в противном случае список на 95% похож на найденный элемент.

Выбор случайных элементов в качестве кандидатов и подсчет их по убыванию частотывероятно, также не будет так плохо, пока найденное число не превысит 95%, или общее количество не превысит 5%.

Answer 7

lst = [1,1,1,1,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
#lst = [1, 2, 1, 4, 1]
#lst = [1, 2, 1, 4]

length = len(lst)
currentValue = lst[0]
lst.pop(0)
currentCount = 1

for val in lst:
   if currentCount == 0:
      currentValue = val

   if val == currentValue:
      currentCount += 1
   else:
      currentCount -= 1

percent = (currentCount * 50.0 / length + 50)
epsilon = 0.1
if (percent - 50 > epsilon):
    print "Percent %g%%" % percent
else:
    print "No majority"

Примечание: epsilon имеет «случайное» значение, выбрал что-то в зависимости от длины массива и т. Д. Решение Никиты Рыбака с currentCount >= n*0.95 не будет работать, потому что значение currentCount отличается в зависимости от порядкаэлементы, но выше работает .

C:\Temp>a.py
[2, 1, 1, 4, 1]
currentCount = 1

C:\Temp>a.py
[1, 2, 1, 4, 1]
currentCount = 2

Answer 8

Думайте о своем списке как о ведре красных и черных шаров.

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

Проверьте распределение Binomial и доверительные интервалы .Если у вас очень длинный список и вы хотите делать что-то относительно эффективно, выборка - это путь.