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

Adding Unique Elements to Array

by thekestrel (Friar)
on Feb 28, 2005 at 18:35 UTC ( [id://435137]=perlquestion: print w/replies, xml ) Need Help??

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

Hi Monks,
I'm wanting have something that adds only unique elements to an array, i.e. only allow the value onto the array if it is not already included.
I'm pretty sure I recall reading a way that does with without recursively checking the elements already in the array, but for the life of me I can't recall it. I have it working recursively, but there possibly being a better bugs me (theres always another way =P). I know this is probably quite trivial, but thanks for any input.
Regards Paul.

Replies are listed 'Best First'.
Re: Adding Unique Elements to Array
by friedo (Prior) on Feb 28, 2005 at 18:39 UTC
    Does the order of the elements matter? If not, you could use hash keys instead.

    my %h; for(qw/foo bar baz quux foo narf bar poit/) { $h{$_} = 1; }

    If the order matters, you could keep a separate hash that has all of the items in it as keys.

    my (%h, @a); for(qw/foo bar baz quux foo narf bar poit/) { push @a, $_ unless exists $h{$_}; $h{$_} = 1; }
      Recall, however, that "last in wins" when populating a hash.

      OP appears to want not only to assure uniqueness (without testing) but also "only allow the value onto the array if it is not already included." (emphasis mine)

        But neither of the above solutions puts the elements in hash values. Either we're using the keys as an unsorted array directly, or using the keys as a separate boolean record of what's already in there.
      Thanks Friedo,
      The order does not matter actually, and as I was posting I was thinking about the use of a hash, just populating it with dummy data for key manipulation bothered me for some reason. Now that I think about it though that might be the best way to do it. Thanks =)
      Regards Paul
        That's the way I do it. It avoids having to test for duplicates (in my code, anyway). Also, if I need 'em in order I can use sort keys.. I'm relieved to see that mentioned here. I was afraid I was the only one doing it, and that there was a far better way.
Re: Adding Unique Elements to Array
by Roy Johnson (Monsignor) on Feb 28, 2005 at 18:46 UTC
    You mean like Array::Unique?

    Caution: Contents may have been coded under pressure.
Re: Adding Unique Elements to Array
by data64 (Chaplain) on Mar 01, 2005 at 04:23 UTC
Re: Adding Unique Elements to Array
by Limbic~Region (Chancellor) on Feb 28, 2005 at 22:17 UTC
    thekestrel,
    Here is how I would do it:
    #!/usr/bin/perl use strict; use warnings; my @uniq; my $add = uniq_array( \@uniq ); $add->(3,1,4,1,5,9); $add->(2,7,2,7,2,7); print "$_\n" for @uniq; sub uniq_array { my ($aref, %uniq) = shift(); return sub { push @$aref, grep { ! $uniq{$_}++ } @_ }; }
    Let me know if you have any questions.

    Cheers - L~R

    Update: Over 2 months after posting this, Roy Johnson asked why I used map instead of grep inside the return sub. The answer is that I was modifying a piece of existing code that does much more. For the sake of clarity, I have replaced the funny looking map.

Re: Adding Unique Elements to Array
by Not_a_Number (Prior) on Feb 28, 2005 at 21:50 UTC

    Expanding on RazorbladeBidet's remark:

    my @ary = qw ( 0 0 1 1 1 ); my $val = 0; # or whatever push @ary, $val unless exists ${{ map { $_ => undef } @ary }}{$val};

    Advantages:

    1. Preserves original array order.

    2. If duplicate elements already exist in the array, leaves them alone (note that the OP said 'only allow the value onto the array if it is not already included', with no reference to any possible pre-existing duplicates in the array).

    Disadvantages:

    1. See (2) above.

    2. Not, er, readily comprehensible.

    dave

Re: Adding Unique Elements to Array
by dmorelli (Scribe) on Feb 28, 2005 at 19:13 UTC
    If your existing array is potentially huge, maybe a binary search would be helpful. I implemented (a lame) one lately. I say lame because it does only eq and lt comparisons.

    I keep meaning to rewrite this more like sort to take a comparison coderef.

    But anyway, the code:

    #! /usr/bin/perl -w use strict; { # Need integer division here. use integer; # Determine if a string exists in a sorted list of strings # using a binary search # Fail to send a sorted list to this sub at your own peril sub listContains($$) { my ($list, $word) = @_; my $min = 0; my $max = $#$list; my $i = ($max - $min) / 2; my $done = 0; while (!$done) { my $current = $list->[$i]; # Found it, return true return 1 if ($word eq $current); # Cut off half of the remaining list ($word lt $current) ? $max = $i : $min = $i; my $newi = $min + (($max - $min) / 2); # Out of list words to try $done = 1 if($newi == $i); $i = $newi; } # If we got here, the word was not found, return false return 0; } } # unsorted list my @words = qw{ icebox jakfruit kelvin liquid effluvia fenestrate ghoul hufflepuff yurt zoroastrian magnanamous necrosis ocular porridge albatross bolognese catharsis denigrate unresponsive versimilitude wrangler xenophobic quayside runcible seriatim tangential }; @words = sort @words; my $word = shift; print "$word: " . listContains(\@words, $word) . "$/";
Re: Adding Unique Elements to Array
by RazorbladeBidet (Friar) on Feb 28, 2005 at 19:10 UTC
    There are several ways to do this and quite a few nodes out there that point to answers.

    my @list = qw( ... ); my %hash; undef @hash{@list}; print $_, "\n" for keys %hash;


    or

    my @list = qw( ... ); my %hash; grep { $hash{$_}++ } @list; print $_, "\n" foreach keys %hash;
    --------------
    It's sad that a family can be torn apart by such a such a simple thing as a pack of wild dogs
      While both of these work, neither is very good code. In the first example, you pass undef an array slice, but undef doesn't work on array slices (you're just not using undef for its designed purpose, so you don't care). It would be better to say
      @hash{@list} = ();
      In the second, you use grep where a foreach is more sensible. In fact,
      1 for @hash{@list};
      works just as well (you don't even have to assign anything).

      Caution: Contents may have been coded under pressure.
Re: Adding Unique Elements to Array
by osunderdog (Deacon) on Feb 28, 2005 at 19:35 UTC

    I would recommend Set::Scalar.


    "Look, Shiny Things!" is not a better business strategy than compatibility and reuse.

Re: Adding Unique Elements to Array
by Pilbox (Initiate) on Mar 01, 2005 at 01:02 UTC
    If i'm reading his request right, here is a way to do that without hashes. I wouldn't recommend this on a large array tho.
    push(@array,$foo) unless (grep /$foo/,@array);

      /$foo/ isn't equivalent to $_ eq $foo. Personally I use $_ eq $foo quite often, as I see no benefit in using /^\Q$foo\E\z/.

      You might want to look at first from List::Util.

      ihb

      See perltoc if you don't know which perldoc to read!

Re: Adding Unique Elements to Array
by Steve_p (Priest) on Feb 28, 2005 at 23:14 UTC

    Have you tried tieing a hash to Tie::InsertOrderHash? Add your values as the key of the hash and it will prevent duplicates. Pull back the keys with keys(), and it will return them in the order they were inserted.

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others chanting in the Monastery: (3)
As of 2024-03-29 02:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found