Re^2: Howto Avoid Memory Problem in List::MoreUtils

well, the algorithm on my previous post is actually O(N^2) on the worst case because of the splice.

A better version is:

@array = sort @array;
my $j = 0;
my $last;
for my $e (@array) {
  if (!$j or $last ne $e) {
    $array[$j] = $last = $e;
    $j++;
  }
}
$#array = $j-1;
[download]

Comment on Re^2: Howto Avoid Memory Problem in List::MoreUtils Download Code

Replies are listed 'Best First'.
Re^3: Howto Avoid Memory Problem in List::MoreUtils by Anonymous Monk on May 09, 2006 at 05:59 UTC
Hi salva, Thanks so much for your reply. Just a minor question. What's the meaning of this line: `$array[$j] = $last = $e;` [download] Why not simply: `$array[$j] = $e;` [download]	[reply] [d/l] [select]
Re^4: Howto Avoid Memory Problem in List::MoreUtils by ikegami (Patriarch) on May 09, 2006 at 06:03 UTC
`$last` is used to remove dups. `$last` needs to be set to the `$e` of this pass to compare it to the `$e` of the next pass. I suppose you could get rid of `$last` and do `@array = sort @array; my $j = -1; for my $e (@array) { if ($j < 0 \|\| $array[$j] ne $e) { $array[++$j] = $e; } } $#array = $j;` [download]	[reply] [d/l] [select]