lặp qua danh sách trong python

Question

Tôi có một danh sách các chuỗi l (nhiều 1000 chuỗi): l = [ABCD,AABA,...]. Tôi cũng có một tệp f với nhiều chuỗi gồm 4 chữ cái (khoảng một triệu trong số đó). Tôi muốn chọn chuỗi gần nhất trong l cho mỗi chuỗi trong f tối đa khoảng cách Hamming tối đa 2 và cập nhật bộ đếm good_count. Tôi đã viết đoạn mã sau cho điều này nhưng nó rất chậm. Tôi đã tự hỏi nếu nó có thể được thực hiện nhanh hơn.

def hamming(s1, s2): 
    if len(s1) != len(s2): 
      raise ValueError("Undefined for sequences of unequal length") 
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2)) 

f = open("input.txt","r") 

l = [ABCD,AABA,...] 

good_count = 0 
for s in f: 
    x = f.readline() 
    dist_array = [] 
    for ll in l: 
     dist = hamming(x,ll) 
     dist_array.append(dist) 
    min_dist = min(dist_array) 
    if min_dist <= 2: 
     good_count += 1 
print good_count 

Nó hoạt động nhanh nếu l và f nhỏ nhưng phải mất quá nhiều thời gian cho lớn l và f. Vui lòng đề xuất giải pháp nhanh hơn.

Answer 1

thư viện Sử dụng hiện có, ví dụ như con sứa:

from jellyfish import hamming_distance 

nào mang đến cho bạn một việc thực hiện C của khoảng cách Hamming.

Answer 2

Ồ, bạn đang tính cách MANY khớp với khoảng cách hấp dẫn < 2? Điều đó có thể được thực hiện nhanh hơn nhiều.

total_count = 0 

for line in f: 
    # skip the s = f.readline() since that's what `line` is in this 
    line = line.strip() # just in case 
    for ll in l: 
     if hamming(line, ll) <= 2: 
      total_count += 1 
      break # skip the rest of the ll in l loop 
    # and then you don't need any processing afterwards either. 

Lưu ý rằng hầu hết thời gian mã của bạn sẽ được chi cho các dòng:

 if hamming(line, ll) <= 2: 

Vì vậy, bất kỳ cách nào bạn có thể cải thiện mà thuật toán rất nhiều sẽ cải thiện tốc độ kịch bản tổng thể của bạn. Câu trả lời của Boud làm nổi bật những đức tính của jellyfish 's hamming_distance chức năng, nhưng không có bất kỳ kinh nghiệm cá nhân tôi không thể giới thiệu nó bản thân mình. Tuy nhiên lời khuyên của ông để sử dụng một thực hiện nhanh hơn khoảng cách hamming là âm thanh!

---

Peter DeGlopper đề nghị thổi l danh sách vào sáu tập hợp khác nhau của "Hai hoặc ít khoảng cách hamming" phù hợp. Đó là, một nhóm các bộ chứa tất cả các cặp có thể có hai hoặc ít khoảng cách hamming. Điều này có thể trông giống như:

# hamming_sets is [ {AB??}, {A?C?}, {A??D}, {?BC?}, {?B?D}, {??CD} ] 
hamming_sets = [ set(), set(), set(), set(), set(), set() ] 

for ll in l: 
    # this should take the lion's share of time in your program 
    hamming_sets[0].add(l[0] + l[1]) 
    hamming_sets[0].add(l[0] + l[2]) 
    hamming_sets[0].add(l[0] + l[3]) 
    hamming_sets[0].add(l[1] + l[2]) 
    hamming_sets[0].add(l[1] + l[3]) 
    hamming_sets[0].add(l[2] + l[3]) 

total_count = 0 

for line in f: 
    # and this should be fast, even if `f` is large 
    line = line.strip() 
    if line[0]+line[1] in hamming_sets[0] or \ 
     line[0]+line[2] in hamming_sets[1] or \ 
     line[0]+line[3] in hamming_sets[2] or \ 
     line[1]+line[2] in hamming_sets[3] or \ 
     line[1]+line[3] in hamming_sets[4] or \ 
     line[2]+line[3] in hamming_sets[5]: 
     total_count += 1 

Bạn có thể có thể đạt được khả năng đọc bằng cách làm cho hamming_sets một cuốn từ điển của transform_function: set_of_results cặp giá trị quan trọng.

hamming_sets = {lambda s: s[0]+s[1]: set(), 
       lambda s: s[0]+s[2]: set(), 
       lambda s: s[0]+s[3]: set(), 
       lambda s: s[1]+s[2]: set(), 
       lambda s: s[1]+s[3]: set(), 
       lambda s: s[2]+s[3]: set()} 

for func, set_ in hamming_sets.items(): 
    for ll in l: 
     set_.add(func(ll)) 

total_count = 0 

for line in f: 
    line = line.strip() 
    if any(func(line) in set_ for func, set_ in hamming_sets.items()): 
     total_count += 1