Xác định nếu một danh sách Python là 95% như nhau?

Question

This question hỏi cách xác định xem mọi phần tử trong danh sách có giống nhau hay không. Làm thế nào tôi sẽ đi về xác định nếu 95% các yếu tố trong một danh sách là như nhau một cách hợp lý hiệu quả? Ví dụ:

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

Điều này sẽ cần phần nào hiệu quả vì danh sách có thể rất lớn.

Answer 1

Thực tế, có giải pháp tuyến tính dễ dàng cho vấn đề tương tự, chỉ với giới hạn 50% thay vì 95%. Check this question, nó chỉ là một vài dòng mã.

Nó cũng sẽ phù hợp với bạn, cuối cùng bạn kiểm tra phần tử đã chọn thỏa mãn ngưỡng 95%, chứ không phải 50%. (Mặc dù, là Thilo ghi chú, không cần thiết nếu currentCount >= n*0.95 đã có.)

Tôi cũng sẽ đăng mã Python từ câu trả lời của st0le, để cho mọi người biết mức độ khó của nó.

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

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

Nếu bạn đang tìm kiếm lời giải thích, tôi nghĩ nabb đã có the best one.

Answer 2

Điều này thậm chí còn kém hiệu quả hơn việc kiểm tra xem mọi phần tử có giống nhau hay không.

Thuật toán gần giống nhau, đi qua mọi phần tử trong danh sách và đếm những phần tử không khớp với phần tử mong đợi (với độ khó thêm khi biết cái nào là mong muốn). Tuy nhiên, lần này, bạn không thể trả về sai khi gặp sự không phù hợp đầu tiên, bạn phải tiếp tục cho đến khi bạn có đủ sự không phù hợp để tạo nên tỷ lệ lỗi 5%. Hãy suy nghĩ về nó, tìm ra yếu tố nào là "đúng" có lẽ không dễ dàng như vậy, và liên quan đến việc đếm mọi giá trị đến mức bạn có thể chắc chắn rằng 5% bị thất lạc.

Hãy xem xét một danh sách với 10.000 yếu tố trong đó 99% là 42:

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

Vì vậy, tôi nghĩ rằng bạn sẽ phải bắt đầu xây dựng một bảng tần số cho ít nhất 5% đầu tiên của bảng.

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) 

Giả sử hiệu suất bảng băm hoàn hảo và một thuật toán phân loại tốt, điều này chạy trong thời gian O (n + m lg m), nơi m là số hạng mục khác nhau. O (n lg n) trường hợp xấu nhất.

Sửa: đây là một O (n + m), single-pass phiên bản (giả sử 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) 

sử dụng bộ nhớ là O (m). max và sum có thể được thay thế bằng một vòng lặp đơn.

Answer 4

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

Đồng thời loại bỏ vấn đề với độ chính xác của phân chia phao.

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

Hãy nghĩ về danh sách của bạn như một nhóm quả bóng màu đỏ và đen.

Nếu bạn có một quả bóng màu đỏ trong một xô mười quả bóng, và bạn chọn một quả bóng ngẫu nhiên và đặt nó trở lại trong xô, và sau đó lặp lại bước mẫu và thay thế đó một nghìn lần, bao nhiêu lần của một ngàn bạn có mong đợi để quan sát một quả bóng màu đỏ, trung bình?

Khám phá phân phối Binomial và kiểm tra confidence intervals. Nếu bạn có một danh sách rất dài và muốn làm những việc tương đối hiệu quả, lấy mẫu là cách để đi.

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" 

Lưu ý: epsilon có giá trị "ngẫu nhiên", đã chọn một cái gì đó tùy thuộc vào độ dài của mảng, vv Nikita Rybak của giải pháp với currentCount >= n*0.95 sẽ không làm việc, bởi vì giá trị của CURRENTCOUNT khác nhau tùy theo thứ tự các yếu tố, nhưng ở trên không hoạt động.

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

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

Answer 8

loại giải pháp chung có thể nặng, nhưng hãy xem xét tính chất cân bằng tốt đặc biệt của sắp xếp thời gian trong Python, sử dụng thứ tự hiện có của danh sách. Tôi sẽ đề nghị để sắp xếp danh sách (hoặc bản sao của nó với sắp xếp, nhưng bản sao đó sẽ làm tổn thương hiệu suất). Quét từ đầu và trước để tìm cùng một phần tử hoặc độ dài quét đạt> 5%, nếu không danh sách tương tự 95% với phần tử được tìm thấy.

Lấy các yếu tố ngẫu nhiên làm ứng cử viên và đếm số lượng bằng cách giảm thứ tự tần suất có thể cũng không quá tệ cho đến khi số lượng được tìm thấy> 95% hoặc tổng số lượt vượt quá 5%.