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

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(N²).~~

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

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

Comment on Re^5: Testing if an array contains a value and then deleting it in most efficient way Select or Download Code

Replies are listed 'Best First'.
Re^6: Testing if an array contains a value and then deleting it in most efficient way by ikegami (Patriarch) on Feb 19, 2008 at 03:59 UTC
No, I was right. `while ( -1 < ( $i = firstidx { $_ == $val } @array ) ) { ... }` [download] is worse case O(N²). Take the case where the condition is true for all items. For the first loop pass, all elements of @array are put on the stack ( time = k * N ) For the second loop pass, all remaining elements of @array are put on the stack ( time = k * (N-1) ) For the third loop pass, all remaining elements of @array are put on the stack ( time = k * (N-2) ) ... For the last loop pass, all remaining element of @array is put on the stack ( time = k * 0 ) The total time = k * ( N * (N+1) / 2 ) = O(N²) If the language evaluated @array lazily, it would be O(N).	[reply] [d/l]
Re^7: Testing if an array contains a value and then deleting it in most efficient way by parv (Parson) on Feb 19, 2008 at 08:49 UTC
Note that OP did not say anything about handling of multiplicates. The inner loop is to delete all the matching values not just the first one, to be a similar solution to a hash solution (since the same key cannot occur multiple times).	[reply]