Comment entrelacer deux chaînes de longueurs variables en Python ?

Il y a une demi-heure, mon ami et co-auteur du manuel "Coffee Break NumPy" m'a posé la question suivante via WhatsApp :

Formulation du problème

Comment résoudriez-vous le problème de l'entrelacement de deux chaînes en Python :

Entrée :Chaîne s1= "AAA" et la chaîne s2 = "BBBBB"
Sortie :Chaîne s="ABABABBB"

Étant obsédé par la recherche de la manière la plus Pythonique d'écrire n'importe quel extrait de code (de préférence dans une seule ligne de code), je suis rapidement devenu frustré car il ne semble pas y avoir de réponse très simple, claire et concise à cette question.

Cependant, dans cet article, vous apprendrez une manière robuste et facile à comprendre de résoudre ce problème (sans support de bibliothèque externe). Alors continuez à lire.

Alternative 1 :la première chaîne s1 est plus courte

En supposant que la première chaîne est plus courte, nous avons la possibilité de résoudre le problème dans une ligne Python en utilisant la compréhension de liste :

s1 = "AAA"
s2 = "BBBBB"

s = "".join([s1[i] + s2[i] for i in range(len(s1))]) + s2[len(s1):]
print(s)
# ABABABBB

En raison de l'implémentation efficace de la compréhension de liste par Python, cette option est extrêmement rapide - je doute qu'il y ait quoi que ce soit de plus rapide (qui soit toujours aussi lisible).

Nous combinons chaque caractère de la chaîne la plus courte s1 avec le caractère de la chaîne la plus longue s2 à la position respective. Cela se traduit par la chaîne partiellement entrelacée "ABABAB" . Maintenant, nous concaténons simplement cela avec les caractères restants de la chaîne plus longue s2 .

Cependant, cette solution ne fonctionne pas si la chaîne s1 peut également être plus long que la chaîne s2 .

Pourquoi? Parce que l'interpréteur Python lèvera une erreur d'index comme accédant au s2[i] n'est pas possible.

Alternative 2 :n'importe quelle chaîne peut être plus longue

Si vous ne supposez pas que l'une des chaînes est plus longue que l'autre, le problème devient légèrement plus difficile. Pourtant, il existe une solution simple et propre à ce problème (sans utiliser de bibliothèques externes). Il ne s'agit pas d'une seule ligne de code, mais il est lisible, rapide et ne nécessite aucune hypothèse de longueur :

s1 = "AAA"
s2 = "BBBBB"

s = list(s2)
for i,c in enumerate(s1):
    s.insert(i*2,c)
print("".join(s))
# ABABABBB

Tout d'abord, nous convertissons la chaîne s2 à une liste de caractères en utilisant le list(...) fonction. C'est la base de notre solution.

Deuxièmement, nous insérons les caractères de la chaîne s1 aux positions 0, 2, 4, … en itérant sur tous les indices i et caractères c de la première chaîne s1 . Maintenant, nous insérons les caractères à toutes les autres positions de la liste.

Alternative 3 :Utiliser des bibliothèques externes

Les codeurs experts utilisent beaucoup les bibliothèques externes car cela rend leur code plus lisible, plus efficace et plus court. Qu'est-ce qui ne va pas avec ça? Voici ce qu'un lecteur expert David de mon cours par e-mail (gratuit) "Coffee Break Python" a proposé :

import itertools


s1 = "AAA"
s2 = "BBBBB"

s = "".join([ x + y for x, y in itertools.zip_longest(s1, s2, fillvalue="")])
print(s)
# ABABABBB

Le problème avec la prise du zip() intégré fonction est que le nombre de paires renvoyées par le zip() fonction est égale à l'itérable le plus court.

Voici ce que soutient mon fidèle lecteur David :

[…] zip_longest() met en coffre le zip() (intégré) 'limitation' de la coupure au plus court len() […]. Il "étend" l'itérable le plus court avec un fillvalue paramètre - en utilisant [la chaîne vide] plutôt que le None par défaut , sinon la concaténation de chaînes suivante échouera !

Encore une fois, si le support de la bibliothèque est autorisé (en d'autres termes :vous n'êtes pas dans un entretien de codage), c'est ma solution préférée.

Mesures des performances

Après avoir publié cet article, mon co-auteur Lukas (livre "Coffee Break NumPy") est revenu vers moi avec un gentil analyse de performance. Quelle fonction fonctionne le mieux ? Je ne veux pas retenir les résultats intéressants, car vous pourriez aussi les trouver utiles :

import itertools
import matplotlib.pyplot as plt
plt.xkcd()


def interleave_strings_listcomprehension(s1, s2):  
    return "".join([s1[i] + s2[i] for i in range(len(s1))]) + s2[len(s1):]    
    

def interleave_strings_enumerate(s1, s2):
    s = list(s2)
    for i, c in enumerate(s1):
        s.insert(i*2, c)
    
    return "".join(s)
    
    
def interleave_strings_slicing(s1, s2):
    length_s1 = len(s1)
    length_s2 = len(s2)
    
    if length_s1 != length_s2:
        if length_s1 > length_s2:
            spaces_count = length_s1 - length_s2
            s2 = s2 + spaces_count * ' '
        else:
            spaces_count = length_s2 - length_s1
            s1 = s1 + spaces_count * ' '
    
    interleaved = len(s1) * 2 * ['']
    interleaved[::2] = s1
    interleaved[1::2] = s2
    
    return ''.join(interleaved).replace(' ', '')
    
    
def interleave_strings_zip(s1, s2):
    length_s1 = len(s1)
    length_s2 = len(s2)
    
    if length_s1 != length_s2:
        if length_s1 > length_s2:
            spaces_count = length_s1 - length_s2
            s2 = s2 + spaces_count * ' '
        else:
            spaces_count = length_s2 - length_s1
            s1 = s1 + spaces_count * ' '
    
    return "".join(i + j for i, j in zip(s1, s2)).replace(' ', '')

def interleave_zip_itertools(s1, s2):
    import itertools
    return "".join([ x + y for x, y in itertools.zip_longest(s1, s2, fillvalue="")])
    
    
    
    
import time

multiplicator = 1000
s1 = multiplicator * "AAA"
s2 = multiplicator * "BBBB"

# Test 1
start = time.perf_counter()
interleave_strings_listcomprehension(s1, s2)
end = time.perf_counter()
plt.bar(1,end - start, hatch=" ", label="List comprehension (Alt 1)")

# Test 2
start = time.perf_counter()
interleave_strings_enumerate(s1, s2)
end = time.perf_counter()
plt.bar(2,end - start, hatch="o", label="Enumerate (Alt 2)")

# Test 3
start = time.perf_counter()
interleave_strings_slicing(s1, s2)
end = time.perf_counter()
plt.bar(3,end - start, hatch="+", label="Slicing")

# Test 4
start = time.perf_counter()
interleave_strings_zip(s1, s2)
end = time.perf_counter()
plt.bar(4,end - start, hatch="/", label="Zip")

# Test 5
start = time.perf_counter()
interleave_zip_itertools(s1, s2)
end = time.perf_counter()
plt.bar(5,end - start, hatch="-", label="Zip Itertools (Alt 3)")


plt.xticks((),())
plt.ylabel("nanosecs")
plt.legend()
plt.tight_layout()
plt.savefig("plot.jpg")
plt.show()

Voici le graphique à barres résultant comparant le temps d'exécution des différentes fonctions :

La fonction de découpage a surpassé toute autre fonction d'au moins 50 % ! Je savais que le tranchage est rapide mais ce résultat m'a époustouflé. J'ai également testé le résultat pour des chaînes encore plus grandes, mais le tranchage semble toujours être l'alternative la plus rapide. Cela se fait au prix que la lisibilité souffre un peu par rapport aux itertools la solution.