CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Advanced:
Effeciently determining if a list is contained in

 



PERLonLINE
stranger

Sep 18, 2001, 3:48 AM

Post #1 of 4 (1276 views)
Effeciently determining if a list is contained in Can't Post

Hi Perl Gurus,

this is my first post in this forum.
So I may ask something that is in the FAQs or has been posted already a thousand times.
But I'm a bit rushed because I have to accomplish a task with Perl right now.
I have searched my available ressources (i.e. Perl's own POD, FAQ, the "Perl Cook Book" other ORA Books, posting in a German Perl forum).
I would consider myself rather a Perl rookie, but I post here in the advanced section because I hope to find the gurus here.

My task at hand is quite simple to describe.
Let me give you two lines of a similar example:

# fill list @a from lower to upper boundary
# with some pseudo random numbers
# (just to have something to play with ;-)
($lb, $ub) = (1, 100);
@a = map int(rand($ub - $lb) + 1) + $lb), ($lb..$ub);
# fill a 2nd, smaller list @b
@b = map int(rand($ub - $lb) + 1) + $lb), ($lb..$ub/5);

Now I would like, for instance, to find all the indices of array @a which hold values from array @b.

To me this seems to call for some Schwartzian transform to do it most effeciently through some cleverly linked greps and maps.
I think one would have to construct some interim anonymous array ref like "map { [$idx++, $_ ] } @a" to grep with through the values of @b, and map the result again into a new list.
But I cannot find the trick.
Of course, I could do it in ordinary foreach loops, but this doesn't seem to be very efficient.




mhx
Enthusiast

Sep 18, 2001, 5:13 AM

Post #2 of 4 (1273 views)
Re: Effeciently determining if a list is contained in [In reply to] Can't Post

Don't know if this is very efficient, but here's what came to my mind immediately:

Code
($lb, $ub) = (1, 100); 
@a = map { int(rand($ub - $lb) + 1) + $lb } $lb..$ub;
@b = map { int(rand($ub - $lb) + 1) + $lb } $lb..$ub/5;

@h{@b} = (0)x@b;
@i = grep exists $h{$a[$_]}, 0..$#a;

print "@i\n";

Hope this helps.

-- Marcus


Code
s$$ab21b8d15c3d97bd6317286d$;$"=547269736;split'i',join$,,map{chr(($*+= 
($">>=1)&1?-hex:hex)+0140)}/./g;$"=chr$";s;.;\u$&;for@_[0,2];print"@_,"



PERLonLINE
stranger

Sep 18, 2001, 6:42 AM

Post #3 of 4 (1271 views)
Re: Effeciently determining if a list is contained in [In reply to] Can't Post

Hello Marcus,

you really are a Perl guru because your solution is concise and elegant.
I feared to have to involve some CPAN Set::* module.
But then, as you may have seen from my question, I'm mathematically not very skilled (especially when it comes to sets ;-)

That I haven't realized the hash trick myself :-(

As you can see from below, I had to device the hash trick a second time to strip possible multiple occurences from the result set.
Btw, is this in mathematical lingo an intersection, or how is it called?

($lb, $ub) = (1, 100);
@a = map int(rand($ub-$lb+1)+$lb), ($lb..$ub);
@b = map int(rand($ub-$lb+1)+$lb), ($lb..$ub/5);
@h{@b} = (0)x@b;
@c = map { $a[$_] } grep exists $h{$a[$_]}, 0..$#a;
%h = ();
@h{@c} = (0)x@c;
@c = ();
@c = sort keys %h;
print "single occurences of elements from \@a in \@b:\n@c\n";
print "\@b:\n@{[sort @b]}\n";




mhx
Enthusiast

Sep 18, 2001, 7:22 AM

Post #4 of 4 (1270 views)
Re: Effeciently determining if a list is contained in [In reply to] Can't Post

What about the following? Wink

Code
($lb, $ub) = (1, 100); 
@a = map int(rand($ub-$lb+1)+$lb), ($lb..$ub);
@b = map int(rand($ub-$lb+1)+$lb), ($lb..$ub/5);

$h{$_}++ for @a; # collect counts of values in @a
@c = sort { $a <=> $b } # sort numerically
grep { exists $h{$_} && $h{$_} == 1 } # check if the count is 1
grep !$_{$_}++, @b; # get only unique elements of @b

-- Marcus


Code
s$$ab21b8d15c3d97bd6317286d$;$"=547269736;split'i',join$,,map{chr(($*+= 
($">>=1)&1?-hex:hex)+0140)}/./g;$"=chr$";s;.;\u$&;for@_[0,2];print"@_,"


 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives