¿cuál es el algoritmo para llenar de manera óptima un DVD para grabar

Question

¿Cuál es el algoritmo óptimo para llenar un conjunto de discos Blu-ray dado muchos cientos de gigabytes de activos de diferentes tamaños?

Estoy tratando de consolidar una gran cantidad de viejos CD-ROM, DVD y discos duros pequeños y poner todo en una base de datos indexada por la firma MD5. Una tarea desalentadora sin dudas.

Lo que hago actualmente es ordenar los tamaños de los activos (generalmente tamaños de directorio) en orden descendente, empiezo a insertar los activos más grandes en la lista de relleno omitiendo los que no se ajustan hasta que me quedo sin activos. Funciona de forma casi instantánea, pero no me importaría correr de la noche a la mañana si fuera necesario.

Por lo general, me da un 95% o más de utilización, pero estoy seguro de que hay una manera de usar otras combinaciones para dar una mayor eficiencia. Con elementos enormes como imágenes de disco, puedo obtener una utilización bastante baja con este método primitivo.

Mi idea es tomar todas las combinaciones de los activos tomados, 1 luego 2, luego 3, ... elementos a la vez y mantener un valor en funcionamiento para el conteo de bytes más alto < 25,025,314,816 bytes apuntando a la matriz que suma eso. Cuando llego al punto en el que tengo tantos activos a la vez que ninguna de las combinaciones se ajusta, detengo y uso la matriz apuntada por el contador más alto en funcionamiento.

¿Es este el mejor algoritmo posible?

Hay 2 módulos Perl que parecen estar a la altura de la tarea, Algoritmo-Combinatorio y Combinatorio matemático. ¿Algún consejo sobre cuál es más rápido, más estable, más frío?

Mi esquema consiste en escribir una secuencia de comandos para calcular los tamaños de una gran cantidad de directorios y mostrarme el contenido óptimo de las docenas de discos para grabar.

Y, no quiero simplemente llenar un archivo por archivo, ya que quiero directorios enteros en el mismo disco.

Answer 1

Utilice el algoritmo del problema de optimización "Knapsack".

http://en.wikipedia.org/wiki/Knapsack_problem

1. peso fijan para ser igual al tamaño del archivo
2. Valor seleccionado para que sea igual a "peso"
3. Ejecutar el algoritmo para cada disco posterior a envasar

Puede que no sea la mejor opción (maximizará el factor de relleno del siguiente disco en lugar de minimizar el número total de discos necesarios), pero está bien documentado y es fácil de encontrar. y código de trabajo para el lenguaje de programación de su elección (incluso hojas de cálculo) en la web.

Answer 2

El algoritmo se denomina bin-packing 1d. El algoritmo es muy rápido pero no óptimo. También puede usar un algoritmo de fuerza bruta, pero el espacio de búsqueda es muy grande. Aquí hay un programa con un algoritmo codicioso: http://www.phpclasses.org/package/2027-PHP-Pack-files-without-exceeding-a-given-size-limit.html

Answer 3

Este es un problema NP-completo conocido como bin packing. No existe un algoritmo conocido de tiempo polinomial que lo resuelva de manera óptima. En otras palabras, la solución óptima no se puede encontrar sin intentar básicamente todas las soluciones.

En el lado positivo, una heurística muy simple como "poner la carpeta restante más grande en el primer disco que tiene espacio" garantizará que utilizará menos del doble de discos que el mejor de los casos. (Puede leer más detalles sobre el artículo de Wikipedia del problema).

Answer 4

El método más práctico que he encontrado para llenar eficientemente mis discos Blu-Ray.

Realizo una lista de rutas completas a todos los archivos disponibles para grabar.

Luego, decida (arbitrariamente) cuántos niveles de directorio considerar como un grupo o acepte una opción de línea de comando para él. Esto es para mantener los directorios llenos de elementos similares en un solo blu-ray. También hay una opción STUFF para insertar primero los archivos más grandes y cuando un archivo podría causar un desbordamiento, busque el siguiente más pequeño hasta que se quede sin archivos o espacio.

Haga un hash con cada directorio como clave y tamaño total de los archivos que contiene como datos. También mantenga un hash paralelo con el recuento de archivos por directorio ya que el espacio libre y la sobrecarga del directorio aparentemente se suman y deben tenerse en cuenta.

Elija 22 como el número mágico. Si tiene < = 22 directorios, pruebe todas las combinaciones para encontrar , el más cercano pero no superior a 25.025 GB. Si tiene más de 22, solo use los 22 más grandes. Uso el algoritmo Perl Algorithm :: Combinatorics para encontrar todas las combinaciones. A través de una prueba y error mayormente, determiné que las combinaciones de 21 ítems toman solo unos segundos. 23 elementos requieren muchos minutos, lo que es más largo que mi capacidad de atención. 22 toma alrededor de 35 segundos.

Un directorio de salida también se acepta y verifica para los datos existentes. Hay una opción para mover los archivos (copiar, verificar tamaño y desvincular).

Cada vez que compré un nuevo disco duro, por lo general era el doble de grande que la anterior por lo que sólo sería copiar todos los objetos. Con una Nikon D800E (Extreme!), HDR y Panoramas, finalmente me quedé sin espacio.

Mi proyecto fue único, deshierbe y consolidé 15 años de fotos [principalmente basura], videos, películas, música, etc. Inventoricé aproximadamente una docena de dispositivos de almacenamiento, calculé firmas MD5 y los puse en una base de datos. Elegí un disco como maestro para fotos y otro para video y controlé todo lo demás. ¡Encontré 8 copias de algunas cosas!

Ahora tengo unos 10 TB de espacio libre en el disco !!!

Debajo de la función que hace todo el trabajo real en caso de que alguien esté interesado.

============================================== = ¡Uy! Su respuesta no pudo ser enviada porque:

Your post appears to contain code that is not properly formatted as code 

La estúpida página web mutiló mi código prístino. Lo sentimos :(..