Re: Re: Removing Duplicates from Array Passed by Reference

We can do much better by avoiding splice!

#! perl -slw
use strict;

sub dedup {
    my $ref = shift;
    my ($r, $l, %h);
    $r=$l=0;
    while( $r < @$ref ) {
        if ($h{$ref->[$r]}++) {
                # already seen
                ++$r;
        }
        else {
                # not yet seen. Copy!
                $ref->[$l++]= $ref->[$r++];
        }
    }
[download]

~~$#$ref= $l;~~

    $#$ref=$l-1
}
my @a = (7, 20..30, 1..1000, 200..300, 7);

print scalar @a;
dedup \@a;
print scalar @a;
#print "@a";
[download]

This works by moving with two indizes (r-ight and l-eft) over the array, copying the right to the left if it hasn't be seen yet. At the end the length of the array is adjusted.

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 19, 2003 at 10:06 UTC
Um:), by what criteria ... much* better? If you run the code from your post, but uncomment the last line, you'll see that your algorithm leaves a single duplicate at the end of the array. With the sample data in your post, this turns out to be the 989. Which is strange as this isn't a duplicate in the input array. That is probably easily fixed though. I had a similar problem with the first cut of my splice version. However, your algorithm is essentially the same as utils above at Re: Re: Removing Duplicates from Array Passed by Reference and as I showed in my reply at Re: Re: Re: Removing Duplicates from Array Passed by Reference, splice wins against the algorithm because splice doesn't have to copy* anything, as it simply unlinks the discarded elements from the linked list that implements perls arrays. I added your version to my benchmark and ignoring the error, splice beats it easily. Here are the results `Rate util___sml skeeve_sml splice_sml util___sml 1368/s -- -1% -11% skeeve_sml 1387/s 1% -- -10% splice_sml 1536/s 12% 11% -- Rate util___big skeeve_big splice_big util___big 17.1/s -- -12% -24% skeeve_big 19.4/s 13% -- -13% splice_big 22.4/s 31% 15% --` [download] As you can see, your implementation beat utils, but maybe once you've fixed the error that may no longer be true. Yell if you want the Benchmark code. 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]
Re: Re: Re: Re: Removing Duplicates from Array Passed by Reference by Skeeve (Parson) on May 19, 2003 at 11:40 UTC
:-) Much better in the sence of not using splice. IIRC I once read in the camel book that one should avoid it. Nevertheless You're right that mine is much like util's solution. Didn't notice that. And then I made the mistake of setting the array one element too big... Bear with me... At least it's Monday ;-)	[reply]