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

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

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

Replies are listed 'Best First'.
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]