Comment pouvons-nous compter efficacement les occurrences de sous-chaînes qui se chevauchent en Python ?

Compter efficacement les occurrences de chaînes qui se chevauchent

Identifier le nombre d'occurrences d'une sous-chaîne dans une chaîne peut être délicat, en particulier lorsque les chevauchements sont autorisés. Les bibliothèques comme la chaîne de Python fournissent des méthodes intégrées telles que « count » à cet effet, mais elles ne prennent pas en compte les instances qui se chevauchent.

Comptage de caractères qui se chevauchent

Considérez l'approche suivante :

def overlapping_count(string, substring):
    count = 0
    for i in range(len(string) - len(substring) + 1):
        if string[i:i+len(substring)] == substring:
            count += 1
    return count

Ici, la fonction parcourt la chaîne, examinant les sous-chaînes de la longueur spécifiée et incrémentant le nombre lorsque une correspondance est trouvée. Cette méthode est simple mais peut être relativement lente pour les grandes chaînes.

Une optimisation potentielle

Pour des raisons de performances, il vaut la peine d'explorer une approche différente qui implique d'utiliser les capacités de Cython :

import cython

@cython.boundscheck(False)
def faster_occurrences(string, substring):
    cdef int count = 0
    cdef int start = 0
    while True:
        start = string.find(substring, start) + 1
        if start > 0:
            count += 1
        else:
            return count

Avec Cython, nous pouvons profiter des déclarations de types statiques et de la compilation Just-In-Time (JIT) pour améliorer les performances en ignorer les vérifications de type et les optimisations inutiles pour le code Python. Cette fonction optimisée devrait être nettement plus rapide pour les ensembles de données plus volumineux.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!