Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

All array elements the same?

by Grumpy (Initiate)
on Aug 01, 2000 at 20:05 UTC ( #25486=perlquestion: print w/replies, xml ) Need Help??

Grumpy has asked for the wisdom of the Perl Monks concerning the following question:

Is there an elegant way to determine whether all elements in an array are the same, aside from brute-force?

While I am here, I can't resist telling everyone what a fabulous resource this place is. Three times in a row I came here with a very complex query and with each one, by the time I had finished describing the problem in detail, I had figured out the answer.

Replies are listed 'Best First'.
Re: All array elements the same?
by davorg (Chancellor) on Aug 01, 2000 at 20:22 UTC

      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;

        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?
      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;
        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.

        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/
        

        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/>
      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
Re: All array elements the same?
by chip (Curate) on Aug 02, 2000 at 10:32 UTC
    Easiest, and cheaper than the hash solution:
    $same = not grep { $_ ne $array[0] } @array;
        -- Chip Salzenberg, Free-Floating Agent of Chaos
Array's structural limitations
by gryng (Hermit) on Aug 01, 2000 at 22:51 UTC
    Hi Grumpy!

    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

Re: All array elements the same?
by japhy (Canon) on Aug 01, 2000 at 23:43 UTC
    To be picky, you can simplify davorg's just a little:
    { my %hash; @hash{@array} = (); $same = (1 == keys %hash); }


    $_="goto+F.print+chop;\n=yhpaj";F1:eval
RE: All array elements the same?
by Nitsuj (Hermit) on Aug 01, 2000 at 21:12 UTC
    Yes there is!

    Make a scalar of size equal to the array, give it a value that is the same, do a comparison. If you take a look at the processes, this is actually a pretty quick way for many numbers :-)

    This is ESPECIALLY true for numbers such as 0.

    This is also true for certain types of numbers.

    Think like this.


    Unsinged Integer Decimal ValueBinary ValueArray of Unsigned Integers Value
    1000000011
    257000000010000000111
    65793000000010000000100000001111
    .........

    Now all you have to do is a comparative operation. Much more can be extracted. By telling a range of difference, you can figure out which characters are different, like say that it is less than 256 off, you know that the first byte is different!

    COOL, HUH?

    "We're all different!"
    "I'm not"
    -The Life of Brian
Re: All array elements the same?
by ray (Initiate) on Aug 01, 2000 at 21:16 UTC
    How about the following?
    @a = qw(one one 1 one); print "not the same\n" unless @a == grep m/$a[0]/o, @a;
    Later,
    Ray.
Re: All array elements the same?
by young perlhopper (Scribe) on Aug 01, 2000 at 20:28 UTC
    if (join '', @array1) eq (join '', @array2) { do_stuff; }

    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"
      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.
(jeffa) Re: All array elements the same?
by jeffa (Bishop) on Aug 01, 2000 at 20:32 UTC
    Here's my 2 cents worth:
    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"; }
    Wow, looks like davorg has got one heck of an elegant solution.
RE: All array elements the same?
by larsen (Parson) on Aug 01, 2000 at 20:39 UTC
    This is the first thing I thought, and perhaps the code I'd write...
    # 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;
    Or, using hashes... (Smaller version, but it seems to me THIS is brute force)
    @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;
    See you
    Larsen
Re: All array elements the same?
by ray (Initiate) on Aug 01, 2000 at 21:13 UTC
    How about the following? @a = qw(one one 1 one); print "not the same\n" unless @a == grep m/$a[0]/o, @a; Later, Ray.
Re: All array elements the same?
by princepawn (Parson) on Aug 02, 2000 at 12:35 UTC
    The example of davorg took my breath away for its elegance, but as I read further I realized something. It wont work on nested structures correctly.

    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/>

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://25486]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (6)
As of 2022-10-04 11:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My preferred way to holiday/vacation is:











    Results (16 votes). Check out past polls.

    Notices?