Does this count as brute force?

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

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

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

Thanks, that solved a different problem that I had... Given formal parameter list @params, and argument list @args, how do you get %table such that $table{$param[i]} eq $args[i]. Solution: @table{@params} = @args; That'll eliminate a subroutine or two in my current project...

You don't usually need the (1) x @arr when doing stuff like this. This would suffice perfectly:

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

If you were checking a true/false condition based on the presence of any of the keys, the 1 would be needed, but all we're interested in here is the keys.

Davorg: Out of curiosity, that *would* count as brute force, wouldn't it? Please explain why, or why not, if you have time. update: Would this be considered a tied hash? According to camel pg 182, perl does walk entire tied hash. (brute force)

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.

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/

Reverse brute force.
It is sort of brute force in the reverse, rather than checking each element as it comes, you are making an equivalent object and checking it. The means that you are generating it by are not brute force by abstraction, but in actual implementation they might be, which really depends on the algorithm employeed in the operators which you used (I've never read the PERL souce to those operators, so I don't know). Still, it is a very elegant piece of code, and I know that I enjoyed it :-)

"We're all different!"
"I'm not"
-The Life of Brian

    $same = not grep { $_ ne $array[0] } @array;
[download]

I think we need to back up for a second. You're asking if using an array (which is a particular sort of data structure), there is a way to check if all elements are the same, without using brute force. The answer would basically be no, as you are using an array. The best you can do is O(N) time (that is the check time is proportional to the list's size), because of the data structure you are using.

For example, davorg's hash example and also a simple loop would exhibit this O(N) time (well actually davorg's is techinically slower, even in big O notation.. but not by much :) ).

Now, if you would like to make this check something you can do in less than O(N) time you will need to use a different data structure, and probably have to pay some cost for that choice.

The first thing that springs to my mind is to use both an array, and a hash. Use the array, but whenever you insert an item also do a: $hash{$item} = 1 . Then you can see how many different items are in the array by: keys %hash.

Unfortunately this particular arrangement pays a large cost to delete items from the array. It also pays a small cost for insertion. However, if you are not deleting items from this array, then this is not a problem! :) (if you are you will pay a O(N) cost per deletion).

There are other arrangements that would not have the cost for deletion, however you will pay the price someplace else. For instance, as was mentioned higher up (lhoward), you could just use a hash. Then you add an item to your array using: $hash{$item}++ . To remove you need slightly longer code, something like: delete $hash{$item} if not --$hash{item};

This scheme pays a slight cost for deletions and inserts, but you get the same  keys %hash function to see how many different items are present.

There are other data structures you could use, such as binary trees, but they each have their own unique features. So I as said in the beginning, it all depends on the data structure you use.

Cheers,
Gryn

{
  my %hash;
  @hash{@array} = ();
  $same = (1 == keys %hash);
}
[download]

@a = qw(one one 1 one);
print "not the same\n" unless @a == grep m/$a[0]/o, @a;
[download]

if (join '', @array1) eq (join '', @array2) {
    do_stuff;
}
[download]

Not sure if this will work properly in all cases, but it should work for arrays containing strings. Really though, I can't think of any reason why it would work for numbers and such...

waiting to be proven wrong,
Mark

If you wanted to compare two arrays (and I don't think that's what the original poster wanted) then you could use the Array::Compare module from CPAN which works in a similar manner to your code.

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

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

This wouldn't work very well for arrays that concatenate the same but have different values. Consider:

@one = (undef, 1, 2);   # "12"
@two = (1, undef, 2);   # "12"

@one = (12, 3, 4);      # "1234"
@two = (1, 2, 34);      # "1234"
[download]

The Array::Compare module basically does a join() using an unlikely delimiter (like a pipe character or \0 or \255). Unfortunately, my own benchmarks typically put a "brute force" comparison faster than Array::Compare (sometimes significantly, depending on the amount and type of data in the two arrays), especially when dealing with numeric items in the array. Conversions of data types to strings plus string comparisons tend to be expensive in bulk. If you're working with string data, it might not be so bad.

use strict;

my @foo1 = qw(1 1 1 1 1 1 1 1 1 1);
my @foo2 = qw(1 1 1 1 1 1 3 1 1 1);

print "Checking  \@foo1: ";
&ident_array(\@foo1);
print "Checking  \@foo2: ";
&ident_array(\@foo2);


sub ident_array($) {

    my $array_ref = shift;
    my $flag = 1;

    for(my $i=1; $i < $#{$array_ref}; $i++) {
        $flag = 0, last if $array_ref->[0] ne $array_ref->[$i];
    }

    print "array elements are ";
    print "not " unless $flag;
    print "identicle\n";
}
[download]

# ASSERTION: array contains at least 2 elements
@v = (1,2,3,4,5);

$flag = 0;
$first = $v[0];
foreach ( @v[1,] ) { # Starts from second element
    print "Examining $_...\n";
    if ($_ != $first) {
        $flag = 1;
        last;
    }
}
print "All elements are equal" unless $flag;
[download]

@v = (1,2,3,4,5);

map { $set{$_} = 1 } @v;

# Elements are equal, unless set contains more than one element
@k = keys %set;
print "All elements are equal" unless $#k != 1;
[download]

If the values in a nested structure are equal in value but not in reference, then his method will return false because the number of keys if greater than 1.

You're absolutely right of course, but I think that all the proposed solutions will fail for the same reason. If you have an arrary containing data structures then you'd need to serialise it first using something like Data::Dumper or FreezeThaw.

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

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