«¡Qué desperdicio!», pensamos cuando hemos acabado de grabar un CD o un DVD y no hemos podido aprovechar toda la capacidad de estos medios de almacenamiento.
Los usamos para guardar todo tipo de archivos: fotos, textos, copias de seguridad, películas… Yo lo uso, casi en exclusiva, para estas últimas —recodificadas, previamente, con recode ;-)—, así, en un DVD+R DL, puedo guardar entre diez y once películas.
Pensé en idear un algoritmo que me calculara cómo llenar de manera óptima un DVD, eligiendo de un grupo de archivos aquellos cuya suma de tamaños se acercara más a la capacidad del disco.
Pasó el tiempo y no era capaz de resolver el problema sin recurrir a la fuerza bruta. Este problema no es ni nuevo ni único. De forma genérica, se trata de llenar un contenedor de capacidad limitada con el máximo número de objetos de tamaño «x». Buscando por la red, encontré una solución muy buena de Thanassis Tsiodras que usa programación dinámica.
He escrito un script en python, basado en su algoritmo, que consigue el objetivo en dos segundos. Sólo utiliza librerías estándar por lo que no hay que instalar nada (sólo python, si no lo tienes instalado ya).
Ejecutando el comando siguiente puedes ver cuál es su sintaxis y para qué sirve cada una de las opciones:
fillmedia.py -h
La salida es esta:
fillmedia.py [-h|--help]|[-v|--version]|[-t|--types]|-i source.dir|--indir=source.dir [-o dest.dir|--outdir=dest.dir] -m media.type|--media=media.type [-u unit|--unit=unit][-s scale|--scale=scale][-l limit|--limit=limit][-d|--dry][-r log.file|--reg=log.file] -h | --help Show this help and exit -v | --version Show author & version and exit -t | --types Show media types & units allowed and exit -i source.dir | --indir=source.dir Source directory -o dest.dir | --outdir=dest.dir Destination directory (default = source.dir) -m media | --media=media Media type to fill -u unit | --unit=unit Unit of measurement (default = 'MB') -s scale | --scale=scale Unit scale (default = 1.0) -l limit | --limit limit Percent threshold to stop processing (default = 1) -d | --dry Do nothing on disk, dry-run -r log.file | --reg=log.file Redirects output to log.file
Puedes ver los tipos de medios y las unidades de capacidad que admite el script, ejecutando:
fillmedia.py -t
Media types allowed: ---------------------- cd-650: 681.98 MB cd-700: 737.28 MB cd-800: 829.44 MB cd-900: 912.38 MB dvd+r-sl: 4700.37 MB dvd-r-sl: 4707.32 MB dvd-r-dl: 8543.67 MB dvd+r-dl: 8547.99 MB Units allowed: ---------------- kB: 1000 Bytes KiB: 1024 Bytes MB: 1000000 Bytes MiB: 1048576 Bytes
Todas las opciones tienen una forma corta (como -v) y una forma, equivalente, larga (–version). Se puede usar una forma u otra indistintamente y mezclar unas con otras al gusto. Las únicas opciones obligatorias son: especificar el directorio origen (opción -i)(donde tenemos los archivos que quieres grabar en el CD o DVD) y el tipo de medio (opción -m) que usarás para grabarlos: CD o DVD de diferentes capacidades. Las demás son opcionales y paso a explicarlas:
-o dest.dir
Indica el directorio de destino, por defecto, si no se usa esta opción, se tomará el directorio origen también como destino. En realidad, los archivos seleccionados por el script se guardarán en directorios creados dentro del que especifiquemos como destino, nombrándose, consecutivamente, disk1, disk2…, diskn.
El script, partiendo de la lista de archivos que haya en el directorio origen (no tiene en cuenta los subdirectorios que pueda haber en él), intentará llenar, de forma óptima, tantos medios como sea posible. En cada directorio «diskx» moverá los archivos desde el origen para que luego sólo tengamos que seleccionarlos con el programa de grabación elegido y quemar el CD o DVD con ellos.
-u unit
Por defecto, la unidad de medida es el Megabyte (MB) = 106 bytes, pero puedes modificarla con esta opción.
-s scale
La escala por defecto es 1.0 y es ajustable con este parámetro. Por ejemplo, si quieres que el script haga los cálculos usando como unidad 20 KiB, debes usar KiB para la unidad y 20 para la escala, así:
fillmedia.py -u KiB -s 20 -i /home/usuario/directorio-con-archivos-a-grabar -m dvd-r-sl
-l limit
Esta opción indica el porcentaje máximo de la capacidad del disco que permitimos que se desperdicie, por defecto es el 1% (sólo hay que indicar un número, mayor o igual que 0 y menor o igual a 100, sin añadir el «%»). Si se llega a ese límite el proceso se para.
-r log.file
Puedes especificar el nombre de un archivo que guardará la salida de la ejecución del script, en vez de hacerlo por pantalla.
Cuando se trabaja con archivos grandes, del orden de megabytes, los parámetros por defecto funcionan muy bien y el script hace su trabajo muy rápido. A razón de dos segundos por disco, más o menos. Cambiando las unidades a, por ejemplo, 20 KiB, el tiempo por disco crece hasta el minuto y medio aproximadamente. Con archivos grandes el beneficio que se obtiene es casi nulo, por lo que es mejor usar los parámetros por defecto. Pero si se trata de archivos pequeños, la cosa cambia. Usando unidades más pequeñas, el aprovechamiento del espacio del disco es significativamente mejor (y si son múltiplos del tamaño de sector —2 KiB—, aun mejor).
He adaptado el algoritmo ideado por Thanassis Tsiodras a mis necesidades, para los detalles técnicos te invito a que leas su artículo.
Creo que he mejorado algunas cosas que no me acababan de gustar en el original y le he añadido funcionalidad.
Espero que te sea tan útil como lo está siendo para mi.
Ejemplo de ejecución:
fillmedia.py -i /media/media/peliculas/vistas/ -m dvd+r-dl -d Dry run. Changes will not be written on disk. Starting... Unit selected: 1.00 MB Threshold: 1.00% Getting files... Done! Disk number: 1 -------------------- Extracting file sizes... Done! Processing: 13 files 100.00% complete... Objective: 8547991552.00 Bytes Attainable: 8547000000.00 Bytes Real size: 8541320796.00 Bytes Wasted space: 0.08% Disk number: 1 contains: 11 files Moving files to: /media/media/peliculas/vistas/disk1 /media/media/peliculas/vistas/peli-kr.avi /media/media/peliculas/vistas/peli-iq.avi /media/media/peliculas/vistas/peli-xc.avi /media/media/peliculas/vistas/peli-jw.avi /media/media/peliculas/vistas/peli-8q.avi /media/media/peliculas/vistas/peli-9a.avi /media/media/peliculas/vistas/peli-07.avi /media/media/peliculas/vistas/peli-oa.avi /media/media/peliculas/vistas/peli-le.avi /media/media/peliculas/vistas/peli-qk.avi /media/media/peliculas/vistas/peli-dh.avi Disk number: 2 -------------------- Extracting file sizes... Done! Processing: 2 files 100.00% complete... Objective: 8547991552.00 Bytes Attainable: 2038000000.00 Bytes Real size: 2037223888.00 Bytes Wasted space: 76.17% Threshold reached. Total efficiency: 99.92% Elapsed time: 0h 0m 2s 74ms
Esta es la función que hace casi todo el trabajo (tienes el script completo aquí: fillmedia.py):
def do_fit():
"""Calculate best fit of media selected"""
print "Starting..."
print "Unit selected: {0:.2f} {1:s}".format(efunit / unit,unitname)
print "Threshold: {0:3.2f}%".format(threshold)
print "Getting files...",
# files to be processed
listoffiles = []
for filename in os.listdir(sourcedir):
# file full path
filename = os.path.join(sourcedir,filename)
if os.path.isfile(filename):
# file real size in bytes
realfilesize = os.path.getsize(filename)
# file size depends on sector size = 2 KiB
filesize = int(round(realfilesize/2048+0.5)*2048) + 1024 # file system entry size added
# working file size rounded up
filesize = int(round(filesize/efunit+0.5))
listoffiles.append([filename,filesize,realfilesize])
print "Done!"
mediasize = int(size/efunit)
disknumber = 0
efficiency = 0
useddisks = 0
# Process files
while len(listoffiles) > 0:
disknumber += 1
print
print "Disk number: {0:n}".format(disknumber)
print "-"*20
print "Extracting file sizes...",
# isolate working file sizes
listofsizes = [x[1] for x in listoffiles]
numberoffiles = len(listofsizes)-1
print "Done!"
print "Processing: {0:n} files".format(numberoffiles+1)
optimalresult = {}
laststep = {}
for containersize in xrange(0, mediasize+1): # containersize takes values 0 .. mediasize
if not logging:
sys.stdout.write("{0:3.2f}% complete...".format(containersize*100.0/mediasize)+' '*30+'\r')
sys.stdout.flush()
for idx,filesize in enumerate(listofsizes):
cellcurrent = (containersize, idx)
cellontheleftofcurrent = (containersize, idx-1)
# if file doesn't fit into container
if containersize laststep[cellcurrent] = laststep.get(cellontheleftofcurrent,0)
else:
# If I use file of column "idx", then the remaining space is...
remainingspace = containersize - filesize
# ...and for that remaining space, the optimal result using the first idx-1 columns was:
optimalresultofremainingspace = optimalresult.get((remainingspace, idx-1),0)
if optimalresultofremainingspace + filesize > optimalresult.get(cellontheleftofcurrent,0):
# we improved the best result, using the column "idx"!
optimalresult[cellcurrent] = optimalresultofremainingspace + filesize
laststep[cellcurrent] = filesize
else:
# no improvement...
optimalresult[cellcurrent] = optimalresult.get(cellontheleftofcurrent,0)
laststep[cellcurrent] = laststep.get(cellontheleftofcurrent,0)
else:
print
finalchosenlist = []
total = optimalresult[(mediasize, numberoffiles)]
attainable = total * efunit
print "Objective: {0:.2f} Bytes".format(size)
print "Attainable: {0:.2f} Bytes".format(attainable)
if int(total) == 0:
print "No file fits on media, aborting..."
break
realsize = 0
fileschoosed = 0
# walk the build path in reverse order to get the files involved in the solution
while total>0:
lastfilesize = laststep[(total, numberoffiles)]
if lastfilesize != 0:
for fileitem in listoffiles:
# fileitem[0] = full path filename
# fileitem[1] = working file size
# fileitem[2] = real file size in bytes
# search lastfilesize
if fileitem[1] == lastfilesize:
# found! Add it
finalchosenlist.append(fileitem[0])
fileschoosed += 1
realsize += fileitem[2]
# remove the file from the list of files
listoffiles.remove(fileitem)
# stop searching
break
else:
assert(False) # we should have found the file
# total now points to next step backwards
total -= lastfilesize
# calculate percent real wasted space on media
wasted = 100.0 - (realsize * 100.0 / size)
print "Real size: {0:.2f} Bytes".format(realsize)
print "Wasted space: {0:3.2f}%".format(wasted)
print
if wasted > threshold:
print "Threshold reached."
break
efficiency += wasted
print "Disk number: {0:n} contains: {1:n} files".format(disknumber,fileschoosed)
print "Moving files to:",
try:
diskdir = os.path.join(destdir,'disk'+str(disknumber))
if not dry:
os.mkdir(diskdir)
except:
print "Error! Can't create: {0:s}".format(diskdir)
print diskdir
print
for final in finalchosenlist:
if not dry:
try:
shutil.move(final, diskdir)
except:
print "Error! Can't move: {0:s}".format(final)
continue
print final
useddisks += 1
else:
print "No more files left"
print
try:
print "Total efficiency: {0:3.2f}%".format(100.0 - (efficiency / useddisks))
except:
print "No disks generated!"
print
return
( Nota: el script está en inglés para dármelas de internacional :-P )
hola, me interesa esto, pero me podrias ayudar con un ejemplo de 0 ya que no se como se usa pithon y como se usa el script?
Hola, Eric.
Si usas Windows, debes descargar el instalador de Python desde aquí:
http://www.python.org/ftp/python/2.7.4/python-2.7.4.msi
Descarga luego mi script, guárdalo en la carpeta que quieras y renómbralo como fillmedia.py
Abre una ventana de «simbolo del sistema» (que está en Inicio -> Accesorios) y ejecuta el script así:
c:\Python27\python.exe fillmedia.py -h
Este comando te sacará la ayuda, tal como explico en el post.
Un ejemplo:
Supongamos que los archivos que quieres pasar a un DVD+R los tienes en la carpeta «C:\Mis archivos» y que el script está en «C:\script».
Debes ejecutar el comando:
cd C:\script
para situarte donde está el script y luego:
c:\Python27\python.exe fillmedia.py -i «C:\Mis archivos» -m dvd+r-sl
En el comando anterior supongo que python lo has instalado en «C:\Python27», si no es así, cambia la ruta por la que sea correcta.
Consulta este post para el resto de parámetros.
Si tienes alguna duda o te sale algún error, dímelo.
Saludos.
hola , gracias por la respuesta, pero instale el programa, y al tratar de seguir los pasos me sale este error https://mega.co.nz/#!Q01inSqS!OGyh3GxOC3qWT5tV7k1wpjif0l138z9MzxbMBfEzXjI , lo que pasa es que tengo instalado el python en «D» y mis archivos para bajar en una carpeta tambien en D llamada «descargas»
No puedo ver el error que indicas, el enlace no funciona.
¿Puedes pegar aquí el texto del error?
https://docs.google.com/file/d/0BwrMH7epU2NsNjkweER3dUlabmM/edit?usp=sharing
Tampoco puedo acceder, me tienes que dar permiso.
disculpa..
https://docs.google.com/file/d/0BwrMH7epU2NsNjkweER3dUlabmM/edit?usp=sharing
El problema es que has abierto la consola de Python y NO el simbolo de sistema.
Tienes que abrir el símbolo de sistema desde Inicio -> Accesorios -> Simbolo de sistema o también: Inicio -> Ejecutar -> cmd
Después, sigue los pasos…
he tratado de hacerlo en simbolo de sistema, pero me disculparas nuevamente por mi desconocimiento de DOS , pero me sale este error
https://docs.google.com/file/d/0BwrMH7epU2NsOC0xQ1FUN1l5c0k/edit?usp=sharing
otra consulta cuando apreto el link del script de tu pagina se me abre otra ventana y me da la opcion de guardarlo en .txt es decir como archivo de texto, en todo caso como se descarga y guarda con que extension?
Cuando pinchas en el enlace del script, se abre en otra ventana. Usa la opción Archivo -> Guardar y grábalo en la carpeta que quieras pero renombrándolo como «fillmedia.py»
El problema es que debes estar en la carpeta donde guardaste el script.
Si lo has guardado en D:\script (por ejemplo), lo primero que debes hacer después de abrir la ventana de simbolo de sistema es:
cd D:\script
verás que estás en la carpeta correcta porque la línea de comandos te muestra donde estás:
D:\script>
Ejecuta ahora el comando:
D:\Python27\python.exe fillmedia.py -h
una consulta mas, logre que hiciera el proceso… pero ahora no se cuales son los archivos seleccionados como hago para ver lo que ha hecho , porque no me visualiza lo que contiene el «disk 1 … por ejemplo», gracias por contestar mis consultas.
Si te fijas en el ejemplo de ejecución en este post, verás que el script te lista los archivos que ha movido a las carpetas disk1, disk2, etc…
Si miras dentro de la carpeta disk1 (que te debe haber creado), ahí tienes los archivos que debes copiar al medio que hayas elegido en el script (un DVD, CD, etc.). Si no te ha creado la carpeta disk1, puede ser porque con los archivos que tienes no se llena el disco elegido (eso también te lo habrá dicho). Está todo explicado en el post.