Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re^4: Create unique array --the hard way!

by kcott (Archbishop)
on Mar 08, 2014 at 09:32 UTC ( [id://1077503]=note: print w/replies, xml ) Need Help??


in reply to Re^3: Create unique array --the hard way!
in thread Create unique array --the hard way!

Well, you could but I don't know why you'd want to.

In the following script (using Benchmark) you'll see:

  • splice is relatively less efficient. I also suspect it might have future maintainers scratching their heads wondering why it was used ("splice @array, 0, 1" has identical functionality to "shift @array" — it's just slower and requires more keystrokes to code).
  • shift is more efficient than splice.
  • My original map is faster than both of those; it doesn't destroy the original array; and it's a lot less coding.
#!/usr/bin/env perl use strict; use warnings; use Benchmark qw{cmpthese}; cmpthese -1 => { splice_unique => \&splice_unique, shift_unique => \&shift_unique, map_unique => \&map_unique, }; sub splice_unique { my @sorted = sort qw{q w e r t y q w e r t y}; my $last = ''; my @unique; while (@sorted) { my $element = splice @sorted, 0, 1; if ($last ne $element) { $last = $element; push @unique, $element } } } sub shift_unique { my @sorted = sort qw{q w e r t y q w e r t y}; my $last = ''; my @unique; while (@sorted) { my $element = shift @sorted; if ($last ne $element) { $last = $element; push @unique, $element } } } sub map_unique { my @sorted = sort qw{q w e r t y q w e r t y}; my $last = ''; my @unique = map { $last eq $_ ? () : ($last = $_) } @sorted; }

Representative result:

Rate splice_unique shift_unique map_unique splice_unique 93699/s -- -5% -20% shift_unique 98642/s 5% -- -16% map_unique 117028/s 25% 19% --

-- Ken

Replies are listed 'Best First'.
Re^5: Create unique array --the hard way!
by Anonymous Monk on Mar 08, 2014 at 10:19 UTC
    Ah ok, I thought slice would not involve pushing the unique elements into a new array, rather remove them "as-you-go" if the array is sorted, since they would be next to each other...

      Stepping through an array and making changes "as-you-go" has unforeseen problems. We get quite a few "Why didn't this work?" questions related directly to attempting to do this type of thing.

      The issue is actually documented in "perlsyn: Foreach Loops" and specifically mentions splice:

      "If any part of LIST is an array, foreach will get very confused if you add or remove elements within the loop body, for example with splice. So don't do that."

      [In case you didn't know, for and foreach are synonymous.]

      So, you'd need to do something like the following.

      sub splice_unique2 { my @sorted = sort qw{q w e r t y q w e r t y}; my $last = ''; my @unique = @sorted; my $removed = 0; for (0 .. $#sorted) { if ($sorted[$_] eq $last) { splice @unique, $_ - $removed++, 1; } else { $last = $sorted[$_]; } } }

      I plugged that in to my earlier benchmarking script. Here's a representative result:

      Rate splice_unique2 splice_unique shift_unique +map_unique splice_unique2 83836/s -- -10% -15% + -28% splice_unique 92839/s 11% -- -6% + -20% shift_unique 99211/s 18% 7% -- + -14% map_unique 115924/s 38% 25% 17% + --

      My coding of splice_unique2() was really just intended to show a way to get around the documented issue. If you think the task has any merit, feel free to try to rewrite it to run faster.

      -- Ken

        Thank you Ken, will read up on it :)

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (5)
As of 2024-03-28 21:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found