Inscription / Connexion Nouveau Sujet
Niveau exercices
Partager :

chaine de caractères et algo

Posté par
flight
18-02-23 à 19:39

Bonsoir

je vous propose l'exercice suivant  :

Ecrire un algorithme qui permet de transformer une chaine de caractère de sorte que si la chaine contient une ou plusieurs lettres groupées alors celle ci soit remplacées  par une chaine numerique du type "1234...ect" selon le nombre de lettres  ....
un exemple parle mieux :
soit la chaine  "6930A85CDU744ZABR09"  
celle ci doit devenir  "6930185123744123409"

Posté par
Ulmiere
re : chaine de caractères et algo 18-02-23 à 20:59

 Cliquez pour afficher

Posté par
dpi
re : chaine de caractères et algo 19-02-23 à 13:12

Bonjour,
Selon mon habitude..

 Cliquez pour afficher

Posté par
flight
re : chaine de caractères et algo 19-02-23 à 18:59

salut dpi il doit y avoir une erreur dans ta colonne verte   T et X  doivent normalement devenir "1" et "2"

Posté par
dpi
re : chaine de caractères et algo 19-02-23 à 19:13

Oui,
J'ai un test qui m'a lâché,j'y retravaille...

Posté par
dpi
re : chaine de caractères et algo 20-02-23 à 08:07

Bonjour,
voici mon résultat rectifié.
les deux colonnes masquées sont des tests qui fonctionnent.

 Cliquez pour afficher

Posté par
dpi
re : chaine de caractères et algo 21-02-23 à 10:07

Voici mes formules:

 Cliquez pour afficher

Posté par
flight
re : chaine de caractères et algo 21-02-23 à 14:42

excellent à  dpi et Ulmière

Posté par
LittleFox
re : chaine de caractères et algo 21-02-23 à 17:25


Le code de Ulmiere me semble bien compliqué pour cette tâche. Celui de dpi me semble bien plus efficace.

Voici ma version:

 Cliquez pour afficher


Bonne journée

Posté par
Ulmiere
re : chaine de caractères et algo 21-02-23 à 18:18

Et non, il ne faut pas s'y tromper, c'est peut-être bien mon code qui est plus efficace, parce que les votres (ab)usent de l'allocation dynamique des chaines de caractère (et donc de la reallocation quand la capacité est atteinte).

Quand tu fais modified_message += c en boucle, ça dépend de comment Python gère ça mais en gros

- soit (improbable) Python realloue un buffer de taille (len(message) + len(c)) * sizeof(UnicodeChar) puis strcpy message et c successivement
- soit Python agit plutôt comme un std::vector<UnicodeChar> et va donc doubler la capacité de la chaîne à chaque fois qu'elle est pleine. Le fait de toujours appeler str.__radd__ implique que le code va systématiquement calcler len(modified_message)+len(c) pour savoir si cette quantité est inférieure à la capacité de modified_message. Mais ce sont des cycles gâchés. Dans mon code, je ne fais de concaténation que quand c'est nécessaire.

On pourrait grandement accélérer no sdeux codes de toute façon en utilisant un accumulateur et une seule et unique conversion en str à la fin

Posté par
LittleFox
re : chaine de caractères et algo 22-02-23 à 10:01


Ce serait vrai en C mais en Python le code interprété est beaucoup plus lent que le code builtin. Du coup, c'est un cas d'optimisation prématurée code le montre le test si dessous:

 length      t1      t2
      1   0.000   0.001
     10   0.002   0.006
    100   0.022   0.047
   1000   0.307   0.482
  10000   2.933   4.795
 100000  29.667  48.136
1000000 317.803 474.689

Avec t1 (resp. t2) le temps en millisecondes pour exécuter la fonction sur un message de longueur length (moitié chiffres, moitié lettres mélangés) pour replace_letters (resp. flight).

Un profiling montre que replace_letters passe le plus de temps dans c.isdigit()et effectivement on peut gagner un peu de temps en remplacant c.isdigit() par c in digits.
Et un profiling montre que flight pass le plus de temps dans ''.join(str(k) for k in range(1, j - i + 1)) (la moitié pour le générateur et l'autre pour le join). On peut réduire le temps passé dans le générateur en le remplaçant par map: ''.join(map(str, range(1, j - i + 1))). Mais pour le join, je ne sais pas. Je suppose qu'il faudrait le faire à la fin avec un accumulateur comme tu dis.

Posté par
LittleFox
re : chaine de caractères et algo 22-02-23 à 10:02


Le code est disponible ici:

Posté par
LittleFox
re : chaine de caractères et algo 22-02-23 à 10:13


Ce oneliner avec un accumulateur ce situe entre les deux:

def replace_letters(message):
    return ''.join(map(str, chain.from_iterable(
        g if k else (i for i, c in enumerate(g)) for k, g in groupby(message, digits.__contains__))))


Mais devient incompréhensible.

Posté par
LittleFox
re : chaine de caractères et algo 22-02-23 à 10:19


Cette version ci est aussi entre les deux:

def replace_letters_2(message):
    modified_message = []
    count = 0
    for c in message:
        if c in digits:
            modified_message.extend(map(str, range(1, count+1)))
            count = 0
            modified_message.append(c)
        else:
            count += 1
    return ''.join(modified_message)


Non décidement, en Python, le plus simple est le mieux la plupart du temps.  Et ça c'est chouette

Posté par
dpi
re : chaine de caractères et algo 22-02-23 à 12:21

Bonjour,
J'ai transposé ma chaîne horizontalement

chaine de caractères et algo

Posté par
Ulmiere
re : chaine de caractères et algo 22-02-23 à 14:23

J'ai pas Python sous la main là, tu peux tester cette version avec accumulateur ?

 Cliquez pour afficher



Et aussi, si tu as le temps et l'envie, la même mais en exécutant letters2digits (ou l'identité, pour le premier while) dans une coroutine/light thread si j-i > t avec t un entier positif de ton choix pour faire en sorte de ne pas lancer de thread si ça ne sert à rien.
Et aussi une autre variante dichotomique où on coupe d'abord la chaine en deux (si elle est de longueur supérieure à un paramètre L) et lance deux fois la fonction de résolution en parallèle avant de concaténer les résultats. Une sorte de tri fusion mais sans tri

Je pense qu'il y a moyen que la solution optimale soit un mix de ces deux là

Posté par
LittleFox
re : chaine de caractères et algo 22-02-23 à 16:09

Je n'ai pas accès à mon ordi pour l'instant non plus. Je te laisse faire les tests 🙂

Mais ça m'étonnerait qu'appeler les sous fonctions letters2digits et nbdigits soit plus efficace que de manipuler les strings. D'ailleurs la méthode la plus efficace que j'aie trouvé à ce jour pour nb_digits(n) est len(str(n)).
La coroutine ne servira à rien, en effet elle tournera sur le même processeur. Les coroutine tournent dans une event loop. Elles ne sont utiles que s'il y a des temps d'attente (typiquement les opérations IO).
On peut faire du multiprocess avec la version dichotomique mais il faut déjà que la chaîne soit longue avant que l'overhead ne soit remboursé. S'il est remboursé un jour car il faut encore concaténer les résultats.

Je pense que la solution optimale reste la plus simple

Posté par
LittleFox
re : chaine de caractères et algo 23-02-23 à 15:25

La fonction flight_with_acc est vraiment inefficace

length replace_letters flight replace_letters_2 replace_letters_3 flight_with_acc
      1   0.000   0.001   0.001   0.001   0.001
     10   0.002   0.005   0.005   0.003   0.009
    100   0.020   0.039   0.037   0.030   0.074
   1000   0.285   0.471   0.406   0.321   1.074
  10000   3.730   5.751   5.043   4.671  27.049
 100000  29.408  45.253  37.747  32.012 1277.769


Elle n'est même plus linéaire par rapport à la longueur du message. On a un facteur 4x pour un message de longueur 1000 qui passe à 40x pour un message de longueur 100000.

Le code github est mis à jour:

Posté par
LittleFox
re : chaine de caractères et algo 23-02-23 à 16:28


J'ai trouvé une méthode plus rapide (à partir de ~100 caractères) :

 Cliquez pour afficher


length replace_letters flight replace_letters_2 replace_letters_3 replace_letters_4
      1   0.000   0.001   0.001   0.001   0.002
     10   0.002   0.004   0.004   0.003   0.003
    100   0.016   0.034   0.031   0.025   0.015
   1000   0.237   0.381   0.305   0.251   0.136
  10000   2.275   3.754   2.983   2.489   1.271
 100000  22.670  37.364  30.632  26.504  13.304


L'idée est de découper le message en blocs de chiffres et lettres au lieu de travailler caractère par caractère. On manipule moins de strings. On peut remplacer les blocs de lettres par leur longueur pour manipuler encore moins de strings.
Ainsi '6930A85CDU744ZABR09' devient ['6930', 1, '85', 3, '744', 4, '09']
L'autre idée est de calculer une seule fois la table ['', '1', '12', '123', '1234', ...] au lieu de régénérer ces strings pour chaque bloc de lettres.
Un petit remplacement et on obtient  ['6930', '1', '85', '123', '744', '1234', '09']. Qu'il suffit de concaténer pour avoir la réponse.

Posté par
Ulmiere
re : chaine de caractères et algo 23-02-23 à 19:48

C'est étonnant que flight_with_acc soit si lente
Peut-être le reduce qui est plus lent qu'une simple boucle

Posté par
dpi
re : chaine de caractères et algo 24-02-23 à 08:22

Nous avons tous constaté que concatener ne pouvait se transcrire



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !