qual è l'algoritmo per riempire in modo ottimale un dvd per la masterizzazione

Question

Qual è l'algoritmo ottimale per riempire un set di dischi Blu-ray dato molte centinaia di gigabyte di risorse di varie dimensioni?

Sto cercando di consolidare un gran numero di vecchi CD-ROM, DVD e piccoli dischi rigidi e di mettere tutto in un database indicizzato dalla firma MD5. Un compito scoraggiante di sicuro.

Quello che faccio attualmente è ordinare le dimensioni delle risorse (di solito le dimensioni delle directory) in ordine decrescente, iniziare a inserire le risorse più grandi nell'elenco di riempimento saltando quelle che non si adattano finché non esaurisco le risorse. Funziona quasi istantaneamente, ma non mi dispiacerebbe correre di notte se necessario una volta.

Di solito mi dà il 95% o più di utilizzo, ma sono sicuro che c'è un modo di usare altre combinazioni per dare una maggiore efficienza. Con oggetti enormi come le immagini disco, posso ottenere un utilizzo piuttosto basso con questo metodo primitivo.

Il mio pensiero è di prendere tutte le combinazioni delle risorse prese, 1 quindi 2, poi 3, ... elementi alla volta e mantenere un valore corrente per il conteggio di byte più elevato < 25,025,314,816 byte che puntano alla matrice che somma a esso. Quando arrivo al punto in cui ho raccolto così tante risorse in una volta che nessuna delle combinazioni si adatta, si ferma e usa l'array puntato dal contatore più alto in esecuzione.

È questo il miglior algoritmo possibile?

Ci sono 2 moduli Perl che sembrano all'altezza del compito, Algoritmo-Combinatorio e Math-Combinatorics. Qualche consiglio su quale è più veloce, più stabile, più fresco?

Il mio schema è di scrivere uno script per calcolare le dimensioni di un gran numero di directory e mostrarmi il contenuto ottimale delle dozzine di dischi da masterizzare.

E, non voglio semplicemente riempire un file per file perché voglio intere directory sullo stesso disco.

Answer 1

Utilizzare l'algoritmo del problema di ottimizzazione "Zaino".

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

1. Set peso per essere uguale alla dimensione del file
2. Impostare il valore di essere uguale a "peso"
3. eseguire l'algoritmo per ogni disco successivo da confezionare

Potrebbe non essere la scelta migliore (massimizzerà il fattore di riempimento del prossimo disco invece di ridurre al minimo il numero di dischi totali necessari), ma è ben documentato e facile da trovare s e codice di lavoro per il linguaggio di programmazione di tua scelta (anche fogli di calcolo) sul web.

Answer 2

L'algoritmo è denominato 1d bin-packing. L'algoritmo è molto veloce ma non ottimale. Puoi anche usare un algoritmo di forza bruta ma lo spazio di ricerca è molto grande. Ecco un programma con un algoritmo avido: http://www.phpclasses.org/package/2027-PHP-Pack-files-without-exceeding-a-given-size-limit.html

Answer 3

Questo è un problema NP-completo noto come bin packing. Non esiste un algoritmo polinomiale noto che lo risolva in modo ottimale. In altre parole, la soluzione ottimale non può essere trovata senza praticamente provare tutte le soluzioni.

Sul lato positivo, un'euristica molto semplice come "metti la cartella più grande sul primo disco che ha spazio" ti garantirà che utilizzerai meno del doppio dei dischi del caso migliore. (Puoi leggere maggiori dettagli sull'articolo di Wikipedia del problema).

Answer 4

Il metodo più pratico che ho ancora trovato per riempire in modo efficiente i miei dischi Blu-Ray.

Creazione di un elenco di percorsi completi per tutti i file disponibili da masterizzare.

Quindi (arbitrariamente) decidere quanti livelli di directory considerare un gruppo o accettare un'opzione della riga di comando per esso. Questo per mantenere le directory piene di elementi simili tutti insieme su un singolo blu-ray. Esiste anche un'opzione STUFF per inserire prima i file più grandi e quando un file causerebbe un overflow, guardate al successivo più piccolo finché non esaurite i file o lo spazio.

Creare un hash con ogni directory come chiave e dimensione totale dei file che contiene come dati. Mantenere anche un hash parallelo con il conteggio dei file per directory come lo spazio allentato e il sovraccarico della directory apparentemente si sommano e devono essere presi in considerazione.

Selezionare 22 come numero magico. Se hai < = 22 directory, prova tutte le combinazioni per trovare quello più vicino ma non superiore a 25.025 GB. Se ne hai più di 22, usa solo il 22 più grande. Io uso il modulo Perl Algorithm :: Combinatorics per trovare tutte le combinazioni. Attraverso la prova e principalmente l'errore, ho determinato che le combinazioni di 21 elementi richiedono solo pochi secondi. 23 elementi richiede molti minuti, che è più lungo della mia capacità di attenzione. 22 impiegano circa 35 secondi.

Una directory di output è anche accettata e controllata per i dati esistenti. C'è un'opzione per spostare i file (copia, controlla la dimensione e scollega).

Ogni volta che ho acquistato un nuovo disco rigido, era solitamente due volte più grande del precedente, quindi dovrei semplicemente copiare tutto. Con una Nikon D800E (Extreme!), HDR e Panorami, ho finalmente esaurito lo spazio.

Il mio progetto è stato quello di unificare, eliminare e consolidare 15 anni di foto, video, film, musica, ecc. Per lo più indesiderati. Ho inventariato circa una dozzina di dispositivi di archiviazione, ho calcolato le firme MD5 e le ho inserite in un database. Ho scelto un disco come master per le foto e uno per i video e ho messo a fuoco tutto il resto. Ho trovato 8 copie di alcune cose!

Ora ho circa 10 TB di spazio libero su disco !!!

Sotto la funzione che fa tutto il lavoro vero nel caso in cui qualcuno sia interessato.

========================================= = Oops! La tua risposta non può essere inviata perché:

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

La stupida pagina web ha alterato il mio codice originale. Spiacente :(..