[Cascavel-pm] algoritmo

[Marco A P D´Andrade]

Luis,

Vc não foi muito claro, porém eu estou assumindo que vc calcula a 
posição entre:

1o elemento e ultimo alterado (regra1) + ultimo alterado e ultimo 
elemento (regra 2)


Suponho como resposta, não muito elegante, pois depende de variaveis 
globais:

#--
use strict;
use warnings;
 my @Itens;
 my $Max = 10;
 my ( $LastChange );
  map {
    Insere( $_ );
    print "+$Itens[-1]($Max): @Itens\n";
    } ( 1 .. 10 );

        print "$Itens[-1]($Max): @Itens ($LastChange)\n";
  Insere( 11 );    print "$Itens[-1]($Max): @Itens ($LastChange)\n";
  Insere( 12 );    print "$Itens[-1]($Max): @Itens ($LastChange)\n";

sub Insere {
 my ( $Val ) = @_;
 my ( $Range1, $Range2 );
  # Atingiu o limite
  if (  @Itens  == $Max ) {

     # Nao houve nenhuma alteracao ainda
     unless ( $LastChange ) {
         $LastChange = int(($Itens[-1]-$Itens[0])/2);
  
      } else {
         # Range inferior
         $Range1 = int(($Itens[0]-$Itens[$LastChange])/2);

         # Range superior
         $Range2 = int(($Itens[-1]-$Itens[$LastChange])/2);

         $LastChange = ( $Range1 > $Range2 ? $Range1 : $LastChange + 
$Range2 );

     }

     # Removo um item
     splice(@Itens, --$LastChange, 1);
  }

  # acrescento ...
  push(@Itens, $Val);

}
---
Bate com seus valores...
Feito com somente 2 ranges fixos, utilizando variavel e memoria em 
variaveis globais (nao recomendo).

Agora diga... qual o uso prático ?


Sds,
Marco Antonio



Luís Fernando wrote:

>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
>
>_______________________________________________
>Cascavel-pm mailing list
>Cascavel-pm em mail.pm.org
>http://cascavel.pm.org/mailman/listinfo/cascavel-pm
>
>
>