Ce n'est peut-être pas une question spécifique à Python, mais la voici:
J'essaie de résoudre un problème numérique du type dans lequel je dois montrer quels éléments d'une liste a = [a_1, a_2, a_3, ...] ont une propriété X. Cependant, quand je le prouve pour certains a_n, je le prouverai parfois aussi pour d'autres éléments a_m de la liste. Donc, pour accélérer l'algorithme, je ne veux pas refaire le test de ces éléments.
Maintenant, je peux créer une liste has_property_X et, tout en itérant sur a, tester si chaque élément est dans la liste (et remplir cette liste après avoir testé chaque élément). Cependant, je dois encore passer en revue chaque élément pour ce faire.
Existe-t-il une approche plus intelligente?
3 Réponses :
Une chose que vous pourriez faire est de remplacer votre liste has_property_X par une table de recherche (dictionnaire). La table de recherche gardera une trace de chaque a_i . La clé sera a_i et la valeur sera l'une des
Aucun , si l'élément n'a pas encore été traité True , si l'élément a la propriété False , si l'élément ne possède pas la propriété. Cela vous donne la complexité O (1) pour vérifier si un élément a déjà été traité. Cela ressemblerait à quelque chose comme ceci:
a = [1, 2, 3, 4, 5] # your list `a`
lookup_table = {a_i: None for a_i in a}
for element in a:
if lookup_table[element] is None:
# determine if element has the property
element_has_property = False
# if, in the process, you determine that another element `a_m` also has the property,
# then set lookup_table[a_m] = True
lookup_table[element] = element_has_property
# assemble list of elements which have the target property
has_property_x = [a_i for a_i in lookup_table if lookup_table[a_i] ]
Je pense que votre approche est correcte, en ce sens que le coût du temps intervient dans le calcul de chaque a_i , et non dans la boucle des listes. Si vous bouclez sur la liste a avec une liste d'arrêt has_x_property (ou peut-être un ensemble si les valeurs répétées n'ont pas d'importance)
for elem in a:
if elem not in has_property_x:
algoritm(elem)
update(has_property_x)
p>
En y réfléchissant un peu plus longtemps, j'ai pensé à l'approche suivante:
a = [a_1,a_2,a_3...] #the list
has_property_X = []
while a!=[]:
#algorithm that tests and removes a[0] and appends to has_property_X the elements that
#do and removes them from a as well
Je ne sais pas à quel point cette approche est bonne (disons, comparée à celle de zachdj). Cependant, il répond à la question, et je ne vois pas pourquoi cela fera pire ...
Est-ce que m est garanti inférieur à n ? (ou est-ce que m est garanti supérieur à n ?)
@zachdj si m est toujours inférieur à n, alors la "preuve bonus" est superflue, car
a_ma déjà été prouvée avant d'atteindrea_n. Le gain d'efficacité n'est donc que dans le cas où m> n. Il pourrait cependant y avoir un certain avantage à trier la liste d'une manière ou d'une autre pour que les éléments susceptibles de produire de nombreuses "preuves bonus" apparaissent au début de la liste.@ kaya3 l'astuce de tri est ce que j'avais en tête. Si m est inférieur à n , alors OP peut améliorer l'efficacité en itérant sur la liste en sens inverse.