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

CGI/Perl Guide | Learning Center | Forums | Advertise | Login

Site Search: in


	MAIN INDEX	SEARCH POSTS	WHO'S ONLINE	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 (979 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 (976 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 (974 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 (973 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)

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