boucles imbriquées évitant les comparaisons auto et réciproques

Question

Puisqu'il doit être un scénario assez commun, je me demande s'il existe des solutions préexistantes à ce qui suit. Disons que j'ai un ensemble de chaînes N, et je calcule les distances entre elles. Dans ce cas, c'est une distance de Hamming, mais ce n'est pas vraiment important.

Si je voulais faire cela aussi vite que possible, je voudrais éviter des comparaisons auto comme ceci:

def hamming_distance(string1, string2): 
    """Return the Hamming distance between equal-length sequences""" 
    if len(string1) != len(string2): 
     raise ValueError("Undefined for sequences of unequal length") 
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2)) 


ratios=[] 
for a, i in enumerate(string_list): 
    for b, j in enumerate(string_list): 
     if a == b: # Avoid self comparisons for speed 
      break 
    ratios.append(hamming_distance(string_list[i], string_list[j])) 
return ratios 

Mais puisque c'est « symétrique », je pourrais aussi jeter des comparaisons réciproques qui augmenterait la vitesse si les cordes étaient nombreuses et/ou grandes.

Y a-t-il une manière généralement acceptée/élégante de faire ceci dans la configuration ci-dessus? Je suis également conscient que, en général, il est conseillé d'éviter les boucles imbriquées car elles peuvent être lentes - donc s'il y a une meilleure façon d'obtenir cette itération par paire sur les listes (peut-être quelque chose en collections?) Et en évitant auto et comparaisons réciproques, je suis tout ouïe.

Answer 1

Vous pouvez limiter l'imbriqué pour pour passer de l'élément suivant à l'élément actuel dans la boucle externe. De cette façon, vous exécutez seulement à travers chaque fois uniques:

for i, s1 in enumerate(string_list): 
    for s2 in string_list[i+1:]: 
     ratios.append(hamming_distance(s1, s2)) 
return ratios 

Vous pouvez mettre cela dans une liste comp .:

ratios = [(s1, s2, hamming_distance(s1, s2)) for i, s1 in enumerate(string_list) 
                for s2 in string_list[i+1:]] 

Vous pouvez mettre les chaînes dans un tuple dans le cadre du résultat comme J'ai fait dans la liste comp.

Answer 2

Ce que vous cherchez est implémenté par itertools.combinations().

>>> import itertools 
>>> a = [1,2,3] 
>>> list(itertools.combinations(a, 2)) 
[(1, 2), (1, 3), (2, 3)] 

Donc, dans votre cas, il ressemblera à ceci:

for a, b in itertools.combinations(string_list, 2): 
    ratios.append(hamming_distance(a, b))