Script para llenar de manera óptima un CD o DVD

Lleno, por favor. Script para llenar de manera óptima un CD o DVD

“¡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 )

Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

14 comentarios en “Lleno, por favor. Script para llenar de manera óptima un CD o DVD”

  1. Navegando con Google Chrome Google Chrome 26.0.1410.64 en Windows Windows XP

    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?

    1. Navegando con Mozilla Firefox Mozilla Firefox 21.0 en Ubuntu Linux Ubuntu Linux

      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.

        1. Navegando con Mozilla Firefox Mozilla Firefox 21.0 en Ubuntu Linux Ubuntu Linux

          No puedo ver el error que indicas, el enlace no funciona.
          ¿Puedes pegar aquí el texto del error?

          1. Navegando con Mozilla Firefox Mozilla Firefox 21.0 en Ubuntu Linux Ubuntu Linux

            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…

    1. Navegando con Mozilla Firefox Mozilla Firefox 21.0 en Windows Windows XP

      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

  2. Navegando con Google Chrome Google Chrome 26.0.1410.64 en Windows Windows XP

    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?

    1. Navegando con Mozilla Firefox Mozilla Firefox 20.0 en Windows Windows XP

      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”

  3. Navegando con Google Chrome Google Chrome 26.0.1410.64 en Windows Windows XP

    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.

    1. Navegando con Mozilla Firefox Mozilla Firefox 21.0 en Ubuntu Linux Ubuntu Linux

      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.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Antes de enviar el formulario: