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

Question

This 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

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

Он будет работать и на вас, только в конце вы проверите, что выбранный элемент удовлетворяет 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 

Если вы ищете для объяснения, я думаю Nabb получил the best one.

Answer 2

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

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

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

Рассмотрим список с 10.000 элементами, из которых 99% являются 42:

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

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

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 (п + м Л.Г. м), где м является число различных элементов. O (n lg n) наихудший случай.

Edit: вот O (п + м), версия однопроходный (при условии, м < < п):

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 (м). max и sum могут быть заменены одним контуром.

Answer 4

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

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

Answer 5

>>> 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 6

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

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

Отъезд Binomial Распределение и выезд confidence intervals. Если у вас очень длинный список и вы хотите делать что-то относительно эффективно, выборка - это путь.

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" 

Примечание: эпсилон имеет «случайное» значение, выбрать что-то в зависимости от длины массива и т.д. решение Никиты Рыбака с 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

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

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