Okay, you threw me on this one. Could someone please explain the above code. I am completely lost!

J. J. Horner
Linux, Perl, Apache, Stronghold, Unix
jhorner@knoxlug.org http://www.knoxlug.org/

It does the job tho' :)

Ok. With comments...

# define a hash to count the unique elements in @arr
my %check;

# @check{@arr} is a hash slice. It gives to all of the 
# values in %check where the key is an element from @arr.
# This is a list and it's also an lvalue (i.e. you can 
# assign values to it.
# 
# (1) x @arr (and I've corrected this from the original
# version. Uses the 'x' operator as a list constructor.
# In a list context it creates a list containing its
# left operand repeated the number of times given by
# the right operand (which is a scalar). @arr in a scalar
# context gives the number of elements in @arr. Hence
# we get a list containing scalar(@arr) 1s.
#
# We then assign this list to the list of lvalues created
# by @check{@arr}. This assigns a 1 to each value associated
# with a key found %check. The keys of %check are given by
# @arr, therefore we effectively create a key/value pair
# in %check for each element of @arr where the key is the
# element of @arr and the value is 1. If any element of
# @arr occurs multiple times we assign to the relevant
# value in %check multiple times.
# 
# We can then use 'keys' to extract this list of keys. If
# all the elements of @arr are the same the list of keys
# in %create only has one element.

@check{@arr} = (1) x @arr;

print "All the same" if keys %check == 1;
[download]

Does that help?</code> --
<http://www.dave.org.uk>

European Perl Conference - Sept 22/24 2000, ICA, London
<http://www.yapc.org/Europe/>

He's putting all the elements of the array into a hash, using a hash slice @check{@arr} = @arr x 1;

Then, if there is only one key, all the values must have been identical.

@check{@arr} is the "keys" part of the slice, and @arr x 1 just gives us the correct number of "values."

Voila! A list of the unique elements of @arr (in keys %check). If there is only one unique element, then they are all the same. Two problems solved for the price (two lines, in this case) of one. :-)

Russ
Brainbench 'Most Valuable Professional' for Perl

I see now. Apparently I don't have enough caffeine.

It was the @hash{@array} thing that threw me. Don't see that often and have never used it.

J. J. Horner
Linux, Perl, Apache, Stronghold, Unix
jhorner@knoxlug.org http://www.knoxlug.org/

@check{@array_to_test} = ();         # Sets them all to undef
$all_the_same = (keys %check <= 1);  # empty @ary = true too? heck, wh
+y not?
[download]

I don't think it does count as brute force. davorg may disagree, of course, but here are my two cents.

This is brute force:
(Note: this is deliberately not perl-idiom, just to be obtuse...)

my @Unique;
for (my $i = 0; $i != @Arr; $i++){
  my $Val = $Arr[$i];
  my $Found = 0;
  for (my $j = 0; $j != @Unique; $j++){
    if ($Val == $Unique[$j]){
      $Found = 1;
      last;
    }
  }
  if (not $Found){
    push @Unique, $Val;
  }
}
print 'Unique values are: ', join ', ', @Unique;
[download]

Now, in perl idiom, we do all that in one line using a hash. Of course, the specific problem we are solving here would be much simpler, even in 'C' mentality...

I guess my definition of brute-force is "the opposite of perl idiom."

Russ
Brainbench 'Most Valuable Professional' for Perl

I would argue that this is still brute-force. Since every array element (at least till a mismatch is found) must still be examined. In this case "brute-force" = O(n) (time is proportional to the size of the list). The technique presented above has the performance characteristic that its speed is directly proportional to the list size so IMHO it is still brute-force (or at least performance-equivalent to brute-force).

However, if you were to do something like populate your list elements into a hash as keys at the same time as you added them to a list then determining that they were all the same would be O(1), better than brute-force. However, this would slow-down your "add an element to the list" function.

...proving that brute force is not always a Bad Thing (tm), and that non-brute force methods can be a Bad Thing (tm), depending on your purpose and perspective.

IMHO: Given all the above descriptions, I would consider the hash method brute force and in this case, the more efficient method.

I suppose it depends what your definition of 'brute force' is. I'd say that a brute force solution would involve looping around the array checking each element and therefore this isn't brute force.

This certainly isn't a tied hash. A tied hash is some random object whcih you can access via a hash interface. This is a real hash which just happens to contain some interesting information about an array.

--
<http://www.dave.org.uk>

European Perl Conference - Sept 22/24 2000, ICA, London
<http://www.yapc.org/Europe/>

Why is recursion always considered the same as "brute force".

I'm pretty sure they aren't always the same.

I've seen some beautiful recursive techniques that were both elegant and efficient.

J. J. Horner
Linux, Perl, Apache, Stronghold, Unix
jhorner@knoxlug.org http://www.knoxlug.org/