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"
salut dpi il doit y avoir une erreur dans ta colonne verte T et X doivent normalement devenir "1" et "2"
Bonjour,
voici mon résultat rectifié.
les deux colonnes masquées sont des tests qui fonctionnent.
Le code de Ulmiere me semble bien compliqué pour cette tâche. Celui de dpi me semble bien plus efficace.
Voici ma version:
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
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
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__))))
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)
J'ai pas Python sous la main là, tu peux tester cette version avec accumulateur ?
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
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
J'ai trouvé une méthode plus rapide (à partir de ~100 caractères) :
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
C'est étonnant que flight_with_acc soit si lente
Peut-être le reduce qui est plus lent qu'une simple boucle
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :