Je cherche à écrire un algorithme pas trop compliqué (réalisable en script shell) dont le but est de calculer N quantités Q[i] dont la somme est égale à une quantité totale Qt.
Chaque quantité Q[i] est encadrée par un minimum Min[i] strictement positif et un maximum Max[i] strictement supérieur au minimum et qui peut être infini.
Chaque quantité Q[i] est aussi associée à un poids P[i] strictement positif.
Le rapport de deux quantités Q[i]/Q[j] qui ne sont pas limitées par leur minimum ni leur maximum doit être égal au rapport de leurs poids respectifs P[i]/P[j].
Autrement dit approximativement, chaque quantité doit être proportionnelle à son poids sauf si cette valeur est inférieure à son mimimum ou supérieure à son maximum.
Merci pour vos idées et suggestions car je sèche, toutes mes approches finissent en usines à gaz inextricables.
Edit: application pratique (certains l’auront deviné) : partitionner un disque.
6. HOW THE ACTUAL PARTITION SIZES ARE COMPUTED
----------------------------------------------
Suppose we have to create N partitions and min[i], max[i] and
priority[i] are the minimal size, the maximal size and the priority of
the partition #i as described in section 1.
Let free_space be the size of the free space to partition.
Then do the following:
for(i=1;i<=N;i++) {
factor[i] = priority[i] - min[i];
}
ready = FALSE;
while (! ready) {
minsum = min[1] + min[2] + ... + min[N];
factsum = factor[1] + factor[2] + ... + factor[N];
ready = TRUE;
for(i=1;i<=N;i++) {
x = min[i] + (free_space - minsum) * factor[i] / factsum;
if (x > max[i])
x = max[i];
if (x != min[i]) {
ready = FALSE;
min[i] = x;
}
}
}
Then min[i] will be the size of partition #i.
Oui, j’ai même étudié le script lib/recipes.sh. Mais comme écrit plus haut, il ne fait pas exactement ce que je recherche et ça fait une grosse différence.
Hélas ce n’est pas si simple sinon j’aurais déjà résolu le problème… L’application du minimum à une quantité peut impacter l’application du maximum d’une autre quantité et vice versa.
Oui c’est normal, c’est un algorithme itératif. Mais ca s’adapte, car pour ce qui est du preseed, je peux te dire que ça marche parfaitement bien, je l’utilise et j’ai fait pas loin de 1000 installation en 2 ans avec des résultat correspondants aux attendus.
en fait ce que tu veux n’est pas clair.
Si on considère des partitions Qi qui doit etre comprise entre Min(i) et Max(i), et dont somme(Qi)<=Qt, cela implique que Somme(Min(i))<=somme(Qi)<=somme(max(i)<=Qt>
l’algorithme que j’ai donne est lui capable de prendre en compte le fait la possibilité que somme(Max(i)>=Qt mais la somme des Min(i)<=Qt dans tous les cas
Tu as oublié de prendre en compte les contraintes de minimum et maximum.
Qu’est-ce qui n’est pas clair exactement ?
Non, ça implique que Somme(Min[i]) <= somme(Q[i]) = Qt
Il n’y a aucune relation entre Qt et les Max[i].
Si tu parles de l’algorithme de partman-auto, il applique le poids P[i] à la différence (Q[i] - Min[i]) et non à Q[i]. Ça simplifie le calcul mais les tailles résultantes ne sont pas exactement proportionnelles à leurs poids. Peut-être qu’il fait très bien ce qu’il est censé faire mais il ne fait pas (ou très approximativement) ce que je veux, merci d’arrêter d’essayer de me le vendre.
ce que tu n’a pas compris c’est que la taille n’est pas resultant du poids. le poids determine la priorité d’une partition a etre de la taille donnée en max si celui ci est inférieur à la taille du disque, ou bien à lui donner la préseance si le max est supérieur au disque.
Qi est un résultat pas une valeur que tu fixe, ou alors considère qu’au départ, Qi=Min(i).
personnellement j’ai fait mes calcul pour partman pour travailler avec des pourcentages plutot que des valeurs.
et ca marche. mes partitions gardent toutes les mêmes proportion quelque soit la taille du disque en ayant au départ défini ma valeur Qt
J’en ai bien conscience.
Je voulais juste montrer que les contraintes hors min/max imposent une valeur et donc que la prise en compte de la contrainte min/max n’est pas possible.
Et donc que probablement je n’avais pas bien compris les contraintes.
En supposant que j’ai plus ou moins bien compris :
0. EnsI={1…N} , Qt0=Qt
tu calcules les q[i] avec ma formule pour I dans EnsI
MIN
2a. tu crées l’ensemble EnsMin des i tels que qi<min[i]
2b pour i dans EnsMin, qi= min[i]
MAX
3a. tu crée l’ensemble EnsMax des i tels que qi>max[i]
3b. pour i dans EnsMax, qi= max[i]
tu recalcules le nouveau EnsI=EnsI-EnsMin-EnsMax , le nouveau QT et tu reprends 1,2,3,4
Un exemple simple avec deux partitions avec des poids identiques.
Partition 1 : min=2G maxi=20G poids=50
Partition 2 : min=5G maxi=infini poids=50
Le résultat de mes spécifications est :
Pour un disque de taille comprise entre 7G et 10G :
Partition 1 = taille disque - 5G
Partition 2 = 5G
Pour un disque de taille comprise entre 10G et 40G :
Partition 1 = taille disque * 0,5
Partition 2 = taille disque * 0,5
Pour un disque de taille supérieure à 40G :
Partition 1 = 20 G
Partition 2 = taille disque - 20G
Le résultat de l’algorithme de partman-auto est :
Pour un disque de taille comprise entre 7G et 43G :
Partition 1 = 2G + (taille disque - 7G) * 0,5
Partition 2 = 5G + (taille disque - 7G) * 0,5
Pour un disque de taille supérieure à 43G :
Partition 1 = 20 G
Partition 2 = taille disque - 20G
Bien que les deux partitions aient des poids identiques, il y a un écart de 3 Go entre elles pour les tailles de disque comprises entre 10G et 40G (où elles ne sont limitées ni par leurs minimums ni par leur maximums) avec l’algorithme de partman-auto, alors qu’elles sont égales avec mes spécifications.
Tu es en train de m’expliquer que je n’ai pas compris mes propres spécifications ? C’est plutôt toi qui n’as pas compris, parce que ce que tu décris ne correspond pas du tout à mes spécifications. C’est moi qui décide à quoi sert le poids.
C’est faux, voir l’exemple ci-dessus.
Absurde. Qt, c’est la taille du disque. Tu ne peux pas en même temps la fixer et dire quelle qu’elle soit.
Si car il y a une priorité entre les contraintes. Les contraintes min et max sont prioritaires sur les contraintes de poids.
[Edit] J’ai étudié ton algorithme. Si j’ai bien compris, l’entrée dans EnsMin ou EnsMax est définitive. Or cela ne doit pas forcément être le cas :
Si une quantité entre dans EnsMin, cela diminue le total disponible pour les autres quantités, donc une autre quantité qui était dans EnsMax pourrait en sortir.
Réciproquement si une quantité entre dans EnsMax, cela augmente le total disponible pour les autres quantités, donc une autre quantité qui était dans EnsMin pourrait en sortir.
class partition(object):
def __init__(self,MIN=2,MAX=20,POIDS=0.5):
self._trouvee=False
self._MIN=MIN
self._MAX=MAX
self._POIDS=POIDS
pass
p1=partition(MIN=2,MAX=20,POIDS=0.5)
p2=partition(MIN=5,MAX=1E100,POIDS=0.5)
P=[p1,p2]
N=len(P)
Qt0=50
EnsI=[i for i in range(N) if P[i]._trouvee==False]
MINMAX=True
while len(EnsI)!=0 and MINMAX==True:
print('##'*5)
print("EnsI=",EnsI)
no=no-1
Qt=Qt0-sum([P[i]._q for i in range(N) if P[i]._trouvee==True])
print("Qt=",Qt)
PoidsRestant=sum([P[i]._POIDS for i in range(N) if P[i]._trouvee==False])
print("PoidsRestant=",PoidsRestant)
MINMAX=False
for i in EnsI:
P[i]._q=Qt*P[i]._POIDS/PoidsRestant
print("P["+str(i)+"]._q=",P[i]._q)
if P[i]._q < P[i]._MIN:
P[i]._q = P[i]._MIN
P[i]._trouvee=True
MINMAX=True
if P[i]._q > P[i]._MAX:
P[i]._q = P[i]._MAX
P[i]._trouvee=True
MINMAX=True
print("P["+str(i)+"]._q=",P[i]._q)
EnsI=[i for i in range(N) if P[i]._trouvee==False]
print("# "*20)
for i in range(N):
print("P["+str(i)+"]._q=",P[i]._q)
