Répartir des fichiers

Bertrand Bine wrote:

Un ensemble de fichiers à répartir sur des supports d'une capacité
limitée et standardisée ?

L'exemple type est le remplissage d'un nombre calculé de CD d'une
capacité de 700 Mb avec des fichiers dont la taille est aléatoire.

L'un de vous aurait il lu, vu ou réalisé un algorithme de répartition
optimale pour ce genre de problèmatique.
La répartition optimale est très difficile à atteindre (NP-complet)

http://www.bibmath.net/dico/index.php3?action¯fiche&quoi=./s/sacados.html
Comme beaucoup de pb d'optimisation des ressources.

Si la taille de tes fichiers est vraiement aléatoire, la solution de
commencer par les plus gros est, je crois quasi optimale, dans le cas
contraire, c'est aussi très correct. En gros, c'est comme quand tu range
un tas de bois, si tu as suffisememnt de petits morceaux, tu arriveras
toujours à boucher les trous.
Plutôt que te fatiguer, pourquoi tu ne coupes pas tes fichiers ou ca va
bien. Tu peux même ajouter un utilitaire de compression/decompression,
découpe. Si tes fichiers font moins de 700Mo, tu as auras au plus de
deux fichiers par cd de coupé par cd.
Comme très souvent, pour résoudre un problème, il faut préciser le
contexte. Que veux tu faire de tes cd une fois que les données seront
dedans? Pourquoi ne pas utiliser des dvd? Si c'est pour éviter à un
utilisateur de faire le disk jockey, tu as tout interêt à regrouper tes
fichiers par thème commun. Si c'est pour optimiser le stockage: une
seule solution: concaténer tous tes fichiers, les compresser et découper
le résultat.

Si vous connaissez des liens, je suis preneur...
le forum fr.comp.algorithme me parait tout désigné pour ce pb,

un petit coup de google dessus pourrait t'aider

D'avance, merci.

Bertrand Bine.

Xavier Combelle wrote:

Bertrand Bine wrote:

Un ensemble de fichiers à répartir sur des supports d'une capacité
limitée et standardisée ?

L'exemple type est le remplissage d'un nombre calculé de CD d'une
capacité de 700 Mb avec des fichiers dont la taille est aléatoire.

L'un de vous aurait il lu, vu ou réalisé un algorithme de répartition
optimale pour ce genre de problèmatique.

La répartition optimale est très difficile à atteindre (NP-complet)
http://www.bibmath.net/dico/index.php3?action¯fiche&quoi=./s/sacados.html
Comme beaucoup de pb d'optimisation des ressources.

Si la taille de tes fichiers est vraiement aléatoire, la solution de
commencer par les plus gros est, je crois quasi optimale, dans le cas
contraire, c'est aussi très correct. En gros, c'est comme quand tu range
un tas de bois, si tu as suffisememnt de petits morceaux, tu arriveras
toujours à boucher les trous.

D'accord sur le principe, les solutions cependant sont multiples...

Plutôt que te fatiguer, pourquoi tu ne coupes pas tes fichiers ou ca va
bien. Tu peux même ajouter un utilitaire de compression/decompression,
découpe. Si tes fichiers font moins de 700Mo, tu as auras au plus de
deux fichiers par cd de coupé par cd.

Certes, mais l'idée est de conserver chaque fichier entier

Comme très souvent, pour résoudre un problème, il faut préciser le
contexte. Que veux tu faire de tes cd une fois que les données seront
dedans? Pourquoi ne pas utiliser des dvd? Si c'est pour éviter à un
utilisateur de faire le disk jockey, tu as tout interêt à regrouper tes
fichiers par thème commun. Si c'est pour optimiser le stockage: une
seule solution: concaténer tous tes fichiers, les compresser et découper
le résultat.

Il s'agit bien d'optimiser le stockage sur les supports, en remplissant
N-1 support au maximum de leur capacité.
Le support N recevant seulement le reliquat.

Si vous connaissez des liens, je suis preneur...

le forum fr.comp.algorithme me parait tout désigné pour ce pb,
un petit coup de google dessus pourrait t'aider

Ok c'est une voie que je m'en vais de ce pas explorer.

D'avance, merci.

Bertrand Bine.

Si certains d'entre vous sont intéressés, voici un script commis sur la
base d'un algorithme que j'ai imaginé.


Malheureusement je ne suis pas plus performant que l'algorithme
"glouton" décrit par Johanne Cohen :

La répartition de la liste [4,3,3,2,2,2] dans des "clusters" de
dimension =8 n'est pas parfaitement optimisée...


Le programme n'est peut être pas optimisé, et je vous serai
reconnaissant de me transmettre vos idées le cas échéant.

En particulier, je ne suis pas très satisfait du "break" en ligne 24 que
j'ai écrit faute de trouver une meilleure solution (manque de rigueur
sans aucun doute).


Bertrand Bine

from string import *

def somme(a):
if len(a)==0:return 0
else:return reduce(lambda a,b:a+b,a)

P=[]
S=[]
h,i,j=0,0,0

c=eval(raw_input("Capacité unitaire "))
N=eval(raw_input("Liste des dimensions"))
N.sort()
N.reverse()
print N
while len(N)>0:
while h<len(N):
if N[h]>c:
h+=1
else:
i=h
P.append([])
if len(P)>1:
if len(P[-2])<1:break
while i<len(N):
if somme(P[j])+N[i]==c:
P[j].append(N[i])
j+=1
h+=1
i=len(N)
elif somme(P[j])+N[i]>c:
i+=1
elif somme(P[j])+N[i]<c:
P[j].append(N[i])
i+=1
if i==len(N):
j+=1
h+=1
P.sort(lambda a,b:somme(b)-somme(a))
S.append(P[0])
for i in P[0]:
N.remove(i)
P=[]
h,i,j=0,0,0
perte=0
for i in S:
perte+=c-somme(i)
print "Capacité : ",c
print "Proposition : "
for i in S:
print i,"(occ:",somme(i),", lib:",c-somme(i),"tx
rempl.:",round(somme(i)/float(c),3)*100,"%)"
print "Perte totale: ",perte
fin=raw_input("Appuyez sur [Return] pour quitter")

Je crois que le script ci dessous réparti mieux que le précédent, mais
il n'est pas mieux optimisé :-(

from string import *

def somme(a):
if len(a)==0:return 0
else:return reduce(lambda a,b:a+b,a)

P=[[],]
S=[]
h,i,j=0,0,0

c=eval(raw_input("Capacité unitaire "))
N=eval(raw_input("Liste des dimensions"))
N.sort()
N.reverse()
print N
while len(N)>0:
while h<len(N):
if N[h]>c:
h+=1
else:
i=h
P.append([])
while i<len(N):
if somme(P[j])+N[i]==c:
P[j].append(N[i])
P.append([])
j+=1
h+=1
i=h
elif somme(P[j])+N[i]>c:
i+=1
if i==len(N):
P.append([])
j+=1
h+=1
i=h
elif somme(P[j])+N[i]<c:
P[j].append(N[i])
i+=1
if i==len(N):
P.append([])
j+=1
h+=1
i=h
P.sort(lambda a,b:somme(b)-somme(a))
S.append(P[0])
for i in P[0]:
N.remove(i)
P=[]
h,i,j=0,0,0
perte=0
for i in S:
perte+=c-somme(i)
print "Capacité : ",c
print "Proposition : "
for i in S:
print i,"(occ:",somme(i),", lib:",c-somme(i),"tx
rempl.:",round(somme(i)/float(c),3)*100,"%)"
print "Perte totale: ",perte
fin=raw_input("Appuyez sur [Return] pour quitter")