in reply to Re: Testing if an array contains a value and then deleting it in most efficient way
in thread Testing if an array contains a value and then deleting it in most efficient way

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;

[download]
  • Comment on Re^2: Testing if an array contains a value and then deleting it in most efficient way
  • Download Code

Replies are listed 'Best First'.
Re^3: Testing if an array contains a value and then deleting it in most efficient way
by ikegami (Patriarch) on Feb 18, 2008 at 16:30 UTC

    ow! You transformed a O(N) problem into an O(N2) 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.

[reply]
[d/l]
[select]

      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).

[reply]

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

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

        [download]

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

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

        [download]

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

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom