python

Question

'daki bir listede yinelemek l dizilerinin l listesini (birçok 1000 dizisi): l = [ABCD,AABA,...]. Ayrıca bir çok 4 harfli (0,) bir dosyam var (yaklaşık bir milyon). En yakın 2 değerindeki bir Hamming mesafesine kadar f her dizi için l en yakın dize seçmek ve sayaç good_count güncelleştirin. Bunun için şu kodu yazdım ama çok yavaş. Daha hızlı yapılabilir mi diye merak ediyordum.

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 

Hızlı eğer l ve f küçük çalışıyor ancak l ve f büyük için çok uzun sürüyor. Lütfen daha hızlı bir çözüm öner. Örneğin denizanası için

Answer 1

Kullanım mevcut kütüphaneler,:

size hamming mesafenin C uygulamasını verir

from jellyfish import hamming_distance 

.

Answer 2

Oh, sadece MANY'ın bir hamming mesafesi < 2 ile nasıl eşleştiğini sayıyorsunuz? Bu çok daha hızlı yapılabilir. kodunuzu çoğu zaman on line harcanacak

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. 

Not:

 if hamming(line, ll) <= 2: 

Yani BÜYÜK genel komut hızını artıracağını algoritmayı geliştirmek herhangi bir yolu. Boud'un cevabı, jellyfish'un hamming_distance işlevinin erdemlerini yüceltir, ancak herhangi bir kişisel deneyim olmadan kendimi tavsiye edemem. Ancak hamming mesafesinin daha hızlı uygulanmasına yönelik tavsiyesi ses!

---

Peter DeGlopper "İki ya da daha az hamming mesafe" kibrit altı farklı kümeler halinde l liste üfleme önerir. Yani, iki veya daha az hamming mesafesine sahip olabilecek tüm olası çiftleri içeren bir grup set. Muhtemelen hamming_setstransform_function: set_of_results anahtar değer çiftleri bir sözlük yaparak okunabilirliği kazanabilir

# 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 

: gibi bu görünebilir.

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