[Cascavel-pm] algoritmo

Luís Fernando lemon em grad.icmc.usp.br
Terça Junho 22 16:42:08 CDT 2004


Sei que esse não é um problema de específico perl (e sim mais de
algoritmo), mas agradeço se alguém puder me ajudar :)

Eu tenho um buffer não-sequencial* de 100 bytes, e vou gravando "seqüências ordenadas de
amostragem" nele.
Supondo: eu recebo 1 amostra de 1 byte a cada segundo, e salvo-a no
final desse buffer. Para facilitar o entendimento, vou supor que essa amostra é uma
seqüência que começa no 1 quando eu rodo o programa e vai
incrementando de 1 a cada segundo.
O problema é que uma hora o buffer vai encher. Quando isso acontecer,
para ter o mínimo de perda possível, quero que amostras sejam apagadas
"da melhor forma possível".

Se, quando chegasse em 100 bytes, para adicionar uma
nova eu apagasse a primeira (e assim por diante), eu perderia todos os
dados antigos. Em vez disso, eu prefiro ter amostras a cada 2
segundos.
Clareando: Se eu tenho o buffer de 100 bytes e recebo 200 informações,
eu não armazenaria apenas as 100 últimas, e sim "1 sim outra não"
(ficaria, no buffer, 1 3 5 7 9, etc.).

Mas como as informações "vão chegando" (tempo real), não dá para
saber quantas vão ter.


Melhor solução que consegui pensar até agora:
- quando rodar o programa, inicie uma lista vazia;
- a cada amostra recebida, verifique qual o intervalo entre os
extremos do buffer e os valores da lista e os intervalos entre
os próprios valores (calma que já explico melhor). Escolha o que for
maior e insira no meio deles.

Agora explicando:
Se eu posso colocar 10 elementos, e já coloquei:
1 2 3 4 5 6 7 8 9 10

Agora chegou o "11". Como a lista está vazia, eu verifico o intervalo
entre o "1" e o "10" (int((10-1)/2) = 4). Vou lá e APAGO a POSIÇÃO 4
(* automaticamente, por causa da estrutura de dados, o 5 já vira 4, o 6
vira 5, etc.) e salvo-a na lista.
Terei agora:
1 2 3 5 6 7 8 9 10 11

Quando chegar o "12", Faço a diferença entre 1 e 4 (int((4-1)/2) = 1) e entre
10 e 4 (int((10-4)/2) = 3). O "3" é maior, então eu apago o elemento
entre o 4 e o 10 (no caso, "7") e insiro novamente no final.

Espero não ter sido MUITO confuso.

Alguém consegue pensar numa solução mais eficiente?

Obrigado por ter lido até aqui :P

/*

+---------------------------------+
| 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




Mais detalhes sobre a lista de discussão Cascavel-pm