[Cascavel-pm] algoritmo

[Luís Fernando]

Digamos que a diferença entre o que eu desejo e o que o que você citou
é exatamente a "aleatoriedade".

Para simplificar:
Se cabe 10 elementos e eu mando inserir 10 (1..10), é para ficar:
1 2 3 4 5 6 7 8 9 10

Se cabe 10 elementos e eu mando inserir 20 (1..20):
1 3 5 7 9 11 13 15 17 19

Se cabe 10 elementos e eu mando inserir 40 (1..40):
1 5 9 13 17 21 25 29 33 37

Entendeu?

Como cada "sample" é pego em intervalos de 1 segundo, no primeiro caso
o intervalo entre um e outro seria de 1 segundo
No segundo, como não coube no buffer, ele excluiu alguns
intermediários, ficando com intervalos de 2 segundos... no terceiro,
com intervalos de 4 segundos.

Obviamente, há "intermediários" disso (por exemplo, 15 elementos
quando só cabem 10) e acho que o método que descrevi funciona para
eles, porém não me parece muito eficiente (tenho a impressão que é
possível fazer em O(1)).

/*

+---------------------------------+
| Luís Fernando Estrozi           |
+---------------------------------+
| Ciência da Computação - USP     |
|                                 |
| mailto:lemon em grad.icmc.usp.br   |
| ICQ#: 25541891                  |
|                                 |
| http://grad.icmc.usp.br/~lemon/ |
+---------------------------------+

There are 10 types of people in the world: Those who understand binary, and those who don't

*/ EOF

|---> Original Message <---> 22/6/2004, 19:47 <---|
Luís,

Aparentemente uma porcentagem do seu objetivo, que não ficou
completamente claro para mim, pode ser obtida deste modo:

A partir do momento em que o buffer estiver completo, você passa a
descartar um ítem aleatório antes de adicionar o novo elemento no final:

$conta=-1;

push(@buff, novo_byte()) while(++$conta < $tamanho);

while(1) {
  splice(@buff, rand($tamanho), 1);
  push @buff, novo_byte();  
}

Compreender a diferença efetiva entre os dois algoritmos está além da
minha capacidade de abstração. Mas assim fica bem mais simples!

Silvio