La partie concernant la bibliothèque de astuces à connaître lors de la programmation de la compétition avec Python2 a été divisée.
La version Python est ** 2.7.5 ** (En Python3, les spécifications telles que l'entrée et la sortie sont très différentes, il est donc recommandé de se référer à d'autres articles).
Voici quelques bibliothèques que je trouve utiles, bien qu'elles soient un peu mineures.
Je l'écrirai un jour.
9.7. Itertools - Fonction de génération d'itérateur pour une exécution de boucle efficace
Utilisez itertools pour obtenir des combinaisons et des séquences en Python | CUBE SUGAR STORAGE
Une bibliothèque remplie de méthodes pour générer des itérateurs.
En programmation compétitive, il est utile lors de la génération de séquences et de combinaisons (correspondant à next_permutation en C ++). Il fonctionne beaucoup plus rapidement que de tourner plusieurs boucles par vous-même, vous devez donc l'utiliser activement.
permutations.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Sélectionnez deux éléments dans l et organisez-les
#Ne considérez pas la duplication
#La commande est considérée(permutation)
for elem in itertools.permutations(l, 2):
print elem #Le taple des éléments disposés est attribué à elem
output
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 1)
(2, 3)
(2, 4)
(2, 5)
(3, 1)
(3, 2)
(3, 4)
(3, 5)
(4, 1)
(4, 2)
(4, 3)
(4, 5)
(5, 1)
(5, 2)
(5, 3)
(5, 4)
combinations.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Sélectionnez 3 éléments de l et disposez-les
#Ne considérez pas la duplication
#Ne considère pas la commande(combinaison)
for elem in itertools.combinations(l, 3):
print elem
output
(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)
Par ailleurs, il est également possible d'obtenir des combinaisons prenant en compte la duplication et les produits cartésiens (produits directs).
combinations_with_replacement.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Disposer les deux ensembles d'éléments extraits de l
#Envisagez la duplication
#Ne considère pas la commande
for elem in itertools.product(l, repeat=2):
print elem
output
(1, 1)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 2)
(2, 3)
(2, 4)
(2, 5)
(3, 3)
(3, 4)
(3, 5)
(4, 4)
(4, 5)
(5, 5)
cartesian_product.py
import itertools
l = range(1, 6) # [1, 2, 3, 4, 5]
#Disposer les deux ensembles d'éléments extraits de l
#Envisagez la duplication
#La commande est considérée
for elem in itertools.product(l, repeat=2):
print elem
#Le code ci-dessus est équivalent au code suivant
for a in l:
for b in l:
print (a, b)
output
(1, 1)
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(2, 5)
(3, 1)
(3, 2)
(3, 3)
(3, 4)
(3, 5)
(4, 1)
(4, 2)
(4, 3)
(4, 4)
(4, 5)
(5, 1)
(5, 2)
(5, 3)
(5, 4)
(5, 5)
collections
8.3. Collections - type de données conteneur hautes performances - documentation Python 2.7ja1
Le module de collections Python est sobre et pratique-Yuimono Seishin @Scaled_Wurm
defaultdict
Comme son nom l'indique, collections.defaultdict est un dict avec des valeurs par défaut.
Dans la programmation compétitive, il existe de nombreuses possibilités de créer des compteurs (en particulier pour les problèmes de jeu d'implémentation).
Par exemple, lorsqu'une question est posée sur la fréquence des mots anglais existant dans l'entrée, il est nécessaire de créer un compteur correspondant à chaque mot à l'aide de dict, mais dict initialise la clé. Sinon, une erreur se produira, ce qui est gênant.
En utilisant defaultdict, vous pouvez réduire l'initialisation et rendre le code plus facile à lire.
from collections import defaultdict
l = ['to', 'be', 'or', 'not', 'to', 'be', 'that', 'is', 'the', 'question']
#Pour dict
d = {}
for e in l:
#Vérifiez s'il y a une valeur de clé à chaque fois, sinon, vous devez initialiser
if e in d.keys():
d[e] += 1
else:
d[e] = 1
print d # {'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2}
dd = defaultdict(int) #Toutes les clés sont initialisées avec 0
for e in l:
dd[e] += 1 #Pas besoin d'initialiser
print dd # defaultdict(<type 'int'>, {'be': 2, 'that': 1, 'is': 1, 'question': 1, 'to': 2, 'not': 1, 'the': 1, 'or': 1})
print dd['be'] # 2
dd2 = defaultdict(list) #Toutes les clés[]Initialisé avec
dd2['a'].append(1)
print dd2 # defaultdict(<type 'list'>, {'a': [1]})
collections.Counter est un objet spécialisé pour la création de compteur, et 0 est automatiquement défini comme valeur initiale.
C'est équivalent à defautdict (int), mais il existe d'autres fonctions utiles telles que la valeur maximale peut être obtenue immédiatement.
from collections import Counter
l = ['to', 'be', 'or', 'not', 'to', 'be', 'that', 'is', 'the', 'question']
c = Counter()
for e in l:
c[e] += 1
print c # Counter({'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2})
print c['be'] # 2
#Si vous passez une liste etc. comme argument, elle sera comptée automatiquement
c2 = Counter(l)
print c2 # Counter({'be': 2, 'is': 1, 'not': 1, 'or': 1, 'question': 1, 'that': 1, 'the': 1, 'to': 2})
#Trier par valeur de compteur décroissante
print c.most_common() # [('be', 2), ('to', 2), ('that', 1), ('is', 1), ('question', 1), ('not', 1), ('the', 1), ('or', 1)]
#Sorties 3 dans l'ordre de celle avec la plus grande valeur de compteur
print c.most_common(3) # [('be', 2), ('to', 2), ('that', 1)]