Re^2: Testing if an array contains a value and then deleting it in most efficient way

[parv]

In code (while using array) ...

use List::MoreUtils qw/ firstidx /;

for my $val ( generate() )
{
  my $i;
  #  Deal w/ "uninitialized variable" warning as appropriate.
  while ( -1 < ( $i = firstidx { $_ == $val } @array ) )
  {
    delete $array[ $i ];
  }
}

#  Later...

#  exists() here would go better with earlier delete(), but
#  then would need to generate list of indices.
my @save = grep { defined $_ } @array;

[ikegami]

ow! You transformed a O(N) problem into an O(N²) solution.
firstidx starts at the start of the array every loop pass.

Not only did you half the speed, you doubled the memory requirements.
"firstidx" copies the entire array before processing it.

[parv]

How can you avoid O(N^2) cost if using unsorted array? So far there is no indication whether it would be sorted. (Addendum: I wasn't thinking so just quoted the O(N^2) cost, which really should have been O(N). Time to sleep belatedly, I suppose.)

I thought that List::MoreUtils::firstidx would use XS magic (to avoid copying). No? (I would have looked inside the C code myself but am not familiar with XS yet.)

Later ... I see now that array might be already sorted (and first element would be the interesting one).

[ikegami]

Update: No, I guess I'm wrong. The nested loops (while and firstidx confused me).

---

  while ( -1 < ( $i = firstidx { $_ == $val } @array ) )
  {
    ...
  }

is best case O(N).
is worse case O(N²).

  for (0 .. $#array)
  {
    next if $_ != $var;
    ...
  }

is best, real & worse case O(N).