Savoir & Culture

Salut,
J'ai une liste a=[a_1, ..., a_n] de grandeurs strictement positives. J'effectue un algorithme du type :

a_0 = min(a)
a_v = quelque chose qui dépend plus ou moins de a_0
a_n+1 = a_0 + a_v
supprimer a_0 et a_v de la liste a

bref, le temps le plus grand est (j'imagine) de chercher le minimum de la liste a. je suis pas du tout calé en complexité et je sais pas trop la complexité de mon algorithme, mais j'imagine qu'il est perfectible. j'avais pensé à trier la liste a dès le départ et à insérer a_(n+1) dans la liste tel que a soit toujours croissante, mais je n'ai aucune idée de comment faire ça "efficacement". ou alors vous avez peut être une meilleure idée?
merci

Je comprends rien à ton algo. C'est quoi v ? Quand tu dis "a_0 = machin", tu veux dire que tu rajoutes la valeur machin eb tete de liste (idem pour a_n+1 mais à la fin) ? Le truc que tu as décrit, tu le répètes en boucle jusqu'à ce que la liste soit vide (ou autre condition) ou bien tu l'exécutes une seule fois ?

Je tente une reformulation, corrige moi si j'ai mal compris :

x = min(a)
v = f(x)
a.append(x + a_v)
a.remove(x)
a.remove(a_v)

La complexité est en O(n), a moins que la fonction f ne soit encore plus coûteuse que ça.
Si tu l'exécutes juste une fois, trier a est déjà en O(n log n) donc plus coûteux que ça.
Si tu l'exécutes au moins n fois, ça peut commencer à être optimisable.

Trier a ne t'aidera pas trop a priori. Les listes de python sont en réalité des tableaux et donc insérer l'élément a_n+1 prend déjà un temps O(n). Même avec de vraies listes, c'est la recherche de l'endroit où il faut insérer qui va prendre un temps O(n).

J'ai l'impression que ce qu'il te faudrait c'est des arbres binaires de recherche (arbres AVL, arbres rouge-noir), mais d'après Google ça a pas trop l'air d'exister dans la stdlib python. C'est touffu à coder à la main. T'as vraiment des problèmes de perfs ? T'es sur que ça vient de cet endroit la du code ? Tu n'as pas d'autre solution (par ex, recoder en C ou autre) ?

Le 25 mai 2018 à 16:24:21 Niverolle a écrit :
Je tente une reformulation, corrige moi si j'ai mal compris :

x = min(a)
v = f(x)
a.append(x + a_v)
a.remove(x)
a.remove(a_v)

La complexité est en O(n), a moins que la fonction f ne soit encore plus coûteuse que ça.
Si tu l'exécutes juste une fois, trier a est déjà en O(n log n) donc plus coûteux que ça.
Si tu l'exécutes au moins n fois, ça peut commencer à être optimisable.

Trier a ne t'aidera pas trop a priori. Les listes de python sont en réalité des tableaux et donc insérer l'élément a_n+1 prend déjà un temps O(n). Même avec de vraies listes, c'est la recherche de l'endroit où il faut insérer qui va prendre un temps O(n).

J'ai l'impression que ce qu'il te faudrait c'est des arbres binaires de recherche (arbres AVL, arbres rouge-noir), mais d'après Google ça a pas trop l'air d'exister dans la stdlib python. C'est touffu à coder à la main. T'as vraiment des problèmes de perfs ? T'es sur que ça vient de cet endroit la du code ? Tu n'as pas d'autre solution (par ex, recoder en C ou autre) ?

oui c'est ça qu'il se passe dans mon algo, déso si j'ai pas été explicite!
disons que j'ai par exemple une liste initiale de 20 000 éléments, donc ça me fait environ 20 000 étapes pour l'algo (je continue jusqu'à ce que ma liste soit vide). et la fonction f est vraiment pas compliquée, je regarde dans une liste associée à ton x qui contient que 4 ou 5 éléments généralement donc ça va vite.
pour le reste de mon algo je peux vraiment rien changer, et j'ai pas vraiment le temps d'apprendre un nouveau langage pour faire ça puis bon y'a un outil très sympa et beaucoup utilisé sous python donc changer de langage me posera + de soucis que ça en réglera. et sinon ouais c'est assez lent, disons qu'avec 20k éléments initiaux mon code met environ 2h pour tourner...

et ce qui me fait dire que c'est cette étape qui prend du temps, c'est parce que l'algo met énormément de temps pour faire la première partie, et au moins moitié moins pour la 2e partie (enfin le temps pour faire une boucle décroît au cours du temps, et pas de manière ridicule)

Oui, 20000^2 c'est non négligeable. Je suis toujours pas sûr de ce que fait ton algo exactement.

et la fonction f est vraiment pas compliquée, je regarde dans une liste associée à ton x qui contient que 4 ou 5 éléments généralement donc ça va vite.

et ça, ça te donne directement la valeur a_v, et pas juste l'indice v comme dans ce que j'ai écrit plus haut ?
Tu peux montrer directement le code pertinent au pire ?

En gros t'as besoin des opérations insérer, supprimer et min qui soient toutes en temps log n (ou moins). Des arbres binaires de recherche font l'affaire peut être que tu peux juste trouver une implémentation qui semble legit sur le net et voir si ça accélère ton truc.

le code pertinent fait appel à beaucoup de choses et à des sous programmes donc bon... je vais essayer d'écrire la partie intéressante
faut se dire que je travaille sur un graphe contenant n noeuds. j'appelle L[i] la liste donnant les voisins du noeud i (donc contenant max 5 noeuds on va dire) ; a[i] est juste un poids associé au noeud i

while L not empty:
   a_m = min(a)
   a_M = max(L[a])
   a.append(a_m+a_M)
   L.append([voisins de m et de M sans les compter en double])
   a.remove(a_m)
   L.remove[L[m]]
   a.remove(a_M)
   L.remove[L[M]]

dans l'idée hein
je vais voir sur les arbres de recherche du coup