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

Ответ 1

На самом деле существует легкое линейное решение для аналогичной задачи, только с ограничением 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

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

Ответ 2

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

Ответ 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 < lt; n):

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 могут быть заменены одним циклом.

Ответ 4

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

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

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

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

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

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

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 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 имеет "случайное" значение, выбирает что-то в зависимости от длины массива и т.д. Решение Nikita Rybak с 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

Ответ 8

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

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