Pessoal,
Estou precisando da ajuda de algum commiter brasileiro do freebsd,
sei que nesta lista existem alguns entao talvez seja prudente eu
postar isso aqui ;)
A alguns meses atras eu fiz um patch para o random(6), um aplicativo
que randomiza as linhas de um dado arquivo, algo muito util em
diversos casos. No entanto a maneira como o random(6) e' implementado
atualmente deixa muito a desejar no quesito performance quando nos
tentamos randomizar arquivos grandes (>100mb).
O algoritmo utilizado no random(6) atualmente constroi uma lista
encadeada contendo linhas/palavras (random(6) tambem pode randomizar
palavras de um arquivo), ou seja um arquivo com 10.000 linhas
resultara em uma lista encadeada de 10.000 nodes, no entanto o
algoritmo utilizado na hora de selecionar randomicamente uma linha e
imprimi-la e' bem "brute-force". Ele randomicamente seleciona um
numero entre 0 e n-linhas e caminha elemento por elemento ate' chegar
no elemento selecionado e imprime essa linha e depois remove o
elemento da lista*, seleciona outro elemento, caminha toda a lista
denovo ate' chegar ao elemento, imprime e remove o elemento e assim
por diante, percorrendo a lista
toda vez que for imprimir uma linha.
O patch que eu desenvolvi transforma esta operacao bastante custosa
em uma operacao O(1) apos a lista ter sido criada pela primeira vez, e
resulta em ganhos de performance assutadores. Apos a lista ter sido
criada eu mapeio um vetor de ponteiros para cada elemento da lista, e
assim nos podemos selecionar uma linha com um unico passo, por
exemplo:
----
linha_ptr = vetor[linha_selecionada];
printf("%s", linha_ptr->conteudo);
----
O pacote contem a documentacao, o patch em si e a atualizacao no man
page do random(6), no entanto parece que nenhum commiter realmente se
importa por esse aplicativo uma vez que eu ja tentei commitar esse
patch diversas vezes e parece que falta tempo/vontade de efetiva-lo ;/
Minha intencao aqui na fug-br e' tentar contactar algum commiter do
freebsd para abracar essa causa e tentar commitar alguns poucos bytes
de alteracoes muito uteis ao programa. O pacote pode ser encontrado
em:
http://setuid.promisc.org/random_faster.tar.gz
Espero que algum brasileiro se comova,
victor f. loureiro lima
-------------------------
Histórico: http://www.fug.com.br/historico/html/freebsd/
Sair da lista: https://www.fug.com.br/mailman/listinfo/freebsd
