L'opérateur de Python est-il lent? (À partir de ABC167D)

On dit que l'utilisation de ʻin (en utilisant ʻin dans une boucle) à chaque fois pour juger à plusieurs reprises "s'il y a un élément dans la liste" peut être lente. La conclusion semble être que "rechercher dans la liste en utilisant ʻin est lent" plutôt que ʻin lui-même étant lent. Je l'avais remarqué légèrement, mais c'était probablement la première fois que je réalisais une telle différence de vitesse.

Un programme similaire soumis dans ABC167D ci-dessous, mais le premier était une parade de «TLE» en recherchant dans la liste en utilisant «in» dans une boucle. D'autre part, le second crée une liste séparée pour les drapeaux et les traite, et c'est légèrement «AC» (139ms). En outre, le troisième est une expérience basée sur les conseils d'une personne aimable: "Vous devez définir la cible de recherche à définir au lieu de la liste." Ceci est également devenu facilement «AC» (188 ms).

AtCoder Beginner Contest 167 D - Teleporter

ABC167D/TLE

n, k = map(int,input().split())
a = list(map(int, input().split()))
dst = [1] #Liste des villes (y compris la première) que j'ai visitées jusqu'à présent
twn = 1 #Destination de transfert de téléporteur
for _ in range(k):
    if a[twn - 1] not in dst: #Si la destination de transfert du téléporteur ne figure pas dans la liste des villes que vous avez visitées
        dst.append(a[twn - 1]) #Sinon, ajoutez-le à la liste des villes que vous avez visitées
        twn = a[twn - 1] #Mettre à jour la destination de transfert du téléporteur
    else: #Si la destination de transfert du téléporteur est dans la liste des villes que vous avez visitées jusqu'à présent (la destination de transfert à partir de là fera une boucle)
        index = dst.index(a[twn - 1]) #Obtenez l'index de la destination de transfert de téléporteur dans la liste des villes que vous avez effectuées jusqu'à présent
        ld = len(dst[:index]) #Trouvez la longueur avant la boucle et la période de la partie de la boucle
        cyc = len(dst[index:])
        print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
        exit()
print(dst[-1])

ABC167D/AC139ms

n, k = map(int,input().split())
a = list(map(int, input().split()))
flg = [True] * n #Liste d'indicateurs indiquant si vous êtes allé dans chaque ville(Vrai sinon parti)
dst = [1]
twn = 0 #Destination de transfert de téléporteur(Index de la liste des indicateurs)
for _ in range(k):
    if flg[twn]:
        dst.append(a[twn])
        flg[twn] = False
        twn = a[twn] - 1
    else:
        index = dst.index(a[twn])
        ld = len(dst[:index])
        cyc = len(dst[index:])
        print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
        exit()
print(dst[-1])

ABC167D/AC188ms

n, k = map(int,input().split())
a = list(map(int, input().split()))
dst = [1] #Liste des villes (y compris la première) que j'ai visitées jusqu'à présent
dsts = set(dst) #Ensemble de villes (y compris la première) que j'ai visitées jusqu'à présent
twn = 1 #Destination de transfert de téléporteur
for _ in range(k):
    if a[twn - 1] in dsts: #Si la destination de transfert du téléporteur est dans l'ensemble de villes où vous vous êtes rendu (les transferts à partir de là feront une boucle)
        index = dst.index(a[twn - 1]) #Obtenez l'index de la destination de transfert de téléporteur dans la liste des villes que vous avez effectuées jusqu'à présent
        ld = len(dst[:index]) #Trouvez la longueur avant la boucle et la période de la partie de la boucle
        cyc = len(dst[index:])
        print(dst[(ld - 1) + (k + 1 - ld) % cyc] if (k + 1 - ld) % cyc != 0 else dst[-1])
        exit()
    else: #Si la destination de transfert du téléporteur ne se trouve pas dans l'ensemble de villes où vous vous êtes rendu
        dst.append(a[twn - 1]) #Sinon, ajoutez-le à la liste des villes que vous avez visitées
        dsts.add(a[twn - 1])
        twn = a[twn - 1] #Mettre à jour la destination de transfert du téléporteur
print(dst[-1])

Conclusion Si vous voulez déterminer la présence ou l'absence plusieurs fois dans une boucle, au lieu de rechercher directement la liste cible en utilisant ʻin, utilisez ʻin pour vérifier un ensemble de recherche créé séparément, ou utilisez ʻin` pour les indicateurs. Il est extrêmement rapide de faire une liste et de la rechercher.