¿Determina si una lista de Python es el 95% igual?

Question

This question pregunta cómo determinar si cada elemento de una lista es el mismo. ¿Cómo podría determinar si el 95% de los elementos en una lista son iguales de una manera razonablemente eficiente? Por ejemplo:

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

Esto debería ser algo eficiente porque las listas pueden ser muy grandes.

Answer 1

En realidad, hay una solución lineal fácil para un problema similar, solo con una restricción del 50% en lugar del 95%. Check this question, son solo unas pocas líneas de código.

Te va a funcionar también, solo al final compruebas que el elemento seleccionado satisface el umbral del 95%, no el 50%. (Aunque, como Thilo notas, ya no es necesario si currentCount >= n*0.95.)

También voy a publicar el código de Python de st0le de la respuesta, para mostrar a todos lo difícil que es.

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

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

Si usted está buscando una explicación, creo Nabb tiene the best one.

Answer 2

Esto es incluso menos eficiente que comprobar si cada elemento es el mismo.

El algoritmo es más o menos el mismo, revise todos los elementos de la lista y cuente los que no coinciden con los esperados (con la dificultad adicional de saber cuál es el esperado). Sin embargo, esta vez, no puede simplemente devolver el mensaje falso cuando se encuentra con el primer desajuste, debe continuar hasta que haya suficientes desajustes para compensar una tasa de error del 5%.

Ahora que lo pienso, descubrir qué elemento es el "correcto" probablemente no sea tan fácil, e implica contar cada valor hasta el punto en que pueda estar seguro de que el 5% está fuera de lugar.

Considérese una lista con 10.000 elementos de los cuales el 99% son 42:

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

Así que creo que tendría que empezar a cabo la construcción de una tabla de frecuencias de al menos el primer 5% de la tabla.

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) 

Suponiendo un rendimiento perfecto tabla hash y un buen algoritmo de ordenación, esta se ejecuta en O (n + m lg m), donde m es el número de elementos distintos. O (n lg n) peor caso.

Editar: aquí hay un O (n + m), la versión de un solo paso (suponiendo m < < 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) 

uso de memoria es O (m). max y sum se pueden reemplazar por un solo bucle.

Answer 4

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

También eliminando el problema con la precisión de la división del flotador.

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

Piensa en tu lista como un cubo de bolas rojas y negras.

Si tiene una bola roja en un cubo de diez bolas, y elige una bola al azar y la coloca de nuevo en el cubo, y luego repite mil veces ese paso de muestra y reemplazo, cuántas veces de mil ¿esperas observar una bola roja, en promedio?

Echa un vistazo a la distribución Binomial y echa un vistazo a confidence intervals. Si tiene una lista muy larga y desea hacer las cosas de manera relativamente eficiente, el muestreo es el camino a seguir.

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" 

Nota: épsilon tiene un valor "al azar", eligió algo dependiendo de la longitud de la matriz, etc. solución de Nikita Rybak con currentCount >= n*0.95 no va a funcionar, porque el valor de currentCount varía en función del orden de elementos, pero lo anterior funciona.

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

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

Answer 8

solución de tipo general, como probablemente es pesado, pero tenga en cuenta la naturaleza equilibrada excepcional de tim tipo en Python, que utilizan el orden existente de la lista. Sugeriría ordenar la lista (o copiarla con ordenada, pero esa copia perjudicará el rendimiento). Escanee desde el extremo y el frente para encontrar el mismo elemento o alcance la longitud de escaneo> 5%, de lo contrario, la lista es 95% similar con el elemento encontrado.

Tomar elementos aleatorios como candidatos y contarlos por orden decreciente de frecuencia probablemente tampoco sería tan malo hasta que el recuento encontrado> 95% o el total de recuentos supere el 5%.