Re: Common Perl Pitfalls

Deleting some array elements

I'd write that as:

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

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

Comment on Re: Common Perl Pitfalls Select or Download Code

Replies are listed 'Best First'.
Re^2: Common Perl Pitfalls by Joe_ (Beadle) on Apr 09, 2012 at 23:24 UTC
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 :)	[reply]
Re^2: Common Perl Pitfalls by Joe_ (Beadle) on Apr 09, 2012 at 23:50 UTC
Care to elaborate on that "quadratic" comment? How do you figure? I'm not that good with complexity theory, I'm afraid...	[reply]
Re^3: Common Perl Pitfalls by JavaFan (Canon) on Apr 10, 2012 at 13:22 UTC
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.	[reply]
Re^4: Common Perl Pitfalls by Joe_ (Beadle) on Apr 10, 2012 at 18:10 UTC
Wonderful. Thanks for enlightening me...	[reply]


laziness, impatience, and hubris
	PerlMonks