Just another Perl shrine PerlMonks

### Re: Common Perl Pitfalls

by JavaFan (Canon)
 on Apr 09, 2012 at 23:16 UTC ( #964224=note: print w/replies, xml ) Need Help??

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

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

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

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 + 1st iteration, the splicing takes at least N/2 - 1 steps, as that many array elements need to be moved. On the N/2 + 2nd iteration, the splicing takes at least N/2 - 2 steps. In total, you will be moving

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

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

Wonderful. Thanks for enlightening me...

Create A New User
Node Status?
node history
Node Type: note [id://964224]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (8)
As of 2018-06-18 18:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (110 votes). Check out past polls.

Notices?