Python: Kiểm tra các lần xuất hiện trong danh sách với giá trị

Question

lst = [1,2,3,4,1] 

Tôi muốn biết 1 xảy ra hai lần trong danh sách này, có cách nào hiệu quả không?

Answer 1

lst.count(1) sẽ trả về số lần nó xảy ra. Nếu bạn sẽ đếm các mục trong một danh sách, O (n) là những gì bạn sẽ nhận được.

Chức năng chung trong danh sách là list.count(x) và sẽ trả lại số lần x xảy ra trong danh sách.

Answer 2

Bạn có hỏi liệu mọi mục trong danh sách có độc đáo không?

len(set(lst)) == len(lst) 

Có phải 1 xảy ra nhiều lần không?

lst.count(1) > 1 

Lưu ý rằng ở trên không phải là tối đa hiệu quả, bởi vì nó sẽ không ngắn mạch - ngay cả khi 1 xảy ra hai lần, nó sẽ vẫn đếm phần còn lại của sự cố. Nếu bạn muốn nó ngắn mạch, bạn sẽ phải viết một cái gì đó phức tạp hơn một chút.

Liệu yếu tố đầu tiên có xảy ra nhiều lần không?

lst[0] in lst[1:] 

Tần suất mỗi phần tử xảy ra?

import collections 
collections.Counter(lst) 

Cái gì khác?

Answer 3

def valCount(lst): 
    res = {} 
    for v in lst: 
     try: 
      res[v] += 1 
     except KeyError: 
      res[v] = 1 
    return res 

u = [ x for x,y in valCount(lst).iteritems() if y > 1 ] 

u bây giờ là danh sách tất cả các giá trị xuất hiện nhiều lần.

Edit:

@katrielalex: cảm ơn bạn đã chỉ ra collections.Counter, trong đó tôi đã không biết trước đây. Nó cũng có thể được viết ngắn gọn hơn bằng cách sử dụng một collection.defaultdict, như được minh chứng trong các bài kiểm tra sau đây. Cả ba phương thức đều xấp xỉ O (n) và đóng một cách hợp lý trong hiệu năng thời gian chạy (sử dụng collections.defaultdict thực tế là nhanh hơn collection.Counter) một chút.

Ý định của tôi là đưa ra một câu trả lời dễ hiểu cho những gì dường như là một yêu cầu tương đối không phức tạp. Cho rằng, có bất kỳ giác quan khác trong đó bạn xem xét nó "xấu mã" hoặc "thực hiện kém"?

import collections 
import random 
import time 

def test1(lst): 
    res = {} 
    for v in lst: 
     try: 
      res[v] += 1 
     except KeyError: 
      res[v] = 1 
    return res 

def test2(lst): 
    res = collections.defaultdict(lambda: 0) 
    for v in lst: 
     res[v] += 1 
    return res 

def test3(lst): 
    return collections.Counter(lst) 

def rndLst(lstLen): 
    r = random.randint 
    return [r(0,lstLen) for i in xrange(lstLen)] 

def timeFn(fn, *args): 
    st = time.clock() 
    res = fn(*args) 
    return time.clock() - st 

def main(): 
    reps = 5000 

    res = [] 
    tests = [test1, test2, test3] 

    for t in xrange(reps): 
     lstLen = random.randint(10,50000) 
     lst = rndLst(lstLen) 
     res.append([lstLen] + [timeFn(fn, lst) for fn in tests]) 

    res.sort() 
    return res 

Và kết quả, cho các danh sách ngẫu nhiên chứa lên đến 50.000 mặt hàng, như sau: (Trục dọc là thời gian trong vài giây, trục ngang là số mục trong danh sách)

Answer 4

Một cách khác để có được tất cả các mục mà xảy ra nhiều hơn một lần:

lst = [1,2,3,4,1] 
d = {} 
for x in lst: 
    d[x] = x in d 
print d[1] # True 
print d[2] # False 
print [x for x in d if d[x]] # [1] 

Answer 5

Đối với nhiều lần xuất hiện, điều này cung cấp cho bạn những chỉ số của mỗi điều xảy ra:

>>> lst=[1,2,3,4,5,1] 
>>> tgt=1 
>>> found=[] 
>>> for index, suspect in enumerate(lst): 
...  if(tgt==suspect): 
...  found.append(index) 
... 
>>> print len(found), "found at index:",", ".join(map(str,found)) 
2 found at index: 0, 5 

Nếu bạn muốn đếm từng hạng mục trong danh sách:

>>> lst=[1,2,3,4,5,2,2,1,5,5,5,5,6] 
>>> count={} 
>>> for item in lst: 
...  count[item]=lst.count(item) 
... 
>>> count 
{1: 2, 2: 3, 3: 1, 4: 1, 5: 5, 6: 1} 

Answer 6

Bạn cũng có thể sắp xếp danh sách đó là O (n * log (n)), sau đó kiểm tra các yếu tố liền kề cho bình đẳng, đó là O (n). Kết quả là O (n * log (n)). Điều này có bất lợi của yêu cầu toàn bộ danh sách được sắp xếp trước khi có thể bailing khi trùng lặp được tìm thấy.

Đối với danh sách lớn có bản sao tương đối hiếm, đây có thể là điều tốt nhất bạn có thể làm. Cách tốt nhất để tiếp cận điều này thực sự phụ thuộc vào kích thước của dữ liệu có liên quan và tính chất của nó.