Array containment

[Jan Eden]

Hi all,

a while ago, I wrote a little subroutine to test wether a given element is in a given array:

sub contains {

my $result = 0;
my $contained = shift;
foreach (@_) {
if ($_ eq $contained){ $result = 1; }
}
$result;
}

Now I found a nicer solution in "Learning Perl Objects, References & Modules" and adapted it:

sub contains {
my $contained = shift;
my $result = grep { $contained eq $_ } @_;
}

Smart. But immediately after giving this example, Randal notes that this isnot the best solution for testing large arrays. Can anyone give me a hint to what he might have meant? Or, to put it this way: Randal, what did you think of writing this?

Thanks,

Jan
--
The day Microsoft makes something that doesn't suck is the day they start selling vacuum cleaners.

[Rob Dixon]

Jan Eden wrote:

>
> a while ago, I wrote a little subroutine to test wether a given element is in a
> given array:
>
> sub contains {
>
> my $result = 0;
> my $contained = shift;
> foreach (@_) {
> if ($_ eq $contained){ $result = 1; }
> }
> $result;
> }
>
> Now I found a nicer solution in "Learning Perl Objects, References & Modules"
> and adapted it:
>
> sub contains {
> my $contained = shift;
> my $result = grep { $contained eq $_ } @_;
> }
>
> Smart. But immediately after giving this example, Randal notes that this is not
> the best solution for testing large arrays. Can anyone give me a hint to what he
> might have meant? Or, to put it this way: Randal, what did you think of writing
> this?

Hi Jan.

If you want to test a static (unchanging) array for the containment of many different
values you should build a hash out of the array elements:

my @data = 'a' .. 'm';
my %data_hash;
@data_hash{@data} = ();

Then simply check for the existence of a hash element with the required value as
a key:


for (split '', 'robdixon') {
if (exists $data_hash{$_}) {
printf "Element %s found in \@data\n", $_;
}
else {
printf "Element %s isn't in \@data\n", $_;
}
}

**OUTPUT

Element r isn't in @data
Element o isn't in @data
Element b found in @data
Element d found in @data
Element i found in @data
Element x isn't in @data
Element o isn't in @data
Element n isn't in @data

But this isn't practical if the hash keeps needing to be rebuilt because the array
hash changed. Depending on your data it may be a good idea to start with a hash anyway,
but for a general overview of the topic look at:

perldoc -q "array contains"

HTH,

Rob

[Jan Eden]

Hi Rob,

Rob Dixon wrote:

>Hi Jan.
>
>If you want to test a static (unchanging) array for the containment of many
>different
>values you should build a hash out of the array elements:
>
> my @data = 'a' .. 'm';
> my %data_hash;
> @data_hash{@data} = ();
>

I see. But shouldn't the last line be a complete hash slice:

$data_hash{@array} = ();

>Then simply check for the existence of a hash element with the
>required value as a key:
>
>
> for (split '', 'robdixon') {
> if (exists $data_hash{$_}) {
> printf "Element %s found in \@data\n", $_;
> }
> else {
> printf "Element %s isn't in \@data\n", $_;
> }
> }
>

I thought of the exists function, but I always hesitate to use a hash if mydata is not really hash-like. Thinking perlish is still on my to do list.

Thank you!

- Jan
--
How many Microsoft engineers does it take to screw in a lightbulb? None. They just redefine "dark" as the new standard.

[James Edward Gray II]

On Feb 10, 2004, at 5:04 AM, Jan Eden wrote:

> Hi all,

Howdy.

> a while ago, I wrote a little subroutine to test wether a given
> element is in a given array:
>
> sub contains {
>
> my $result = 0;
> my $contained = shift;
> foreach (@_) {
> if ($_ eq $contained){ $result = 1; }
> }
> $result;
> }
>

That works, though I would probably drop the extra variable.

sub contains {
my $contained = shift;
foreach (@_) { return 1 if $_ eq $contained; }
return 0;
}

> Now I found a nicer solution in "Learning Perl Objects, References &
> Modules" and adapted it:
>
> sub contains {
> my $contained = shift;
> my $result = grep { $contained eq $_ } @_;
> }

Again, no need for the variable.

sub contains {
my $contained = shift;
return grep $_ eq $contained, @_;
}

> Smart. But immediately after giving this example, Randal notes that
> this is not the best solution for testing large arrays. Can anyone
> give me a hint to what he might have meant? Or, to put it this way:
> Randal, what did you think of writing this?

I'm not Randal, but will I do? <laughs>

The problem with both of your posted solutions is that they run the
entire list of elements. The question is, "Is $contained in there
somewhere?" That means that the first time we see it, we have answered
that question. If we have 20,000 elements and we find it in the second
slot, we waste 19,998 lookups, right?

We can't fix this in the grep() version, because grep() finds ALL
matches, not just the first. It must walk the list to do its job.
However, I snuck in a fix for your version above. Go take a peak...

James

[James Edward Gray II]

On Feb 10, 2004, at 8:53 AM, Jan Eden wrote:

> Rob Dixon wrote:
>

>> @data_hash{@data} = ();
>>

> I see. But shouldn't the last line be a complete hash slice:
>
> $data_hash{@array} = ();

Rob's line is a hash slice. Note the @. Yours is a simple hash
lookup, one scalar value affected, thus the $.

James

[Jan Eden]

James Edward Gray II wrote:

>That works, though I would probably drop the extra variable.
>
>sub contains {
> my $contained = shift;
> foreach (@_) { return 1 if $_ eq $contained; }
> return 0;
>}
>

Perfect. Returns 1 as soon as it finds the element.

>I'm not Randal, but will I do? <laughs>
>

To my experience, your postings have been highly informative.

>The problem with both of your posted solutions is that they run the
>entire list of elements. The question is, "Is $contained in there
>somewhere?" That means that the first time we see it, we have answered
>that question. If we have 20,000 elements and we find it in the second
>slot, we waste 19,998 lookups, right?
>
>We can't fix this in the grep() version, because grep() finds ALL
>matches, not just the first. It must walk the list to do its job.
>However, I snuck in a fix for your version above. Go take a peak...

Your suggestion is certainly a "peak" in elegant programming. ;)

Thanks! Jan
--
Either this man is dead or my watch has stopped. - Groucho Marx

[Jan Eden]

James Edward Gray II wrote:

>On Feb 10, 2004, at 8:53 AM, Jan Eden wrote:
>

>> Rob Dixon wrote:
>>

>>> @data_hash{@data} = ();
>>>

>> I see. But shouldn't the last line be a complete hash slice:
>>
>> $data_hash{@array} = ();

>
>Rob's line is a hash slice. Note the @. Yours is a simple hash
>lookup, one scalar value affected, thus the $.
>

My mistake. Thanks.

- Jan
--
If all else fails read the instructions. - Donald Knuth

[Rob Dixon]

James wrote:

>
> On Feb 10, 2004, at 5:04 AM, Jan Eden wrote:
>

> > Now I found a nicer solution in "Learning Perl Objects, References &
> > Modules" and adapted it:
> >
> > sub contains {
> > my $contained = shift;
> > my $result = grep { $contained eq $_ } @_;
> > }

>
> Again, no need for the variable.
>
> sub contains {
> my $contained = shift;
> return grep $_ eq $contained, @_;
> }
>
> We can't fix this in the grep() version, because grep() finds ALL
> matches, not just the first. It must walk the list to do its job.
> However, I snuck in a fix for your version above. Go take a peak...

What do you mean here James? All I can see is that you changed

grep BLOCK

into

grep EXPRESSION

reversed the operands of 'eq' and dropped the assignment.

Am I missing something?

Rob

[James Edward Gray II]

On Feb 10, 2004, at 11:20 AM, Rob Dixon wrote:

> James wrote:

>>
>> On Feb 10, 2004, at 5:04 AM, Jan Eden wrote:
>>

>>> Now I found a nicer solution in "Learning Perl Objects, References &
>>> Modules" and adapted it:
>>>
>>> sub contains {
>>> my $contained = shift;
>>> my $result = grep { $contained eq $_ } @_;
>>> }

>>
>> Again, no need for the variable.
>>
>> sub contains {
>> my $contained = shift;
>> return grep $_ eq $contained, @_;
>> }
>>
>> We can't fix this in the grep() version, because grep() finds ALL
>> matches, not just the first. It must walk the list to do its job.
>> However, I snuck in a fix for your version above. Go take a peak...

>
> What do you mean here James? All I can see is that you changed
>
> grep BLOCK
>
> into
>
> grep EXPRESSION
>
> reversed the operands of 'eq' and dropped the assignment.
>
> Am I missing something?

Yes, you did. :D

I was talking about the fix to Jan's version, though I probably should
have made that more clear. It does not need to walk the whole list.
Here it is again:

sub contains {
my $contained = shift;
foreach (@_) { return 1 if $_ eq $contained; }
return 0;
}

I said I cannot fix the grep() version. I'm just not that cool.
<laughs>

James

[Jeff 'Japhy' Pinyan]

On Feb 10, James Edward Gray II said:

>I said I cannot fix the grep() version. I'm just not that cool.

I guess I'm cooler than you. ;)

sub find {
my $wanted = shift;
my $found = 0;
{ grep $_ eq $wanted && ++$found && last, @_ }
return $found;
}

--
Jeff "japhy" Pinyan [email]japhy@pobox.com[/email] [url]http://www.pobox.com/~japhy/[/url]
RPI Acacia brother #734 [url]http://www.perlmonks.org/[/url] [url]http://www.cpan.org/[/url]
<stu> what does y/// stand for? <tenderpuss> why, yansliterate of course.
[ I'm looking for programming work. If you like my work, let me know. ]

[Jeff 'Japhy' Pinyan]

On Feb 10, Jeff 'japhy' Pinyan said:

>On Feb 10, James Edward Gray II said:
>

>>I said I cannot fix the grep() version. I'm just not that cool.

>
>I guess I'm cooler than you. ;)
>
> sub find {
> my $wanted = shift;
> my $found = 0;
> { grep $_ eq $wanted && ++$found && last, @_ }
> return $found;
> }

Or even:

sub find {
my $wanted = shift;
grep $_ eq $wanted && return(1), @_;
return 0;
}

--
Jeff "japhy" Pinyan [email]japhy@pobox.com[/email] [url]http://www.pobox.com/~japhy/[/url]
RPI Acacia brother #734 [url]http://www.perlmonks.org/[/url] [url]http://www.cpan.org/[/url]
<stu> what does y/// stand for? <tenderpuss> why, yansliterate of course.
[ I'm looking for programming work. If you like my work, let me know. ]

[Rob Dixon]

Jeff 'Japhy' Pinyan wrote:

>

> >I said I cannot fix the grep() version. I'm just not that cool.

>
> I guess I'm cooler than you. ;)
>
> sub find {
> my $wanted = shift;
> my $found = 0;
> { grep $_ eq $wanted && ++$found && last, @_ }
> return $found;
> }

Ouch! Nobody knows you can do that. Please keep it a secret
or this will become an 'obfuscated Perl' group :)

And these shortcut logical operators annoy me because
they break the 'don't do something for its side-effects'
rule. This is the same as

sub find {
my $wanted = shift;
my $found = ''; # The preferred 'false'
{
grep { $found++, last if $_ eq $wanted } @_;
}
return $found;
}

Anyway, since we're in a subroutine.

sub find {
my $wanted = shift;
grep { return 1 if $_ eq $wanted } @_;
}

which returns zero instead of 'undef', but hey..

Rob

[Jan Eden]

James, Rob, Japhy,

I am impressed, really. Thank you!

Rob, I read the perlfaq paragraph you mentioned and found that it proposes a solution which does not make use of 'exists':

@blues = qw/azure cerulean teal turquoise lapis-lazuli/;
%is_blue = ();
for (@blues) { $is_blue{$_} = 1 }

Now, I had the idea to combine your hash slice with this solution doing:

@blues = qw/azure cerulean teal turquoise lapis-lazuli/;
@is_blue{@blues} = 1;

But since I have only a single number on the right side of the assignment function, only one hash element gets 1. Is there a way to automatically assign "1" to all elements with the hash slice notation (i.e. without using a loop)?

I promise to drop the subject after this question. ;)

Thanks again,

Jan
--
There are two major products that come out of Berkeley: LSD and UNIX. We don't believe this to be a coincidence. - Jeremy S. Anderson

[James Edward Gray II]

On Feb 10, 2004, at 2:39 PM, Jan Eden wrote:

> James, Rob, Japhy,
>
> I am impressed, really. Thank you!

Me too. We haven't scared you off yet. :) Impressive.

> Rob, I read the perlfaq paragraph you mentioned and found that it
> proposes a solution which does not make use of 'exists':

What's wrong with exists()? I like exists() and you're going to hurt
it's feelings. :)

> @blues = qw/azure cerulean teal turquoise lapis-lazuli/;
> %is_blue = ();
> for (@blues) { $is_blue{$_} = 1 }
>
> Now, I had the idea to combine your hash slice with this solution
> doing:
>
> @blues = qw/azure cerulean teal turquoise lapis-lazuli/;
> @is_blue{@blues} = 1;

@is_blue{@blues} = (1) x scalar @blues;

> But since I have only a single number on the right side of the
> assignment function, only one hash element gets 1. Is there a way to
> automatically assign "1" to all elements with the hash slice notation
> (i.e. without using a loop)?

You could also use map() I guess, if you don't consider that a loop:

@is_blue{@blues} = map { 1 } 0..$#blues;

> I promise to drop the subject after this question. ;)

I don't mind. I'm not even Rob. ;)

James

[Rob Dixon]

Jan Eden wrote:

>
> Rob, I read the perlfaq paragraph you mentioned and found that it proposes a
> solution which does not make use of 'exists':
>
> @blues = qw/azure cerulean teal turquoise lapis-lazuli/;
> %is_blue = ();
> for (@blues) { $is_blue{$_} = 1 }

It's not for me to rewrite the docs (or perhaps it is?) but

for (@blues) { $is_blue{$_} = 1 }

does the same thing as

@is_blue{@blues} = (1) x @blues;

but (I would guess) the former is slower because it has a source-level loop.

That means that it's the equivalent to

@is_blue{@blues} = ();

(which the parallel to my code) except that the value for each hash
element is '1' instead of 'undef', which means that you could write
the tidier

if ($is_blue{$_})

instead of

if (exists $is_blue{$_})

> Now, I had the idea to combine your hash slice with this solution doing:
>
> @blues = qw/azure cerulean teal turquoise lapis-lazuli/;
> @is_blue{@blues} = 1;
>
> But since I have only a single number on the right side of the assignment
> function, only one hash element gets 1. Is there a way to automatically assign
> "1" to all elements with the hash slice notation (i.e. without using a loop)?

I think I just showed you that before you asked. You need as many '1's as there
are hash elements, so you need to assign 'scalar @blues' copies of the list '(1)'.

@is_blue{@blues} = (1) x @blues

> I promise to drop the subject after this question. ;)

Believe me, we're really having fun thinking around your ideas: it's better
than working for a living :) While you're learning, please keep asking.

Rob

[John W. Krahn]

James Edward Gray II wrote:

>
> On Feb 10, 2004, at 2:39 PM, Jan Eden wrote:

> >
> > @blues = qw/azure cerulean teal turquoise lapis-lazuli/;
> > %is_blue = ();
> > for (@blues) { $is_blue{$_} = 1 }
> >
> > Now, I had the idea to combine your hash slice with this solution
> > doing:
> >
> > @blues = qw/azure cerulean teal turquoise lapis-lazuli/;
> > @is_blue{@blues} = 1;

>
> @is_blue{@blues} = (1) x scalar @blues;
>

> > But since I have only a single number on the right side of the
> > assignment function, only one hash element gets 1. Is there a way to
> > automatically assign "1" to all elements with the hash slice notation
> > (i.e. without using a loop)?

>
> You could also use map() I guess, if you don't consider that a loop:
>
> @is_blue{@blues} = map { 1 } 0..$#blues;

And if you don't really need the @blues array:

my %is_blue = map { $_ => 1 } qw/azure cerulean teal turquoise
lapis-lazuli/;



John
--
use Perl;
program
fulfillment

[Jan Eden]

Rob, James,

James Edward Gray II wrote:

>On Feb 10, 2004, at 2:39 PM, Jan Eden wrote:

>> Rob, I read the perlfaq paragraph you mentioned and found that it
>> proposes a solution which does not make use of 'exists':

>
>What's wrong with exists()? I like exists() and you're going to hurt
>it's feelings. :)
>

It has six characters which can be left out to minimize typing.

>You could also use map() I guess, if you don't consider that a loop:
>
>@is_blue{@blues} = map { 1 } 0..$#blues;
>

For some irrational reason, I consider this more of a loop than your first/Rob's solution below.

Rob Dixon wrote:

>It's not for me to rewrite the docs (or perhaps it is?) but
>
>for (@blues) { $is_blue{$_} = 1 }
>
>does the same thing as
>
>@is_blue{@blues} = (1) x @blues;
>

I finally came up with an idea of my own, just when I got up this morning:

@is_blue{@blues} = 1 .. @blues;

This way each of the hash keys gets a value different from zero, so

>if ($is_blue{$_})

still works. Now it might be hard to determine which of these two is faster.

There's really more than one way to do it.

Thanks to you all, for patience and friendliness,

Jan
--
These are my principles and if you don't like them... well, I have others. - Groucho Marx

[James Edward Gray II]

On Feb 11, 2004, at 12:14 AM, Jan Eden wrote:

> James Edward Gray II wrote:
>

>> On Feb 10, 2004, at 2:39 PM, Jan Eden wrote:

>

>>> Rob, I read the perlfaq paragraph you mentioned and found that it
>>> proposes a solution which does not make use of 'exists':

>>
>> What's wrong with exists()? I like exists() and you're going to hurt
>> it's feelings. :)
>>

> It has six characters which can be left out to minimize typing.

All of the solutions posted added more than six characters, so you'll
need multiple tests before you start saving keystrokes. Make sure
you're lazy in the good way. ;)

>> You could also use map() I guess, if you don't consider that a loop:
>>
>> @is_blue{@blues} = map { 1 } 0..$#blues;
>>

> For some irrational reason, I consider this more of a loop than your
> first/Rob's solution below.

map() is a loop, to be sure, but it comes from inside perl and thus
should be faster much of the time than a loop you create yourself.
(Compare 'foreach' and 'map_hash' in the results below.)

>> It's not for me to rewrite the docs (or perhaps it is?) but
>>
>> for (@blues) { $is_blue{$_} = 1 }
>>
>> does the same thing as
>>
>> @is_blue{@blues} = (1) x @blues;
>>

> I finally came up with an idea of my own, just when I got up this
> morning:
>
> @is_blue{@blues} = 1 .. @blues;
>
> This way each of the hash keys gets a value different from zero, so
>

>> if ($is_blue{$_})

>
> still works.

Clever.

> Now it might be hard to determine which of these two is faster.

Why would that be hard? ;)

#!/usr/bin/perl

use strict;
use warnings;

use Benchmark;

my @blues = qw/azure cerulean teal turquoise lapis-lazuli/;
my %is_blue;

timethese( 3000000, {
foreach => '$is_blue{$_} = 1 foreach @blues',
hash_slice => '@is_blue{@blues}',
all_ones => '@is_blue{@blues} = (1) x @blues',
map_ones => '@is_blue{@blues} = map { 1 } 0..$#blues',
map_hash => '%is_bllue = map { $_ => 1 } @blues',
range => '@is_blue{@blues} = 1 .. @blues'
} );

__END__

And the results, from my G5:

Benchmark: timing 3000000 iterations of all_ones, foreach, hash_slice,
map_hash, map_ones, range...
all_ones: 1 wallclock secs ( 1.76 usr + 0.00 sys = 1.76 CPU) @
1704545.45/s (n=3000000)
foreach: 3 wallclock secs ( 2.39 usr + 0.00 sys = 2.39 CPU) @
1255230.13/s (n=3000000)
hash_slice: 1 wallclock secs ( 0.94 usr + 0.00 sys = 0.94 CPU) @
3191489.36/s (n=3000000)
map_hash: 2 wallclock secs ( 1.43 usr + 0.00 sys = 1.43 CPU) @
2097902.10/s (n=3000000)
map_ones: 4 wallclock secs ( 3.91 usr + 0.00 sys = 3.91 CPU) @
767263.43/s (n=3000000)
range: 1 wallclock secs ( 2.20 usr + 0.00 sys = 2.20 CPU) @
1363636.36/s (n=3000000)

Looks like Rob is still the man to beat. :D

James

[Rob Dixon]

Jan Eden wrote:

>
> Rob, James,
>
> James Edward Gray II wrote:

> >
> > What's wrong with exists()? I like exists() and you're going to hurt
> > it's feelings. :)
> >

>
> It has six characters which can be left out to minimize typing.

Proper Perl programmers like typing ;) And so do you given:

> I finally came up with an idea of my own, just when I got up this morning:
>
> @is_blue{@blues} = 1 .. @blues;

which is nine extra characters instead of six :)

> This way each of the hash keys gets a value different from zero, so

Ah! "different from": British English at last!

> >if ($is_blue{$_})

>
> still works.

I have to say I like it, but it needs to be commented to say that the the
hash values are irrelevant but need to be 'true'. If your code does anything
specific it needs to have a reason.

> Now it might be hard to determine which of these two is faster.

Development time is many millions of times more expensive than processor
time. Try to make it run faster /only/ if it's too slow; otherwise
make it maintainable above everything else.

> There's really more than one way to do it.

Strictly, there are infinite ways. Perl is rich in that there are usually
many /sensible/ ways to express a solution. Hence, I suppose, this group's
enthusiasm: C, and even C++, cannot generate this level of enthusiasm.

> Thanks to you all, for patience and friendliness,

Thanks to you Jan.

Rob

[Jan Eden]

James Edward Gray II wrote:

>> Now it might be hard to determine which of these two is faster.

>And the results, from my G5:
>
>Benchmark: timing 3000000 iterations of all_ones, foreach, hash_slice,
>map_hash, map_ones, range...
> all_ones: 1 wallclock secs ( 1.76 usr + 0.00 sys = 1.76 CPU) @
>1704545.45/s (n=3000000)
> foreach: 3 wallclock secs ( 2.39 usr + 0.00 sys = 2.39 CPU) @
>1255230.13/s (n=3000000)
>hash_slice: 1 wallclock secs ( 0.94 usr + 0.00 sys = 0.94 CPU) @
>3191489.36/s (n=3000000)
> map_hash: 2 wallclock secs ( 1.43 usr + 0.00 sys = 1.43 CPU) @
>2097902.10/s (n=3000000)
> map_ones: 4 wallclock secs ( 3.91 usr + 0.00 sys = 3.91 CPU) @
>767263.43/s (n=3000000)
> range: 1 wallclock secs ( 2.20 usr + 0.00 sys = 2.20 CPU) @
>1363636.36/s (n=3000000)
>
>Looks like Rob is still the man to beat. :D
>

Dang. Ok, Rob's original idea is the fastest solution, but he has to use exists later. Of the solutions not using exists, I come in third (range). That's not bad for an amateur or is it? ;)

- Jan
--
There are 10 kinds of people: those who understand binary, and those who don't