Because you are compressing sequences of bits rather than bytes I am not convinced that you will see a saving in space. It will depend on whether you have longish sequences of contiguous ones or zeros. If there are many short runs or singletons, your array of counts is likely to take more space than the vector. Unless I'm misunderstanding something, you need to have runs of more than eight ones or zeros before you break even if representing each count as a signed character; it gets worse if having to use shorts or longs.
Packing the array as signed characters would cater for up to 256128 contiguous ones or 255127 contiguous zeros. The following code uses a regex against a string representation of the vector but a pure vec solution as suggested by BrowserUk would be better. However, it illustrates my point.
use strict;
use warnings;
use 5.010;
my $vector = pack q{N*}, 0x01020304, 0x11121314;
my $bitStr = unpack q{b*}, $vector;
say $bitStr;
say q{=} x 20;
my $rcSign = do {
my $val = $bitStr =~ m{^1} ? 1 : -1;
sub { $val *= -1 }
};
my @posns = ( 0 );
my @lengths;
while ( $bitStr =~ m{(?x)
(?:
(?<=0)(?=1)
|
(?<=1)(?=0)
|
(?=\z)
)}g )
{
push @posns, pos $bitStr;
push @lengths, ( $posns[ -1 ] - shift @posns ) * $rcSign->();
}
my $rle = pack q{c*}, @lengths;
say q{Length of vector - }, length $vector;
say q{Length of packed RLE array - }, length $rle;
say q{=} x 20;
say qq{@lengths};
my @restored = unpack q{c*}, $rle;
say qq{@restored};
say q{=} x 20;
The output.
1000000001000000110000000010000010001000010010001100100000101000
====================
Length of vector - 8
Length of packed RLE array - 24
====================
-1 8 -1 6 -2 8 -1 5 -1 3 -1 4 -1 2 -1 3 -2 2 -1 5 -1 1 -1 3
-1 8 -1 6 -2 8 -1 5 -1 3 -1 4 -1 2 -1 3 -2 2 -1 5 -1 1 -1 3
====================
As I say, I may be misunderstanding something or your vector might consist of very long contiguous runs. I'd be interested to know whether you will see a benefit using RLE.
Update: Corrected the senior moment with maximum -ve and +ve values that can be held in a byte.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.