Re: Re: Removing Duplicates from Array Passed by Reference

For this particular problem, I believe that we can manually do the work of splice more efficiently than splice could itself.

# Untested :(
sub dedup {
  my $ref = shift;
  my %seen;
  my $c = 0; # current
  my $n = 0; # next available slot
  foreach (@$ref) {
    if (not $seen{$_}++) {
      $ref->[$n] = $_ unless $n == $c;
      $n++;
    }
    $c++;
  }
  $#{$ref} = $n-1;
}
[download]

Every element gets moved once, at most. Elements before the first duplicate don't get moved at all.

Comment on Re: Re: Removing Duplicates from Array Passed by Reference Select or Download Code

Replies are listed 'Best First'.
Re: Re: Re: Removing Duplicates from Array Passed by Reference by BrowserUk (Patriarch) on May 17, 2003 at 04:48 UTC
That's cool. From what I understand, which may well be wrong, splice doesn't actually move anything. It just unlink the deleted item or range from the chain and frees off the unlinked space? (Must re-read Perlguts Illustrated again sometime:). I'm wary of using `foreach (@$_)...` as I thought that it would expand the array to a list of aliases? I know that `for( 0..n) {...}` uses an iterator rather than a list, but I'm not sure about with an array. If that isn't the case, it would be good to know. It would be interesting to compare the performance (memory and speed). Maybe I'll have a go at it later. Update Perl wins again:) `D:\Perl\test>258641 Rate util___big splice_big util___sml splice_sml util___big 14.0/s -- -45% -98% -99% splice_big 25.4/s 81% -- -97% -98% util___sml 876/s 6151% 3348% -- -41% splice_sml 1490/s 10529% 5764% 70% --` [download] I'll post the benchmark if anyone is interested. Examine what is said, not who speaks. "Efficiency is intelligent laziness." -David Dunham "When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller	[reply] [d/l] [select]

Replies are listed 'Best First'.

Re: Re: Re: Removing Duplicates from Array Passed by Reference
by BrowserUk (Patriarch) on May 17, 2003 at 04:48 UTC

That's cool.

From what I understand, which may well be wrong, splice doesn't actually move anything. It just unlink the deleted item or range from the chain and frees off the unlinked space? (Must re-read Perlguts Illustrated again sometime:).

I'm wary of using foreach (@$_)... as I thought that it would expand the array to a list of aliases? I know that for( 0..n) {...} uses an iterator rather than a list, but I'm not sure about with an array. If that isn't the case, it would be good to know.

It would be interesting to compare the performance (memory and speed). Maybe I'll have a go at it later.

Update Perl wins again:)

D:\Perl\test>258641
             Rate util___big splice_big util___sml splice_sml
util___big 14.0/s         --       -45%       -98%       -99%
splice_big 25.4/s        81%         --       -97%       -98%
util___sml  876/s      6151%      3348%         --       -41%
splice_sml 1490/s     10529%      5764%        70%         --
[download]

I'll post the benchmark if anyone is interested.

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller

[reply]
[d/l]
[select]