Re: Common Perl Pitfalls

[JavaFan]

in reply to Common Perl Pitfalls

Deleting some array elements

I'd write that as:

@array = @array[grep {!should_delete($_)} 0..$#array];

If only because your splice solution can be quadratic worst case, while the above is linear (assuming should_delete has a running time bounded by a constant).

[Joe_]

That's a really great one, too.
I've only recently started coming to grips with grep and map. I've always felt that this problem can be tackled by a one-liner but I just couldn't put my hands on it. Thanks for finally providing it :)

[Joe_]

Care to elaborate on that "quadratic" comment? How do you figure? I'm not that good with complexity theory, I'm afraid...

[JavaFan]

Care to elaborate on that "quadratic" comment?

Say you want to delete all elements in the second half of the array. The first N/2 iterations of your loop, no splicing happens. But on the N/2 + 1^st iteration, the splicing takes at least N/2 - 1 steps, as that many array elements need to be moved. On the N/2 + 2^nd iteration, the splicing takes at least N/2 - 2 steps. In total, you will be moving

Σ^N/2-1_i=1(i)

array elements. If I've done my math correctly, the above sum equals (N² - 2N + 4)/8. Which means your algorithm runs in Ω(N²) time.

[Joe_]

Wonderful. Thanks for enlightening me...