Minimizando desperdícios de espaço com o gaffitter
“Genetic Algorithm File Fitter, ou simplesmente gaffitter, é uma ferramenta que emprega otimização por Algoritmos Genéticos a fim de, dada uma lista de arquivos/diretórios, extrair o subconjunto que melhor se ajusta a um tamanho fornecido, isto é, a seleção que minimiza o desperdício de espaço. Sua aplicação é especialmente útil quando há necessidade de armazenamento de quantidades de arquivos cuja soma dos tamanhos ultrapassa a capacidade de, por exemplo, uma mídia de CD ou DVD. O gaffitter é um software livre (licença GPL) de minha autoria, escrito em C++ e com interface linha de comando. Finalmente, é com satisfação que anuncio, diante da imensidão do Software Livre, esta minha singela contribuição.” A nota foi enviada por Douglas A. Augusto (daaugustoΘgmail·com) , que enviou este link para mais detalhes.(postado por Augusto Campos)
Comentários dos leitores
Comentário de Douglas Augusto
19/12/05 0:09 - usuário registrado #12
Damarinho,
: Damarinho,
Existe a opção "--block-size" (ou simplesmente "--bs") que serve justamente para isso, ou seja, informa o tamanho mínimo em bytes que um arquivo pode ocupar. Por padrão está configurado em "1", a menor quantidade possível.
O propósito do gaffitter é bastante diversificado (sistema de arquivos local, CD, DVDs, etc.), portanto seria pouco interessante favorecer uma determinada arquitetura.
--
FLTK fltk.org (Fast Light C++ GUI Toolkit)
Existe a opção "--block-size" (ou simplesmente "--bs") que serve justamente para isso, ou seja, informa o tamanho mínimo em bytes que um arquivo pode ocupar. Por padrão está configurado em "1", a menor quantidade possível.
O propósito do gaffitter é bastante diversificado (sistema de arquivos local, CD, DVDs, etc.), portanto seria pouco interessante favorecer uma determinada arquitetura.
--
FLTK fltk.org (Fast Light C++ GUI Toolkit)
Comentário de welrbraga
19/12/05 12:25 - usuário registrado #487
Muito bom': Muito bom o seu programa.
Eu estava procurando por algo que fizesse isso e acabei fazendo um "negócio meio porco" que juntava shell-script e python usando um horrível loop com vários testes :-P
---
Dar boot no Windows é humano, Insistir em usar é burrice!
User Linux: #253605
Eu estava procurando por algo que fizesse isso e acabei fazendo um "negócio meio porco" que juntava shell-script e python usando um horrível loop com vários testes :-P
---
Dar boot no Windows é humano, Insistir em usar é burrice!
User Linux: #253605
Comentário de pappacena
19/12/05 14:08 - usuário registrado #2897
Bem...: Não quero desmerecer o programa do colega (até pq eu realmente já precisei MUITO de um desses e, à época, não achei nada), mas um algoritmo genético não faz muito diferente de um horrível loop com vários testes...
A diferença é dar uma nota para saber quais dos resultados foram mais "aptos a sobreviver" para o próximo loop. ;)
Não vi como está implementado, nem cheguei a testar, mas parabéns pelo programa. Sei que também vai me ser muito útil. :D
print "\n";
exit(0); // Thiago F. Pappacena
A diferença é dar uma nota para saber quais dos resultados foram mais "aptos a sobreviver" para o próximo loop. ;)
Não vi como está implementado, nem cheguei a testar, mas parabéns pelo programa. Sei que também vai me ser muito útil. :D
print "\n";
exit(0); // Thiago F. Pappacena
Comentário de Douglas Augusto
19/12/05 17:00 - usuário registrado #12
> Não quero desmerecer o pro: > Não quero desmerecer o programa do colega (até pq eu realmente já precisei MUITO de um desses e, à época, não achei nada), mas um algoritmo genético não faz muito diferente de um horrível loop com vários testes...
Lembre-se de que você e todos nós estamos aqui por culpa desse "horrível loop com vários testes" --se porventura não acredita na Seleção Natural, não vamos entrar no off-topic, apenas ignore.
Outrossim, se você conhece um outro algoritmo de otimização global que melhor resolva esta tarefa (Problema de Knapsack) em todas as configurações de entrada (pequena, média e grande), me dê um toque que possivelmente implementarei como alternativa --eu já coloquei como opção os algoritmos Força Bruta (global garantido, mas explode fácil) e Best First (otimização local, mas muito rápido).
Uma das coisas que pesou a favor dos AGs (além do meu background nesta área) foi sua flexibilidade. Com isso, por exemplo, é possível que futuramente venha incluir opções do tipo "quero que o resultado favoreça arquivos de tamanho perto de x". Ainda, como são várias possibilidades dentro dos AGs (daí "algoritmos"), extensões e especializações (otimização) tornam-se plausíveis --meu objetivo no decorrer da evolução do gaffitter é refinar/especializar o AG de modo a torná-lo cada vez mais eficiente (tanto em tempo como na qualidade das soluções).
Não se esqueça que são problemas NP-completo. Formalmente, existem 2^n possibilidades (isto somente na forma "pura"), onde 'n' é o tamanho de entrada. Por exemplo, meu /usr/bin tem 2900 arquivos, isto significa que existem 2^2900 soluções candidatas (um número com mais de 870 casas!).
Por fim, recomendo você procurar alguns papers sobre computação evolucionária (em especial Algoritmos Genéticos e Programação Genética) para ver o que "horríveis loops" podem fazer --e verá que não é parecido com o sentido pejorativo ("força bruta") que o outro colega quis dizer com "horrível loop". Se quiser um embasamento matemático-estatístico de como esses "horríveis loops" funcionam, procure por "Schema(ta)".
--
FLTK fltk.org (Fast Light C++ GUI Toolkit)
Lembre-se de que você e todos nós estamos aqui por culpa desse "horrível loop com vários testes" --se porventura não acredita na Seleção Natural, não vamos entrar no off-topic, apenas ignore.
Outrossim, se você conhece um outro algoritmo de otimização global que melhor resolva esta tarefa (Problema de Knapsack) em todas as configurações de entrada (pequena, média e grande), me dê um toque que possivelmente implementarei como alternativa --eu já coloquei como opção os algoritmos Força Bruta (global garantido, mas explode fácil) e Best First (otimização local, mas muito rápido).
Uma das coisas que pesou a favor dos AGs (além do meu background nesta área) foi sua flexibilidade. Com isso, por exemplo, é possível que futuramente venha incluir opções do tipo "quero que o resultado favoreça arquivos de tamanho perto de x". Ainda, como são várias possibilidades dentro dos AGs (daí "algoritmos"), extensões e especializações (otimização) tornam-se plausíveis --meu objetivo no decorrer da evolução do gaffitter é refinar/especializar o AG de modo a torná-lo cada vez mais eficiente (tanto em tempo como na qualidade das soluções).
Não se esqueça que são problemas NP-completo. Formalmente, existem 2^n possibilidades (isto somente na forma "pura"), onde 'n' é o tamanho de entrada. Por exemplo, meu /usr/bin tem 2900 arquivos, isto significa que existem 2^2900 soluções candidatas (um número com mais de 870 casas!).
Por fim, recomendo você procurar alguns papers sobre computação evolucionária (em especial Algoritmos Genéticos e Programação Genética) para ver o que "horríveis loops" podem fazer --e verá que não é parecido com o sentido pejorativo ("força bruta") que o outro colega quis dizer com "horrível loop". Se quiser um embasamento matemático-estatístico de como esses "horríveis loops" funcionam, procure por "Schema(ta)".
--
FLTK fltk.org (Fast Light C++ GUI Toolkit)
Comentário de pappacena
19/12/05 17:44 - usuário registrado #2897
Flames...: recomendo você procurar alguns papers sobre computação evolucionária
Não, obrigado. Prefiro os sobre ART2 e redes de Kohonen. ;)
Não disse que a solução era ruim, nem tentei desmerecer os AG. Acho uma solução muito boa, só tentei desmistificar um pouco o idéia do nosso amigo acima.
Acho que se revoltou à toa...
print "\n";
exit(0); // Thiago F. Pappacena
Não, obrigado. Prefiro os sobre ART2 e redes de Kohonen. ;)
Não disse que a solução era ruim, nem tentei desmerecer os AG. Acho uma solução muito boa, só tentei desmistificar um pouco o idéia do nosso amigo acima.
Acho que se revoltou à toa...
print "\n";
exit(0); // Thiago F. Pappacena
Comentário de Douglas Augusto
19/12/05 18:36 - usuário registrado #12
> Acho que se revoltou à toa: > Acho que se revoltou à toa...
Desculpe se interpretei errado, mas seu comentário anterior deu a entender que os Algoritmos Genéticos não fazem muito além do que força bruta --o que o welrbraga referenciou como "horrível loop com vários testes", acredito.
E sua super simplificação do mecanismo dos AGs ("A diferença é dar uma nota para saber quais dos resultados foram mais "aptos a sobreviver" para o próximo loop") está imprecisa, pois a descendência com modificação (além da seleção dos mais aptos), através dos operadores genéticos, é o cerne da evolução. E isto é apenas o crasso do algoritmo. No meu código você verá, por exemplo, que a inicialização é feita de forma não uniforme a fim de melhor cobrir o espaço de busca; que indivíduos "infactíveis" (aqueles que ultrapassam o objetivo) não são simplesmente desprezados, mas sim progressivamente penalizados; entre outras coisas.
Mais uma vez, se sua intenção não havia sido essa, peço desculpas, mas ainda assim minha observação foi pertinente a fim de evitar outras más interpretações.
--
FLTK fltk.org (Fast Light C++ GUI Toolkit)
Desculpe se interpretei errado, mas seu comentário anterior deu a entender que os Algoritmos Genéticos não fazem muito além do que força bruta --o que o welrbraga referenciou como "horrível loop com vários testes", acredito.
E sua super simplificação do mecanismo dos AGs ("A diferença é dar uma nota para saber quais dos resultados foram mais "aptos a sobreviver" para o próximo loop") está imprecisa, pois a descendência com modificação (além da seleção dos mais aptos), através dos operadores genéticos, é o cerne da evolução. E isto é apenas o crasso do algoritmo. No meu código você verá, por exemplo, que a inicialização é feita de forma não uniforme a fim de melhor cobrir o espaço de busca; que indivíduos "infactíveis" (aqueles que ultrapassam o objetivo) não são simplesmente desprezados, mas sim progressivamente penalizados; entre outras coisas.
Mais uma vez, se sua intenção não havia sido essa, peço desculpas, mas ainda assim minha observação foi pertinente a fim de evitar outras más interpretações.
--
FLTK fltk.org (Fast Light C++ GUI Toolkit)
Comentário de pappacena
20/12/05 9:56 - usuário registrado #2897
Ok.: Sem problemas... :)
Aliás, é a segunda vez em menos de uma semana que sou mal compreendido...
Há poucos dias, acabei discutindo sobre o VIM com um colega aqui do BR-Linux. O detalhe é que eu e meu interlocutor usamos e gostamos muito deste editor! Hahahahaha
print "\n";
exit(0); // Thiago F. Pappacena
Aliás, é a segunda vez em menos de uma semana que sou mal compreendido...
Há poucos dias, acabei discutindo sobre o VIM com um colega aqui do BR-Linux. O detalhe é que eu e meu interlocutor usamos e gostamos muito deste editor! Hahahahaha
print "\n";
exit(0); // Thiago F. Pappacena
Comentário de Douglas Augusto
20/12/05 16:36 - usuário registrado #12
> Há poucos dias, acabei dis: > Há poucos dias, acabei discutindo sobre o VIM com um colega aqui do BR-Linux. O detalhe é que eu e meu interlocutor usamos e gostamos muito deste editor! Hahahahaha
Ah, tá. Porque se não gostasse do Vim aí sim teríamos um flamewar aqui. :D
--
FLTK fltk.org (Fast Light C++ GUI Toolkit)
Ah, tá. Porque se não gostasse do Vim aí sim teríamos um flamewar aqui. :D
--
FLTK fltk.org (Fast Light C++ GUI Toolkit)
"[i] ... seleção que minimiza o desperdício de espaço [/i]"
1 - Em conformidade com o formato dos arquivos, considero eleger uma
arquitetura de arquivos, tal como o REISERFS.
Há desperdício em formatos "ext2, ext3". Neste formato um diretório é
criado com 4096 bytes, em REISERFS com 48 bytes.
2 - É considerável este comentário ?