Python- tìm ra mục với lần xuất hiện tối đa trong một danh sách

Question

Trong Python, tôi có một danh sách:

L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67] 

Tôi muốn xác định mục mà xảy ra số lượng cao nhất của thời đại. Tôi có thể giải quyết nó nhưng tôi cần cách nhanh nhất để làm như vậy. Tôi biết có một câu trả lời Pythonic tốt đẹp cho điều này.

Answer 1

Dưới đây là một giải pháp defaultdict rằng sẽ làm việc với các phiên bản Python 2.5 trở lên:

from collections import defaultdict 

L = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67] 
d = defaultdict(int) 
for i in L: 
    d[i] += 1 
result = max(d.iteritems(), key=lambda x: x[1]) 
print result 
# (4, 6) 
# The number 4 occurs 6 times 

Lưu ý nếu L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 7, 7, 7, 7, 7, 56, 6, 7, 67] sau đó có sáu 4s và sáu 7s. Tuy nhiên, kết quả sẽ là (4, 6) tức là sáu 4s.

Answer 2

from collections import Counter 
most_common,num_most_common = Counter(L).most_common(1)[0] # 4, 6 times 

Đối với phiên bản Python cũ (< 2.7), bạn có thể sử dụng this receipe để có được lớp Counter.

Answer 3

Có lẽ most_common() phương pháp

Answer 4

Trong câu hỏi của bạn, bạn đã yêu cầu cách nhanh nhất để làm điều đó. Như đã được chứng minh nhiều lần, đặc biệt là với Python, trực giác không phải là một hướng dẫn đáng tin cậy: bạn cần phải đo lường.

Dưới đây là một thử nghiệm đơn giản của việc triển khai khác nhau:

import sys 
from collections import Counter, defaultdict 
from itertools import groupby 
from operator import itemgetter 
from timeit import timeit 

L = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67] 

def max_occurrences_1a(seq=L): 
    "dict iteritems" 
    c = dict() 
    for item in seq: 
     c[item] = c.get(item, 0) + 1 
    return max(c.iteritems(), key=itemgetter(1)) 

def max_occurrences_1b(seq=L): 
    "dict items" 
    c = dict() 
    for item in seq: 
     c[item] = c.get(item, 0) + 1 
    return max(c.items(), key=itemgetter(1)) 

def max_occurrences_2(seq=L): 
    "defaultdict iteritems" 
    c = defaultdict(int) 
    for item in seq: 
     c[item] += 1 
    return max(c.iteritems(), key=itemgetter(1)) 

def max_occurrences_3a(seq=L): 
    "sort groupby generator expression" 
    return max(((k, sum(1 for i in g)) for k, g in groupby(sorted(seq))), key=itemgetter(1)) 

def max_occurrences_3b(seq=L): 
    "sort groupby list comprehension" 
    return max([(k, sum(1 for i in g)) for k, g in groupby(sorted(seq))], key=itemgetter(1)) 

def max_occurrences_4(seq=L): 
    "counter" 
    return Counter(L).most_common(1)[0] 

versions = [max_occurrences_1a, max_occurrences_1b, max_occurrences_2, max_occurrences_3a, max_occurrences_3b, max_occurrences_4] 

print sys.version, "\n" 

for vers in versions: 
    print vers.__doc__, vers(), timeit(vers, number=20000) 

Các kết quả trên máy tính của tôi:

2.7.2 (v2.7.2:8527427914a2, Jun 11 2011, 15:22:34) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] 

dict iteritems (4, 6) 0.202214956284 
dict items (4, 6) 0.208412885666 
defaultdict iteritems (4, 6) 0.221301078796 
sort groupby generator expression (4, 6) 0.383440971375 
sort groupby list comprehension (4, 6) 0.402786016464 
counter (4, 6) 0.564319133759 

Vì vậy, có vẻ như là giải pháp Counter không phải là nhanh nhất. Và, trong trường hợp này ít nhất, groupby là nhanh hơn. defaultdict là tốt nhưng bạn phải trả một chút cho sự tiện lợi của nó; nhanh hơn một chút để sử dụng số dict thông thường với số get.

Điều gì sẽ xảy ra nếu danh sách lớn hơn nhiều? Thêm L *= 10000 để thử nghiệm trên và giảm số lần lặp lại 200:

dict iteritems (4, 60000) 10.3451900482 
dict items (4, 60000) 10.2988479137 
defaultdict iteritems (4, 60000) 5.52838587761 
sort groupby generator expression (4, 60000) 11.9538850784 
sort groupby list comprehension (4, 60000) 12.1327362061 
counter (4, 60000) 14.7495789528 

Bây giờ defaultdict là người chiến thắng rõ ràng. Vì vậy, có lẽ chi phí của phương pháp 'get' và sự mất mát của việc thêm vào tại chỗ cho biết thêm (một kiểm tra của mã được tạo ra còn lại như là một bài tập).

Nhưng với dữ liệu thử nghiệm đã sửa đổi, số lượng giá trị mặt hàng duy nhất không thay đổi nên có lẽ dict và defaultdict có lợi thế hơn so với các triển khai khác. Vậy điều gì sẽ xảy ra nếu chúng ta sử dụng danh sách lớn hơn nhưng tăng đáng kể số lượng các mặt hàng độc đáo? Thay thế khởi của L với:

LL = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67] 
L = [] 
for i in xrange(1,10001): 
    L.extend(l * i for l in LL) 

dict iteritems (2520, 13) 17.9935798645 
dict items (2520, 13) 21.8974409103 
defaultdict iteritems (2520, 13) 16.8289561272 
sort groupby generator expression (2520, 13) 33.853593111 
sort groupby list comprehension (2520, 13) 36.1303369999 
counter (2520, 13) 22.626899004 

Bây giờ Counter rõ ràng nhanh hơn so với các giải pháp groupby nhưng vẫn là chậm hơn so với các phiên bản của iteritemsdict và defaultdict.

Điểm của những ví dụ này không phải là để tạo ra giải pháp tối ưu. Vấn đề là thường không có một giải pháp chung tối ưu. Ngoài ra còn có các tiêu chí hiệu suất khác.Các yêu cầu bộ nhớ sẽ khác nhau đáng kể trong số các giải pháp và, khi kích thước của đầu vào tăng lên, các yêu cầu bộ nhớ có thể trở thành yếu tố quan trọng trong việc lựa chọn thuật toán.

Tóm lại: tất cả đều phụ thuộc và bạn cần đo lường.

Answer 5

Tôi ngạc nhiên không ai có đề cập đến các giải pháp đơn giản nhất, max() với phím list.count:

max(lst,key=lst.count) 

Ví dụ:

>>> lst = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67] 
>>> max(lst,key=lst.count) 
4 

này hoạt động bằng Python 3 hoặc 2, nhưng lưu ý rằng nó chỉ trả về mục thường xuyên nhất và cũng không phải là tần số. Ngoài ra, trong trường hợp của vẽ (tức là mục thường gặp nhất) chỉ một mục được trả về.

tôi tìm cách tiếp cận max() là khoảng hai lần nhanh như Counter.most_common(1):

from collections import Counter 
from timeit import timeit 

def f1(lst): 
    return max(lst, key = lst.count) 

def f2(lst): 
    return Counter(lst).most_common(1) 

lst = range(100000) 

timeit(lambda: f1(lst), number = 1000) 
# 28.13 
timeit(lambda: f2(lst), number = 1000) 
# 59.01 

Answer 6

tôi thu được kết quả tốt nhất với groupby từ itertools mô-đun với chức năng này sử dụng Python 3.5.2:

from itertools import groupby 

a = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67] 

def occurrence(): 
    occurrence, num_times = 0, 0 
    for key, values in groupby(a, lambda x : x): 
     val = len(list(values)) 
     if val >= occurrence: 
      occurrence, num_times = key, val 
    return occurrence, num_times 

occurrence, num_times = occurrence() 
print("%d occurred %d times which is the highest number of times" % (occurrence, num_times)) 

Đầu ra:

4 occurred 6 times which is the highest number of times 

Tes t với timeit từ mô-đun timeit.

tôi đã sử dụng kịch bản này cho thử nghiệm của tôi với number= 20000:

from itertools import groupby 

def occurrence(): 
    a = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67] 
    occurrence, num_times = 0, 0 
    for key, values in groupby(a, lambda x : x): 
     val = len(list(values)) 
     if val >= occurrence: 
      occurrence, num_times = key, val 
    return occurrence, num_times 

if __name__ == '__main__': 
    from timeit import timeit 
    print(timeit("occurrence()", setup = "from __main__ import occurrence", number = 20000)) 

Output (Tốt nhất):

0.1893607140000313 

Answer 7

Tôi muốn ném vào một giải pháp mà có vẻ tốt đẹp và nhanh chóng cho ngắn danh sách.

def mc(seq=L): 
    "max/count" 
    max_element = max(seq, key=seq.count) 
    return (max_element, seq.count(max_element)) 

Bạn có thể điểm chuẩn này với các mã được cung cấp bởi Ned Deily mà sẽ cung cấp cho bạn những kết quả đối với trường hợp kiểm tra nhỏ nhất:

3.5.2 (default, Nov 7 2016, 11:31:36) 
[GCC 6.2.1 20160830] 

dict iteritems (4, 6) 0.2069783889998289 
dict items (4, 6) 0.20462976200065896 
defaultdict iteritems (4, 6) 0.2095775119996688 
sort groupby generator expression (4, 6) 0.4473949929997616 
sort groupby list comprehension (4, 6) 0.4367636879997008 
counter (4, 6) 0.3618192010007988 
max/count (4, 6) 0.20328268999946886 

Nhưng hãy cẩn thận, nó là không hiệu quả và do đó được thực sự chậm cho các danh sách lớn!

Answer 8

Sau đây là giải pháp mà tôi đã đưa ra nếu có nhiều ký tự trong chuỗi tất cả có tần số cao nhất.

mystr = input("enter string: ") 
#define dictionary to store characters and their frequencies 
mydict = {} 
#get the unique characters 
unique_chars = sorted(set(mystr),key = mystr.index) 
#store the characters and their respective frequencies in the dictionary 
for c in unique_chars: 
    ctr = 0 
    for d in mystr: 
     if d != " " and d == c: 
      ctr = ctr + 1 
    mydict[c] = ctr 
print(mydict) 
#store the maximum frequency 
max_freq = max(mydict.values()) 
print("the highest frequency of occurence: ",max_freq) 
#print all characters with highest frequency 
print("the characters are:") 
for k,v in mydict.items(): 
    if v == max_freq: 
     print(k) 

Input: "hello mọi người"

Output:

{'o': 2, 'p': 2, 'h': 1, ' ': 0, 'e': 3, 'l': 3} 

tần số cao nhất của điều xảy ra: 3

các nhân vật là:

e 

l