[CB-lug] programma per ottimizzare lo spazio

[redcloud]

Salve a tutti! Avete molti file da masterizzare e non volete sprecare lo 
spazio prezioso dei vostri dvd? Da oggi c'è "DSO"!!! Questo simpatico 
programmillo (da me ideato e realizzato in un paio di giorni) permette 
di trovare la migliore combinazione di file che occupano al meglio lo 
spazio disponibile.


INPUT: directory contenente i file da analizzare, spazio a disposizione 
(in byte)

$ ./dso ./ 92800


OUTPUT: lista delle soluzioni migliorative
------------------------------------------
Files found: 149
WARNING: files in directory are more than recommended (30).
Press CTRL+C to exit.
  10 sec. to go...
   9 sec. to go...
   8 sec. to go...
   7 sec. to go...
   6 sec. to go...
   5 sec. to go...
   4 sec. to go...
   3 sec. to go...
   2 sec. to go...
   1 sec. to go...

   1)            4096 byte - .googleearth
1) SOL: 4096 byte    WM: 92800 byte    DIFF: 88704 byte

   1)            4096 byte - .fluxbox
   2)            4096 byte - .googleearth
2) SOL: 8192 byte    WM: 92800 byte    DIFF: 84608 byte

   1)             110 byte - .csmashrc
   2)            4096 byte - .fluxbox
   3)            4096 byte - .googleearth
3) SOL: 8302 byte    WM: 92800 byte    DIFF: 84498 byte

   1)            4096 byte - MonoProjects
   2)            4096 byte - .fluxbox
   3)            4096 byte - .googleearth
4) SOL: 12288 byte    WM: 92800 byte    DIFF: 80512 byte

   1)            4096 byte - MonoProjects
   2)             110 byte - .csmashrc
   3)            4096 byte - .fluxbox
   4)            4096 byte - .googleearth
5) SOL: 12398 byte    WM: 92800 byte    DIFF: 80402 byte

.
..
...

   1)            4096 byte - .fblevels
   2)            4096 byte - .inkscape
   3)            2144 byte - .asoundrc
   4)           12276 byte - .libquicktime_codecs
   5)            4096 byte - .gnusound
   6)             559 byte - log.txt
   7)             584 byte - dares.log
   8)            4096 byte - .gnupg
   9)            4096 byte - .cache
  10)            4096 byte - .gtodo
  11)             961 byte - .BOINC Manager
  12)            4096 byte - .balazar_saved_games
  13)            4096 byte - .armagetron
  14)           10477 byte - dso
  15)            4096 byte - .nexuiz
  16)            4096 byte - .loki
  17)            4096 byte - .wine
  18)            4248 byte - dso.c
  19)            4096 byte - d
  20)            4096 byte - MonoProjects
  21)             110 byte - .csmashrc
  22)            4096 byte - .fluxbox
  23)            4096 byte - .googleearth
84) SOL: 92799 byte    WM: 92800 byte    DIFF: 1 byte
------------------------------------------

SOL è lo spazio occupato dalla soluzione attuale
WM è lo spazio disponibile dato in input
DIFF è WM - SOL

Data la natura del problema (enumerazione di sottoinsiemi), la 
complessità temporale è O(2^n) (fortunatamente la complessità spaziale 
delle chiamate ricorsive utilizzate dall'algoritmo è O(n)), quindi è 
estremamente consigliato analizzare liste di file < 30. Con 30 file in 
in quarto d'ora (sul mio Sempron 1800MHz) si riesce ad ottenere un 
risultato certo. Tuttavia è possibile ottenere risultati soddisfacenti 
anche con liste di file > 30 (il programma ammette 10000 file). 
Nell'output di prova di cui sopra ho considerato una lista di 149 file. 
Per avere un risultato certo, il programma avrebbe dovuto analizzare 
2^149 combinazioni... un bel po' di tempo! Dopo solo 3 minuti però ho 
ottenuto la soluzione numero 84 che mi lascia libera solo 1 byte (come 
si può vedere dal parametro DIFF), soluzione decisamente soddisfacente!

Se analizzate più di 30 file (più di 15 minuti di attesa su un Sempron 
1800MHz per ottenere una soluzione certa) e avete individuato una 
soluzione soddisfacente e non volete attendere ancora inutilmente il 
termine del programma, potete premere sempre CTRL+C ;)

Da compilare con "gcc dso.c -o dso"

P.s. se volete potete pubblicarlo sul sito del LUG.
-------------- parte successiva --------------
Un allegato non testuale è stato rimosso....
Nome:        dso.c
Tipo:        text/x-csrc
Dimensione:  4248 bytes
Descrizione: non disponibile
Url:         http://lists.linux.it/pipermail/lugcb/attachments/20060808/cb425d0a/dso.c