arriver à a=b est susceptible de ne jamais arriver (on est en flottant), et si cela représente des Koctets, l’attribution à 10K près est absurde. Donc < 10 est très précis.
T est la taille de la mémoire totale (T=200000 3ième ligne), mettre Qmax à T lorsque Qmax n’est pas précisé n’est pas si mal. Contrairement au précedent, il faut tout connaitre ici, c’est pour ça que j’aime moins
En effet mais x n’est pas une taille. Pourquoi ne pas plutôt utiliser l’écart entre T et ft(x) comme condition d’arrêt ?
J’ai bien compris mais pourquoi T*ln(T)*n et pas ln(T)*n ?
Pour faire une dichotomie, oui. En fait ma première idée était plutôt de parcourir les segments de ft(x) à partir de x=0. Si on a préalablement ordonné les points {Qmin[i]/P[i], Qmax[i]/P[i]}, cela demande au plus 2*n itérations (nombre maxi de segments).
Alors dans l’ordre, le but est d’avoir f(x)=Q et d’avoir une précision importante sur x. Si la pente est très importante, une petite variation sur f(x)-Q entraine une grosse variation sur x. Donc la technique est de faire l’écart sur x. Comme x est entre a et b, cette précision est b-a. Il suffit donc de s’arrêter dès que
b-a < précision voulue
À chaque étape, b-a est divisé par 2. si il y faut k étapes pour que b-a<precision, c’est que
(b-a)/2^k < delta avec b-a=T-0=T soit k > ln(T/delta)/ln(2)
k est en ln(T). Or chaque étape nécessite n calculs, ça fait un complexité en n.ln(T). J’ai écrit T.ln(T).n… Bon, va savoir pourquoi, sans doute dans ma tête cet algorithme devait être moins bon que le précédent et du coup j’ai discrètement et inconsciemment mis un T…
Bien, il est meilleur surtout si T/g est très grand… Ça me contrarie parce que j’aimais bien l’aspect glouton de l’autre mais bon…
En triant (cout négligeable vu n petit), puis en calculant les f(x) pour les x correspondant, tu te ramène à chercher x sur un segment où f est affine, donc effectivement ça te fait un cout total ne dépendant que de n (cout en n²), un algorithme en 3 étapes hors calcul de f. Ça marche bien mais j’ai la flemme de programmer les 3 étapes 
Ce n’est pas plutôt l’inverse ? Pente forte = petite variation de x → forte variation de ft(x).
Ceci dit, la pente maximum de ft(x) est 1 (si tous les f(i,x) sont en zone linéaire)) donc la marge d’erreur sur ft(x) est inférieure à la marge d’erreur sur x (delta).
Le nombre de segments à examiner dépend de T, c’est pourquoi j’ai hésité à écrire que l’algorithme ne dépendait pas du tout de T.
Ne t’embête pas, je vais le faire. Mais pas en python, je suis trop nul, peut-être en bash ou en C si je galère trop.
Déjà merci pour tes deux scripts.
Oui (j’en aurai dit des conneries ds ce fil) et certes , mais tel un bon automate, j’ai préféré le test universel à celui équivalent dans ce cas particulier…
Procéder par dichotomie était plutôt une bonne idée (à laquelle j’ai honte de n’avoir pas pensé) car cela rend l’algorithme indépendant de la fonction f(x) qui doit seulement être croissante.
#!/usr/bin/python
T=200000
Qmin=[1000,10000,10000,10000,0]
Qmax=[2000,13000,100000000,1000000000,100000000]
P=[1,50,100,100,200]
n=len(Qmin)
Q=[0]*n
Pt=0
for p in P:
Pt=Pt+p
Qt=0
for q in Qmax:
Qt=Qt+q
def f(i,x):
return(min(Qmax[i],max(x*P[i]/Pt,Qmin[i])))
def ft(x):
s=0
for i in range(n):
s=s+f(i,x)
return(s)
# 1
L=([Qmin[i]*Pt/P[i] for i in range(n)]+[Qmax[i]*Pt/P[i] for i in range(n)])
L.sort()
print(L)
# 2
i=0
while(T > ft(L[i])):
i=i+1
# 3
x=(T-ft(L[i-1]))*(L[i]-L[i-1])/(ft(L[i])-ft(L[i-1]))+L[i-1]
Q=[round(f(i,x),0) for i in range(n)]
print(Q)
J’obtiens [1000, 13000, 46500.0, 46500.0, 93000.0], bref ça marche
[correction erreur bête]
Merci. Python a l’air pratique pour faire du calcul, je devrais peut-être m’y mettre…
Ma cible est plutôt du shell ou du C, mais une implémentation en python peut me servir de référence pour comparer les résultats des différents algorithmes et de leurs implémentations.
Je note quand même quelques défauts notamment avec les cas limites :