Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Perl Misc (http://www.velocityreviews.com/forums/f67-perl-misc.html)
-   -   more efficient shift register? (http://www.velocityreviews.com/forums/t898178-more-efficient-shift-register.html)

Chris Richmond - MD6-FDC ~ 05-25-2006 05:34 PM

more efficient shift register?
 
Folks,

This is a trivial example of a larger problem I'm trying to
speed up. What I want to know is if there is a faster way
to impliment a shift register for text chars. I already tried
using arrays and unshifting and popping, and it was 2-3x slower.

Thx, Chris

Output:

-> 0000 -> (pre-shifting)
1 -> 1000 -> 0
1 -> 1100 -> 0
1 -> 1110 -> 0
0 -> 0111 -> 0
1 -> 1011 -> 1
1 -> 1101 -> 1
1 -> 1110 -> 1
0 -> 0111 -> 0
0 -> 0011 -> 1
0 -> 0001 -> 1
1 -> 1000 -> 1
0 -> 0100 -> 0
1 -> 1010 -> 0
0 -> 0101 -> 0
1 -> 1010 -> 1
1 -> 1101 -> 0
1 -> 1110 -> 1
1 -> 1111 -> 0
0 -> 0111 -> 1
0 -> 0011 -> 1
0 -> 0001 -> 1
0 -> 0000 -> 1


Script:

#!/usr/bin/perl -w

$shift_register = '0000';

$input_data = ' ';
$output_data = ' ';

print " $input_data -> $shift_register -> $output_data (pre-shifting)\n";

while(defined($input_data=(<DATA>))) {

chomp($input_data);

$shift_register = $input_data . $shift_register; # prepending $input_data char
$output_data = chop( $shift_register ); # shifting off the last char to $output_data

print " $input_data -> $shift_register -> $output_data\n";
}

__DATA__
1
1
1
0
1
1
1
0
0
0
1
0
1
0
1
1
1
1
0
0
0
0


--
Chris Richmond | I don't speak for Intel & vise versa


Dr.Ruud 05-25-2006 06:19 PM

Re: more efficient shift register?
 
Chris Richmond - MD6-FDC ~ schreef:

> -> 0000 -> (pre-shifting)
> 1 -> 1000 -> 0
> 1 -> 1100 -> 0
>
> <snip>
> __DATA__
> 1
> 1


#!/usr/bin/perl
use strict ;
use warnings ;

my $data = '1110111000101011110000' ;

my @val = split '', '0000' ;
my @data = split '', $data ;

local $" = '' ;
print " -> @val -> (pre-shifting)\n" ;

for my $i (0 .. $#data)
{
unshift @val, shift @data ;
print "$val[0] -> @val[0..3] -> $val[4]\n" ;
}

--
Affijn, Ruud

"Gewoon is een tijger."



DJ Stunks 05-25-2006 06:19 PM

Re: more efficient shift register?
 
Chris Richmond - MD6-FDC ~ wrote:
> Folks,
>
> This is a trivial example of a larger problem I'm trying to
> speed up. What I want to know is if there is a faster way
> to impliment a shift register for text chars. I already tried
> using arrays and unshifting and popping, and it was 2-3x slower.
>
> Thx, Chris
>
> Output:
>
> -> 0000 -> (pre-shifting)
> 1 -> 1000 -> 0
> 1 -> 1100 -> 0
> 1 -> 1110 -> 0
> 0 -> 0111 -> 0
> 1 -> 1011 -> 1
> 1 -> 1101 -> 1
> 1 -> 1110 -> 1
> 0 -> 0111 -> 0
> 0 -> 0011 -> 1
> 0 -> 0001 -> 1
> 1 -> 1000 -> 1
> 0 -> 0100 -> 0
> 1 -> 1010 -> 0
> 0 -> 0101 -> 0
> 1 -> 1010 -> 1
> 1 -> 1101 -> 0
> 1 -> 1110 -> 1
> 1 -> 1111 -> 0
> 0 -> 0111 -> 1
> 0 -> 0011 -> 1
> 0 -> 0001 -> 1
> 0 -> 0000 -> 1
>
>
> Script:
>
> #!/usr/bin/perl -w
>
> $shift_register = '0000';
>
> $input_data = ' ';
> $output_data = ' ';
>
> print " $input_data -> $shift_register -> $output_data (pre-shifting)\n";
>
> while(defined($input_data=(<DATA>))) {
>
> chomp($input_data);
>
> $shift_register = $input_data . $shift_register; # prepending $input_data char
> $output_data = chop( $shift_register ); # shifting off the last char to $output_data
>
> print " $input_data -> $shift_register -> $output_data\n";
> }
>
> __DATA__
> 1
> 1
> 1
> 0
> 1
> 1
> 1
> 0
> 0
> 0
> 1
> 0
> 1
> 0
> 1
> 1
> 1
> 1
> 0
> 0
> 0
> 0
>


Try benchmarking this. I'm sure C will perform this operation much
faster than Perl. I'm pretty sure Bit::Vector is a core module.

#!/usr/bin/perl

use strict;
use warnings;

use Bit::Vector;

my $shift_register = Bit::Vector->new(4);

my ($input_data,$output_data) = (' ',' ');

printf "%s -> %s -> %s (pre-shifting)\n",
$input_data, $shift_register->to_Bin(), $output_data;

while( $input_data = <DATA> ) {
chomp $input_data;

$output_data = $shift_register->shift_right($input_data);

printf "%s -> %s -> %s\n",
$input_data, $shift_register->to_Bin(), $output_data;
}

__DATA__
1
1
1
0
1
1
1
0
0
0
1
0
1
0
1
1
1
1
0
0
0
0

-jp


Dr.Ruud 05-25-2006 06:36 PM

Re: more efficient shift register?
 
Dr.Ruud schreef:
> Chris Richmond - MD6-FDC ~ schreef:
>
>> -> 0000 -> (pre-shifting)
>> 1 -> 1000 -> 0
>> 1 -> 1100 -> 0
>>
>> <snip>
>> __DATA__
>> 1
>> 1

>
> #!/usr/bin/perl
> use strict ;
> use warnings ;
>
> my $data = '1110111000101011110000' ;
>
> my @val = split '', '0000' ;
> my @data = split '', $data ;
>
> local $" = '' ;
> print " -> @val -> (pre-shifting)\n" ;
>
> for my $i (0 .. $#data)
> {
> unshift @val, shift @data ;
> print "$val[0] -> @val[0..3] -> $val[4]\n" ;
> }


String-variant:

#!/usr/bin/perl
use strict ;
use warnings ;

my $data = reverse ('0000' . '1110111000101011110000') ;

my $i = length( $data ) - 4 ;

printf " -> %s -> (pre-shifting)\n", substr( $data, $i, 4 );

while ( --$i >= 0 )
{
printf "%s -> %s -> %s\n", substr( $data, $i, 1 )
, substr( $data, $i, 4 )
, substr( $data, $i+4, 1 ) ;
}

--
Affijn, Ruud

"Gewoon is een tijger."



Ralph Ganszky 05-25-2006 07:51 PM

Re: more efficient shift register?
 

"Chris Richmond - MD6-FDC ~" <crichmon@filc8046.fm.intel.com> wrote in
message news:e54prh$p8r$1@news01.intel.com...
> Folks,
>
> This is a trivial example of a larger problem I'm trying to
> speed up. What I want to know is if there is a faster way
> to impliment a shift register for text chars. I already tried
> using arrays and unshifting and popping, and it was 2-3x slower.
>
> Thx, Chris
>
> Output:
>
> -> 0000 -> (pre-shifting)
> 1 -> 1000 -> 0
> 1 -> 1100 -> 0
> 1 -> 1110 -> 0
> 0 -> 0111 -> 0
> 1 -> 1011 -> 1
> 1 -> 1101 -> 1
> 1 -> 1110 -> 1
>

.... snip...
>
>
> --
> Chris Richmond | I don't speak for Intel & vise versa
>


Hi Chris,

if you don't need the output character I would replace the lines
$shift_register = "$input_data$shift_register"; # prepending
$input_data char
$output_data = chop( $shift_register ); # shifting off the
last char to $output_data

by the line
$shift_register = sprintf("%4.4s", $input_data . $shift_register);

on my Hardware (Perl 5.8.7 on P4 3.2GHz) this executes tow times faster than
your code. If you need the output, I've not found anything faster than your
solution.

I've assumed that you would like to shift any type of text instead of only
binary numbers.

Regards
Ralph



Chris Richmond - MD6-FDC ~ 05-25-2006 07:56 PM

Re: more efficient shift register?
 
In article <e553g4.ks.1@news.isolution.nl>,
"Dr.Ruud" <rvtol+news@isolution.nl> writes:
> my @val = split '', '0000' ;
> my @data = split '', $data ;
>
> local $" = '' ;
> print " -> @val -> (pre-shifting)\n" ;
>
> for my $i (0 .. $#data)
> {
> unshift @val, shift @data ;
> print "$val[0] -> @val[0..3] -> $val[4]\n" ;
> }


This works, but also similar to what I tried that was much slower.
The actual register strings are varying widths.

Thx, Chris

--
Chris Richmond | I don't speak for Intel & vise versa

Brian Wakem 05-25-2006 07:57 PM

Re: more efficient shift register?
 
Chris Richmond - MD6-FDC ~ wrote:

> Folks,
>
> This is a trivial example of a larger problem I'm trying to
> speed up. What I want to know is if there is a faster way
> to impliment a shift register for text chars. I already tried
> using arrays and unshifting and popping, and it was 2-3x slower.
>
> Thx, Chris
>
> Output:
>
> -> 0000 -> (pre-shifting)
> 1 -> 1000 -> 0
> 1 -> 1100 -> 0
> 1 -> 1110 -> 0
> 0 -> 0111 -> 0
> 1 -> 1011 -> 1
> 1 -> 1101 -> 1
> 1 -> 1110 -> 1
> 0 -> 0111 -> 0
> 0 -> 0011 -> 1
> 0 -> 0001 -> 1
> 1 -> 1000 -> 1
> 0 -> 0100 -> 0
> 1 -> 1010 -> 0
> 0 -> 0101 -> 0
> 1 -> 1010 -> 1
> 1 -> 1101 -> 0
> 1 -> 1110 -> 1
> 1 -> 1111 -> 0
> 0 -> 0111 -> 1
> 0 -> 0011 -> 1
> 0 -> 0001 -> 1
> 0 -> 0000 -> 1
>
>
> Script:
>
> #!/usr/bin/perl -w
>
> $shift_register = '0000';
>
> $input_data = ' ';
> $output_data = ' ';
>
> print " $input_data -> $shift_register -> $output_data (pre-shifting)\n";
>
> while(defined($input_data=(<DATA>))) {
>
> chomp($input_data);
>
> $shift_register = $input_data . $shift_register; # prepending
> $input_data char
> $output_data = chop( $shift_register ); # shifting off the
> last char to $output_data
>
> print " $input_data -> $shift_register -> $output_data\n";
> }
>
> __DATA__
> 1
> 1
> 1
> 0
> 1
> 1
> 1
> 0
> 0
> 0
> 1
> 0
> 1
> 0
> 1
> 1
> 1
> 1
> 0
> 0
> 0
> 0
>
>



You'll need to bechmark it of course, but you could try substr.

while(defined($input_data=(<DATA>))) {
chomp($input_data);
$output_data = substr($shift_register,-1,1);
$shift_register = $input_data . substr($shift_register,0,3);
print " $input_data -> $shift_register -> $output_data\n";
}


--
Brian Wakem
Email: http://homepage.ntlworld.com/b.wakem/myemail.png

Dr.Ruud 05-25-2006 08:30 PM

Re: more efficient shift register?
 
Dr.Ruud schreef:

> my $data = reverse ('0000' . '1110111000101011110000') ;


Clearer:

my $data = '0000' . reverse '1110111000101011110000' ;

--
Affijn, Ruud

"Gewoon is een tijger."



Dr.Ruud 05-25-2006 08:32 PM

Re: more efficient shift register?
 
Chris Richmond - MD6-FDC ~ schreef:
> Dr.Ruud:


>> my @val = split '', '0000' ;
>> my @data = split '', $data ;
>>
>> local $" = '' ;
>> print " -> @val -> (pre-shifting)\n" ;
>>
>> for my $i (0 .. $#data)
>> {
>> unshift @val, shift @data ;
>> print "$val[0] -> @val[0..3] -> $val[4]\n" ;
>> }

>
> This works, but also similar to what I tried that was much slower.
> The actual register strings are varying widths.


Do you mean this is faster or slower than what you had?

If slower, could you tell more about your data then? Which widths do you
talk about: 32, 64, 128, ...?

--
Affijn, Ruud

"Gewoon is een tijger."



xhoster@gmail.com 05-25-2006 08:58 PM

Re: more efficient shift register?
 
crichmon@eng.fm.intel.com wrote:
> Folks,
>
> This is a trivial example of a larger problem I'm trying to
> speed up. What I want to know is if there is a faster way
> to impliment a shift register for text chars. I already tried
> using arrays and unshifting and popping, and it was 2-3x slower.


The code you posted spents most of it's time in the print statement.
If you are serious about optimizing this, you need to come up with
a better test harness--a little less trivial but lot more realistic.

Unless of course you real problem includes the print statement. In that
case, the shift register is probably not your problem.

Xho

--
-------------------- http://NewsReader.Com/ --------------------
Usenet Newsgroup Service $9.95/Month 30GB


All times are GMT. The time now is 05:38 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.