[Video] C vs Delphi vs Perl

[fvox]

acpguedes, sim, funciona. Porém, não com a otimização que o smiley se referia.
Ontem debatemos isso no MSN...

(01:55) smiley face: tail optmization
não vem por padrão?
(01:55) Junior Moraes: a unica linguagem que vem por padrão é python, se não me engano... C, java, ruby e perl não.
(01:55) smiley face: tem que compilar com
manjei
mas pq não vem com?
oO
(01:55) Junior Moraes: não ué.
não exatamente
(01:56) smiley face: pq n colocam por padrão?
(01:56) Junior Moraes: a tail optimization meche com estruturas e controle de fluxo.
no caso do perl, os ponteiros de scalar em 'local'
a optimização se perde nisso
(01:56) Junior Moraes: se ao invés de return, você inserir um goto, terá a tail optimization
(01:57) Junior Moraes: tail optimization não é uma implementação em si.
(01:58) smiley face: nesse caso não é tail optmization
mas falei como se fosse,alias.
é simplesmente cache do resultado de funções pra posterior uso em contextos recursivos.
(01:58) Junior Moraes: não tem bem cache, na linguagem que for. pera ai, vou tentar codar aqui
(01:59) Junior Moraes: até porque a porra da função que te passei é uma bosta... duplamente recursiva LOL um momento
(02:00) smiley face: sim
mas eu achei que perl tivesse cache da porra do resultado de funções!
kkkkkkkkk'
mas não tem
(02:00) smiley face: nem python alias
e provavelmente nem ruby
(02:00) Junior Moraes: nenhuma tem heuaehuh

Deste modo, não possuindo o contexto de local e nem utilizando goto, conseguimos optimizar o algoritmo de fibonacci através da feature state do Perl:

use strict;
use warnings;
use feature qw(say state);

sub fib {
    state $m = {
        1 => 1,
        2 => 1,
    };
    return $m->{$_[0]} //= fib($_[0] - 1) + fib($_[0] - 2);
}

say fib 45; 

A recursão ainda existe, e o resultado é imediato... =)

[]'s

[acpguedes]

@fvox, mas pqp, polemica de mais!!! hahaha

mas valeu por defender nossa classe!

Ai vai outro script que tbm gera Fibonacci

não calibrei o script, esta como o original...

#!/usr/bin/perl  #--------------------------------------------------------------------# #Fibonacci Generator #       Date Written:   22-Jul-2001 10:12:09 AM #       Last Modified:  13-Aug-2001 10:06:30 AM #       Author:         Kurt Kincaid # #       This is free software and may be redistributed under the #       same terms as Perl itself. #--------------------------------------------------------------------#  use Getopt::Std; use Math::BigInt;  $| = 1; $VERSION = "1.2"; $x = Math::BigInt->new(1); $y = Math::BigInt->new(2);  getopts("ch");  $\= $opt_c ? "\n" : " ";  if ( $opt_h ) {     print <<END; Fibonacci Generator v$VERSION Usage: $0 [-ch] [number] -c\tPrint output in a single column (default is rows) -h\tPrint help text (what you're reading now)      Include how many numbers in the sequence you want,      otherwise it defaults to 100. END     exit; }  my $stop = shift || 100;  print $x; print $y; for ( 3 .. $stop ) {     ( $x, $y ) = ( $y, $x+$y );     print $y; } 

Creditos: esta no proprio script
Site: PerlMonks

[acpguedes]

foi mal o flood, mas esse script usa outros aperfeiçoamentos,
apesar de ser pesado na memoria o carregamento dele é incrivelmente rápido!

XD

ps: antes que alguém venha postar e me xingar, eu concordo com a velocidade de C
acho uma Linguagem incrível... e essa comparação idiota de velocidades foi feita para sanar duvidas que haviam sido geradas no shoutbox
Mas escolha da linguagem depende da afinidade do programador e do propósito que será aplicado
não que não possa usar uma linguagem fora do propósito... tudo é possível!
XD

[smiley face]

Não é polêmica.Apresentei scripts de mesma semântica e fiz o profile entre eles.
O script em perl com semântica igual ao em C apresentado no tópico roda normalmente.
Entretanto,por causa do nivel de recursividade do programa ele irá ou travar ou demorar horrores para retornar o resultado,o que é infinitamente mais devagar que em C.
O novo código apresentado por você é equivalente em semântica ao primeiro código em perl apresentado no tópico enquanto o do fvox vale-se de otimizações.
Independente das otimizações feitas em perl,esse ainda será infinitamente mais devagar que o em C (o que você parece não entender) já que esse é compilado e o perl é interpretado (o interpretador é em C,inclusive).
Só existe um ponto em fazer profiling entre linguagens se se tem a menor idéia do que está fazendo,o que não é o seu caso.

[_Guga_]

cara, vou dar minha possível explicação e uma possível solução.

vamos do inicio, o que é a sequencia de fibonacci? uma sequencia de numeros definidas pelas equações:

fib 1 = 1
fib 2 = 1
fib n = (fib n-1) + (fib n-2)

ou seja, cada valor da progressão é a soma dos dois valores precedentes. Podemos dizer entao que os 10 termos dela são:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55

agora gostaríamos muito de escrever uma função que calcule fib n para qualquer valor de n. Suponha que traduzimos a definição da sequencia de fibonacci para essa função recurssiva em C:

int fib( int n )
{
     if( n <= 2 ) return 1;
     else return fib( n - 1 ) + fib( n - 2 );
}

isso com certeza é simples e a função irá funcionar corretamente. Mas fiquem atentos para a saída na medida que vc executa um teste com essa função. Para valores de entrada pequenos, o programa é até bastante rápido. Mesmo para valores moderadamente grandes, no entanto, o programa faz pausas incrivelmente longas entre cada saida. Por exemplo, tente valores entre 30 e 50 para ver esse efeito.

é amigo, isso n faz muito sentido. Munido de um lápis, papel e um calculadores vc poderia calcular esses valores de forma bem rápida, de modo que o computador nao deveria levar tanto tempo para fazer.

Quando eu me deparei com esse tipo de problema a algum tempo atrás, eu inseri mensagens de monitoramento na função e consegui montar uma arvore de chamadas, digamos que passamos o valor 6, aqui está a arvore de chamada que é construida:

                                               fib              (6)
                                      /                               \
                               fib(5)                                 fib(4)
                              /      \                                 /     \
                    fib(4)              fib(3)                    fib(3)    fib(2)
                   /       \            /      \                   /    \
          fib(3)          fib(2)  fib(2)     fib(1)         fib(2)     fib(1)
          /     \
    fib(2)     fib(1)

se torna dessa forma aparente o porquê de a função demorar tanto tempo. Ela fica calculando os mesmos numeros repetitivamente. Nesse exemplo ae, o calcula de fib(6) chama fib(4) duas vezes e fib(3) tres vezes. Bem diferente do calculo que vc faria com lapis e papel nao é?
com lapis e papel vc simplismente escreveria os valores à medida em que eles fossem calculados e somaria os dois ultimos para obter o proximo ate q vc alcançasse o termo desejado, dessa forma, nenhum valor da sequencia sera calculado mais de uma vez.

obtemos dessa forma uma nova função:

int fib( int n )
{
   if ( n <= 2 ) return 1;
   int fold = 1;
   int fold2 = 1;
   int fnew;

   int i;

   for( i = 3; i <= n; i++ )
   {
          fnew = fold + fold2;
          fold2 = fold;
          fold = fnew;
    }

    return fnew;
}

sem nenhuma POG e facil de entender. Essa função é executada MUITO mais depressa do que a versao recursiva.

enfim é só!

abraços, T+

[_Guga_]

reerguendo o tópico..

eu estava dando uma olhada na conversa que o fvox teve com o smiley face sobre tail optimization e reparei algo que o fvox disse:

(01:55) Junior Moraes: a unica linguagem que vem por padrão é python, se não me engano... C, java, ruby e perl não.

Isso me despertou uma certa curiosidade e vim testar, porém com a linguagem C++, utilizando templates ( recurso poderoso do C++ para programação genérica e meta-programação ) criei uma função para testes:

template <typename T>
T foobar( T t ) 
{
   cout << t << flush << '\n';


   if ( !t )  return t;


   return foobar( t - 1 );
}

eu verifiquei no GCC, e no entanto, contrariando minhas expectativas pessimistas, o código gerado foi:

  5   T foobar( T t ) {
    6       cout << t << endl;
-   0x401362    <main+22>:      mov    %esi,0x4(%esp)
-   0x401366    <main+26>:      movl   $0x4740c0,(%esp)
-   0x40136d    <main+33>:      call   0x448620 <_ZNSolsEi>
-   0x401372    <main+38>:      mov    %eax,%ebx
    7      if ( !t ) {
-   0x4013a5    <main+89>:      test   %esi,%esi
-   0x4013a7    <main+91>:      je     0x4013c8 <main+124>
    8         return t;
    9      }
    10     return foobar( t - 1 );
-   0x4013a9    <main+93>:      dec    %esi
-   0x4013aa    <main+94>:      jmp    0x401362 <main+22>
    11  }

Como podem ver, a chamada recursiva tornou-se um jump devolta para o entry point da função. Porém esse tipo de otimização é realizada pelo GCC se o código for compilado com otimizações habilitadas, neste caso: -o2.


Não sei se é um tipo de otimização que todos os compiladores C++ implementam e também desconheço se no C exista algo semelhante, também não está especificado no ISO C++03 e tampouco no ISO C++11 sobre essa façanha.

PS: pra quem usa o VC++ ( como eu ), para habilitar a tail call optimization, navegue para Project Property > Configuration Properties> C/C++ > Optimization e sete otimização para /O2 ou /Ox =)

Quanto ao C, se algum compilador o fizer, acredito que funções como:

unsigned f( unsigned a ) 
{
    if ( !a ) return a
    return f(a - 1) + f( a - 1);   
}

são reescritas para depois traduzidas em funções equivalentes das quais pode-se aplicar a otimização, no caso da função acima, o return poderia virar algo do tipo return 2 * f(a-1), mas mesmo assim ainda não daria pra aplicar a otimização, o compilador teria que certificar-se que o tail da função fique dessa forma: return f(....)

Então provavelmente usaria um parametro auxiliar, algo do tipo:

unsigned f( unsigned a, unsigned multiplicative_accumulator = 1 ) 
{
    if ( !a ) return multiplicative_accumulator * a;


    return f( a - 1, multiplicative_accumulator * 2 );  


}

enfim é isso,

abraços

[rock.ownar]

Quando se trabalha com acessos os resultados são totalmente diferentes da mesma forma de quando se trabalha com calculos não há nenhuma conexão, mas no vídeo mesmo mostra que a calculação do perl é muito mais rápida sim!!!

[_Guga_]

Quando se trabalha com acessos os resultados são totalmente diferentes da mesma forma de quando se trabalha com calculos não há nenhuma conexão, mas no vídeo mesmo mostra que a calculação do perl é muito mais rápida sim!!!

http://modperlbook.org/html/13-12-Co...erl-and-C.html

abraços

[acpguedes]

Perl perde pois tem que sofrer uma "compilação" toda vez que é executado, não atentei tambem para recursividade.

Mas acho que poderiamos fazer a mesma comparação mas após os programas terem sidos executados. (
(ficou confuso)

colocando o mesmo padrão de logica e um STDIN (entrada do usuario)
Apos iniciar a execução contamos o tempo a partir da entrada do valor por parte do usuario.
Ficaria mais logico.

Pois considerando o tempo para iniciar a execução do programa em Perl é quase irrelevante,
iriamos medir o tempo de calculo.

Mas como o smiley ja havia dito, "Só ha um motivo de se fazer profiling entre linguagens.".

(Pow Guga, essa imagem da sua assinatura é viciante... kkkkk... patada mo loca!)

[_Guga_]

cara, essa citação do link que eu postei diz tudo e não preciso entrar em detalhes técnicos para provar isso, embora caso se torne necessário eu o faça.

To simplify the task, we are going to demonstrate only the fact that C is more suitable than Perl for mathematical and memory-manipulation task.

abraços