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

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

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

Replies are listed 'Best First'.
Re^5: Testing if an array contains a value and then deleting it in most efficient way by ikegami (Patriarch) on Feb 18, 2008 at 16:50 UTC
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).	[reply] [d/l] [select]
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]


Your skill will accomplish what the force of many cannot
	PerlMonks