Subject:
|
Re: Bitstring vector to list conversion in Perl5
|
Newsgroups:
|
lugnet.off-topic.geek
|
Date:
|
Wed, 3 Jan 2001 22:30:57 GMT
|
Viewed:
|
120 times
|
| |
|
|
On Wed, Jan 03, 2001 at 05:45:17PM +0000, Todd Lehman wrote:
> Anyone know of a super-efficient way in Perl5 to convert a sparse bitstring
> vector to a list of integer-offset values (just the 1-bits) in Perl5?
>
> That is, if you had some $v that was created like so:
>
> my $v;
> my @n = (...some sorted sparse list of positive integer values...);
> foreach (@n) { vec($v,$_,1) = 1; }
>
> then what's the fastest way to regenerate @n later given $v ? Bitstring
> vectors can be |'d, &'d, and ^'d super-efficiently in Perl5, but I don't know
> the most efficient way to treat them as sparse lists -- i.e., looping over
> just the bits that are set and ignoring the bits that aren't set.
well, I can think of several ways of doing it, but since $v might be
millions of bits long, we don't really want to get the full list in memory
ever. So I guess the simplest way would be to run through the vector,
indexing the 1s:
-=-=-=-=-=-=-
$veclength = length unpack("b*",$v); # only because I don't know how many
# bits are in it - not efficient
@n = ();
for ($index=0;$index<$veclength,$index++) {
push @n, $index if vec($v,$index,1);
}
-=-=-=-=-=-=-
$veclength is terribly inefficient, but I could think of no way of finding
out the length of the vector - I'm sure you have that little bit of
information stored someplace...
this isn't the fastest way... you might be able to do something with
map, but you need to supply the broken down list to it as an argument,
so you'll still end up with the non-sparse array loaded in memory.
--
Dan Boger / dan@peeron.com / www.peeron.com / ICQ: 1130750
<set:9122_1>: Vehicles (DACTA/DUPLO/Toolo), '99, 76 pcs, 2 figs
|
|
Message has 1 Reply:
 | | Re: Bitstring vector to list conversion in Perl5
|
| (...) $veclength = length($v) * 8; It isn't precise, but it's fast -- and a few bits of slop would be perfectly OK here since the slop would be 0-bits. :-) (...) Well, plus, map{} is also almost always slower than looping (especially with use (...) (23 years ago, 4-Jan-01, to lugnet.off-topic.geek)
|
Message is in Reply To:
| | Bitstring vector to list conversion in Perl5
|
| Anyone know of a super-efficient way in Perl5 to convert a sparse bitstring vector to a list of integer-offset values (just the 1-bits) in Perl5? That is, if you had some $v that was created like so: my $v; my @n = (...some sorted sparse list of (...) (23 years ago, 3-Jan-01, to lugnet.off-topic.geek)
|
3 Messages in This Thread:
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
